A branch‐and‐cut algorithm for the nonpreemptive swapping problem

Charles Bordenave, Michel Gendreau and Gilbert Laporte

Naval Research Logistics (NRL), 2009, vol. 56, issue 5, 478-486

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

Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.20361

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:wly:navres:v:56:y:2009:i:5:p:478-486

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().