Advancing Multi-Vehicle Dial-a-Ride Problems with Enhanced Deterministic Annealing Algorithm

By Dr Silpaja Chandrasekar, PhDReviewed by Susha Cheriyedath, M.Sc.Feb 15 2024

In a paper published in the journal PLOS ONE, researchers presented an enhanced deterministic annealing (DA) algorithm for solving large-scale multi-vehicle dial-a-ride problems (DARPs). This method ensured the exploration of feasible search spaces, guaranteeing a feasible solution at any termination point. It incorporated advanced local search techniques to expedite optimal solutions and employed a linearly decreasing DA schedule to mitigate poor jumps during the search.

Through systematic experiments comparing it with state-of-the-art methods such as adaptive large neighborhood search (ALNS), evolutionary local search (ELS), and DA using standard benchmarks, the proposed algorithm demonstrated faster convergence to competitive objective values across various benchmarks on average.

Related Work

Past work has extensively explored the DARP, which is crucial for various transport services like door-to-door transit, airport transfers, and hospital transport. Initially defined by Cordeau and Laporte in 2003, DARP is an extension of the classic pickup-and-delivery problem with time windows (PDPTW). Since then, researchers used extensions to address heterogeneity, multiple depots, stochasticity, and real-time scheduling.

While exact methods offer global optimality, they are time-consuming for large-scale DARPs, leading to the development of efficient meta-heuristic algorithms. Notable methods include DA, ALNS, and ELS. Despite advancements, handling real-world scenarios with more significant passenger numbers and complex networks remains challenging, demanding further improvements in solution methods.

Enhanced DA Algorithm

The proposed methodology introduces the linearly decreasing DA (LD-DA) algorithm, a modified version of the DA algorithm. It operates as a local search-based iterative metaheuristic, initializing with an initial solution generated by adaptive reinforced logit models. The algorithm proceeds through two main phases: it initializes parameters in the initialization phase and applies local search operators in the optimization phase to enhance solutions. LD-DA ensures that only feasible solutions are accepted, thus eliminating the need for repair operators or objective function penalization.

In the optimization phase, local search operators generate new solutions, including inter-route and intra-route operators, such as swapping, relocation, 2-opt*, successive requests relocation, and r-5-opt. These operators enable the algorithm to explore the solution space effectively while maintaining feasibility. Additionally, the algorithm introduces a threshold-adjusting mechanism to regulate the acceptance of non-improved solutions, ensuring a balance between exploration and exploitation.

LD-DA employs a screening process based on an eight-step evaluation scheme to evaluate the feasibility of generated solutions. This process efficiently checks the feasibility of potential solutions, discarding infeasible ones and sorting the feasible solutions based on their objective values. LD-DA optimizes solution evaluation by employing this screening process, enabling faster convergence towards high-quality solutions for large-scale DARP instances.

Performance Evaluation

The computational experiments section thoroughly assesses the LD-DA meta-heuristics performance compared to three other leading algorithms for solving the DARP: ALNS, ELS, and DA. Leveraging the benchmark curated by Cordeau and Laporte, consisting of 20 instances, LD-DA consistently matched or exceeded the Best-Known Solutions (BKS) in seven cases. Furthermore, unlike ALNS and ELS, LD-DA delivered solutions of equivalent or superior quality and demonstrated significantly faster computational speeds. It suggests its applicability in real-world scenarios where efficiency is critical.

The subsequent analysis delves deeper into the performance comparison between LD-DA and DA across various metrics, including solution quality, computational time, convergence rate, and failure rate. Through experiments with standardized specifications and increased iterations, LD-DA consistently outperformed DA, showcasing competitive solution quality and computational efficiency. This consistent performance superiority positions LD-DA as a promising approach for addressing larger-scale problems effectively, indicating its potential utility in practical applications.

The evaluation process additionally focuses on assessing the effectiveness of the LD-threshold adjusting mechanism introduced in the proposed algorithm. Comparative analysis between the LD threshold and the existing accepting threshold mechanism on the DA algorithm highlighted superior solution quality and computational efficiency with the LD threshold. The LD-threshold approach significantly reduced objective function values. It achieved pre-specified objective values more rapidly than the existing mechanism, demonstrating its effectiveness in enhancing solution quality and computational efficiency.

Overall, the computational experiments provide compelling evidence of LD-DA's effectiveness in delivering high-quality solutions efficiently for the DARP. The algorithm's consistent performance superiority over existing methods, coupled with the demonstrated efficacy of the LD-threshold adjusting mechanism, underscores its potential as a valuable tool for addressing complex optimization problems in real-world scenarios.

Conclusion

To sum up, the proposed LD-DA algorithm represented a significant advancement in addressing the DARP by offering efficient solutions for large-scale applications. Its innovative features, including the LD-DA algorithm and the LD-threshold adjusting mechanism, contributed to its effectiveness in rapidly attaining high-quality solutions while minimizing computational time. Through meticulous initialization processes and tailored local search operators, LD-DA ensured the exploration of feasible solution spaces and facilitated the selection of cost-effective routes, making them adaptable to dynamic settings and real-world scenarios.

Furthermore, extensive computational experiments validated LD-DA's performance against state-of-the-art algorithms, demonstrating its ability to achieve comparable solution quality with significantly reduced computational time. The LD-threshold mechanism enhanced LD-DA's efficiency, showcasing statistically significant improvements in solution quality and computational time. As future research avenues, adapting LD-DA to accommodate alternative objective functions and incorporating more real-life problem characteristics will further enhance its versatility and applicability in addressing a broader spectrum of transportation challenges.