### G-2005-69

# The Preemptive Swapping Problem on a Tree

## Shoshana Anily, Michel Gendreau, and Gilbert Laporte

This paper considers the swapping problem on a tree. In this problem at most one
object of some type is available at each vertex, and each vertex also requests at most
one object of a given type. The total demand and the total supply of each object type
are identical. The problem is to determine a minimum cost routing plan starting and
ending at a prespecified vertex which is the depot, for a single vehicle of unit capacity
and *m* object types, so that all vertex requests are satisfied. We consider the preemptive
mode in which objects may be temporarily dropped along the way. It is shown
that this problem is NP-hard. A heuristic with a worst-case performance ratio of 1.5
is developed. Finally, it is shown that the case where *m* = 1 is polynomially solvable.

Published **September 2005**
,
22 pages

This cahier was revised in **August 2006**