THE SHORTEST PATH PROBLEM WITH TIME WINDOWS AND LINEAR WAITING COSTS
This paper examines the shortest path problem with waiting costs (SPWC) as an extension to the shortest path problem with time windows. The problem consists of the minimum cost path in a network, where cost and time are 2 independent quantities associated with a path. Path feasibility is constrained by time windows at each node and a linear cost penality is imposed for each unit of time spent waiting along the path. Starting from a known, nonlinear, integer programming formulation, 2 alternative formulations for which algorithms already exist are proposed. Next, the authors indicate how to transform the SPWC into a shortest path problem with time windows and linear node costs. It is proven that the SPWC can also be formulated as a 2-resource generalized shortest path problem with resource constraints. Computational results used to compare these alternative formulations are presented.
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
-
Corporate Authors:
Institute for Operations Research and the Management Sciences (INFORMS)
901 Elkridge Landing Road, Suite 400
Linthicum, MD United States 21090-2909 -
Authors:
- Desaulniers, G
- Villeneuve, D
- Publication Date: 2000-8
Language
- English
Media Info
- Features: References; Tables;
- Pagination: p. 312-319
-
Serial:
- Transportation Science
- Volume: 34
- Issue Number: 3
- Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
- ISSN: 0041-1655
- Serial URL: http://transci.journal.informs.org/
Subject/Index Terms
- TRT Terms: Costs; Linear programming; Linear systems; Nodes (Networks); Nonlinear programming; Shortest path algorithms; Time windows; Traffic forecasting; Waiting time
- Subject Areas: Finance; Highways; Planning and Forecasting; I72: Traffic and Transport Planning;
Filing Info
- Accession Number: 00798676
- Record Type: Publication
- Files: TRIS
- Created Date: Sep 6 2000 12:00AM