The Dial-a-Ride Problem with Transfers and Stochastic Customers

International audienceThe dial-a-ride problem (DARP) aims at providing solutions to on-demand col-lective human transportation problems. It generalizes the pickup and delivery problem withtime windows (PDPTW) by considering customer convenience constraints in addition tostandard PDPTW constraints. The DARP with Transfers (DARP-T) has recently been in-troduced by Péton et al:[10] in order to permit the customers to change vehicles during theirtrip, at predefined transfer points. One practical application of the DARP-T is an on-demandpublic transportation service planner, provided a solution framework dealing with dynamicinstances. In this paper, we explore several Stochastic Programming models to the dynamicproblem. By modeling customer demands as stochastic data, we can compute anticipativesolutions which are dynamically adapted online in order to maximize the number of onlinesatisfied requests. We also propose a heuristic algorithm that can be exploited on any VehicleRouting problem, including the Dial-a-Ride Problem with Transfers. This paper does notprovide any results, but aims at describing a research plan for the current PhD thesis