A clustering first - route second method for the solution of many-to-many Dial a Ride problem

摘要

A clustering first-route second method to solve the many-to-many Dial a Ride (DAR) problem has been proposed. The clustering phase is the main novelty of the method, taking into account both space and time variables to realize the clusters. The procedure has been tested on a real network during the organization of the mobility of students between some offices and Departments of "Roma Tre" University (Rome, Italy), obtaining good results in terms of waiting time and number of served users. The computational times (few seconds) promise the achievement of an on line service.