Optimal timing computation for quality service in a Dial a Ride problem

International audienceThe Dial-a-Ride Problem (DARP) belongs to the general class of Vehicle Routing Problems with Pickup and Delivery (VRPPD). It consists in scheduling a set of transportation requests on a heterogeneous fleet of vehicles. Each request consists in a number of persons, a specified pickup location, a destination location and desired departure and arrival time windows. We investigate a new and general model for the transportation of persons, it involves three objective functions that have to be optimized in order to measure the potential efficiency of the DARP solution on different aspects. In practice, the transportation requests of the DARP are usually booked in advance, so in this paper we consider the static version of the problem. More precisely we consider a novel model aimed to be closer to real-life situations since we consider not only the reduction of the transportation costs, which only reflects the transportation operator desires, but also criteria related to the quality of service provided to the users and the ecological impact of vehicle routings. The later is too of high importance, mainly for societal and environmental reasons. In this paper we focus on the problem of optimal timing in each route, which consists in finding the optimal dates of start service at each location knowing the routes. To solve this problem we present an O(nlog(n)) optimal algorithm which can be applied to any convex piecewise linear objective function