ABSTRACT
In this section we consider the case of a static belt and generalize possible part destinations to n in number; the robot arm, which can carry a maximum of k parts per cycle, must deliver one part to each sink. We be gin by considering a unit-capacity robot, i.e., the case k = 1. When the robot arm has unit capacity, any de livery route must alternate between part pick-up and and part delivery. Viewing the 1-Delivery TSP as a graph problem, we can re-define it as follows:
Anily and Hassin [2] have shown a 2.5-approximation algorithm for a generalization of this problem known as the Swapping Problem. Their algorithm finds a perfect matching M consisting of edges that connect red and blue vertices, and uses Christofides’s heuris tic [10] to find a tour T of the blue vertices. The final delivery route consists of visiting the blue ver tices in the sequence specified by the tour T, using the matching edges in M to deliver an item to a sink and return to the blue vertex (or “short-cut” to the next blue vertex on T). If OPT is the optimal de livery tour, clearly T < 1.50PT and M < 0.50PT, whereas the total length of the delivery tour is at most T + 2M < 2.50PT. We exploit some combinatorial properties of bipartite spanning trees and matroid in tersection to improve this factor to 2.
