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 C_i (≤) V~* of vertices with |C_i| = n, i = 0,1,..., m, and a starting vertex s (≤) C_0. We seek to find a sequence π = (C_(i1), C_(i2), ···, C_(im)) of the subsets of vertices and a shortest walk P which visits all (m + l)n vertices in G* in such a way that after starting from s, the walk alternately visits the vertices in C_(ik-1) and C_(is), 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 C_(ik-1) and C_(ik),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.