# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2021055

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

 1 Department of Industrial Engineering and Management, National Yang Ming Chiao Tung Univeristy, Hsinchu, 30010, Taiwan 2 Department of Industrial Engineering and Management, National Chiao Tung University, Hsinchu, 30010, Taiwan

* Corresponding author: Sheng-I Chen

Received  October 2020 Revised  December 2020 Published  March 2021

Fund Project: The study is supported by MOST, Taiwan grant 109-2221-E-009-065-

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.

Citation: Sheng-I Chen, Yen-Che Tseng. A partitioning column approach for solving LED sorter manipulator path planning problems. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021055
##### References:

show all references

##### References:
The problem instances of LED distribution
The optimal path for the transformed graph
The example for partitioning columns
The worst case of discarded diodes
The coverage percentages of diodes in transformed graphs using different maximum mismatch ratios
Notations
 Mu The $y-position$ of the uppermost diode Ml The $y-position$ of the lowermost diode r The maximum mismatch ratio nx The number of LEDs at the $\textit{x-th}$ column $\theta$ The threshold of empty positions in the column $(\theta=\lceil\textit{nx}r\rceil)$ $\bar{b}$ The lower bound of the upper component (initialized as Mu) $\underline{b}$ The upper bound of the lower component (initialized as Ml) $\textbf{X}$ The collection of diode's $\textit{y-position}$ $\textbf{Y}$ The set of grades of diodes $\textbf{g}$ A function mapping $\textbf{X}$ into $\textbf{Y}$
 Mu The $y-position$ of the uppermost diode Ml The $y-position$ of the lowermost diode r The maximum mismatch ratio nx The number of LEDs at the $\textit{x-th}$ column $\theta$ The threshold of empty positions in the column $(\theta=\lceil\textit{nx}r\rceil)$ $\bar{b}$ The lower bound of the upper component (initialized as Mu) $\underline{b}$ The upper bound of the lower component (initialized as Ml) $\textbf{X}$ The collection of diode's $\textit{y-position}$ $\textbf{Y}$ The set of grades of diodes $\textbf{g}$ A function mapping $\textbf{X}$ into $\textbf{Y}$
The procedure to find component boundaries
 1.    Set $\bar{b} = i_{1} = M_{u}, \underline{b} = i_{2} = M_{1}, i = 0, \theta = \lceil n_{x} r \rceil$, and $d = True;$ 2.    If($M_{u}-M_{l}+1$)$-n_{x} >\theta$ 3.       While $i <\vert n_{x} \vert$ and $\theta > 0$ 4.          If $d = True$ then 5.             If $g(i_{1}) = g(i_{1}-1)$ then 6.                $\bar{b}:=i_{1}-1;$ 7.             Else 8.                $d = False;$ 9.                $\theta$ – –; 10.             End if 11.             $i{1}$ – –; 12.          Else 13.             If $g(i_{2})=g(i_{2}+1)$ then 14.                $\underline{b}:=i_{2}+1;$ 15.             Else 16.                $d = True;$ 17.                $\theta$ – –; 18.             End if 19.             $i_{2}++;$ 20.          End if 21.          $i++;$ 22.       End while 23.    End if
 1.    Set $\bar{b} = i_{1} = M_{u}, \underline{b} = i_{2} = M_{1}, i = 0, \theta = \lceil n_{x} r \rceil$, and $d = True;$ 2.    If($M_{u}-M_{l}+1$)$-n_{x} >\theta$ 3.       While $i <\vert n_{x} \vert$ and $\theta > 0$ 4.          If $d = True$ then 5.             If $g(i_{1}) = g(i_{1}-1)$ then 6.                $\bar{b}:=i_{1}-1;$ 7.             Else 8.                $d = False;$ 9.                $\theta$ – –; 10.             End if 11.             $i{1}$ – –; 12.          Else 13.             If $g(i_{2})=g(i_{2}+1)$ then 14.                $\underline{b}:=i_{2}+1;$ 15.             Else 16.                $d = True;$ 17.                $\theta$ – –; 18.             End if 19.             $i_{2}++;$ 20.          End if 21.          $i++;$ 22.       End while 23.    End if
The size of the original and transformed problems (maximum mismatch ratio = 0.3)
 Instance Original problem size Transformed problem size Reduction $\vert \boldsymbol{V} \vert$ $\vert \boldsymbol{E} \vert$ $\vert \boldsymbol{V_{r}} \vert$ $\vert \boldsymbol{E_{r}} \vert$ $1-\vert \boldsymbol{V_{r}} \vert / \vert \textbf{V} \vert$ $1-\vert \boldsymbol{E_{r}} \vert / \vert \textbf{E} \vert$ Grade1 48 2,256 30 870 38% 61% Grade2 74 5,402 108 11,556 -46% -114% Grade3 118 13,806 80 6,320 32% 54% Grade4 396 156,420 126 15,750 68% 90% Grade5 1,849 3,416,952 226 50,850 88% 99% Grade6 3,921 15,370,320 164 26,732 96% 100%
 Instance Original problem size Transformed problem size Reduction $\vert \boldsymbol{V} \vert$ $\vert \boldsymbol{E} \vert$ $\vert \boldsymbol{V_{r}} \vert$ $\vert \boldsymbol{E_{r}} \vert$ $1-\vert \boldsymbol{V_{r}} \vert / \vert \textbf{V} \vert$ $1-\vert \boldsymbol{E_{r}} \vert / \vert \textbf{E} \vert$ Grade1 48 2,256 30 870 38% 61% Grade2 74 5,402 108 11,556 -46% -114% Grade3 118 13,806 80 6,320 32% 54% Grade4 396 156,420 126 15,750 68% 90% Grade5 1,849 3,416,952 226 50,850 88% 99% Grade6 3,921 15,370,320 164 26,732 96% 100%
Vertex reduction percentages in transformed graphs using different mismatch ratios
 Instance $r=0.01$ $r=0.05$ $r=0.1$ $r=0.15$ $r=0.2$ $r=0.25$ $r=0.3$ $r=0.33$ $r=0.35$ $r=0.5$ $r=0.65$ Grade1 33% 33% 33% 38% 38% 38% 38% 38% 38% 38% 38% Grade2 -46% -46% -46% -46% -46% -46% -46% -46% -46% -46% -46% Grade3 32% 32% 32% 32% 32% 32% 32% 32% 32% 32% 32% Grade4 67% 67% 67% 67% 67% 68% 68% 68% 68% 68% 69% Grade5 87% 87% 87% 87% 88% 88% 88% 88% 88% 88% 88% Grade6 95% 96% 96% 96% 96% 96% 96% 96% 96% 96% 96%
 Instance $r=0.01$ $r=0.05$ $r=0.1$ $r=0.15$ $r=0.2$ $r=0.25$ $r=0.3$ $r=0.33$ $r=0.35$ $r=0.5$ $r=0.65$ Grade1 33% 33% 33% 38% 38% 38% 38% 38% 38% 38% 38% Grade2 -46% -46% -46% -46% -46% -46% -46% -46% -46% -46% -46% Grade3 32% 32% 32% 32% 32% 32% 32% 32% 32% 32% 32% Grade4 67% 67% 67% 67% 67% 68% 68% 68% 68% 68% 69% Grade5 87% 87% 87% 87% 88% 88% 88% 88% 88% 88% 88% Grade6 95% 96% 96% 96% 96% 96% 96% 96% 96% 96% 96%
Edge reduction percentages in transformed graphs using different maximum mismatch ratios
 Instance $r=0.01$ $r=0.05$ $r=0.1$ $r=0.15$ $r=0.2$ $r=0.25$ $r=0.3$ $r=0.33$ $r=0.35$ $r=0.5$ $r=0.65$ Grade1 55% 55% 55% 61% 61% 61% 61% 61% 61% 61% 61% Grade2 -114% -114% -114% -114% -114% -114% -114% -114% -114% -114% -114% Grade3 54% 54% 54% 54% 54% 54% 54% 54% 54% 54% 54% Grade4 89% 89% 89% 89% 89% 90% 90% 90% 90% 90% 90% Grade5 98% 98% 98% 98% 98% 98% 98% 99% 99% 99% 99% Grade6 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
 Instance $r=0.01$ $r=0.05$ $r=0.1$ $r=0.15$ $r=0.2$ $r=0.25$ $r=0.3$ $r=0.33$ $r=0.35$ $r=0.5$ $r=0.65$ Grade1 55% 55% 55% 61% 61% 61% 61% 61% 61% 61% 61% Grade2 -114% -114% -114% -114% -114% -114% -114% -114% -114% -114% -114% Grade3 54% 54% 54% 54% 54% 54% 54% 54% 54% 54% 54% Grade4 89% 89% 89% 89% 89% 90% 90% 90% 90% 90% 90% Grade5 98% 98% 98% 98% 98% 98% 98% 99% 99% 99% 99% Grade6 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
Computational results of solving the original and transformed problems
 Instance Partitioning column MTZ formulation Run time(s) Total cost MIPGap Run time(s) Total cost MIPGap Grade1 <1 227 0% 7,200 229 42% Grade2 14 386 0% 184 386 0% Grade3 8 393 0% 7,200 444 61% Grade4 78 660 0% $-$ $-$ $-$ Grade5 260 2,078 0% $-$ $-$ $-$ Grade6 6,356 4,205 0% $-$ $-$ $-$
 Instance Partitioning column MTZ formulation Run time(s) Total cost MIPGap Run time(s) Total cost MIPGap Grade1 <1 227 0% 7,200 229 42% Grade2 14 386 0% 184 386 0% Grade3 8 393 0% 7,200 444 61% Grade4 78 660 0% $-$ $-$ $-$ Grade5 260 2,078 0% $-$ $-$ $-$ Grade6 6,356 4,205 0% $-$ $-$ $-$
Comparing the performance of Concorde in solving problem instances with integral and fractional edge distances
 Instance Concord(with rounding to the nearest integer) Concorde(with four decimal place) Run time(s) Total cost Rounding Error % Run time(s) Total cost Grade1 <1 227 0% 1 227 Grade2 <1 386 0% 1 386 Grade3 1 393 0% 1 394 Grade4 5 582 4% 18 605 Grade5 $-$ $-$ $-$ $-$ $-$ Grade6 42 3,926 $-$ $-$ $-$
 Instance Concord(with rounding to the nearest integer) Concorde(with four decimal place) Run time(s) Total cost Rounding Error % Run time(s) Total cost Grade1 <1 227 0% 1 227 Grade2 <1 386 0% 1 386 Grade3 1 393 0% 1 394 Grade4 5 582 4% 18 605 Grade5 $-$ $-$ $-$ $-$ $-$ Grade6 42 3,926 $-$ $-$ $-$
The benchmark of Concorde and the proposed algorithm using Manhattan and Euclidean distances
 Instance Euclidean distance Manhattan distance Concorde Proposed algorithm Concorde Proposed algorithm Grade1 227 227 258 258 Grade2 386 386 462 462 Grade3 394 393 430 428 Grade4 605 660 692 742 Grade5 $-$ 2,078 $-$ 2,154 Grade6 $-$ 4,205 $-$ 4,286
 Instance Euclidean distance Manhattan distance Concorde Proposed algorithm Concorde Proposed algorithm Grade1 227 227 258 258 Grade2 386 386 462 462 Grade3 394 393 430 428 Grade4 605 660 692 742 Grade5 $-$ 2,078 $-$ 2,154 Grade6 $-$ 4,205 $-$ 4,286
 [1] Yi Gao, Rui Li, Yingjing Shi, Li Xiao. Design of path planning and tracking control of quadrotor. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021063 [2] Yongkun Wang, Fengshou He, Xiaobo Deng. Multi-aircraft cooperative path planning for maneuvering target detection. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021050 [3] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [4] Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058 [5] Jianli Xiang, Guozheng Yan. The uniqueness of the inverse elastic wave scattering problem based on the mixed reciprocity relation. Inverse Problems & Imaging, 2021, 15 (3) : 539-554. doi: 10.3934/ipi.2021004 [6] Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 [7] Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102 [8] Hsin-Lun Li. Mixed Hegselmann-Krause dynamics. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021084 [9] Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044 [10] Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973 [11] Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817 [12] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [13] Guo-Bao Zhang, Ruyun Ma, Xue-Shi Li. Traveling waves of a Lotka-Volterra strong competition system with nonlocal dispersal. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 587-608. doi: 10.3934/dcdsb.2018035 [14] Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189 [15] Yu Yang, Jinling Zhou, Cheng-Hsiung Hsu. Critical traveling wave solutions for a vaccination model with general incidence. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021087 [16] Chiun-Chuan Chen, Hung-Yu Chien, Chih-Chiang Huang. A variational approach to three-phase traveling waves for a gradient system. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021055 [17] Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045 [18] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [19] Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521 [20] Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055

2019 Impact Factor: 1.366

## Metrics

• HTML views (45)
• Cited by (0)

• on AIMS