Paper Info
Title
Feasibility testing for dial-a-ride problems
Abstract
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.
Year
DOI
Venue
2010
10.1007/978-3-642-14355-7_18
AAIM
Keywords
Field
DocType
time bound,logarithmic factor,ride time bound,feasibility testing,time windows,load capacity constraint,dial-a-ride problem,correct algorithm,simple example,time complexity
Mathematical optimization,Computer science,Algorithm,Logarithm,Time complexity,Dial
Conference
Volume
ISSN
ISBN
6124
0302-9743
3-642-14354-7
Citations 
PageRank 
References 
8
0.63
6
Authors
2
Name
Order
Citations
PageRank
Dag Haugland115115.18
Sin C. Ho21727.49