A heuristic algorithm for a dial-a-ride problem with time windows,multiple capacities,and multiple objectives

The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface.