A Deterministic Annealing Local Search for the Electric Autonomous Dial-a-Ride Problem - Équipe : Management des opérations Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

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

Résumé

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.
Fichier principal
Vignette du fichier
A_Deterministic_Annealing_Local_Search_for_the_Electric_Autonomous_Dial_a_Ride_Problem.pdf (452.2 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03211499 , version 1 (28-04-2021)
hal-03211499 , version 2 (22-12-2021)
hal-03211499 , version 3 (09-12-2022)

Identifiants

  • HAL Id : hal-03211499 , version 1

Citer

Yue Su, Jakob Puchinger, Nicolas Dupin. A Deterministic Annealing Local Search for the Electric Autonomous Dial-a-Ride Problem. 2021. ⟨hal-03211499v1⟩
391 Consultations
171 Téléchargements

Partager

Gmail Facebook X LinkedIn More