Please use this identifier to cite or link to this item:
Title: Scheduling procedure minimizing the total user ride time
Authors: MOLENBRUCH, Yves 
Issue Date: 2017
Source: VeRoLog 2017, Amsterdam, The Netherlands, 10-12/07/2017
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.
Keywords: dial-a-ride; vehicle routing; scheduling
Document URI:
Category: C2
Type: Conference Material
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
Full text.pdf
  Restricted Access
2.61 MBAdobe PDFView/Open    Request a copy
Show full item record

Page view(s)

checked on May 26, 2022


checked on May 26, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.