Learning Feature Embedding Refiner for Solving Vehicle Routing Problems

doi:10.1109/TNNLS.2023.3285077

Learning Feature Embedding Refiner for Solving Vehicle Routing Problems

2024-11-01

5

OA

AI

DOI：10.1109/TNNLS.2023.3285077

Original

Original request for help

Save

Abstract

En 中文

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:

Probability distribution

Decoding

Search problems

Vehicle routing

Routing

Logic gates

Costs

Encoder-decoder structure

neural combinatorial optimization

reinforcement learning

vehicle routing problems (VRPs)

Learning Feature Embedding Refiner for Solving Vehicle Routing Problems

Abstract

Journal

Organization