Learning (Re-)Starting Solutions for Vehicle Routing Problems

Xingwen Zhang, Shuang YangarXiv 2020 · arXiv

Abstract

Searching for the optimal route for a fleet of delivery trucks is notoriously difficult because the number of possible paths is astronomical. This paper introduces Learn to Restart (L2R), a method that uses a neural network to "peek" at potential starting solutions and predict which ones will lead to the best results before a heavy-duty solver even begins its work. By filtering out bad starts, L2R significantly speeds up the search for high-quality solutions in Capacitated Vehicle Routing Problems (CVRP).

Introduction

Combinatorial optimization problems, like the Vehicle Routing Problem (VRP), are NP-hard. Imagine a fleet of trucks that must deliver goods to various customers while staying under a weight limit and minimizing total distance. Because the search space is so vast, traditional solvers often get stuck in "local optima"—solutions that look good locally but are far from the best possible outcome.

To escape these traps, researchers use "restarts": they pick a new starting point and try again. However, picking these starting points at random is inefficient. You might waste hours of compute time optimizing a starting point that was doomed from the beginning. The authors tackle this "blind exploration" problem by building an "oracle" that can distinguish a good starting point from a bad one with minimal computational overhead.

The L2R Framework and Architecture

The core of the paper is the Learn to Restart (L2R) framework. It consists of three integrated parts:

  1. The Black-box Optimization Agent (BOA): Any existing iterative solver (like a local search algorithm) that takes a starting solution and improves it.
  2. The Value Network: A neural network trained to evaluate a starting solution ($X_0$) and predict the quality of the final solution ($X^*$) the BOA would produce.
  3. The Exploration Strategy: A set of rules for how the BOA and the Value Network interact, such as picking the best of $K$ random starts.
The L2R system diagram and the internal architecture of the Value Network.

The authors utilize a Siamese Network architecture. Instead of predicting the exact mileage of a route, the network is trained to compare two different starting solutions and identify the superior one. Each truck route is processed by a bi-directional LSTM to capture customer sequences, followed by an attention mechanism that analyzes inter-route relationships. Finally, a Multi-Layer Perceptron (MLP) generates a score for the entire solution.

Experimental Setup and Datasets

The researchers evaluated their method on standard benchmarks for the Capacitated Vehicle Routing Problem (CVRP), specifically CVRP-20, CVRP-50, and CVRP-100 (representing 20, 50, and 100 customers). For training, they generated massive datasets, including up to 75 million instances for the CVRP-20 model. Unlike previous transductive methods that required re-training for every new problem, L2R is inductive, meaning it can generalize to entirely new sets of customers once the initial training is complete.

Key Results and Insights

Experimental results demonstrate that L2R consistently finds shorter total distances than baseline random-restart methods across all problem sizes.

Comparison of average distance per iteration and cumulative best distance between L2R and the baseline.

Several key insights emerged from the study:

  • The Power of a "Weak Learner": Surprisingly, the value network's raw accuracy was only about 53-54%. However, even this slight guidance was enough to significantly outperform random restarts, proving that a small nudge in the right direction is highly effective in optimization.
  • Scaling with $K$: As the number of candidate starts ($K$) increased, the performance gap between L2R and the baseline widened, showing that the value network effectively filters the "noise" of random starts.
  • Preferential Learning: Training the network to rank solutions (the Siamese approach) proved far more effective than training it to predict absolute final distances (regression).

Limitations and Future Work

While successful, the authors note that the model's raw predictive accuracy remains a bottleneck. Improving the neural architecture to better capture the "ruggedness" of combinatorial search spaces is a priority. Additionally, they observed that aggressive filtering can sometimes reduce population diversity in evolutionary algorithms, potentially leading to new types of local optima traps. Future work may explore Active Learning, where the BOA's real-time results are used to update the value network during the optimization process, allowing the oracle to adapt to the specific quirks of the problem at hand.

Summary updated

BibTeX
@misc{zhang2020learning,
  author = {Xingwen Zhang and Shuang Yang},
  title = {{Learning (Re-)Starting Solutions for Vehicle Routing Problems}},
  year = {2020},
  eprint = {2008.03424},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.03424},
}
Figure