Please use this identifier to cite or link to this item:
Title: Learning feature embedding refiner for solving vehicle routing problems
Authors: Li, Jingwen
Ma, Yining
Cao, Zhiguang
Wu, Yaoxin
Song, Wen
Zhang, Jie
Chee, Yeow Meng
Keywords: Engineering::Computer science and engineering
Issue Date: 2023
Source: Li, J., Ma, Y., Cao, Z., Wu, Y., Song, W., Zhang, J. & Chee, Y. M. (2023). Learning feature embedding refiner for solving vehicle routing problems. IEEE Transactions On Neural Networks and Learning Systems.
Project: C222812027
Journal: IEEE Transactions on Neural Networks and Learning Systems
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.
ISSN: 2162-237X
DOI: 10.1109/TNNLS.2023.3285077
Schools: School of Computer Science and Engineering 
Rights: © 2023 IEEE. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Jun 13, 2024

Page view(s)

Updated on Jun 19, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.