A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots

作者：Shurbevski Aleksandar^*; Karuno Yoshiyuki; Nagamochi Hiroshi

来源：Journal of Advanced Mechanical Design Systems and Manufacturing, 2012, 6(5): 611-621.

DOI：10.1299/jamdsm.6.611

• Combinatorial Optimization
• Routing and Scheduling
• Approximation Algorithms
• Performance Guarantee
• Empirical Performance
• Dynamic Programming

We consider a repetitive routing problem of a single grasp-and-delivery robot used on a printed circuit board (PCB) assembly line. The robot arranges n identical pins from their current configuration to the next required one by transferring at most one pin at a time. The pins support a PCB from underneath to prevent it from overbending, while an automated manipulator embeds electronic parts in the PCB from above. Given an initial configuration of 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. A polynomial time approximation algorithm with factor two has been proposed by the authors to the problem. In this paper, we design a dynamic programming (DP) procedure to improve its empirical performance, and also conduct numerical experiments to show how well the proposed DP procedure performs.

• 出版日期2012