.png){kind=icon}
返回
Approximation algorithms for pick-and-place robots
.png){kind=icon}
PRE
AI
DOI：10.1023/A:1014923704338.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper we study the problem of finding placement tours for pick-and-place robots, also known as the printed circuit board assembly problem with m positions on a board, n bins containing In components and n locations for the bins. In the standard model where the working time of the robot is proportional to the distances travelled, the general problem appears as a combination of the travelling salesman problem and the matching problem, and for m = n we have an Euclidean, bipartite travelling salesman problem. We give a polynomial-time algorithm which achieves an approximation guarantee of 3 + epsilon. An important special instance of the problem is the case of a fixed assignment of bins to bin-locations. This appears as a special case of a bipartite TSP satisfying the quadrangle inequality and given some fixed matching arcs. We obtain a 1.8 factor approximation with the stacker crane algorithm of Frederikson, Hecht and Kim. For the general bipartite case we also show a 2.0 factor approximation algorithm which is based on a new insertion technique for bipartite TSPs with quadrangle inequality. Implementations and experiments on real-world as well as random point configurations conclude this paper.
Keyword:
pick-and-place robots
printed circuit board assembly problem
approximation algorithms
bipartite travelling salesman problem
matching
combinatorial optimization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
