The multiple vehicle many-to-many routing problem is presented in the context of a dial-a-ride system. It is solved by mini-clustering first and optimal routing second, an innovative modification of the "cluster first - route second" method which permits a more intelligent clustering of customers. A heuristic sequential insertion algorithm groups nearby customers (mini-clusters) who can be efficiently served by the same vehicle route segment. An optimal column generation algorithm then constructs routes corresponding to drivers' workdays by stringing together these vehicle route segments. Finally, the route segments are reopened in order to reoptimize each route. Problems with up to 200 customers and 85 mini-clusters are easily solved. Larger problems are solved by applying the algorithm to several non-disjoint subproblems obtained by dividing the territory into sub-areas and the day into time slices.
Published September 1989 , 31 pages