Scheduling procedure minimizing the total user ride time

Abstract

A dial-a-ride system is an application of demand-dependent, collective people transportation. Users request a trip between an origin and destination of choice. A time window is imposed on the departure or the arrival of the user and his ride time (the time spent in the vehicle) is limited. The service provider attempts to develop efficient vehicle routes and schedules, respecting these requirements and the technical constraints of a pickup and delivery problem. Solution algorithms invoke a scheduling procedure to assess the time feasibility of routes. Due to the maximum ride time constraint, serving each node at the earliest possible time is not effective. Postponing a pickup may reduce the ride time of the user involved. Cordeau and Laporte (2003) apply the forward time slack principle to eliminate constraint violations whenever possible. However, their procedure ignores the quality of the schedule. Parragh et al. (2009) modify the forward time slack approach to minimize the total ride time of all users, at the expense of occasional incorrect infeasibility declarations. Our work introduces a scheduling procedure that minimizes the total user ride time according to a different strategy. Starting from a schedule with minimal ride times for the given time windows, potential travel time shortages are eliminated while keeping ride time increases as limited as possible. Extensive computational tests on different sets of benchmark data show that the proposed procedure is fast and fails on fewer routes than Parragh et al. (2009). In addition, feasible schedules exhibit smaller deviations from the optimal solution.