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

Aleksandar SHURBEVSKI; Hiroshi NAGAMOCHI; Yoshiyuki KARUNO

doi:10.1587/transinf.E96.D.450

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

Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, Yoshiyuki KARUNO

Full Text Views

0

Share
Cite this

Summary :

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₀. We seek to find a sequence π=(C_i₁, C_i₂, ..., C_{i_m}) 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 C_{i_k-1} and C_{i_k}, for k=1,2,...,m (i₀=0). Thus, P is a walk with m(2n-1) edges obtained by concatenating m alternating Hamiltonian paths between C_{i_k-1} and C_{i_k}, 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.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.3 pp.450-456

Publication Date: 2013/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.450

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)

Category

Cite this

Copy

Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, Yoshiyuki KARUNO, "Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 3, pp. 450-456, March 2013, doi: 10.1587/transinf.E96.D.450.
Abstract: 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₀. We seek to find a sequence π=(C_i₁, C_i₂, ..., C_{i_m}) 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 C_{i_k-1} and C_{i_k}, for k=1,2,...,m (i₀=0). Thus, P is a walk with m(2n-1) edges obtained by concatenating m alternating Hamiltonian paths between C_{i_k-1} and C_{i_k}, 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E96.D.450/_p

Copy

@ARTICLE{e96-d_3_450,
author={Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, Yoshiyuki KARUNO, },
journal={IEICE TRANSACTIONS on Information},
title={Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems},
year={2013},
volume={E96-D},
number={3},
pages={450-456},
abstract={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₀. We seek to find a sequence π=(C_i₁, C_i₂, ..., C_{i_m}) 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 C_{i_k-1} and C_{i_k}, for k=1,2,...,m (i₀=0). Thus, P is a walk with m(2n-1) edges obtained by concatenating m alternating Hamiltonian paths between C_{i_k-1} and C_{i_k}, 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.},
keywords={},
doi={10.1587/transinf.E96.D.450},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
T2 - IEICE TRANSACTIONS on Information
SP - 450
EP - 456
AU - Aleksandar SHURBEVSKI
AU - Hiroshi NAGAMOCHI
AU - Yoshiyuki KARUNO
PY - 2013
DO - 10.1587/transinf.E96.D.450
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2013
AB - 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₀. We seek to find a sequence π=(C_i₁, C_i₂, ..., C_{i_m}) 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 C_{i_k-1} and C_{i_k}, for k=1,2,...,m (i₀=0). Thus, P is a walk with m(2n-1) edges obtained by concatenating m alternating Hamiltonian paths between C_{i_k-1} and C_{i_k}, 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.
ER -