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

Sheng-I Chen*, Yen Che Tseng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


This study considers the path planning problem of picking lightemitting diodes on a silicon wafer. The ob jective 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 languageEnglish
Pages (from-to)2033-2047
Number of pages15
JournalJournal of Industrial and Management Optimization
Issue number3
StatePublished - May 2022


  • 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