Fast Local Search Algorithms for the Handicapped Persons Transportation Problem

We examine the problem of determining an optimal schedule for a fleet of vehicles used to cover the trips required to transport handicapped persons in an urban area. The problem is a generalization of the well-known Pickup and Delivery Problem with Time Windows since, due to the high level of service required by this kind of transport, many additional operational constraints must be considered. We describe fast and effective local search refining procedures, based on trip movements and exchanges, which can be used to improve within acceptable computing time the solutions of large-size instances obtained by using a parallel insertion heuristic algorithm. The procedures have been successfully applied to a set of large real-life problems for the town of Bologna, involving about 300 trips each, showing the effectiveness of the proposed approach.