Abstract We develop an O(N 2) heuristic to solve the single vehicle many-to-many Euclidean Dial-A-Ride problem. The heuristic is based on the Minimum Spanning Tree of the modes of the problem. The algorithm's worst case performance is four times the length of the optimal Dial-A-Ride tour. An analysis of the algorithm's average performance reveals that in terms of sizes of single-vehicle problems that are likely to be encountered in the real world (up to 100 nodes) and in terms of computational complexity, the O(N 2) heuristic performs equally well, or, in many cases, better than heuristics described earlier by Stein for the same problem. The performance of the heuristic exhibits statistical stability over a broad range of problem sizes.
Analysis of an O(N2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem
Transportation Research Part B: Methodological ; 17 , 2 ; 133-145
1982-05-03
13 pages
Article (Journal)
Electronic Resource
English
Tour Length of Many-To-One Dial-A-Ride Service
British Library Conference Proceedings | 2005
|A tabu search heuristic for the static multi-vehicle dial-a-ride problem
Elsevier | 2002
|A tabu search heuristic for the static multi-vehicle dial-a-ride problem
Online Contents | 2003
|A rejected-reinsertion heuristic for the static Dial-A-Ride Problem
Online Contents | 2007
|