Maximizing the Number of Served Requests in an Online Shared Transport System by Solving a Dynamic DARP - Université de Lorraine Access content directly
Book Section Year : 2017

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

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.
No file

Dates and versions

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

Identifiers

Cite

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⟩
59 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More