Analysis of an O(N²) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem

We develop an O(N²) 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 nodes 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’) 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.