Neuro CROSS exchange: Learning to CROSS exchange to solve realistic vehicle routing problems

Minjun Kim, Junyoung Park, Jinkyoo ParkarXiv 2022 · DOI · OpenReview

TL;DR

This paper introduces Neuro CROSS exchange (NCE), a novel neural network-based operator that significantly speeds up solving complex vehicle routing problems (VRPs) by learning to predict the effectiveness of solution improvements. NCE achieves near-optimal solutions with drastically reduced computation time, outperforming existing meta-heuristics and neural methods, and importantly, generalizes well to different VRP variants without retraining.

What Problem Does This Paper Address?

Vehicle Routing Problems (VRPs) are a class of NP-hard optimization problems with numerous real-world applications, such as logistics and delivery. Traditional approaches often rely on meta-heuristics, which use iterative improvement operators to find good solutions. One such operator is CROSS exchange (CE), which swaps segments of routes between vehicles to reduce overall cost. However, CE's brute-force search for the best swap is computationally expensive, scaling as O(n⁴), making it impractical for large-scale problems. Existing neural approaches to VRPs often require problem-specific training or complex reinforcement learning setups, limiting their generalizability. This paper aims to bridge this gap by developing a learned operator that retains the effectiveness of CE but with a significantly reduced computational cost and improved generalizability across various VRP types.

Methods

The core innovation is Neuro CROSS exchange (NCE). NCE leverages a Graph Neural Network (GNN) to predict the "cost decrement" – the expected reduction in total cost – that would result from a specific CROSS exchange operation. Instead of exhaustively searching all possible swaps (which is O(n⁴)), NCE uses the GNN's predictions to guide its search towards promising swaps.

Here's a breakdown of the NCE process:

  1. Cost-Decrement Prediction: A GNN takes a pair of tours (from two different vehicles) and potential sub-tour starting points as input. It outputs a prediction of the maximum cost reduction achievable by swapping these sub-tours. This prediction is trained in a supervised manner using readily available data.
  2. Candidate Set Construction: The GNN's predictions are used to identify a smaller set of "promising" pairs of starting nodes (a₁, a₂) that are most likely to lead to significant cost improvements.
  3. Reduced Search: For these promising pairs, NCE then performs a more targeted search to find the optimal sub-tour endpoints (b₁, b₂). This two-stage approach reduces the overall search complexity from O(n⁴) to O(n²).
  4. Generalization: Crucially, the NCE operator is trained on the Flexible Multi-Depot VRP (FMDVRP) and then applied to other VRP variants (MDVRP, mTSP, CVRP) without any additional training or fine-tuning. This demonstrates its ability to learn a fundamental, transferable operator.

Datasets

The paper uses synthetic datasets for training and evaluation.

  • Training Data: 50,000 random FMDVRP instances were generated. For each instance, two tours were created using an initial solution construction heuristic. The true cost decrements for all feasible swaps were computed to prepare the training dataset, resulting in approximately 47.8 million training samples.
  • Evaluation Data: The authors evaluated NCE on various VRP instances, including:
  • FMDVRP: 100 random instances for each size (Nc, Nd, Nv).
  • MDVRP: Similar to FMDVRP, 100 instances per size.
  • mTSP: 100 instances for each (Nc, N) pair, using instances from mTSPLib.
  • CVRP: Standard CVRP benchmark instances (CVRP20, CVRP50, CVRP100).

Key Insights and Ideas

  • Learning a Fundamental Operator: The key insight is that instead of learning to solve specific VRPs end-to-end, NCE learns a general "improvement operator" (CROSS exchange) that can be applied across different VRP types. This is more efficient and transferable than problem-specific models.
  • Predicting Cost Decrements is Sufficient: The paper shows that predicting the change in cost (cost decrement) is a more tractable learning problem than predicting the entire solution. This simplifies training and allows for effortless data preparation.
  • Impressive Generalization: The fact that an NCE model trained only on FMDVRP can effectively solve MDVRP, mTSP, and CVRP without retraining is a significant finding. It suggests that the learned operator captures universal principles of route improvement.
  • Speedup is Dramatic: The reduction in complexity from O(n⁴) to O(n²) is substantial. The experimental results clearly demonstrate this, showing NCE to be orders of magnitude faster than traditional CE for larger instances.

Key Results

  • Performance: NCE achieves near-optimal or optimal solutions across FMDVRP, MDVRP, mTSP, and CVRP.
  • For FMDVRP, NCE achieved makespans comparable to CPLEX (optimal) and CE (near-oracle) with significantly lower computation times. For large instances, NCE had a near-zero gap compared to CE.
  • For mTSP, NCE achieved similar performance to state-of-the-art meta-heuristics like LKH-3, but with much shorter computation times. It also outperformed neural baselines.
  • For CVRP, NCE performed on par with or better than other neural baselines.
  • Speed: NCE is significantly faster than traditional CE. For instance, on FMDVRP with 100 customers, NCE was orders of magnitude faster while achieving comparable solution quality.
  • Transferability: The NCE model trained on FMDVRP demonstrated strong performance on MDVRP, mTSP, and CVRP without any retraining, highlighting its generalizability.

Limitations and Future Work

  • Complex Constraints: The paper acknowledges that NCE currently does not explicitly handle more complex VRP constraints such as pickup and delivery, or time windows.
  • Future Work: The authors suggest extending NCE to incorporate these complex constraints into the operator or the search process. They also plan to explore solving more complex VRP variants by considering these additional constraints during the NCE operation.

Summary updated

Abstract

CROSS exchange (CE), a meta-heuristic that solves various vehicle routing problems (VRPs), improves the solutions of VRPs by swapping the sub-tours of the vehicles. Inspired by CE, we propose Neuro CE (NCE), a fundamental operator of learned meta-heuristic, to solve various VRPs while overcoming the limitations of CE (i.e., the expensive $\mathcal{O}(n^4)$ search cost). NCE employs a graph neural network to predict the cost-decrements (i.e., results of CE searches) and utilizes the predicted cost-decrements as guidance for search to decrease the search cost to $\mathcal{O}(n^2)$. As the learning objective of NCE is to predict the cost-decrement, the training can be simply done in a supervised fashion, whose training samples can be prepared effortlessly. Despite the simplicity of NCE, numerical results show that the NCE trained with flexible multi-depot VRP (FMDVRP) outperforms the meta-heuristic baselines. More importantly, it significantly outperforms the neural baselines when solving distinctive special cases of FMDVRP (e.g., MDVRP, mTSP, CVRP) without additional training.
BibTeX
@misc{kim2022neuro,
  author = {Minjun Kim and Junyoung Park and Jinkyoo Park},
  title = {{Neuro CROSS exchange: Learning to CROSS exchange to solve realistic vehicle routing problems}},
  year = {2022},
  eprint = {2206.02771},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.02771},
}
Figure