Parallel adaptive large neighborhood search based on spark to solve VRPTW

Songzuo Liu, Jian Sun, Xiaohong Duan, G.y. LiuScientific 2024 · DOI

This paper, published in Scientific Reports, introduces Spark-ALNS, a high-performance optimization framework designed to tackle one of the most persistent headaches in logistics: the Vehicle Routing Problem with Time Windows (VRPTW). By combining a refined meta-heuristic with the distributed computing power of Apache Spark, the researchers achieved state-of-the-art results, finding 31 new optimal solutions for standard benchmarks while running up to five times faster than existing parallel methods.

TL;DR

Spark-ALNS is a parallelized optimization algorithm that solves complex vehicle routing problems by combining a novel "tempering" cooling strategy with the distributed processing power of Apache Spark. It significantly outperforms existing evolutionary algorithms, reaching known optimal solutions for 73% of standard test cases and setting new records for 31 specific instances.

What Problem Does This Paper Address?

The Vehicle Routing Problem (VRP) is a classic "NP-hard" challenge: how do you dispatch a fleet of vehicles to service a set of customers at the lowest possible cost? The Vehicle Routing Problem with Time Windows (VRPTW) adds a layer of complexity—each customer must be visited within a specific time frame.

Traditional algorithms like Adaptive Large Neighborhood Search (ALNS) are great at exploring these massive search spaces by "destroying" parts of a route and "repairing" them. However, ALNS often suffers from two major flaws:

  1. Local Optima: It gets "stuck" in a good-but-not-great solution.
  2. Computational Bottlenecks: High-quality repair operators (like Greedy Insertion) are computationally expensive, making the algorithm slow as the number of customers scales.

Methods

The authors propose a "4-point strategy" to overhaul the standard ALNS approach:

  1. Spark-Based Parallelization: The algorithm is deployed on Apache Spark using Resilient Distributed Datasets (RDDs). Crucially, they improved the parallel strategy for the "Greedy Insertion" operator—the most time-consuming part of the process—by using a "Shuffle" mechanism that distributes the workload across worker nodes based on vehicle routes.
  2. Tempering Cooling Strategy: Instead of a standard linear cooling curve (used in Simulated Annealing), they designed a cosine-based "tempering" function. This allows the "temperature" of the search to fluctuate, giving the algorithm the energy to "jump out" of local optimal traps periodically.
  3. CW Initialization: Rather than starting with a random, messy route, the algorithm uses the Clarke-Wright (CW) "savings" method to generate a high-quality initial solution, significantly accelerating convergence.
  4. Diverse Operators: The framework employs three destruction operators (Random, Route, and Related removal) and three repair operators (Random, Greedy, and Random-criticality repair) to maintain a healthy balance between exploring new areas and refining existing ones.

Datasets

The researchers evaluated Spark-ALNS using the Solomon benchmark dataset, a gold standard in the field since 1986. It consists of 56 instances categorized into:

  • C (Clustered): Customers are grouped geographically.
  • R (Random): Customers are spread out randomly.
  • RC (Mixed): A combination of clustered and random distributions.

Key Insights and Ideas

  • The Power of "Floating" Temperature: The most interesting technical insight is the improved cooling function. By using a cosine wave, the algorithm doesn't just get colder; it "tempers." This periodic reheating is what allowed the researchers to find new optimal solutions that previous algorithms missed because they settled too early.
  • Parallelizing the Bottleneck: Most parallel algorithms struggle with "Greedy" operators because they require global knowledge. By using Spark’s Master-Worker architecture to shuffle data specifically when the Greedy operator is selected, they turned a bottleneck into a strength.
  • Initialization is Half the Battle: The move from random initialization to CW initialization proved that a "warm start" is essential for big data optimization, preventing the algorithm from wasting thousands of iterations on obviously poor routes.

Key Results

  • New Records: Spark-ALNS found 31 new optimal solutions compared to other leading algorithms like HGA-SIH and ACS-BSO.
  • Benchmark Success: It reached the known optimal solution for 41 out of 56 Solomon instances.
  • Massive Speedups: The parallel framework on three processors was 3 to 5 times faster than other parallel algorithms (like ACS and PMA).
  • Efficiency: Using the parallel framework saved approximately 80–90% of the runtime compared to a traditional serial (single-thread) execution of the same algorithm.

Limitations and Future Work

While highly effective, the authors acknowledge a few limitations:

  • Single Warehouse Focus: The current model assumes all vehicles originate from a single distribution center. Real-world logistics often involve multi-warehouse systems.
  • Static Windows: The model doesn't account for real-time traffic changes or dynamic time window shifts.
  • Future Directions: The authors suggest extending the Spark-ALNS framework to "multilevel" problems and integrating it with other emerging meta-heuristics to further improve solution quality in even larger, more complex networks.

Summary updated

Abstract

Aiming at the multi-objective vehicle path planning problem with time windows (VRPTW), a Spark-based parallel Adaptive Large Neighborhood Search algorithm (Spark-ALNS) is proposed to solve it. The main design of the 4-point strategy: (1) Design a new simulated annealing algorithm cooling strategy to achieve a better jump out of the local optimal solution. (2) Adopt CW initialization to accelerate the convergence speed. (3) Use three destruction operators and three repair operators to implement local path optimization. (4) A new parallel strategy is proposed to improve the algorithm's accuracy and reduce the running time. To illustrate the algorithm's effectiveness, the arithmetic example in Solomon is used as an example. The experimental results show that the proposed Spark-ALNS can find better solutions, get the known optimal solutions for 41 out of 56 instances, and find new optimal solutions for 31 algorithms, which outperforms other evolutionary algorithms. The runtime is 3-5 times better than other parallel algorithms and is able to solve VRPTW effectively.
BibTeX
@inproceedings{liu2024parallel,
  author = {Songzuo Liu and Jian Sun and Xiaohong Duan and G.Y. Liu},
  title = {{Parallel adaptive large neighborhood search based on spark to solve VRPTW}},
  booktitle = {Scientific},
  year = {2024},
  doi = {10.1038/s41598-024-74432-2},
}
Figure