A note on "Efficient feasibility testing for dial-a-ride problems''

Jiafu Tang; Yuan Kong; Henry C. W. Lau; Andrew W. H. Ip

doi:10.1016/j.orl.2010.05.002

A note on "Efficient feasibility testing for dial-a-ride problems''

Jiafu Tang
, Yuan Kong
, Henry C. W. Lau
, Andrew W. H. Ip

School of Business

Research output: Contribution to journal › Article

29 Citations (Scopus)

Abstract

Hunsaker and Savelsbergh [B. Hunsaker, M.W.P. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169ÃƒÂ¢Ã¢"šÂ¬Ã¢â‚¬Å“173.] developed a linear-time algorithm to verify the feasibility for dial-a-ride problems. However, this algorithm may incorrectly declare infeasibility due to ride time constraints in some cases. We propose a revised procedure to address this flaw, but in an O(n2) worst-case time.

Original language	English
Pages (from-to)	405-407
Number of pages	3
Journal	Operations Research Letters
Volume	38
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2010.05.002
Publication status	Published - 2010

Keywords

linear-time algorithms
operations research

Access to Document

10.1016/j.orl.2010.05.002

Cite this

@article{f946a786609149459df2eaf5c39c8557,

title = "A note on {"}Efficient feasibility testing for dial-a-ride problems''",

abstract = "Hunsaker and Savelsbergh [B. Hunsaker, M.W.P. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169{\~A}ƒ{\^A}¢{\~A}¢{"}{\v s}{\^A}¬{\~A}¢{\^a}‚¬{\AA}“173.] developed a linear-time algorithm to verify the feasibility for dial-a-ride problems. However, this algorithm may incorrectly declare infeasibility due to ride time constraints in some cases. We propose a revised procedure to address this flaw, but in an O(n2) worst-case time.",

keywords = "linear-time algorithms, operations research",

author = "Jiafu Tang and Yuan Kong and Lau, \{Henry C. W.\} and Ip, \{Andrew W. H.\}",

year = "2010",

doi = "10.1016/j.orl.2010.05.002",

language = "English",

volume = "38",

pages = "405--407",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - A note on "Efficient feasibility testing for dial-a-ride problems''

AU - Tang, Jiafu

AU - Kong, Yuan

AU - Lau, Henry C. W.

AU - Ip, Andrew W. H.

PY - 2010

Y1 - 2010

N2 - Hunsaker and Savelsbergh [B. Hunsaker, M.W.P. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169ÃƒÂ¢Ã¢"šÂ¬Ã¢â‚¬Å“173.] developed a linear-time algorithm to verify the feasibility for dial-a-ride problems. However, this algorithm may incorrectly declare infeasibility due to ride time constraints in some cases. We propose a revised procedure to address this flaw, but in an O(n2) worst-case time.

AB - Hunsaker and Savelsbergh [B. Hunsaker, M.W.P. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169ÃƒÂ¢Ã¢"šÂ¬Ã¢â‚¬Å“173.] developed a linear-time algorithm to verify the feasibility for dial-a-ride problems. However, this algorithm may incorrectly declare infeasibility due to ride time constraints in some cases. We propose a revised procedure to address this flaw, but in an O(n2) worst-case time.

KW - linear-time algorithms

KW - operations research

UR - http://handle.uws.edu.au:8081/1959.7/505665

U2 - 10.1016/j.orl.2010.05.002

DO - 10.1016/j.orl.2010.05.002

M3 - Article

SN - 0167-6377

VL - 38

SP - 405

EP - 407

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

A note on "Efficient feasibility testing for dial-a-ride problems''

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this