Skip to Main content Skip to Navigation
Book section

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

Sven Vallée 1 Ammar Oulamara 1 Wahiba Ramdane Cherif-Khettaf 1
1 OPTIMIST - OPTImisation Methods for Integrated SysTems
LORIA - NSS - Department of Networks, Systems and Services
Abstract : 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.
Document type :
Book section
Complete list of metadata
Contributor : Wahiba Ramdane Cherif-Khettaf Connect in order to contact the contributor
Submitted on : Thursday, October 29, 2020 - 12:56:50 AM
Last modification on : Wednesday, November 3, 2021 - 7:08:58 AM



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⟩



Record views