Approximation algorithms for pick-and-place robots

Approximation algorithms for pick-and-place robots

0.00 Avg rating0 Votes
Article ID: iaor20023503
Country: Netherlands
Volume: 107
Issue: 1
Start Page Number: 321
End Page Number: 338
Publication Date: Oct 2001
Journal: Annals of Operations Research
Authors: , ,
Keywords: robots, matching
Abstract:

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 m 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 + ϵ. 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.

Reviews

Required fields are marked *. Your email address will not be published.