Open AccessA partitioning column approach for solving LED sorter manipulator path planning problems
Author(s) -
Sheng-I Chen,
Yen-Che Tseng
Publication year - 2022
Publication title -
journal of industrial and management optimization
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.325
H-Index - 32
eISSN - 1553-166X
pISSN - 1547-5816
DOI - 10.3934/jimo.2021055
Subject(s) - traverse , solver , shortest path problem , computer science , mathematical optimization , integer programming , graph , path (computing) , motion planning , column generation , enhanced data rates for gsm evolution , benchmarking , column (typography) , mathematics , algorithm , theoretical computer science , robot , artificial intelligence , telecommunications , geodesy , marketing , frame (networking) , business , programming language , geography
This study considers the path planning problem of picking light-emitting diodes on a silicon wafer. The objective is to find the shortest walk for the sorter manipulator covering all nodes in a fully connected graph. We propose a partitioning column approach to reduce the original graph's size, where adjacent nodes at the same column are seen as a required edge, and the connection of vertices at different required edges is viewed as a non-required edge. The path planning problem turns to find the shortest closed walk to traverse required edges and is modeled as a rural postman problem with a solvable problem size. We formulate a mixed-integer program to obtain the exact solution for the transformed graph. We compare the proposed method with a TSP solver, Concorde. The result shows that our approach significantly reduces the problem size and obtains a near-optimal solution. For large problem instances, the proposed method can obtain a feasible solution in time, but not for the benchmarking solver.