The Shortest Path Problem with Time Windows and Linear Waiting Costs

Guy Desaulniers and Daniel Villeneuve
Additional contact information
Guy Desaulniers: Groupe d'Études et de Recherche en Analyse des Décisions and École Polytechnique, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec H3T 2A7, Canada
Daniel Villeneuve: Groupe d'Études et de Recherche en Analyse des Décisions and École Polytechnique, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec H3T 2A7, Canada

Transportation Science, 2000, vol. 34, issue 3, 312-319

Abstract: This paper considers the shortest path problem with waiting costs (SPWC) as an extension to the shortest path problem with time windows. The problem consists of finding the minimum cost path in a network, where cost and time are two independent quantities associated with a path. Path feasibility is constrained by time windows at each node and a linear cost penalty is imposed for each unit of time spent waiting along the path. Starting from a known, nonlinear, integer programming formulation, we propose two alternative formulations for which algorithms already exist. First, we indicate how to transform the SPWC into a shortest path problem with time windows and linear node costs. Second, we prove that the SPWC can also be formulated as a two-resource generalized shortest path problem with resource constraints. Computational results used to compare these alternative formulations are presented.

Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.34.3.312.12298 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:34:y:2000:i:3:p:312-319

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().