Premium
The preemptive swapping problem on a tree
Author(s) -
Anily Shoshana,
Gendreau Michel,
Laporte Gilbert
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20451
Subject(s) - vertex (graph theory) , object (grammar) , computer science , tree (set theory) , heuristic , mathematical optimization , combinatorics , mathematics , routing (electronic design automation) , type (biology) , graph , computer network , artificial intelligence , ecology , biology
This article 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. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011