For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI Yoshiyuki KARUNO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Online ISSN: 1745-1361
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)>>
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.