Lagrangian Relaxation Methods for Solving the Minimum Fleet Size Multiple Traveling Salesman Problem with Time Windows

Jacques Desrosiers, Michel Sauvé and François Soumis
Additional contact information
Jacques Desrosiers: École des Hautes Études Commerciales and GERAD, Montréal, Québec, Canada H3T 1V6
Michel Sauvé: École des Hautes Études Commerciales and GERAD, Montréal, Québec, Canada H3T 1V6
François Soumis: École Polytechnique and Centre de Recherche sur les Transports, Montréal, Québec, Canada H3C 3A7

Management Science, 1988, vol. 34, issue 8, 1005-1022

Abstract: We consider the problem of finding the minimum number of vehicles required to visit once a set of nodes subject to time window constraints, for a homogeneous fleet of vehicles located at a common depot. This problem can be formulated as a network flow problem with additional time constraints. The paper presents an optimal solution approach using the augmented Lagrangian method. Two Lagrangian relaxations are studied. In the first one, the time constraints are relaxed producing network subproblems which are easy to solve, but the bound obtained is weak. In the second relaxation, constraints requiring that each node be visited are relaxed producing shortest path subproblems with time window constraints and integrality conditions. The bound produced is always excellent. Numerical results for several actual school busing problems with up to 223 nodes are discussed. Comparisons with a set partitioning formulation solved by column generation are given.

Keywords: multiple traveling salesman; time windows; fleet size; Lagrangian relaxation methods (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.8.1005 (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:ormnsc:v:34:y:1988:i:8:p:1005-1022

Access Statistics for this article

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