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

Aleksandar SHURBEVSKI  Hiroshi NAGAMOCHI  Yoshiyuki KARUNO  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.3   pp.450-456
Publication Date: 2013/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.450
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
combinatorial optimization,  routing and scheduling,  industrial robots,  approximation algorithms,  metric traveling salesperson problem,  

Full Text: PDF(261.4KB)>>
Buy this Article

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 CiV* of vertices with |Ci|=n, i=0,1,...,m, and a starting vertex sC0. 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.