Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh

Murat Firat; Gerhard J. Woeginger

doi:10.1016/j.orl.2010.11.004

Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh

Murat Firat^*, Gerhard J. Woeginger

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Hunsaker and Savelsbergh [B. Hunsaker, M. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169173] 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.

Original language	English
Pages (from-to)	32-35
Number of pages	4
Journal	Operations Research Letters
Volume	39
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2010.11.004
Publication status	Published - Jan 2011
Externally published	Yes

Keywords

Dial-a-ride
Difference constraint system
Feasibility check
Shortest path

Access to Document

10.1016/j.orl.2010.11.004

Cite this

@article{0bc8f09c9ae04cb984663e937f1ae672,

title = "Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh",

abstract = "Hunsaker and Savelsbergh [B. Hunsaker, M. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169173] 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.",

keywords = "Dial-a-ride, Difference constraint system, Feasibility check, Shortest path",

author = "Murat Firat and Woeginger, {Gerhard J.}",

year = "2011",

month = jan,

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

language = "English",

volume = "39",

pages = "32--35",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh

AU - Firat, Murat

AU - Woeginger, Gerhard J.

PY - 2011/1

Y1 - 2011/1

N2 - Hunsaker and Savelsbergh [B. Hunsaker, M. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169173] 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 [B. Hunsaker, M. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169173] 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.

KW - Dial-a-ride

KW - Difference constraint system

KW - Feasibility check

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=78650774229&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2010.11.004

DO - 10.1016/j.orl.2010.11.004

M3 - Article

AN - SCOPUS:78650774229

SN - 0167-6377

VL - 39

SP - 32

EP - 35

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this