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

Sheng-I Chen; Yen-Che Tseng

doi:10.3934/jimo.2021055

Article Contents

2022, Volume 18, Issue 3: 2033-2047. Doi: 10.3934/jimo.2021055

This issue Previous Article Nonlinear Grey Bernoulli model NGBM (1, 1)'s parameter optimisation method and model application Next Article The optimal pricing and service strategies of a dual-channel retailer under free riding

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

Sheng-I Chen^1,2, , and
Yen-Che Tseng^1,2,

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
^* Corresponding author: Sheng-I Chen

Received: October 2020

Revised: December 2020

Published: May 2022

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

Abstract Full Text(HTML) Figure(5) / Table(8) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 05A18, 05C45, 90B06, 90C11.

Citation:

Full Text(HTML)

Figure 1. The problem instances of LED distribution

Download: Full-size image PowerPoint slide

Figure 2. The optimal path for the transformed graph

Download: Full-size image PowerPoint slide

Figure 3. The example for partitioning columns

Download: Full-size image PowerPoint slide

Figure 4. The worst case of discarded diodes

Download: Full-size image PowerPoint slide

Figure 5. The coverage percentages of diodes in transformed graphs using different maximum mismatch ratios

Download: Full-size image PowerPoint slide

Table 1. Notations

M_u	The $ y-position $ of the uppermost diode
M_l	The $ y-position $ of the lowermost diode
r	The maximum mismatch ratio
n_x	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 M_u)
$ \underline{b} $	The upper bound of the lower component (initialized as M_l)
$ \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} $

| Show Table

DownLoad: CSV

Table 2. 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

| Show Table

DownLoad: CSV

Table 3. The size of the original and transformed problems (maximum mismatch ratio = 0.3)

Instance	Original problem size		Transformed problem size		Reduction
Instance	$ \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%

| Show Table

DownLoad: CSV

Table 4. 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%

| Show Table

DownLoad: CSV

Table 5. 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%

| Show Table

DownLoad: CSV

Table 6. Computational results of solving the original and transformed problems

Instance	Partitioning column			MTZ formulation
Instance	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%	$ - $	$ - $	$ - $

| Show Table

DownLoad: CSV

Table 7. 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	$ - $	$ - $	$ - $

| Show Table

DownLoad: CSV

Table 8. The benchmark of Concorde and the proposed algorithm using Manhattan and Euclidean distances

Instance	Euclidean distance		Manhattan distance
Instance	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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	D. Applegate, R. Bixby, V. Chvátal and W. Cook, Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems, Mathematical Programming, 97 (2003), 91-153. doi: 10.1007/s10107-003-0440-4.
[2]	S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Y. Wu, An optimal algorithm for approximate nearest neighbor searching, Journal of the ACM, 45 (1998), 891-923. doi: 10.1145/293347.293348.
[3]	N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report, 388, Graduate School of Industrial Administration, CMU, 1976.
[4]	N. Christofides, V. Campos, A. Corberan and E. Mota, An Algorithm for the Rural Postman Problem, , Imperical College, London, England, Tech. Report, 1981.
[5]	W. Cook, Concorde TSP solver, Available at: http://www.math.uwaterloo.ca/tsp/concorde/index.html. [Accessed on March 29, 2019], 2006.
[6]	A. Corberan and J. M. Sanchis, A polyhedral approach to therural postman problem, European Journal of Operational Research, 79 (1994), 95-114. doi: 10.1016/0377-2217(94)90398-0.
[7]	G. Cornuéjols, J. Fonlupt and D. Naddef, The traveling salesman problem on a graph and some related integer polyhedra, Mathematical Programming, 33 (1985), 1-27. doi: 10.1007/BF01582008.
[8]	H. Crowder and M. W. Padberg, Solving large-scale symmetric travelling salesman problems to optimality, Management Science, 26 (1980), 495-509. doi: 10.1287/mnsc.26.5.495.
[9]	M. Drexl, On the generalized directed rural postman problem, Journal of the Operational Research Society, 65 (2014), 1143-1154. doi: 10.1057/jors.2013.60.
[10]	M. Dror, Arc Routing: Theory, Solutions, and Applications, Kluwer, Boston, MA, 2000. doi: 10.1007/978-1-4615-4495-1.
[11]	H. A. Eiselt, M. Gendreau and G. Laporte, Arc routing problems, part Ⅱ: The rural postman problem, Operations Research, 43 (1995), 399-414. doi: 10.1287/opre.43.3.399.
[12]	J. Edmond and E. L. Johnson, Matching, Euler tour and the chinese postman problem, Mathematical Programming, 5 (1973), 88-124. doi: 10.1007/BF01580113.
[13]	E. Fernández, O. Meza, R. Garfinkel and M. Ortega, On the undirected rural postman problem: Tight bounds based on a new formulation, Operations Research, 51 (2003), 281-291. doi: 10.1287/opre.51.2.281.12790.
[14]	J. Fonlupt and A. Nachef, Dynamic programming and the graphical traveling salesman problem, Journal of the ACM (JACM), 40 (1993), 1165-1187. doi: 10.1145/174147.169803.
[15]	R. W. Folyd, Algorithm 97: Shortest path, Communications of the ACM, 5 (1962), 345. doi: 10.1145/367766.368168.
[16]	R. S. Garfinkel and I. R. Webb, On crossings, the crossing postman problem, and the rural postman problem, Networks: An International Journal, 34 (1999), 173-180. doi: 10.1002/(SICI)1097-0037(199910)34:3<173::AID-NET1>3.0.CO;2-W.
[17]	R. Kala, A. Shukla and R. Tiwari, Robotic path planning using evolutionary momentum-based exploration, Journal of Experimental and Theoretical Artificial Intelligence, 23 (2011), 469-495. doi: 10.1080/0952813X.2010.490963.
[18]	E. L. Lawler, J. K. Lenstra, A. R. Kan and D. B. Shmoys, The traveling salesman problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, Ltd., Chichester, 1985.
[19]	S. Lin and B. W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21 (1973), 498-516. doi: 10.1287/opre.21.2.498.
[20]	C. E. Miller, A. W. Tucker and R. A. Zemlin, Integer programming formulation of traveling salesman problems, Journal of the ACM, 7 (1960), 326-329. doi: 10.1145/321043.321046.
[21]	M. Padberg and G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, 33 (1991), 60-100. doi: 10.1137/1033004.
[22]	Rosenkrantz, Stearns, Lewis and II, An analysis of several heuristics for the traveling salesman problem, SIAM Journal on Computing, 6 (1977), 563-581. doi: 10.1137/0206041.
[23]	J. Sankaranarayanan, H. Samet and A. Varshney, A fast all nearest neighbor algorithm for applications involving large point-clouds, Computers and Graphics, 31 (2007), 157-174. doi: 10.1016/j.cag.2006.11.011.
[24]	W. Sheng, N. Xi, M. Song and Y. Chen, Robot path planning for dimensional measurement in automotive manufacturing, Journal of Manufacturing Science and Engineering, 127 (2005), 420-428. doi: 10.1115/1.1870013.
[25]	T. Wu, B. Li, L. Wang and Y. Huang, Study on path-optimization by grade sorting dies, In IEEE International Conference on Mechatronics and Automation, (2010), 876–880. doi: 10.1109/ICMA.2010.5589000.