Paper Info
Title
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.
Year
Venue
Field
2017
ICCL
Heuristic,Ask price,Computer science,Simulation,Transport system,Operations research,Theoretical computer science
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
9
3
Name
Order
Citations
PageRank
Sven Vallée100.34
Ammar Oulamara2173.89
Wahiba Ramdane Chérif-Khettaf342.15