A branch-and-cut algorithm for the preemptive swapping problem

Charles Bordenave, Michel Gendreau, G. Laporte

Research output: Contribution to journalArticlepeer-review

10 Citations (SciVal)


In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determining a minimum cost route that allows the vehicle to satisfy every supply and demand. This article investigates the preemptive version of the SP in which the objects are allowed to be dropped at temporary locations along the route. The problem is modeled as a mixed integer linear program which is solved by branch-and-cut. Computational results on random geometric instances containing up to 100 vertices and eight object types are reported.

Original languageEnglish
Pages (from-to)387-399
Number of pages13
Issue number4
Publication statusPublished - Jul 2012


  • branch-and-cut
  • precedence relationships
  • swapping problem
  • vehicle routing

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'A branch-and-cut algorithm for the preemptive swapping problem'. Together they form a unique fingerprint.

Cite this