Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A Deterministic Annealing Local Search for the Electric Autonomous Dial-a-Ride Problem

Abstract : This paper investigates the Electric Autonomous Dial-a-Ride Problem (E-ADARP) which consists of scheduling electric autonomous vehicles (EAVs) to transport users from specific origins to specific destinations within predefined time windows. We propose a Deterministic Annealing (DA) meta-heuristic where efficient local search operators are integrated to enhance the solution's quality. The potential visits to the recharging stations are explicitly handled by a bi-directional insertion algorithm. Computational experiments prove the effectiveness of the proposed algorithm in solving E-ADARP. The experiments are conducted under three scenarios: low, medium, and high energy level restriction, representing the constraint on the minimum level of the battery capacity at the end of the route. For each scenario, adapted instances from the literature are tested and an average gap of 0.58% is achieved compared to the best-known solutions for E-ADARP. Several new best solutions are found on previously solved and unsolved instances. Then, we investigate the effect of allowing multiple visits to the recharging stations. The experiments show that this operation can efficiently decrease the total cost and improve the solution feasibility. Furthermore, we establish new benchmark instances based on literature with up to 8 vehicles and 96 requests, with our algorithm providing feasible solutions that the exact method from the literature cannot solve in a given amount of time. These results are an indicator of the high performance of the proposed algorithm.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03211499
Contributor : Nicolas Dupin <>
Submitted on : Wednesday, April 28, 2021 - 5:31:16 PM
Last modification on : Tuesday, July 20, 2021 - 3:06:57 AM

File

A_Deterministic_Annealing_Loca...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03211499, version 1

Citation

Yue Su, Jakob Puchinger, Nicolas Dupin. A Deterministic Annealing Local Search for the Electric Autonomous Dial-a-Ride Problem. 2021. ⟨hal-03211499⟩

Share

Metrics

Record views

91

Files downloads

46