Parallel Adaptive Large Neighborhood Search based on Spark to solve VRPTW

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

TL;DR

This paper introduces Spark-ALNS, a parallelized Adaptive Large Neighborhood Search algorithm designed to solve the complex Vehicle Routing Problem with Time Windows (VRPTW). By leveraging Apache Spark’s distributed computing power and an improved "tempered" cooling function, the researchers achieved a 3–5x speedup over existing parallel algorithms and even discovered 13 new "best" solutions for the standard Solomon benchmark dataset.

What Problem Does This Paper Address?

The Vehicle Routing Problem with Time Windows (VRPTW) is a classic NP-hard optimization challenge: how do you route a fleet of vehicles to deliver goods to a set of customers at the lowest cost, while ensuring every delivery happens within a specific time slot and no vehicle exceeds its capacity?

While heuristic algorithms like Adaptive Large Neighborhood Search (ALNS) are popular for these problems, they often suffer from three main issues:

  1. Slow Convergence: Finding a "good enough" solution takes too long for large-scale problems.
  2. Local Optima: The algorithm gets "stuck" in a mediocre solution and can't find the global best.
  3. Computational Bottlenecks: Certain operations, like "Greedy Insertion," are mathematically powerful but computationally expensive.

The authors aim to solve these by moving the computation to a distributed framework (Apache Spark) and refining the underlying search logic.

Methods

The authors built a hybrid approach that combines classical optimization techniques with modern distributed computing:

  • CW Initialization: Instead of starting with a random (and likely terrible) route, they use the Clarke-Wright (CW) savings algorithm to generate a high-quality initial feasible solution, giving the search a head start.
  • The Destroy-and-Repair Cycle: Like standard ALNS, the algorithm iteratively "destroys" parts of a route (removing customers) and "repairs" them (re-inserting them elsewhere). The paper uses three destruction operators (Random, Route, and Related Removal) and three repair operators (Random, Greedy, and Random-Criticality).
  • Improved Cooling Function: They modified the Simulated Annealing acceptance criteria. Unlike standard cooling (which can be too slow) or fast cooling (which can miss the global optimum), their function includes a "tempering" or floating interval. This allows the "temperature" to fluctuate slightly, helping the algorithm "jump out" of local optima.
  • Spark Parallelization: This is the core innovation. They used Spark’s Resilient Distributed Datasets (RDDs) to parallelize the search. Specifically, when the "Greedy Insertion" operator is chosen—usually a major bottleneck—the Master node shuffles the workload across Worker nodes to evaluate insertion costs in parallel.

Datasets

The researchers evaluated their algorithm using the Solomon dataset, a world-standard benchmark for VRPTW. It contains 56 instances categorized by customer distribution (clustered, random, or a mix) and time window density.

Key Insights and Ideas

  • Parallelizing the Bottleneck: The most interesting insight is the targeted parallelization of the Greedy Insertion operator. By recognizing that this specific operator provides high-quality solutions but carries the highest time complexity, the authors used Spark to turn a weakness into a strength.
  • The "Floating" Temperature: Most optimization algorithms cool down linearly or exponentially. The authors’ "floating" interval (Equation 14 in the paper) acts like a periodic re-heating of the search, which is a clever way to maintain diversity in the solution pool and prevent premature convergence.
  • Memory vs. Disk: The paper highlights why Spark is superior to Hadoop/MapReduce for this task. Because ALNS is highly iterative, Spark’s ability to keep data in memory (avoiding frequent disk I/O) is critical for the 3-5x speedup observed.

Key Results

The performance of Spark-ALNS was compared against other state-of-the-art parallel metaheuristics (like ACS, CPTS, and PMA):

  • Accuracy: Out of 56 test instances, Spark-ALNS matched the known optimal solution in 42 cases. Most impressively, it found 13 solutions that were better than the previously recorded "best" results in the literature.
  • Speed: The algorithm demonstrated a 3–5 times improvement in solving speed compared to other parallel algorithms.
  • Scalability: Moving from a serial execution to a 3-processor Spark cluster reduced computation time by 80–90%. For example, on instance RC201, the serial runtime was 536 seconds, while the three-processor Spark setup finished in just 81.9 seconds.

Limitations and Future Work

While the results on the Solomon benchmark are stellar, the paper leaves a few stones unturned:

  • Static vs. Dynamic: The Solomon dataset is static. In the real world, traffic, vehicle breakdowns, and new orders happen in real-time. The authors do not discuss how Spark-ALNS would handle a dynamic environment.
  • Hardware Overhead: Spark is powerful but has overhead. For very small VRP problems, the time spent setting up the Spark context and shuffling data might outweigh the computational gains.
  • Future Directions: The authors suggest that further optimizing the parallel approach and exploring more complex constraints (like multi-depot or heterogeneous fleets) would be the next logical steps.

Summary updated

Abstract

<title>Abstract</title> The Adaptive Large Neighborhood Search is an effective method for solving unconstrained optimization problems, but there are drawbacks such as poor accuracy, easy falling into local optimum and slow convergence when solving VRPTW. In order to improve the above problems, this paper improves the cooling function, uses CW initialization to improve the quality of the solution, and adopts three destruction operators and three repair operators, on the basis of which a parallel strategy is proposed to improve the accuracy of the algorithm and reduce the running time. The Solomon dataset is selected for simulation experiments to test both solution quality and running time, and comparison experiments are conducted with other parallel algorithms. The simulation results show that the algorithm can effectively solve VRPTW with a greater improvement in the solving accuracy and a 3–5 times improvement in the solving speed compared with other parallel algorithms.
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 = {Research Square},
  year = {2024},
  doi = {10.21203/rs.3.rs-4610138/v1},
}
Figure