New online reinsertion approaches for a dynamic Dial-A-Ride Problem - Université de Lorraine Access content directly
Journal Articles Journal of computational science Year : 2020

New online reinsertion approaches for a dynamic Dial-A-Ride Problem


This study is inspired by a challenging dynamic Dial-a-Ride Problem (DARP) encountered in a mobility service operated by the company Padam.1 . 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. The main goal is to maximize the number of accepted requests during the service while respecting maximum capacity of limited number of vehicles. In this study, we propose novel methods based on reinsertion techniques to improve Padam's online system. The proposed reinsertion techniques aim to exploit the neighborhood of a solution and must be run in real-time whenever a request is rejected by an online system. Three main online reinsertion heuristics based on different neighborhoods are proposed. The first heuristic called HDR uses destruction and repair operators, the second heuristic called GH (graph heuristic) uses the ejection chain concept, and allow modeling the reinsertion problem as a constrained shortest path problem on directed graph built from a current solution, and the third heuristic called IGH (improved graph heuristic) based on GH with intensive exploration of the neighborhood. Our proposed approaches were extensively tested on real and hard instances provided by Padam. These instances contain up to 1011 requests and 14 vehicles and with very tight time windows. The obtained results revealed the performance of the proposed reinsertion methods compared to the online heuristic, where the number of served requests is increased and the number of vehicles is reduced while maintaining operating costs close to those of the online system. The results confirm the interest of using reinsertion techniques in the dynamic DARP service.
Fichier principal
Vignette du fichier
S1877750320305007.pdf (543.25 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02981758 , version 1 (08-09-2022)





Sven Vallée, Ammar Oulamara, Wahiba Ramdane Cherif-Khettaf. New online reinsertion approaches for a dynamic Dial-A-Ride Problem. Journal of computational science, 2020, 47, ⟨10.1016/j.jocs.2020.101199⟩. ⟨hal-02981758⟩
103 View
17 Download



Gmail Facebook Twitter LinkedIn More