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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

21 Citaties (Scopus)

Uittreksel

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.
Originele taal-2Engels
Pagina's (van-tot)32-35
TijdschriftOperations Research Letters
Volume39
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 2011

Vingerafdruk

Operations research
Interval Graphs
Shortest Path Problem
Operations Research
Testing
Weighted Graph
Linear-time Algorithm
Vertex of a graph
Graph
Time constraints
Shortest path

Citeer dit

@article{baa8963f68b147ac9eea8ab152a70644,
title = "Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh",
abstract = "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.",
author = "M. Firat and G.J. Woeginger",
year = "2011",
doi = "10.1016/j.orl.2010.11.004",
language = "English",
volume = "39",
pages = "32--35",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "1",

}

Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh. / Firat, M.; Woeginger, G.J.

In: Operations Research Letters, Vol. 39, Nr. 1, 2011, blz. 32-35.

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

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

VL - 39

SP - 32

EP - 35

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 1

ER -