Automated Algorithm Design with Partial Reconstruction Heuristics for Solving Vehicle Routing Problems

Automatic algorithm design has gained extensive research interest in addressing combinatorial optimization problems (COPs). Neural Combinatorial Optimization (NCO) is a novel application of automated algorithm design, which can be divided into two categories, i.e., the Constructive Neural Combinatorial Optimization (CNCO) that constructs solutions from scratch and Perturbative Neural Combinatorial Optimization (PNCO) that improves existing solutions via perturbing them. However, the proper integration of CNCO methods and PNCO methods into an automated algorithm design framework appears to be a research gap in the field of COPs. In this study, we propose an automatic algorithm design framework called Automatic Search Algorithm Framework (AutoSAF) that integrates CNCO into PNCO methods. AutoSAF can intelligently select the appropriate heuristics from the reconstruction pool, improvement pool, and perturbation pool, to improve the current solutions. The reconstruction pool consists of neural network heuristics. i.e., the CNCO methods, aiming at optimizing the solutions by reconstructing fragments of them. The heuristics in the improvement pool are to fine tune the solutions through minor perturbation. The heuristics in the perturbation pool are to modify the solutions significantly, preventing them from getting stuck in local optima. Additionally, we design an Adversarial Transformer Model (ATM) to provide rich learning-based meta-heuristics for the reconstruction pool. Specifically, employing a divide-and-conquer strategy, ATM iteratively reconstructs partial solutions to facilitate the optimization of the entire solution. The effectiveness of AutoSAF is validated on the Vehicle Routing Problems (VRPs).