TY - JOUR
T1 - Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh
AU - Firat, M.
AU - Woeginger, G.J.
PY - 2011
Y1 - 2011
N2 - Hunsaker and Savelsbergh [Operations Research Letters 30, 2002] discussed feasibility testing for a dial-a-ride problem under maximum wait time and maximum ride time constraints. We show that this feasibility test can be expressed as a shortest path problem in vertex-weighted interval graphs, which leads to a simple linear time algorithm.
AB - Hunsaker and Savelsbergh [Operations Research Letters 30, 2002] discussed feasibility testing for a dial-a-ride problem under maximum wait time and maximum ride time constraints. We show that this feasibility test can be expressed as a shortest path problem in vertex-weighted interval graphs, which leads to a simple linear time algorithm.
U2 - 10.1016/j.orl.2010.11.004
DO - 10.1016/j.orl.2010.11.004
M3 - Article
SN - 0167-6377
VL - 39
SP - 32
EP - 35
JO - Operations Research Letters
JF - Operations Research Letters
IS - 1
ER -