American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Channel leadership and recycling channel in closed-loop supply chain: The case of recycling price by the recycling party
  • JIMO Home
  • This Issue
  • Next Article
    Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem
November  2021, 17(6): 3223-3246. doi: 10.3934/jimo.2020115

Tabu search guided by reinforcement learning for the max-mean dispersion problem

Dieudonné Nijimbere 1, , Songzheng Zhao 1, , Xunhao Gu 1, , Moses Olabhele Esangbedo 1,, and  Nyiribakwe Dominique 2,

1. 

School of Management, Northwestern Polytechnical University, 710072, Xi'an, China
2. 

Department of Computer science and Technology, Xidian University, 710071, Xi'an, China

* Corresponding author: Moses Olabhele Esangbedo

Received  May 2019 Revised  December 2019 Published  November 2021 Early access  June 2020

We present an effective hybrid metaheuristic of integrating reinforcement learning with a tabu-search (RLTS) algorithm for solving the max–mean dispersion problem. The innovative element is to design using a knowledge strategy from the $ Q $-learning mechanism to locate promising regions when the tabu search is stuck in a local optimum. Computational experiments on extensive benchmarks show that the RLTS performs much better than state-of-the-art algorithms in the literature. From a total of 100 benchmark instances, in 60 of them, which ranged from 500 to 1, 000, our proposed algorithm matched the currently best lower bounds for all instances. For the remaining 40 instances, the algorithm matched or outperformed. Furthermore, additional support was applied to present the effectiveness of the combined RL technique. The analysis sheds light on the effectiveness of the proposed RLTS algorithm.

Keywords: Hybrid metaheuristics algorithm, reinforcement learning, Q-learning algorithm, tabu search.
Mathematics Subject Classification: Primary: 65K05; Secondary: 90-08.
Citation: Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115
References:
[1]

R. Aringhieri, R. Cordone and A. Grosso, Construction and improvement algorithms for dispersion problems, European J. Oper. Res., 242 (2015), 21-33.  doi: 10.1016/j.ejor.2014.09.058.  Google Scholar

[2]

R. Aringhieri and R. Cordone, Comparing local search metaheuristics for the maximum diversity problem, J. Oper. Res. Soc., 62 (2011), 266-280.  doi: 10.1057/jors.2010.104.  Google Scholar

[3]

J. Boyan and A. W. Moore, Learning evaluation functions to improve optimization by local search, J. Machine Learning Research, 1 (2000), 77-112.  doi: 10.1162/15324430152733124.  Google Scholar

[4]

J. Brimberg, N. Mladenović, R. Todosijević and D. Urošević, Less is more: Solving the max-mean diversity problem with variable neighborhood search, Information Sciences, 382 (2017), 179-200.  doi: 10.1016/j.ins.2016.12.021.  Google Scholar

[5]

E. K. Burke, G. Kendall and E. Soubeiga, A tabu-search hyperheuristic for timetabling and rostering, J. Heuristics, 9 (2003), 451-470.  doi: 10.1023/B:HEUR.0000012446.94732.b6.  Google Scholar

[6]

R. Carrasco, A. Pham, M. Gallego, F. Gortázar, R. Martí and A. Duarte, Tabu search for the Max–Mean Dispersion Problem, Knowledge-Based Systems, 85 (2015), 256-264.  doi: 10.1016/j.knosys.2015.05.011.  Google Scholar

[7]

F. C. De Lima Júnior, A. D. D. Neto and J. D. De Melo, Hybrid metaheuristics using reinforcement learning applied to salesman traveling problem, in Traveling Salesman Problem, Theory and Applications, IntechOpen, 2010. doi: 10.5772/13343.  Google Scholar

[8]

F. Della Croce, M. Garraffa and F. Salassa, A hybrid heuristic approach based on a quadratic knapsack formulation for the max-mean dispersion problem, in Combinatorial Optimization, Lecture Notes in Comput. Sci., 8596, Springer, Cham, 2014,186–194. doi: 10.1007/978-3-319-09174-7_16.  Google Scholar

[9]

F. Della Croce, M. Garraffa and F. Salassa, A hybrid three-phase approach for the max-mean dispersion problem, Comput. Oper. Res., 71 (2016), 16-22.  doi: 10.1016/j.cor.2016.01.003.  Google Scholar

[10]

F. Della Croce, A. Grosso and M. Locatelli, A heuristic approach for the max-min diversity problem based on max-clique, Comput. Oper. Res., 36 (2009), 2429-2433.  doi: 10.1016/j.cor.2008.09.007.  Google Scholar

[11]

P. Galinier, Z. Boujbel and M. Coutinho Fernandes, An efficient memetic algorithm for the graph partitioning problem, Ann. Oper. Res., 191 (2011), 1-22.  doi: 10.1007/s10479-011-0983-3.  Google Scholar

[12]

M. Garraffa, F. Della Croce and F. Salassa, An exact semidefinite programming approach for the max-mean dispersion problem, J. Comb. Optim., 34 (2017), 71-93.  doi: 10.1007/s10878-016-0065-1.  Google Scholar

[13]

A. Gosavi, Reinforcement learning: A tutorial survey and recent advances, INFORMS J. Comput., 21 (2009), 178-192.  doi: 10.1287/ijoc.1080.0305.  Google Scholar

[14]

X. Lai, D. Yue, J.-K. Hao and F. Glover, Solution-based tabu search for the maximum min-sum dispersion problem, Inform. Sci., 441 (2018), 79-94.  doi: 10.1016/j.ins.2018.02.006.  Google Scholar

[15]

X. Lai and J. K. Hao, A tabu search based memetic algorithm for the max-mean dispersion problem, Comput. Oper. Res., 72 (2016), 118-127.  doi: 10.1016/j.cor.2016.02.016.  Google Scholar

[16]

P. Larranaga, A review on estimation of distribution algorithms, in Estimation of Distribution Algorithmn, Genetic Algorithms and Evolutionary Computation, 2, Springer, Boston, 2002, 57–100. doi: 10.1007/978-1-4615-1539-5_3.  Google Scholar

[17]

Z. Lu, F. Glover and J.-K. Hao, Neighborhood combination for unconstrained binary quadratic programming, MIC 2009: The VIII Metaheuristics International Conference, Hamburg, Germany, 2009. Google Scholar

[18]

R. Martí and F. Sandoya, GRASP and path relinking for the equitable dispersion problem, Comput. Oper. Res., 40 (2013), 3091-3099.  doi: 10.1016/j.cor.2012.04.005.  Google Scholar

[19]

V. V. Miagkikh and W. F. Punch, Global search in combinatorial optimization using reinforcement learning algorithms, Proceedings of the 1999 Congress on Evolutionary Computation-CEC99, Washington, DC, 1999. doi: 10.1109/CEC.1999.781925.  Google Scholar

[20]

D. Nijimbere, S. Zhao, H. Liu, B. Peng and A. Zhang, A hybrid metaheuristic of integrating estimation of distribution algorithm with tabu search for the max-mean dispersion problem, Math. Probl. Eng., 2019 (2019), 16pp. doi: 10.1155/2019/7104702.  Google Scholar

[21]

D. C. Porumbel, J.-K. Hao and F. Glover, A simple and effective algorithm for the MaxMin diversity problem, Ann. Oper. Res., 186 (2011), 275-293.  doi: 10.1007/s10479-011-0898-z.  Google Scholar

[22]

O. A. Prokopyev, N. Kong and and D. L. Martinez-Torres, The equitable dispersion problem, European J. Oper. Res., 197 (2009), 59-67.  doi: 10.1016/j.ejor.2008.06.005.  Google Scholar

[23]

A. P. Punnen, S. Taghipour, D. Karapetyan and B. Bhattacharyya, The quadratic balanced optimization problem, Discrete Optim., 12 (2014), 47-60.  doi: 10.1016/j.disopt.2014.01.001.  Google Scholar

[24]

I. Sghir, J. K. Hao, I. B. Jaafar and K. Ghédira, A multi-agent based optimization method applied to the quadratic assignment problem, Expert Systems Appl., 42 (2015), 9252-9262.  doi: 10.1016/j.eswa.2015.07.070.  Google Scholar

[25]

J. A. Torkestani and M. R. Meybodi, A cellular learning automata-based algorithm for solving the vertex coloring problem, Expert Systems Appl., 38 (2011), 9237-9247.  doi: 10.1016/j.eswa.2011.01.098.  Google Scholar

[26]

Y. Wang, Q. Wu and F. Glover, Effective metaheuristic algorithms for the minimum differential dispersion problem, European J. Oper. Res., 258 (2017), 829-843.  doi: 10.1016/j.ejor.2016.10.035.  Google Scholar

[27]

Y. Wang, J.-K. Hao, F. Glover and Z. Lü, A tabu search based memetic algorithm for the maximum diversity problem, Engineering Appl. Artificial Intell., 27 (2014), 103-114.  doi: 10.1016/j.engappai.2013.09.005.  Google Scholar

[28]

Y. Xu, D. Stern and H. Samulowitz, Learning adaptation to solve constraint satisfaction problems. Available from: https://www.microsoft.com/en-us/research/wp-content/uploads/2009/01/lion2009.pdf. Google Scholar

[29]

T. Yu and W.-G. Zhen, A multi-step $ Q(\lambda)$ learning approach to power system stabilizer, IFAC Proceedings Volumes, 43 (2010), 220-224.  doi: 10.3182/20100826-3-tr-4015.00042.  Google Scholar

[30]

Y. Zhou, J.-K. Hao and and B. Duval, Reinforcement learning based local search for grouping problems: A case study on graph coloring, Expert Systems Appl., 64 (2016), 412-422.  doi: 10.1016/j.eswa.2016.07.047.  Google Scholar

show all references

References:
[1]

R. Aringhieri, R. Cordone and A. Grosso, Construction and improvement algorithms for dispersion problems, European J. Oper. Res., 242 (2015), 21-33.  doi: 10.1016/j.ejor.2014.09.058.  Google Scholar

[2]

R. Aringhieri and R. Cordone, Comparing local search metaheuristics for the maximum diversity problem, J. Oper. Res. Soc., 62 (2011), 266-280.  doi: 10.1057/jors.2010.104.  Google Scholar

[3]

J. Boyan and A. W. Moore, Learning evaluation functions to improve optimization by local search, J. Machine Learning Research, 1 (2000), 77-112.  doi: 10.1162/15324430152733124.  Google Scholar

[4]

J. Brimberg, N. Mladenović, R. Todosijević and D. Urošević, Less is more: Solving the max-mean diversity problem with variable neighborhood search, Information Sciences, 382 (2017), 179-200.  doi: 10.1016/j.ins.2016.12.021.  Google Scholar

[5]

E. K. Burke, G. Kendall and E. Soubeiga, A tabu-search hyperheuristic for timetabling and rostering, J. Heuristics, 9 (2003), 451-470.  doi: 10.1023/B:HEUR.0000012446.94732.b6.  Google Scholar

[6]

R. Carrasco, A. Pham, M. Gallego, F. Gortázar, R. Martí and A. Duarte, Tabu search for the Max–Mean Dispersion Problem, Knowledge-Based Systems, 85 (2015), 256-264.  doi: 10.1016/j.knosys.2015.05.011.  Google Scholar

[7]

F. C. De Lima Júnior, A. D. D. Neto and J. D. De Melo, Hybrid metaheuristics using reinforcement learning applied to salesman traveling problem, in Traveling Salesman Problem, Theory and Applications, IntechOpen, 2010. doi: 10.5772/13343.  Google Scholar

[8]

F. Della Croce, M. Garraffa and F. Salassa, A hybrid heuristic approach based on a quadratic knapsack formulation for the max-mean dispersion problem, in Combinatorial Optimization, Lecture Notes in Comput. Sci., 8596, Springer, Cham, 2014,186–194. doi: 10.1007/978-3-319-09174-7_16.  Google Scholar

[9]

F. Della Croce, M. Garraffa and F. Salassa, A hybrid three-phase approach for the max-mean dispersion problem, Comput. Oper. Res., 71 (2016), 16-22.  doi: 10.1016/j.cor.2016.01.003.  Google Scholar

[10]

F. Della Croce, A. Grosso and M. Locatelli, A heuristic approach for the max-min diversity problem based on max-clique, Comput. Oper. Res., 36 (2009), 2429-2433.  doi: 10.1016/j.cor.2008.09.007.  Google Scholar

[11]

P. Galinier, Z. Boujbel and M. Coutinho Fernandes, An efficient memetic algorithm for the graph partitioning problem, Ann. Oper. Res., 191 (2011), 1-22.  doi: 10.1007/s10479-011-0983-3.  Google Scholar

[12]

M. Garraffa, F. Della Croce and F. Salassa, An exact semidefinite programming approach for the max-mean dispersion problem, J. Comb. Optim., 34 (2017), 71-93.  doi: 10.1007/s10878-016-0065-1.  Google Scholar

[13]

A. Gosavi, Reinforcement learning: A tutorial survey and recent advances, INFORMS J. Comput., 21 (2009), 178-192.  doi: 10.1287/ijoc.1080.0305.  Google Scholar

[14]

X. Lai, D. Yue, J.-K. Hao and F. Glover, Solution-based tabu search for the maximum min-sum dispersion problem, Inform. Sci., 441 (2018), 79-94.  doi: 10.1016/j.ins.2018.02.006.  Google Scholar

[15]

X. Lai and J. K. Hao, A tabu search based memetic algorithm for the max-mean dispersion problem, Comput. Oper. Res., 72 (2016), 118-127.  doi: 10.1016/j.cor.2016.02.016.  Google Scholar

[16]

P. Larranaga, A review on estimation of distribution algorithms, in Estimation of Distribution Algorithmn, Genetic Algorithms and Evolutionary Computation, 2, Springer, Boston, 2002, 57–100. doi: 10.1007/978-1-4615-1539-5_3.  Google Scholar

[17]

Z. Lu, F. Glover and J.-K. Hao, Neighborhood combination for unconstrained binary quadratic programming, MIC 2009: The VIII Metaheuristics International Conference, Hamburg, Germany, 2009. Google Scholar

[18]

R. Martí and F. Sandoya, GRASP and path relinking for the equitable dispersion problem, Comput. Oper. Res., 40 (2013), 3091-3099.  doi: 10.1016/j.cor.2012.04.005.  Google Scholar

[19]

V. V. Miagkikh and W. F. Punch, Global search in combinatorial optimization using reinforcement learning algorithms, Proceedings of the 1999 Congress on Evolutionary Computation-CEC99, Washington, DC, 1999. doi: 10.1109/CEC.1999.781925.  Google Scholar

[20]

D. Nijimbere, S. Zhao, H. Liu, B. Peng and A. Zhang, A hybrid metaheuristic of integrating estimation of distribution algorithm with tabu search for the max-mean dispersion problem, Math. Probl. Eng., 2019 (2019), 16pp. doi: 10.1155/2019/7104702.  Google Scholar

[21]

D. C. Porumbel, J.-K. Hao and F. Glover, A simple and effective algorithm for the MaxMin diversity problem, Ann. Oper. Res., 186 (2011), 275-293.  doi: 10.1007/s10479-011-0898-z.  Google Scholar

[22]

O. A. Prokopyev, N. Kong and and D. L. Martinez-Torres, The equitable dispersion problem, European J. Oper. Res., 197 (2009), 59-67.  doi: 10.1016/j.ejor.2008.06.005.  Google Scholar

[23]

A. P. Punnen, S. Taghipour, D. Karapetyan and B. Bhattacharyya, The quadratic balanced optimization problem, Discrete Optim., 12 (2014), 47-60.  doi: 10.1016/j.disopt.2014.01.001.  Google Scholar

[24]

I. Sghir, J. K. Hao, I. B. Jaafar and K. Ghédira, A multi-agent based optimization method applied to the quadratic assignment problem, Expert Systems Appl., 42 (2015), 9252-9262.  doi: 10.1016/j.eswa.2015.07.070.  Google Scholar

[25]

J. A. Torkestani and M. R. Meybodi, A cellular learning automata-based algorithm for solving the vertex coloring problem, Expert Systems Appl., 38 (2011), 9237-9247.  doi: 10.1016/j.eswa.2011.01.098.  Google Scholar

[26]

Y. Wang, Q. Wu and F. Glover, Effective metaheuristic algorithms for the minimum differential dispersion problem, European J. Oper. Res., 258 (2017), 829-843.  doi: 10.1016/j.ejor.2016.10.035.  Google Scholar

[27]

Y. Wang, J.-K. Hao, F. Glover and Z. Lü, A tabu search based memetic algorithm for the maximum diversity problem, Engineering Appl. Artificial Intell., 27 (2014), 103-114.  doi: 10.1016/j.engappai.2013.09.005.  Google Scholar

[28]

Y. Xu, D. Stern and H. Samulowitz, Learning adaptation to solve constraint satisfaction problems. Available from: https://www.microsoft.com/en-us/research/wp-content/uploads/2009/01/lion2009.pdf. Google Scholar

[29]

T. Yu and W.-G. Zhen, A multi-step $ Q(\lambda)$ learning approach to power system stabilizer, IFAC Proceedings Volumes, 43 (2010), 220-224.  doi: 10.3182/20100826-3-tr-4015.00042.  Google Scholar

[30]

Y. Zhou, J.-K. Hao and and B. Duval, Reinforcement learning based local search for grouping problems: A case study on graph coloring, Expert Systems Appl., 64 (2016), 412-422.  doi: 10.1016/j.eswa.2016.07.047.  Google Scholar

Figure 1.  Box diagrams of debugging data for greedy factor $\epsilon$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Box diagrams of debugging data for learning factor $\alpha$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Box diagrams of debugging data for discount factor rate $\gamma{}$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Effectiveness of the incorporated RLTS component in the proposed algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Computational results of reinforcement-learning tabu-search (RLTS) algorithm on 60 benchmark instances
Instance($ n $) GRASP-PR[18] HH[8] HHP[9] TP-TS[6] MAMMDP[15] EDA[16] RLTS
$ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $
MDPI1(500) 78.61 81.25 81.28 81.28 81.2770 81.2770 81.2770 81.2770 81.2770 81.2770
MDPI2(500) 76.87 77.45 77.79 77.60 78.6102 78.6102 78.6102 78.6102 78.6102 78.6102
MDPI3(500) 75.69 75.31 76.30 75.65 76.3008 76.3008 76.3008 76.3008 76.3008 76.3008
MDPI4(500) 81.81 82.28 82.33 81.47 82.3321 82.3321 82.3321 82.3321 82.3321 82.3321
MDPI5(500) 78.57 80.01 80.08 79.92 80.3540 80.3540 80.3540 80.3540 80.3540 80.3540
MDPI6(500) 79.64 81.12 81.25 79.93 81.2486 81.2486 81.2486 81.2486 81.2486 81.2486
MDPI7(500) 75.50 78.09 78.16 77.71 78.1645 78.1645 78.1645 78.1645 78.1645 78.1645
MDPI8(500) 76.98 79.01 79.06 78.70 79.1399 79.1399 79.1399 79.1399 79.1399 79.1399
MDPI9(500) 75.72 76.98 77.36 77.15 77.4210 77.4210 77.4210 77.4210 77.4210 77.4210
MDPI10(500) 80.38 81.24 81.25 81.02 81.3099 81.3099 81.3099 81.3099 81.3099 81.3099
MDPII1(500) 108.15 109.16 109.38 109.33 109.6101 109.6101 109.6101 109.6101 109.6101 109.6101
MDPII2(500) 103.29 105.06 105.33 104.81 105.7175 105.7175 105.7175 105.7175 105.7175 105.7175
MDPII3(500) 106.30 107.64 107.79 107.18 107.8217 107.8217 107.8217 107.8217 107.8217 107.8217
MDPII4(500) 104.62 105.37 106.10 105.69 106.1001 106.1001 106.1001 106.1001 106.1001 106.1001
MDPII5(500) 103.61 106.37 106.55 106.59 106.8572 106.8572 106.8572 106.8572 106.8572 106.8572
MDPII6(500) 104.81 105.52 105.77 106.17 106.2980 106.2980 106.2980 106.2980 106.2980 106.2980
MDPII7(500) 104.50 106.61 107.06 106.92 107.1494 107.1494 107.1494 107.1494 107.1494 107.1494
MDPII8(500) 100.02 103.41 103.78 103.49 103.7792 103.7792 103.7792 103.7792 103.7792 103.7792
MDPII9(500) 104.93 106.20 106.24 105.97 106.6198 106.6198 106.6198 106.6198 106.6198 106.6198
MDPII10(500) 103.50 103.79 104.15 103.56 104.6515 104.6515 104.6515 104.6515 104.6515 104.6515
MDPI1(750) – – – 95.86 96.6507 96.6507 96.6507 96.6507 96.6507 96.6507
MDPI2(750) – – – 97.42 97.5649 97.5649 97.5649 97.5649 97.5649 97.5649
MDPI3(750) – – – 96.97 97.7989 97.7989 97.7989 97.7989 97.7989 97.7989
MDPI4(750) – – – 95.21 96.0414 96.0414 96.0414 96.0414 96.0414 96.0414
MDPI5(750) – – – 96.65 96.7619 96.7619 96.7619 96.7619 96.7619 96.7619
MDPI6(750) – – – 99.25 99.8613 99.8613 99.8613 99.8613 99.8613 99.8613
MDPI7(750) – – – 96.26 96.5454 96.5454 96.5454 96.5454 96.5454 96.5454
MDPI8(750) – – – 96.46 96.7270 96.7270 96.7270 96.7270 96.7270 96.7270
MDPI9(750) – – – 96.78 98.0584 98.0584 98.0584 98.0584 98.0584 98.0584
MDPI10(750) – – – 99.85 100.0642 100.0642 100.0642 100.0642 100.0642 100.0642
MDPII1(750) – – – 127.69 128.8637 128.8637 128.8637 128.8637 128.8637 128.8637
MDPII2(750) – – – 130.79 130.9544 130.9544 130.9544 130.9544 130.9544 130.9544
MDPII3(750) – – – 129.40 129.7825 129.7825 129.7825 129.7825 129.7825 129.7825
MDPII4(750) – – – 125.68 126.5823 126.5823 126.5823 126.5823 126.5823 126.5823
MDPII5(750) – – – 128.13 129.1229 129.1229 129.1229 129.1229 129.1229 129.1229
MDPII6(750) – – – 128.55 129.0252 129.0252 129.0252 129.0252 129.0252 129.0252
MDPII7(750) – – – 124.91 125.6467 125.6467 125.6467 125.6467 125.6467 125.6467
MDPII8(750) – – – 130.66 130.9405 130.9405 130.9405 130.9405 130.9405 130.9405
MDPII9(750) – – – 128.89 128.8899 128.8899 128.8899 128.8899 128.8899 128.8899
MDPII10(750) – – – 132.99 133.2653 133.2653 133.2653 133.2653 133.2653 133.2653
MDPI1(1, 000) – – – 118.76 119.1741 119.1741 119.1741 119.1741 119.1741 119.1741
MDPI2(1, 000) – – – 113.22 113.5248 113.5248 113.5248 113.5248 113.5248 113.5248
MDPI3(1, 000) – – – 114.51 115.1386 115.1386 115.1386 115.1386 115.1386 115.1386
MDPI4(1, 000) – – – 110.53 111.1504 111.1504 111.1504 111.1504 111.1504 111.1504
MDPI5(1, 000) – – – 111.24 112.7232 112.7232 112.7232 112.7232 112.7232 112.7232
MDPI6(1, 000) – – – 112.08 113.1987 113.1987 113.1987 113.1987 113.1987 113.1987
MDPI7(1, 000) – – – 110.94 111.5555 111.5555 111.5555 111.5555 111.5555 111.5555
MDPI8(1, 000) – – – 110.29 111.2632 111.2632 111.2632 111.2632 111.2632 111.2632
MDPI9(1, 000) – – – 115.78 115.9588 115.9588 115.9588 115.9588 115.9588 115.9588
MDPI10(1, 000) – – – 114.29 114.7316 114.7316 114.7316 114.7316 114.7316 114.7316
MDPII1(1, 000) – – – 145.46 147.9362 147.9362 147.9362 147.9362 147.9362 147.9362
MDPII2(1, 000) – – – 150.49 151.3800 151.3800 151.3800 151.3800 151.3800 151.3800
MDPII3(1, 000) – – – 149.36 150.7882 150.7882 150.7882 150.7882 150.7882 150.7882
MDPII4(1, 000) – – – 147.91 149.1780 149.1780 149.1780 149.1780 149.1780 149.1780
MDPII5(1, 000) – – – 150.23 151.5208 151.5208 151.5208 151.5208 151.5208 151.5208
MDPII6(1, 000) – – – 147.29 148.3434 148.3434 148.3434 148.3434 148.3434 148.3434
MDPII7(1, 000) – – – 148.41 148.7424 148.7424 148.7424 148.7424 148.7424 148.7424
MDPII8(1, 000) – – – 145.87 147.8268 147.8268 147.8268 147.8268 147.8268 147.8268
MDPII9(1, 000) – – – 145.67 147.0839 147.0839 147.0839 147.0839 147.0839 147.0839
MDPII10(1, 000) – – – 148.40 150.0461 150.0461 150.0461 150.0461 150.0461 150.0461
Table Options

Download as excel

Instance($ n $) GRASP-PR[18] HH[8] HHP[9] TP-TS[6] MAMMDP[15] EDA[16] RLTS
$ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $
MDPI1(500) 78.61 81.25 81.28 81.28 81.2770 81.2770 81.2770 81.2770 81.2770 81.2770
MDPI2(500) 76.87 77.45 77.79 77.60 78.6102 78.6102 78.6102 78.6102 78.6102 78.6102
MDPI3(500) 75.69 75.31 76.30 75.65 76.3008 76.3008 76.3008 76.3008 76.3008 76.3008
MDPI4(500) 81.81 82.28 82.33 81.47 82.3321 82.3321 82.3321 82.3321 82.3321 82.3321
MDPI5(500) 78.57 80.01 80.08 79.92 80.3540 80.3540 80.3540 80.3540 80.3540 80.3540
MDPI6(500) 79.64 81.12 81.25 79.93 81.2486 81.2486 81.2486 81.2486 81.2486 81.2486
MDPI7(500) 75.50 78.09 78.16 77.71 78.1645 78.1645 78.1645 78.1645 78.1645 78.1645
MDPI8(500) 76.98 79.01 79.06 78.70 79.1399 79.1399 79.1399 79.1399 79.1399 79.1399
MDPI9(500) 75.72 76.98 77.36 77.15 77.4210 77.4210 77.4210 77.4210 77.4210 77.4210
MDPI10(500) 80.38 81.24 81.25 81.02 81.3099 81.3099 81.3099 81.3099 81.3099 81.3099
MDPII1(500) 108.15 109.16 109.38 109.33 109.6101 109.6101 109.6101 109.6101 109.6101 109.6101
MDPII2(500) 103.29 105.06 105.33 104.81 105.7175 105.7175 105.7175 105.7175 105.7175 105.7175
MDPII3(500) 106.30 107.64 107.79 107.18 107.8217 107.8217 107.8217 107.8217 107.8217 107.8217
MDPII4(500) 104.62 105.37 106.10 105.69 106.1001 106.1001 106.1001 106.1001 106.1001 106.1001
MDPII5(500) 103.61 106.37 106.55 106.59 106.8572 106.8572 106.8572 106.8572 106.8572 106.8572
MDPII6(500) 104.81 105.52 105.77 106.17 106.2980 106.2980 106.2980 106.2980 106.2980 106.2980
MDPII7(500) 104.50 106.61 107.06 106.92 107.1494 107.1494 107.1494 107.1494 107.1494 107.1494
MDPII8(500) 100.02 103.41 103.78 103.49 103.7792 103.7792 103.7792 103.7792 103.7792 103.7792
MDPII9(500) 104.93 106.20 106.24 105.97 106.6198 106.6198 106.6198 106.6198 106.6198 106.6198
MDPII10(500) 103.50 103.79 104.15 103.56 104.6515 104.6515 104.6515 104.6515 104.6515 104.6515
MDPI1(750) – – – 95.86 96.6507 96.6507 96.6507 96.6507 96.6507 96.6507
MDPI2(750) – – – 97.42 97.5649 97.5649 97.5649 97.5649 97.5649 97.5649
MDPI3(750) – – – 96.97 97.7989 97.7989 97.7989 97.7989 97.7989 97.7989
MDPI4(750) – – – 95.21 96.0414 96.0414 96.0414 96.0414 96.0414 96.0414
MDPI5(750) – – – 96.65 96.7619 96.7619 96.7619 96.7619 96.7619 96.7619
MDPI6(750) – – – 99.25 99.8613 99.8613 99.8613 99.8613 99.8613 99.8613
MDPI7(750) – – – 96.26 96.5454 96.5454 96.5454 96.5454 96.5454 96.5454
MDPI8(750) – – – 96.46 96.7270 96.7270 96.7270 96.7270 96.7270 96.7270
MDPI9(750) – – – 96.78 98.0584 98.0584 98.0584 98.0584 98.0584 98.0584
MDPI10(750) – – – 99.85 100.0642 100.0642 100.0642 100.0642 100.0642 100.0642
MDPII1(750) – – – 127.69 128.8637 128.8637 128.8637 128.8637 128.8637 128.8637
MDPII2(750) – – – 130.79 130.9544 130.9544 130.9544 130.9544 130.9544 130.9544
MDPII3(750) – – – 129.40 129.7825 129.7825 129.7825 129.7825 129.7825 129.7825
MDPII4(750) – – – 125.68 126.5823 126.5823 126.5823 126.5823 126.5823 126.5823
MDPII5(750) – – – 128.13 129.1229 129.1229 129.1229 129.1229 129.1229 129.1229
MDPII6(750) – – – 128.55 129.0252 129.0252 129.0252 129.0252 129.0252 129.0252
MDPII7(750) – – – 124.91 125.6467 125.6467 125.6467 125.6467 125.6467 125.6467
MDPII8(750) – – – 130.66 130.9405 130.9405 130.9405 130.9405 130.9405 130.9405
MDPII9(750) – – – 128.89 128.8899 128.8899 128.8899 128.8899 128.8899 128.8899
MDPII10(750) – – – 132.99 133.2653 133.2653 133.2653 133.2653 133.2653 133.2653
MDPI1(1, 000) – – – 118.76 119.1741 119.1741 119.1741 119.1741 119.1741 119.1741
MDPI2(1, 000) – – – 113.22 113.5248 113.5248 113.5248 113.5248 113.5248 113.5248
MDPI3(1, 000) – – – 114.51 115.1386 115.1386 115.1386 115.1386 115.1386 115.1386
MDPI4(1, 000) – – – 110.53 111.1504 111.1504 111.1504 111.1504 111.1504 111.1504
MDPI5(1, 000) – – – 111.24 112.7232 112.7232 112.7232 112.7232 112.7232 112.7232
MDPI6(1, 000) – – – 112.08 113.1987 113.1987 113.1987 113.1987 113.1987 113.1987
MDPI7(1, 000) – – – 110.94 111.5555 111.5555 111.5555 111.5555 111.5555 111.5555
MDPI8(1, 000) – – – 110.29 111.2632 111.2632 111.2632 111.2632 111.2632 111.2632
MDPI9(1, 000) – – – 115.78 115.9588 115.9588 115.9588 115.9588 115.9588 115.9588
MDPI10(1, 000) – – – 114.29 114.7316 114.7316 114.7316 114.7316 114.7316 114.7316
MDPII1(1, 000) – – – 145.46 147.9362 147.9362 147.9362 147.9362 147.9362 147.9362
MDPII2(1, 000) – – – 150.49 151.3800 151.3800 151.3800 151.3800 151.3800 151.3800
MDPII3(1, 000) – – – 149.36 150.7882 150.7882 150.7882 150.7882 150.7882 150.7882
MDPII4(1, 000) – – – 147.91 149.1780 149.1780 149.1780 149.1780 149.1780 149.1780
MDPII5(1, 000) – – – 150.23 151.5208 151.5208 151.5208 151.5208 151.5208 151.5208
MDPII6(1, 000) – – – 147.29 148.3434 148.3434 148.3434 148.3434 148.3434 148.3434
MDPII7(1, 000) – – – 148.41 148.7424 148.7424 148.7424 148.7424 148.7424 148.7424
MDPII8(1, 000) – – – 145.87 147.8268 147.8268 147.8268 147.8268 147.8268 147.8268
MDPII9(1, 000) – – – 145.67 147.0839 147.0839 147.0839 147.0839 147.0839 147.0839
MDPII10(1, 000) – – – 148.40 150.0461 150.0461 150.0461 150.0461 150.0461 150.0461
Table 2.  Computational results of RLTS algorithm on the 40 benchmark large instances with $n = 3, 000, 5, 000$. Each instance was independently solved 20 times, and results were compared to the TP-TS, MAMMDP, and EDA algorithms
Instance $ (n) $ TP-TS MAMMDP EDA RLTS
$ f_{best} $ $ f_{avg} $ $ time $ $ f_{best} $ $ f_{avg} $ time $f_{best} $ $ f_{avg} $ $ time $
MDPI1(3, 000) 188.0953 189.049 189.049 88.36 189.049 189.049 69.35 189.049 189.049 47.45
MDPI2(3, 000) 186.4730 187.3873 187.3873 60.71 187.3873 187.3873 53.64 187.3873 187.3873 66.65
MDPI3(3, 000) 184.3414 185.6668 185.6551 352.85 185.6668 185.6453 399.44 185.6668 185.6622 426.7
MDPI4(3, 000) 185.5882 186.1637 186.1536 300.37 186.1637 186.1637 240.45 186.1637 186.1637 137.8
MDPI5(3, 000) 186.2349 187.5455 187.5455 61.29 187.5455 187.5455 94.16 187.5455 187.5455 54.23
MDPI6(3, 000) 189.0935 189.4313 189.4313 51.99 189.4313 189.4313 48.21 189.4313 189.4313 23.15
MDPI7(3, 000) 187.4512 188.2426 188.2426 86.57 188.2426 188.2426 120.95 188.2426 188.2426 65.45
MDPI8(3, 000) 185.7358 186.7968 186.7968 48.04 186.7968 186.7968 38.7 186.7968 186.7968 31.2
MDPI9(3, 000) 187.1076 188.2313 188.2313 151.78 188.2313 188.2313 82.66 188.2313 188.2313 47.25
MDPI10(3, 000) 184.6866 185.6825 185.6238 228.72 185.6825 185.6719 510.41 185.6825 185.6822 467.1
MDPII1(3, 000) 252.1818 252.3204 252.3204 59.7 252.3204 252.3204 42.42 252.3204 252.3204 51.2
MDPII2(3, 000) 248.6972 250.0621 250.0621 220.1 250.0621 250.0617 248.1 250.0621 250.0576 514.4
MDPII3(3, 000) 250.5303 251.9063 251.9063 146.32 251.9063 251.9063 139.36 251.9063 251.9063 78.1
MDPII4(3, 000) 253.0963 253.941 253.9406 370.76 253.941 253.9406 352.17 253.941 253.941 184.05
MDPII5(3, 000) 252.5621 253.2604 253.2604 374 253.2604 253.2603 308.8 253.2604 253.2608 344.15
MDPII6(3, 000) 249.7160 250.6778 250.6778 55.35 250.6778 250.6778 55.9 250.6778 250.6778 37.25
MDPII7(3, 000) 249.5939 251.1344 251.1344 74.72 251.1344 251.1344 88.61 251.1344 251.1344 59.85
MDPII8(3, 000) 252.0565 252.9996 252.9996 79.82 252.9996 252.9996 123.56 252.9996 252.9996 61.72
MDPII9(3, 000) 251.3625 252.4258 252.4258 90.27 252.4258 252.4258 58.5 252.4258 252.4258 94.4
MDPII10(3, 000) 251.1169 252.3966 252.3966 13.18 252.3966 252.3966 8.73 252.3966 252.3966 12.02
MDPI1(5, 000) 236.3332 4395.321 4395.24 2914.9 4395.321 4395.288 3084.12 4395.321 4395.312 2804.12
MDPI2(5, 000) 239.0143 219.7661 219.762 145.745 219.7661 219.7644 154.206 219.7661 219.7656 140.206
MDPI3(5, 000) 238.4742 240.1625 240.1029 312.13 240.1625 240.0434 905.58 240.1625 240.0519 1061.45
MDPI4(5, 000) 237.3972 241.8274 241.793 1244.36 241.8274 241.768 958.6 241.8274 241.7649 1046.76
MDPI5(5, 000) 240.0439 240.8908 240.8882 810.48 240.8908 240.8494 992.57 240.8908 240.8518 1040.85
MDPI6(5, 000) 238.0015 240.9972 240.9768 653.64 240.9972 240.9281 1240.33 240.9925 240.9129 910.6
MDPI7(5, 000) 239.7444 242.4801 242.4759 735.16 242.4801 242.4419 1104.64 242.4801 242.4593 895.02
MDPI8(5, 000) 237.9150 240.3229 240.3063 976.02 240.376 240.2726 992.36 240.376 240.2698 1072.8
MDPI9(5, 000) 235.9103 242.8149 242.775 259.5 242.8201 242.7624 965.79 242.8201 242.7778 1036.81
MDPI10(5, 000) 241.8043 241.195 241.1618 1148.6 241.195 241.1291 909.39 241.195 241.134 1036.05
MDPII1(5, 000) 316.7478 239.7606 239.6676 1219.71 239.7606 239.5363 1001.4 239.7606 239.6131 1441.87
MDPII2(5, 000) 323.6829 243.4737 243.373 457.28 243.4737 243.3442 981.99 243.4737 243.3673 758.61
MDPII3(5, 000) 321.9291 322.2359 322.1813 1519.05 322.2359 322.1594 1114.21 322.2359 322.1691 1089.2
MDPII4(5, 000) 317.6767 327.3019 327.0063 1103.13 327.3019 327.1024 731.65 327.3019 327.2153 858.95
MDPII5(5, 000) 317.7479 324.8135 324.8016 955.81 324.8135 324.777 1043.24 324.8135 324.7917 1039.47
MDPII6(5, 000) 319.3890 322.2376 322.1973 664.1 322.2277 322.1171 1059.47 322.2376 322.1448 1106.05
MDPII7(5, 000) 319.9806 322.4912 322.3807 1014.9 322.5012 322.3717 971.06 322.5012 322.3647 1151.2
MDPII8(5, 000) 318.8545 322.9505 322.7039 352.88 322.9505 322.6878 1405.72 322.9505 322.7466 937.45
MDPII9(5, 000) 320.4376 322.8504 322.7931 714.31 322.8504 322.7615 1164.19 322.8504 322.8136 1052.93
MDPII10(5, 000) 320.8530 323.1121 323.0533 879.48 323.1121 322.8815 1168.86 323.1121 322.8943 1015.75
Table Options

Download as excel

Instance $ (n) $ TP-TS MAMMDP EDA RLTS
$ f_{best} $ $ f_{avg} $ $ time $ $ f_{best} $ $ f_{avg} $ time $f_{best} $ $ f_{avg} $ $ time $
MDPI1(3, 000) 188.0953 189.049 189.049 88.36 189.049 189.049 69.35 189.049 189.049 47.45
MDPI2(3, 000) 186.4730 187.3873 187.3873 60.71 187.3873 187.3873 53.64 187.3873 187.3873 66.65
MDPI3(3, 000) 184.3414 185.6668 185.6551 352.85 185.6668 185.6453 399.44 185.6668 185.6622 426.7
MDPI4(3, 000) 185.5882 186.1637 186.1536 300.37 186.1637 186.1637 240.45 186.1637 186.1637 137.8
MDPI5(3, 000) 186.2349 187.5455 187.5455 61.29 187.5455 187.5455 94.16 187.5455 187.5455 54.23
MDPI6(3, 000) 189.0935 189.4313 189.4313 51.99 189.4313 189.4313 48.21 189.4313 189.4313 23.15
MDPI7(3, 000) 187.4512 188.2426 188.2426 86.57 188.2426 188.2426 120.95 188.2426 188.2426 65.45
MDPI8(3, 000) 185.7358 186.7968 186.7968 48.04 186.7968 186.7968 38.7 186.7968 186.7968 31.2
MDPI9(3, 000) 187.1076 188.2313 188.2313 151.78 188.2313 188.2313 82.66 188.2313 188.2313 47.25
MDPI10(3, 000) 184.6866 185.6825 185.6238 228.72 185.6825 185.6719 510.41 185.6825 185.6822 467.1
MDPII1(3, 000) 252.1818 252.3204 252.3204 59.7 252.3204 252.3204 42.42 252.3204 252.3204 51.2
MDPII2(3, 000) 248.6972 250.0621 250.0621 220.1 250.0621 250.0617 248.1 250.0621 250.0576 514.4
MDPII3(3, 000) 250.5303 251.9063 251.9063 146.32 251.9063 251.9063 139.36 251.9063 251.9063 78.1
MDPII4(3, 000) 253.0963 253.941 253.9406 370.76 253.941 253.9406 352.17 253.941 253.941 184.05
MDPII5(3, 000) 252.5621 253.2604 253.2604 374 253.2604 253.2603 308.8 253.2604 253.2608 344.15
MDPII6(3, 000) 249.7160 250.6778 250.6778 55.35 250.6778 250.6778 55.9 250.6778 250.6778 37.25
MDPII7(3, 000) 249.5939 251.1344 251.1344 74.72 251.1344 251.1344 88.61 251.1344 251.1344 59.85
MDPII8(3, 000) 252.0565 252.9996 252.9996 79.82 252.9996 252.9996 123.56 252.9996 252.9996 61.72
MDPII9(3, 000) 251.3625 252.4258 252.4258 90.27 252.4258 252.4258 58.5 252.4258 252.4258 94.4
MDPII10(3, 000) 251.1169 252.3966 252.3966 13.18 252.3966 252.3966 8.73 252.3966 252.3966 12.02
MDPI1(5, 000) 236.3332 4395.321 4395.24 2914.9 4395.321 4395.288 3084.12 4395.321 4395.312 2804.12
MDPI2(5, 000) 239.0143 219.7661 219.762 145.745 219.7661 219.7644 154.206 219.7661 219.7656 140.206
MDPI3(5, 000) 238.4742 240.1625 240.1029 312.13 240.1625 240.0434 905.58 240.1625 240.0519 1061.45
MDPI4(5, 000) 237.3972 241.8274 241.793 1244.36 241.8274 241.768 958.6 241.8274 241.7649 1046.76
MDPI5(5, 000) 240.0439 240.8908 240.8882 810.48 240.8908 240.8494 992.57 240.8908 240.8518 1040.85
MDPI6(5, 000) 238.0015 240.9972 240.9768 653.64 240.9972 240.9281 1240.33 240.9925 240.9129 910.6
MDPI7(5, 000) 239.7444 242.4801 242.4759 735.16 242.4801 242.4419 1104.64 242.4801 242.4593 895.02
MDPI8(5, 000) 237.9150 240.3229 240.3063 976.02 240.376 240.2726 992.36 240.376 240.2698 1072.8
MDPI9(5, 000) 235.9103 242.8149 242.775 259.5 242.8201 242.7624 965.79 242.8201 242.7778 1036.81
MDPI10(5, 000) 241.8043 241.195 241.1618 1148.6 241.195 241.1291 909.39 241.195 241.134 1036.05
MDPII1(5, 000) 316.7478 239.7606 239.6676 1219.71 239.7606 239.5363 1001.4 239.7606 239.6131 1441.87
MDPII2(5, 000) 323.6829 243.4737 243.373 457.28 243.4737 243.3442 981.99 243.4737 243.3673 758.61
MDPII3(5, 000) 321.9291 322.2359 322.1813 1519.05 322.2359 322.1594 1114.21 322.2359 322.1691 1089.2
MDPII4(5, 000) 317.6767 327.3019 327.0063 1103.13 327.3019 327.1024 731.65 327.3019 327.2153 858.95
MDPII5(5, 000) 317.7479 324.8135 324.8016 955.81 324.8135 324.777 1043.24 324.8135 324.7917 1039.47
MDPII6(5, 000) 319.3890 322.2376 322.1973 664.1 322.2277 322.1171 1059.47 322.2376 322.1448 1106.05
MDPII7(5, 000) 319.9806 322.4912 322.3807 1014.9 322.5012 322.3717 971.06 322.5012 322.3647 1151.2
MDPII8(5, 000) 318.8545 322.9505 322.7039 352.88 322.9505 322.6878 1405.72 322.9505 322.7466 937.45
MDPII9(5, 000) 320.4376 322.8504 322.7931 714.31 322.8504 322.7615 1164.19 322.8504 322.8136 1052.93
MDPII10(5, 000) 320.8530 323.1121 323.0533 879.48 323.1121 322.8815 1168.86 323.1121 322.8943 1015.75
Table 3.  Parameters of $\epsilon$, $\alpha$, and $\gamma$
Names Range Debugging Intervals Final values
Greedy factor [0.5, 1) 0.05 0.7
Learning factor (0, 1) 0.1 0.5
Discount factor [0, 1) 0.1 0.5
Table Options

Download as excel

Names Range Debugging Intervals Final values
Greedy factor [0.5, 1) 0.05 0.7
Learning factor (0, 1) 0.1 0.5
Discount factor [0, 1) 0.1 0.5
Table 4.  Debugging results for factor $\epsilon$
Instances ($ n $) / $ \epsilon $ 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95
MDPI1(5, 000) -0.122851 -0.081087 -0.130172 -0.128802 -0.056058 -0.129919 -0.041805 -0.155847 -0.044694 -0.105110
MDPI2(5, 000) -0.041683 -0.044909 -0.042706 -0.031403 -0.032596 -0.058119 -0.012692 -0.060083 -0.056580 -0.054879
MDPI3(5, 000) -0.067597 -0.050908 -0.053767 -0.106229 -0.068687 -0.076957 -0.105697 -0.085361 -0.115044 -0.051265
MDPI4(5, 000) -0.133373 -0.042282 -0.115774 -0.091527 -0.064438 -0.134837 -0.063109 -0.100193 -0.061781 -0.071073
MDPI5(5, 000) -0.042153 -0.058244 -0.073869 -0.027768 -0.041856 -0.064060 -0.072030 -0.051006 -0.032583 -0.059985
MDPI6(5, 000) -0.040458 -0.030610 -0.054468 -0.079938 -0.042002 -0.093500 -0.018872 -0.071949 -0.053420 -0.030553
MDPI7(5, 000) -0.007039 -0.040785 -0.022835 -0.025523 -0.011432 -0.022520 -0.000364 -0.015116 0.004182 -0.010404
MDPI8(5, 000) -0.048888 -0.064965 -0.040440 -0.050873 -0.058277 -0.058174 -0.040082 -0.054745 -0.050569 -0.078426
MDPI9(5, 000) -0.129854 -0.078371 -0.117872 -0.097018 -0.076916 -0.176947 -0.060925 -0.175825 -0.084588 -0.097384
MDPI10(5, 000) -0.033717 -0.043167 -0.010259 -0.039291 -0.035665 -0.062412 -0.042826 -0.063820 -0.018992 -0.030091
MDPII1(5, 000) -0.005740 -0.033777 -0.059031 -0.047182 -0.044300 -0.066763 -0.060716 -0.031978 -0.014357 -0.039396
MDPII2(5, 000) 0.147624 0.167856 0.178805 0.132264 0.164916 0.118441 0.083772 0.211362 0.147558 0.088298
MDPII3(5, 000) -0.023621 -0.023856 -0.045420 -0.022302 -0.009195 -0.030358 -0.013416 -0.023812 -0.027812 -0.027001
MDPII4(5, 000) -0.166333 -0.094202 -0.120204 -0.096423 -0.085864 -0.121264 -0.120666 -0.188106 -0.240823 -0.147536
MDPII5(5, 000) -0.075976 -0.096680 -0.044135 -0.004540 -0.033960 -0.043347 -0.077273 -0.032238 -0.036416 -0.031091
MDPII6(5, 000) -0.017563 0.058637 0.005761 -0.098428 -0.080234 0.015629 -0.008452 0.021738 0.033528 -0.012549
MDPII7(5, 000) -0.015845 -0.074944 -0.060637 -0.081458 -0.021804 -0.056874 -0.053205 -0.017029 -0.017963 -0.067988
MDPII8(5, 000) -0.178216 -0.143775 -0.177740 -0.229257 -0.176900 -0.163983 -0.205498 -0.172191 -0.244947 -0.188872
MDPII9(5, 000) 0.014833 -0.094614 -0.111384 -0.118775 0.068232 -0.047735 -0.119738 -0.069007 -0.124918 -0.130199
MDPII10(5, 000) 0.017633 -0.048853 -0.107008 -0.162074 0.012272 -0.128291 0.050908 0.021277 0.044312 -0.082684
Debugging results for factors $ \alpha $ and $ \gamma $ were omitted.
Table Options

Download as excel

Instances ($ n $) / $ \epsilon $ 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95
MDPI1(5, 000) -0.122851 -0.081087 -0.130172 -0.128802 -0.056058 -0.129919 -0.041805 -0.155847 -0.044694 -0.105110
MDPI2(5, 000) -0.041683 -0.044909 -0.042706 -0.031403 -0.032596 -0.058119 -0.012692 -0.060083 -0.056580 -0.054879
MDPI3(5, 000) -0.067597 -0.050908 -0.053767 -0.106229 -0.068687 -0.076957 -0.105697 -0.085361 -0.115044 -0.051265
MDPI4(5, 000) -0.133373 -0.042282 -0.115774 -0.091527 -0.064438 -0.134837 -0.063109 -0.100193 -0.061781 -0.071073
MDPI5(5, 000) -0.042153 -0.058244 -0.073869 -0.027768 -0.041856 -0.064060 -0.072030 -0.051006 -0.032583 -0.059985
MDPI6(5, 000) -0.040458 -0.030610 -0.054468 -0.079938 -0.042002 -0.093500 -0.018872 -0.071949 -0.053420 -0.030553
MDPI7(5, 000) -0.007039 -0.040785 -0.022835 -0.025523 -0.011432 -0.022520 -0.000364 -0.015116 0.004182 -0.010404
MDPI8(5, 000) -0.048888 -0.064965 -0.040440 -0.050873 -0.058277 -0.058174 -0.040082 -0.054745 -0.050569 -0.078426
MDPI9(5, 000) -0.129854 -0.078371 -0.117872 -0.097018 -0.076916 -0.176947 -0.060925 -0.175825 -0.084588 -0.097384
MDPI10(5, 000) -0.033717 -0.043167 -0.010259 -0.039291 -0.035665 -0.062412 -0.042826 -0.063820 -0.018992 -0.030091
MDPII1(5, 000) -0.005740 -0.033777 -0.059031 -0.047182 -0.044300 -0.066763 -0.060716 -0.031978 -0.014357 -0.039396
MDPII2(5, 000) 0.147624 0.167856 0.178805 0.132264 0.164916 0.118441 0.083772 0.211362 0.147558 0.088298
MDPII3(5, 000) -0.023621 -0.023856 -0.045420 -0.022302 -0.009195 -0.030358 -0.013416 -0.023812 -0.027812 -0.027001
MDPII4(5, 000) -0.166333 -0.094202 -0.120204 -0.096423 -0.085864 -0.121264 -0.120666 -0.188106 -0.240823 -0.147536
MDPII5(5, 000) -0.075976 -0.096680 -0.044135 -0.004540 -0.033960 -0.043347 -0.077273 -0.032238 -0.036416 -0.031091
MDPII6(5, 000) -0.017563 0.058637 0.005761 -0.098428 -0.080234 0.015629 -0.008452 0.021738 0.033528 -0.012549
MDPII7(5, 000) -0.015845 -0.074944 -0.060637 -0.081458 -0.021804 -0.056874 -0.053205 -0.017029 -0.017963 -0.067988
MDPII8(5, 000) -0.178216 -0.143775 -0.177740 -0.229257 -0.176900 -0.163983 -0.205498 -0.172191 -0.244947 -0.188872
MDPII9(5, 000) 0.014833 -0.094614 -0.111384 -0.118775 0.068232 -0.047735 -0.119738 -0.069007 -0.124918 -0.130199
MDPII10(5, 000) 0.017633 -0.048853 -0.107008 -0.162074 0.012272 -0.128291 0.050908 0.021277 0.044312 -0.082684
Debugging results for factors $ \alpha $ and $ \gamma $ were omitted.
Table 5.  Friedman test results for three parameters
$\epsilon~$ Mean Rank $\alpha~$ Mean Rank $\gamma~$ Mean Rank
$\epsilon~$0.5 6.2 $\alpha~$0.1 3.8 $\gamma~$0 4.2
$\epsilon~$0.55 6.1 $\alpha~$0.2 5.05 $\gamma~$0.1 4.15
$\epsilon~$0.6 4.9 $\alpha~$0.3 4.6 $\gamma~$0.2 4.7
$\epsilon~$0.65 4.7 $\alpha~$0.4 4.25 $\gamma~$0.3 5.6
$\epsilon~$0.7 6.9 $\alpha~$0.5 6.45 $\gamma~$0.4 5.4
$\epsilon~$0.75 3.65 $\alpha~$0.6 4.95 $\gamma~$0.5 7.15
$\epsilon~$0.8 6.15 $\alpha~$0.7 4.85 $\gamma~$0.6 5.75
$\epsilon~$0.85 5.3 $\alpha~$0.8 5.95 $\gamma~$0.7 5.85
$\epsilon~$0.9 6.1 $\alpha~$0.9 5.1 $\gamma~$0.8 6.3
$\epsilon~$0.95 5 $\gamma~$0.9 5.9
$ N $ 20 $ N $ 20 $ N $ 20
Chi-Square 18.12 Chi-Square 13.88 Chi-Square 17.193
$ df $ 9 $ df $ 8 $ df $ 9
Asymp. Sig 0.034 Asymp. Sig. 0.085 Asymp. Sig. 0.46
Table Options

Download as excel

$\epsilon~$ Mean Rank $\alpha~$ Mean Rank $\gamma~$ Mean Rank
$\epsilon~$0.5 6.2 $\alpha~$0.1 3.8 $\gamma~$0 4.2
$\epsilon~$0.55 6.1 $\alpha~$0.2 5.05 $\gamma~$0.1 4.15
$\epsilon~$0.6 4.9 $\alpha~$0.3 4.6 $\gamma~$0.2 4.7
$\epsilon~$0.65 4.7 $\alpha~$0.4 4.25 $\gamma~$0.3 5.6
$\epsilon~$0.7 6.9 $\alpha~$0.5 6.45 $\gamma~$0.4 5.4
$\epsilon~$0.75 3.65 $\alpha~$0.6 4.95 $\gamma~$0.5 7.15
$\epsilon~$0.8 6.15 $\alpha~$0.7 4.85 $\gamma~$0.6 5.75
$\epsilon~$0.85 5.3 $\alpha~$0.8 5.95 $\gamma~$0.7 5.85
$\epsilon~$0.9 6.1 $\alpha~$0.9 5.1 $\gamma~$0.8 6.3
$\epsilon~$0.95 5 $\gamma~$0.9 5.9
$ N $ 20 $ N $ 20 $ N $ 20
Chi-Square 18.12 Chi-Square 13.88 Chi-Square 17.193
$ df $ 9 $ df $ 8 $ df $ 9
Asymp. Sig 0.034 Asymp. Sig. 0.085 Asymp. Sig. 0.46
Table 6.  Comparison between multistart tabu-search (MTS) method and the proposed RLTS algorithm on the set of 40 large instances within ≥ 3, 000. Each instance was independently solved 20 times by the two algorithms
Instance $ (n) $ MTS RLTS
$ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $
MDPI1(3, 000) 189.04897 189.04897 189.04897 189.04897
MDPI2(3, 000) 187.38729 187.38729 187.38729 187.38729
MDPI3(3, 000) 185.66681 185.65159 185.66681 185.6594
MDPI4(3, 000) 186.16373 186.16373 186.16373 186.16373
MDPI5(3, 000) 187.54552 187.54552 187.54552 187.54552
MDPI6(3, 000) 189.43126 189.43126 189.43126 189.43126
MDPI7(3, 000) 188.24258 188.24258 188.24258 188.24258
MDPI8(3, 000) 186.79681 186.79681 186.79681 186.79681
MDPI9(3, 000) 188.23126 188.23126 188.23126 188.23126
MDPI10(3, 000) 185.68251 185.67237 185.68251 185.6747
MDPII1(3, 000) 252.32043 252.32043 252.32043 252.32043
MDPII2(3, 000) 250.06214 250.05474 250.06214 250.0569
MDPII3(3, 000) 251.90627 251.90627 251.90627 251.90627
MDPII4(3, 000) 253.94101 253.93968 253.94101 253.941
MDPII5(3, 000) 253.26042 253.26016 253.26042 253.2604
MDPII6(3, 000) 250.67775 250.67775 250.67775 250.67775
MDPII7(3, 000) 251.13441 251.13441 251.13441 251.13441
MDPII8(3, 000) 252.99965 252.99965 252.99965 252.99965
MDPII9(3, 000) 252.42577 252.42577 252.42577 252.42577
MDPII10(3, 000) 252.39659 252.39659 252.39659 252.39659
MDPI1(5, 000) 240.14121 240.0212 240.1594 240.01588
MDPI2(5, 000) 241.81754 241.75355 241.8274 241.7716
MDPI3(5, 000) 240.89082 240.82517 240.89082 240.8443
MDPI4(5, 000) 240.97349 240.91546 240.9972 240.9249
MDPI5(5, 000) 242.48013 242.43047 242.48013 242.4512
MDPI6(5, 000) 240.32868 240.2663 240.32868 240.26432
MDPI7(5, 000) 242.82014 242.7599 242.82014 242.7793
MDPI8(5, 000) 241.14478 241.11345 241.195 241.1323
MDPI9(5, 000) 239.76056 239.51496 239.76056 239.5929
MDPI10(5, 000) 243.38549 243.34815 243.4737 243.3598
MDPII1(5, 000) 322.22322 322.1312 322.2359 322.1659
MDPII2(5, 000) 327.30191 327.07525 327.30191 327.2223
MDPII3(5, 000) 324.81083 324.79022 324.8135 324.7931
MDPII4(5, 000) 322.21229 322.1266 322.2376 322.08809
MDPII5(5, 000) 322.42081 322.30125 322.5012 322.3782
MDPII6(5, 000) 322.95049 322.61523 322.95049 322.7672
MDPII7(5, 000) 322.85044 322.7784 322.85044 322.7757
MDPII8(5, 000) 323.03384 322.87316 323.1121 322.8885
MDPII9(5, 000) 323.52271 323.27856 323.5438 323.4081
MDPII10(5, 000) 324.51991 324.29479 324.51991 324.5191
Table Options

Download as excel

Instance $ (n) $ MTS RLTS
$ f_{best} $ $ f_{avg} $ $ f_{best} $ $ f_{avg} $
MDPI1(3, 000) 189.04897 189.04897 189.04897 189.04897
MDPI2(3, 000) 187.38729 187.38729 187.38729 187.38729
MDPI3(3, 000) 185.66681 185.65159 185.66681 185.6594
MDPI4(3, 000) 186.16373 186.16373 186.16373 186.16373
MDPI5(3, 000) 187.54552 187.54552 187.54552 187.54552
MDPI6(3, 000) 189.43126 189.43126 189.43126 189.43126
MDPI7(3, 000) 188.24258 188.24258 188.24258 188.24258
MDPI8(3, 000) 186.79681 186.79681 186.79681 186.79681
MDPI9(3, 000) 188.23126 188.23126 188.23126 188.23126
MDPI10(3, 000) 185.68251 185.67237 185.68251 185.6747
MDPII1(3, 000) 252.32043 252.32043 252.32043 252.32043
MDPII2(3, 000) 250.06214 250.05474 250.06214 250.0569
MDPII3(3, 000) 251.90627 251.90627 251.90627 251.90627
MDPII4(3, 000) 253.94101 253.93968 253.94101 253.941
MDPII5(3, 000) 253.26042 253.26016 253.26042 253.2604
MDPII6(3, 000) 250.67775 250.67775 250.67775 250.67775
MDPII7(3, 000) 251.13441 251.13441 251.13441 251.13441
MDPII8(3, 000) 252.99965 252.99965 252.99965 252.99965
MDPII9(3, 000) 252.42577 252.42577 252.42577 252.42577
MDPII10(3, 000) 252.39659 252.39659 252.39659 252.39659
MDPI1(5, 000) 240.14121 240.0212 240.1594 240.01588
MDPI2(5, 000) 241.81754 241.75355 241.8274 241.7716
MDPI3(5, 000) 240.89082 240.82517 240.89082 240.8443
MDPI4(5, 000) 240.97349 240.91546 240.9972 240.9249
MDPI5(5, 000) 242.48013 242.43047 242.48013 242.4512
MDPI6(5, 000) 240.32868 240.2663 240.32868 240.26432
MDPI7(5, 000) 242.82014 242.7599 242.82014 242.7793
MDPI8(5, 000) 241.14478 241.11345 241.195 241.1323
MDPI9(5, 000) 239.76056 239.51496 239.76056 239.5929
MDPI10(5, 000) 243.38549 243.34815 243.4737 243.3598
MDPII1(5, 000) 322.22322 322.1312 322.2359 322.1659
MDPII2(5, 000) 327.30191 327.07525 327.30191 327.2223
MDPII3(5, 000) 324.81083 324.79022 324.8135 324.7931
MDPII4(5, 000) 322.21229 322.1266 322.2376 322.08809
MDPII5(5, 000) 322.42081 322.30125 322.5012 322.3782
MDPII6(5, 000) 322.95049 322.61523 322.95049 322.7672
MDPII7(5, 000) 322.85044 322.7784 322.85044 322.7757
MDPII8(5, 000) 323.03384 322.87316 323.1121 322.8885
MDPII9(5, 000) 323.52271 323.27856 323.5438 323.4081
MDPII10(5, 000) 324.51991 324.29479 324.51991 324.5191
[1]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31
[2]

Jingang Zhao, Chi Zhang. Finite-horizon optimal control of discrete-time linear systems with completely unknown dynamics using Q-learning. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1471-1483. doi: 10.3934/jimo.2020030
[3]

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017
[4]

Ziju Shen, Yufei Wang, Dufan Wu, Xu Yang, Bin Dong. Learning to scan: A deep reinforcement learning approach for personalized scanning in CT imaging. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021045
[5]

Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
[6]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[7]

Aude Hofleitner, Tarek Rabbani, Mohammad Rafiee, Laurent El Ghaoui, Alex Bayen. Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 503-523. doi: 10.3934/dcdss.2014.7.503
[8]

Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021102
[9]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[10]

Jiaxin Zhang, Hoang Tran, Guannan Zhang. Accelerating reinforcement learning with a Directional-Gaussian-Smoothing evolution strategy. Electronic Research Archive, , () : -. doi: 10.3934/era.2021075
[11]

Minlong Lin, Ke Tang. Selective further learning of hybrid ensemble for class imbalanced increment learning. Big Data & Information Analytics, 2017, 2 (1) : 1-21. doi: 10.3934/bdia.2017005
[12]

Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021144
[13]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[14]

Yuan Xu, Xin Jin, Saiwei Wang, Yang Tang. Optimal synchronization control of multiple euler-lagrange systems via event-triggered reinforcement learning. Discrete & Continuous Dynamical Systems - S, 2021, 14 (4) : 1495-1518. doi: 10.3934/dcdss.2020377
[15]

Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059
[16]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193
[17]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[18]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041
[19]

Chuanxin Zhao, Lin Jiang, Kok Lay Teo. A hybrid chaos firefly algorithm for three-dimensional irregular packing problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 409-429. doi: 10.3934/jimo.2018160
[20]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (317)
  • HTML views (485)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences