Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142580 | Operations Research Letters | 2011 | 4 Pages |
Abstract
Hunsaker and Savelsbergh [B. Hunsaker, M. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169–173] 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Murat Firat, Gerhard J. Woeginger,