Skip to Main content Skip to Navigation
Book section

Maximizing the Number of Served Requests in an Online Shared Transport System by Solving a Dynamic DARP

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 users who specify their departure or arrival locations using a single vehicle. The aim of DARP is to design vehicle routes satisfying requests of users and minimizing the total traveled distance. In this work, we consider a real case of dynamic DARP service operated by Padam (www.padam.io) in Paris and Bristol. Padam offers a high quality transportation service in which users ask for a service either in real time or in advance, and get an immediate answer about whether their requests are accepted or not. The transport activity is outsourced in Padam’s service, and contracts are negotiated with third parties firms. Then each day, a fixed set of drivers is available during a working period of time to provide a transportation service of Padam. The main goal then becomes to maximize the number of accepted requests during the service. In this work, we develop a two-phase procedure to achieve it. In the first phase an insertion heuristic is used to quickly find out whether a request of a customer can be inserted, then, in the second phase, we run an ALNS algorithm between the occurrence of requests to improve the quality of the solution. The procedure was extensively tested on real data provided by Padam with up to 2000 requests and very tight side constraints and time-windows.
Document type :
Book section
Complete list of metadatas

https://hal.univ-lorraine.fr/hal-02982809
Contributor : Wahiba Ramdane Cherif-Khettaf <>
Submitted on : Thursday, October 29, 2020 - 1:10:46 AM
Last modification on : Tuesday, November 24, 2020 - 11:38:54 PM

Identifiers

Citation

Sven Vallée, Ammar Oulamara, Wahiba Ramdane Cherif-Khettaf. Maximizing the Number of Served Requests in an Online Shared Transport System by Solving a Dynamic DARP. Bektaş T.; Coniglio S.; Martinez-Sykora A.; Voß S. Computational Logistics 8th International Conference, 10572, springer, pp.64-78, 2017, ⟨10.1007/978-3-319-68496-3_5⟩. ⟨hal-02982809⟩

Share

Metrics

Record views

17