Learning feature embedding refiner for solving vehicle routing problems

• Main Authors: LI, Jingwen, MA, Yining, CAO, Zhiguang, WU, Yaoxin, SONG, Wen, ZHANG, Jie, CHEE, Yeow Meng
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Vehicle routing problems; neural combinatorial optimization; encoder-decoder structure; reinforcement learning; OS and Networks
• Online Access: https://ink.library.smu.edu.sg/sis_research/8087; https://ink.library.smu.edu.sg/context/sis_research/article/9090/viewcontent/LearningFeatureEmbeddingRefinerforSolvingVehicleRoutingProblems.pdf
• Institution: Singapore Management University

While the encoder–decoder structure is widely used in the recent neural construction methods for learning to solve vehicle routing problems (VRPs), they are less effective in searching solutions due to deterministic feature embeddings and deterministic probability distributions. In this article, we propose the feature embedding refiner (FER) with a novel and generic encoder–refiner–decoder structure to boost the existing encoder–decoder structured deep models. It is model-agnostic that the encoder and the decoder can be from any pretrained neural construction method. Regarding the introduced refiner network, we design its architecture by combining the standard gated recurrent units (GRU) cell with two new layers, i.e., an accumulated graph attention (AGA) layer and a gated nonlinear (GNL) layer. The former extracts dynamic graph topological information of historical solutions stored in a diversified solution pool to generate aggregated pool embeddings that are further improved by the GRU, and the latter adaptively refines the feature embeddings from the encoder with the guidance of the improved pool embeddings. To this end, our FER allows current neural construction methods to not only iteratively refine the feature embeddings for boarder search range but also dynamically update the probability distributions for more diverse search. We apply FER to two prevailing neural construction methods including attention model (AM) and policy optimization with multiple optima (POMO) to solve the traveling salesman problem (TSP) and the capacitated VRP (CVRP). Experimental results show that our method achieves lower gaps and better generalization than the original ones and also exhibits competitive performance to the state-of-the-art neural improvement methods.