Article ID Journal Published Year Pages File Type
421273 Discrete Applied Mathematics 2010 16 Pages PDF
Abstract

This paper models and solves a capacitated version of the Non-Preemptive Swapping Problem  . This problem is defined on a complete digraph G=(V,A)G=(V,A), at every vertex of which there may be one unit of supply of an item, one unit of demand, or both. The objective is to determine a minimum cost capacitated vehicle route for transporting the items in such a way that all demands are satisfied. The vehicle can carry more than one item at a time. Three mathematical programming formulations of the problem are provided. Several classes of valid inequalities are derived and incorporated within a branch-and-cut algorithm, and extensive computational experiments are performed on instances adapted from TSPLIB.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,