A partitioning column approach for solving LED sorter manipulator path planning problems

Sheng-I Chen, Yen-Che Tseng

Research output: Contribution to journalArticlepeer-review


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.
Original languageAmerican English
Number of pages15
JournalJournal of Industrial and Management Optimization
StatePublished - 2021


  • Light-emitting diode sorter
  • Manipulator path planning
  • Mixed-integer programming
  • Rural postman problems
  • Traveling salesman problem


Dive into the research topics of 'A partitioning column approach for solving LED sorter manipulator path planning problems'. Together they form a unique fingerprint.

Cite this