Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems

概要

論文の詳細を見る
In this paper, we consider a problem of simultaneously optimizing a sequence of graphs and a route which exhaustively visits the vertices from each pair of successive graphs in the sequence. This type of problem arises from repetitive routing of grasp-and-delivery robots used in the production of printed circuit boards. The problem is formulated as follows. We are given a metric graph G*=(V*,E*), a set of m+1 disjoint subsets Ci ⊆ V* of vertices with |Ci|=n, i=0,1,...,m, and a starting vertex s ∈ C0. We seek to find a sequence π=(Ci1, Ci2, ..., Cim) of the subsets of vertices and a shortest walk P which visits all (m+1)n vertices in G* in such a way that after starting from s, the walk alternately visits the vertices in Cik-1 and Cik, for k=1,2,...,m (i0=0). Thus, P is a walk with m(2n-1) edges obtained by concatenating m alternating Hamiltonian paths between Cik-1 and Cik, k=1,2,...,m. In this paper, we show that an approximate sequence of subsets of vertices and an approximate walk with at most three times the optimal route length can be found in polynomial time.