# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2021055
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## 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 Early access 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] René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 [2] Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 [3] Annegret Glitzky, Matthias Liero, Grigor Nika. Dimension reduction of thermistor models for large-area organic light-emitting diodes. Discrete & Continuous Dynamical Systems - S, 2021, 14 (11) : 3953-3971. doi: 10.3934/dcdss.2020460 [4] Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 [5] Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431 [6] Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial & Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179 [7] Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67 [8] Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020 [9] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [10] Matthias Gerdts, René Henrion, Dietmar Hömberg, Chantal Landry. Path planning and collision avoidance for robots. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 437-463. doi: 10.3934/naco.2012.2.437 [11] Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 [12] Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783 [13] Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128 [14] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [15] Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial & Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079 [16] 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 [17] Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497 [18] Poonam Savsani, Mohamed A. Tawhid. Discrete heat transfer search for solving travelling salesman problem. Mathematical Foundations of Computing, 2018, 1 (3) : 265-280. doi: 10.3934/mfc.2018012 [19] Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2783-2804. doi: 10.3934/jimo.2020094 [20] Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks & Heterogeneous Media, 2010, 5 (1) : 143-162. doi: 10.3934/nhm.2010.5.143

2020 Impact Factor: 1.801