Technical Note—Optimizing the Schedule for a Fixed Vehicle Path with Convex Inconvenience Costs

Yvan Dumas, François Soumis and Jacques Desrosiers
Additional contact information
Yvan Dumas: GERAD and École des Hautes Études Commerciales, Montréal, Canada H3T 1V6
François Soumis: GERAD and École Polytechnique de Montréal, Montréal, Canada H3C 3A7
Jacques Desrosiers: GERAD and École des Hautes Études Commerciales, Montréal, Canada H3T 1V6

Transportation Science, 1990, vol. 24, issue 2, 145-152

Abstract: We present an algorithm that solves the problem of finding the vehicle schedule which minimizes total inconveniences for travel along a fixed path, where service times at nodes are constrained by time windows and where inconvenience is modeled using convex functions of the service times. This problem occurs as the last step or as a sub-problem in many common approaches to solving routing and scheduling problems. We show that the complexity of the algorithm, expressed as a number of unidimensional minimizations, is on the order of the number of nodes for convex inconvenience functions. For linear and quadratic functions, this complexity is linear in the number of nodes. We present extensions to the case where linear costs are applied to waiting time, and also to the case where the service time variables are discrete.

Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.24.2.145 (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:24:y:1990:i:2:p:145-152

Access Statistics for this article

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