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
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.
-  A. Srivastav, H. Schroeter, and C. Michel, “Approximation algorithms for pick-and-place robots,” Annals of Operations Research, Vol.107, pp. 321-338, 2001.
-  M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, 1979.
-  M. S. Krishnamoorthy, “An NP-hard problem in bipartite graphs,” SIGACT News, Vol.7, p. 26, 1975.
-  A. Frank, “A weighted matroid intersection algorithm,” Journal of Algorithms, Vol.2, pp. 328-336, 1981.
-  V. V. Vazirani, “Approximation Algorithms,” Springer, 2001.
-  A. Baltz and A. Srivastav, “Approximation algorithms for the Euclidean bipartite TSP,” Operations Research Letters, Vol.33, pp. 403-410, 2005.
-  J. M. Aldous and R. J. Wilson, “Graphs and Applications: An Introductory Approach,” The Open University, Springer, 2000.
-  P. Chalasani and R. Motwani, “Approximating capacitated routing and delivery problems,” SIAM Journal on Computing, Vol.28, pp. 2133-2149, 1999.
-  B. Korte and J. Vygen, “Combinatorial Optimization: Theory and Algorithms, 3rd Edition,” Springer, 2005.
-  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.
-  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.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.