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

Research output: Contribution to journalJournal articleResearchpeer-review

173 Downloads (Pure)

Abstract

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.
Original languageEnglish
JournalTransportation Research. Part B: Methodological
Volume17B
Issue number2
Pages (from-to)133-145
ISSN0191-2615
Publication statusPublished - 1983
Externally publishedYes

Fingerprint Dive into the research topics of 'Analysis of an O(N²) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem'. Together they form a unique fingerprint.

Cite this