A branch‐and‐cut algorithm for the nonpreemptive swapping problem |
| |
Authors: | Charles Bordenave Michel Gendreau Gilbert Laporte |
| |
Affiliation: | 1. CIRRELT, Université de Montréal, Montréal H3C 3J7, Canada;2. Département d'Informatique et de recherche opérationnelle, Université de Montréal, Montréal H3C 3J7, Canada;3. Canada Research Chain in Distribution Management, HEC Montréal, Montréal H3T 2A7, Canada |
| |
Abstract: | In the Swapping Problem (SP), we are given a complete graph, a set of object types, and a vehicle of unit capacity. An initial state specifies the object type currently located at each vertex (at most one type per vertex). A final state describes where these object types must be repositioned. In general, there exist several identical objects for a given object type, yielding multiple possible destinations for each object. The SP consists of finding a shortest vehicle route starting and ending at an arbitrary vertex, in such a way that each object is repositioned in its final state. This article exhibits some structural properties of optimal solutions and proposes a branch‐and‐cut algorithm based on a 0‐1 formulation of the problem. Computational results on random instances containing up to 200 vertices and eight object types are reported. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009 |
| |
Keywords: | swapping problem branch‐and‐cut vehicle routing |
|
|