Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Feasibility Testing for Dial-a-Ride Problems
verfasst von : Dag Haugland, Sin C. Ho
Erschienen in: Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Hunsaker and Savelsbergh have proposed an algorithm for testing feasibility of a route in the solution to the dial-a-ride problem. The constraints that are checked are load capacity constraints, time windows, ride time bounds and wait time bounds. The algorithm has linear running time. By virtue of a simple example, we show in this work that their algorithm is incorrect. We also prove that by increasing the time complexity by only a logarithmic factor, a correct algorithm is obtained.