Top > JACIII > An Approximation Algorithm with Factor Two for a Repetitive Ro ...

single-jc.php

JACIII Vol.15 No.8 pp. 1103-1108
doi: 10.20965/jaciii.2011.p1103
(2011)

Paper:

Views over last 60 days: 477

An Approximation Algorithm with Factor Two for a Repetitive Routing Problem of Grasp-and-Delivery Robots

Yoshiyuki Karuno*, Hiroshi Nagamochi**,
and Aleksandar Shurbevski*

*Department of Mechanical and System Engineering, Kyoto Institute of Technology, Matsugasaki, Sakyo-ku, Kyoto-shi, Kyoto 606-8585, Japan

**Department of Applied Mathematics and Physics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto-shi, Kyoto 606-8501, Japan

Received:
March 5, 2011
Accepted:
July 15, 2011
Published:
October 20, 2011
Creative Commons License
Keywords:
combinatorial optimization, approximation algorithms, repetitive routing, grasp-and-delivery, intersection of matroids
Abstract
In this paper, we consider a routing problem for a single grasp-and-delivery robot used on a printed circuit (PC) board assembly line. The robot arranges n identical pins from their current configuration to the next required configuration by transferring them one by one in a transition. The n pins support a PC board from underneath to prevent it from overbending as an automated manipulator embeds electronic parts in the PC board from above. Each PC board has its own circuit pattern, and required configurations for PC boards all differ. Given an initial configuration of n pins and a sequence of m required configurations, the problem asks to find a transfer route of the robot that minimizes the route length over all m transitions. By applying a weighted matroid intersection algorithm, we show the repetitive routing problem to be 2-approximable in polynomial time.
Cite this article as:
Y. Karuno, H. Nagamochi, and A. Shurbevski, “An Approximation Algorithm with Factor Two for a Repetitive Routing Problem of Grasp-and-Delivery Robots,” J. Adv. Comput. Intell. Intell. Inform., Vol.15 No.8, pp. 1103-1108, 2011.
Data files:
References
  1. [1] A. Srivastav, H. Schroeter, and C. Michel, “Approximation algorithms for pick-and-place robots,” Annals of Operations Research, Vol.107, pp. 321-338, 2001.
  2. [2] M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, 1979.
  3. [3] M. S. Krishnamoorthy, “An NP-hard problem in bipartite graphs,” SIGACT News, Vol.7, p. 26, 1975.
  4. [4] A. Frank, “A weighted matroid intersection algorithm,” Journal of Algorithms, Vol.2, pp. 328-336, 1981.
  5. [5] V. V. Vazirani, “Approximation Algorithms,” Springer, 2001.
  6. [6] A. Baltz and A. Srivastav, “Approximation algorithms for the Euclidean bipartite TSP,” Operations Research Letters, Vol.33, pp. 403-410, 2005.
  7. [7] J. M. Aldous and R. J. Wilson, “Graphs and Applications: An Introductory Approach,” The Open University, Springer, 2000.
  8. [8] P. Chalasani and R. Motwani, “Approximating capacitated routing and delivery problems,” SIAM Journal on Computing, Vol.28, pp. 2133-2149, 1999.
  9. [9] B. Korte and J. Vygen, “Combinatorial Optimization: Theory and Algorithms, 3rd Edition,” Springer, 2005.
  10. [10] D. S. Johnson and C. H. Papadimitriou, “Performance guarantees for heuristics,” in: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys (Eds.), “The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,” Wiley, pp. 145-180, 1985.
  11. [11] Y. Karuno, H. Nagamochi, and A. Shurbevski, “Approximation algorithms for a cyclic routing problem of grasp-and-delivery robots,” Proceedings of Joint 5th Int. Conf. on Soft Computing and Intelligent Systems and 11th Int. Symposium on Advanced Intelligent Systems (SCIS & ISIS 2010), pp. 94-99, 2010.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 19, 2024