Groupe d’études et de recherche en analyse des décisions


An Algorithm for Mini-Clustering in Handicapped Transport

, , , et

In many cities around the world, public transportation services are requested to provide adapted transportation for handicapped persons and people with restricted mobility. Efficiently dispatching daily several thousands of requests to a hundred vehicle fleet is a difficult and time consuming task. The DARSY package (described in Desrosiers et al. 1988) redesigns the classical "cluster first-route second" approach by reducing the relative importance of heuristic methods and by extending the utility of optimization procedures to global decision making in the routing process. A set of mini-clusters are created at the first stage. A heuristic algorithm builds good segments of routes transporting small groups of neighbouring passengers. At the second stage, all the vehicle routes are simultaneously constructed using a column generation algorithm which deals with global operational planning considerations. This paper is dedicated to the first stage. The mini-clustering algorithm we propose does not attempt to construct full itineraries and split passengers between vehicles. It only makes local decisions on grouping together similar requests. The quality of attraction between two requests is measured by temporal and spatial proximities, directionality, economy of distance, and feasibility. Handicapped transport is a very personalized type of service in which thousands of different persons (users, operators, and schedulers) may be involved. And from this perspective the construction of mini-clusters occupies a very strategic position in the optimization process. The quality of the service offered to users is intimately tied to the quality of these mini-clusters. This paper presents numerical tests on a typical daily data set involving almost 3000 users.

, 15 pages