A heuristic algorithm for the multivehicle advance request dial-a-ride problem with time windows

A heuristic algorithm is described for a time-constrained version of the advance-request, multivehicle, many-to-many dial-a-ride problem. The time constraints consist of upper bounds on the amount of time by which the pick-up or delivery of a customer can deviate from the desired pick-up or delivery time and on 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.