Reinsertion Algorithm Based on Destroy and Repair Operators for Dynamic Dial a Ride Problems - Université de Lorraine Accéder directement au contenu
Chapitre D'ouvrage Année : 2019

Reinsertion Algorithm Based on Destroy and Repair Operators for Dynamic Dial a Ride Problems

Résumé

The Dial-a-Ride Problem (DARP) consists in serving a set of customers who specify their pickup and drop-off locations using a fleet of vehicles. The aim of DARP is designing vehicle routes satisfying requests of customers and minimizing the total traveled distance. In this paper, we consider a real case of dynamic DARP service operated by Padam3 in which customers ask for a transportation service either in advance or in real time and get an immediate answer about whether their requests are accepted or rejected. A fleet of fixed number of vehicles is available during a working period of time to provide a transportation service. The goal is to maximize the number of accepted requests during the service. In this paper, we propose an original and novel online Reinsertion Algorithm based on destroy/repair operators to reinsert requests rejected by the online algorithm used by Padam. The proposed algorithm was implemented in the optimization engine of Padam and extensively tested on real hard instances up to 1011 requests and 14 vehicles. The results show that our method succeeds in improving the number of accepted requests.
Fichier non déposé

Dates et versions

hal-02982807 , version 1 (29-10-2020)

Identifiants

Citer

Sven Vallée, Ammar Oulamara, Wahiba Ramdane Cherif-Khettaf. Reinsertion Algorithm Based on Destroy and Repair Operators for Dynamic Dial a Ride Problems. Lecture Notes in Computer Science book series, 11536, springer, pp.81-95, 2019, Computational Science – ICCS 2019 19th International Conference, Faro, Portugal, June 12–14, 2019, Proceedings, Part I, ⟨10.1007/978-3-030-22734-0_7⟩. ⟨hal-02982807⟩
77 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More