Publication Type
Journal Article
Version
acceptedVersion
Publication Date
1-2023
Abstract
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.
Keywords
Vehicle routing problems, neural combinatorial optimization, encoder-decoder structure, reinforcement learning
Discipline
OS and Networks
Research Areas
Information Systems and Management
Publication
IEEE Transactions on Neural Networks and Learning Systems
First Page
1
Last Page
13
ISSN
2162-237X
Identifier
10.1109/TNNLS.2023.3285077
Publisher
Institute of Electrical and Electronics Engineers
Citation
LI, Jingwen; MA, Yining; CAO, Zhiguang; WU, Yaoxin; SONG, Wen; ZHANG, Jie; and CHEE, Yeow Meng.
Learning feature embedding refiner for solving vehicle routing problems. (2023). IEEE Transactions on Neural Networks and Learning Systems. 1-13.
Available at: https://ink.library.smu.edu.sg/sis_research/8087
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/TNNLS.2023.3285077