Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt

• Main Authors: MA, Yining, CAO, Zhiguang, CHEE, Yew Meng
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/8399; https://ink.library.smu.edu.sg/context/sis_research/article/9402/viewcontent/2310.18264.pdf
• Institution: Singapore Management University

In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As a pioneering work to circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which supplements the NeuOpt policy network with feasibility-related features and leverages reward shaping to steer reinforcement learning more effectively. Besides, we further equip NeuOpt with dynamic data augmentations during inference for more diverse searches. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing (masking-based) L2S solvers, but also showcases superiority over the learning-to-construct (L2C) and learning-to-predict (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers could efficiently handle VRP constraints, against masking-based feasibility representation.