Abstract A heuristic algorithm is described for a time-constrained version of the advance-request, multi-vehicle, many-to-many Dial-A-Ride Problem (DARP). The time constraints consist of upper bounds on: (1) the amount of time by which the pick-up or delivery of a customer can deviate from the desired pick-up or delivery time; (2) the time that a customer can spend riding in a vehicle. The algorithm uses a sequential insertion procedure to assign customers to vehicles and to determine a time schedule of pick-ups and deliveries for each vehicle. A flexible objective function balances the cost of providing service with the customers' preferences for pick-up and delivery times close to those requested, and for short ride times. Computational experience with the algorithm is described, including a run with a real database of 2600 customers and some 20 simultaneously active vehicles. The scenario for the application of the algorithm is also discussed in detail.
A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows
Transportation Research Part B: Methodological ; 20 , 3 ; 243-257
1984-10-15
15 pages
Article (Journal)
Electronic Resource
English
A tabu search heuristic for the static multi-vehicle dial-a-ride problem
Elsevier | 2002
|A tabu search heuristic for the static multi-vehicle dial-a-ride problem
Online Contents | 2003
|