Premium
A branch‐and‐cut algorithm for the nonpreemptive swapping problem
Author(s) -
Bordenave Charles,
Gendreau Michel,
Laporte Gilbert
Publication year - 2009
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20361
Subject(s) - vertex (graph theory) , object (grammar) , algorithm , computer science , type (biology) , graph , state (computer science) , set (abstract data type) , mathematical optimization , mathematics , combinatorics , theoretical computer science , artificial intelligence , ecology , biology , programming language
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