American Institute of Mathematical Sciences

Advanced
June  2021, 11(2): 321-332. doi: 10.3934/naco.2020028

Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks

Mohsen Abdolhosseinzadeh 1,, and  Mir Mohammad Alipour 2,

1. 

Department of Mathematics, University of Bonab, Bonab, Iran
2. 

Department of Computer Engineering, University of Bonab, Bonab, Iran

* Corresponding author: Mohsen Abdolhosseinzadeh

The authors would like to thank anonymous reviewers for their useful comments

Received  September 2019 Revised  January 2020 Published  June 2021 Early access  May 2020

In a grid network, the nodes could be traversed either horizontally or vertically. The constrained shortest Hamiltonian path goes over the nodes between a source node and a destination node, and it is constrained to traverse some nodes at least once while others could be traversed several times. There are various applications of the problem, especially in routing problems. It is an NP-complete problem, and the well-known Bellman-Held-Karp algorithm could solve the shortest Hamiltonian circuit problem within $ {\rm O(}{{\rm 2}}^{{\rm n}}{{\rm n}}^{{\rm 2}}{\rm )} $ time complexity; however, the shortest Hamiltonian path problem is more complicated. So, a metaheuristic algorithm based on ant colony optimization is applied to obtain the optimal solution. The proposed method applies the rooted shortest path tree structure since in the optimal solution the paths between the restricted nodes are the shortest paths. Then, the shortest path tree is obtained by at most $ {\rm O(}{{\rm n}}^{{\rm 3}}{\rm )} $ time complexity at any iteration and the ants begin to improve the solution and the optimal solution is constructed in a reasonable time. The algorithm is verified by some numerical examples and the ant colony parameters are tuned by design of experiment method, and the optimal setting for different size of networks are determined.

Keywords: Shortest Hamiltonian path, constrained shortest path, ant colony optimization, grid networks, design of experiments, response surface method.
Mathematics Subject Classification: Primary: 62K20, 58F17; Secondary: 53C35.
Citation: 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
References:
[1]

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, 1$^st$ edition, Prentice hall, New York, 1993.  Google Scholar

[2]

M. M. Alipour and S. N. Razavi, A new multiagent reinforcement learning algorithm to solve the symmetric traveling salesman problem, Multiagent Grid Syst., 11 (2015), 107-119.   Google Scholar

[3]

M. M. Alipour, S. N. Razavi, M. R. Feizi Derakhshi and M. A. Balafar, A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem, Neural Comput. Appl., 30 (2018), 2935-2951.   Google Scholar

[4]

B. Appleton and C. Sun, Circular shortest paths by branch and bound, Pattern Recognit., 36 (2003), 2513-2520.   Google Scholar

[5]

A. A. Bertossi, The edge Hamiltonian path problem is NP-complete, Inf. Process. Lett., 13 (1981), 157-159.  doi: 10.1016/0020-0190(81)90048-X.  Google Scholar

[6]

B. Bontoux, C. Artigues and D. Feillet, A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem, Comput. Oper. Res., 37 (2010), 1844-1852.  doi: 10.1016/j.cor.2009.05.004.  Google Scholar

[7]

G. A. Bula, C. Prodhon, F. A. Gonzalez, H. M. Afsar and N. Velasco, Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation, J. Hazard. Mater., 324 (2017), 472-480.   Google Scholar

[8]

E. Cao, M. Lai and H. Yang, Open vehicle routing problem with demand uncertainty and its robust strategies, Expert Syst. Appl., 41 (2014), 3569-3575.   Google Scholar

[9]

T. S. Chang, Y. W. Wan and W. T. Ooi, A stochastic dynamic traveling salesman problem with hard time windows, Eur. J. Oper. Res., 198 (2009), 748-759.  doi: 10.1016/j.ejor.2008.10.012.  Google Scholar

[10]

S. S. Choong, L. P. Wong and C. P. Lim, An artificial bee colony algorithm with a modified choice function for the traveling salesman problem, Swarm Evol. Comput., 44 (2019), 622-635.   Google Scholar

[11]

A. Colorni, M. Dorigo, V. Maniezzo, D. Elettronica and P. Milano, Distributed optimization by ant colonies, The 1991 European Conference on Artificial Life, (1991), 134–142. Google Scholar

[12]

D. Ferone, P. Festa, F. Guerriero and D. Laganá, The constrained shortest path tour problem, Comput. Oper. Res., 74 (2016), 64-77.  doi: 10.1016/j.cor.2016.04.002.  Google Scholar

[13]

D. Ferone, P. Festa, F. Guerriero and D. Laganá, An integer linear programming model for the constrained shortest path tour problem, Electron. Notes Discret. Math., 69 (2018), 141-148.  doi: 10.1016/j.endm.2018.07.019.  Google Scholar

[14]

A. Gunawan, H. C. Lau and Li ndawati, Fine-tuning algorithm parameters using the design of experiments approach, Lect. Notes Comput. Sci., 6683 (2011), 278-292.   Google Scholar

[15]

M. Held and R. M. Karp, A dynamic programming approach to sequencing problems, J. Soc. Ind. Appl. Math., 10 (1962), 196-210.   Google Scholar

[16]

J. Jana and S. Kumar Roy, Solution of matrix games with generalised trapezoidal fuzzy payoffs, Fuzzy Inf. Eng., 10 (2018), 213-224.   Google Scholar

[17]

J. Jana and S. K. Roy, Dual hesitant fuzzy matrix games: based on new similarity measure, Soft Comput., 23 (2019), 8873-8886.   Google Scholar

[18]

M. Kuby, O. M. Araz, M. Palmer and I. Capar, An efficient online mapping tool for finding the shortest feasible path for alternative-fuel vehicles, Int. J. Hydrogen Energy, 39 (2014), 18433-18439.   Google Scholar

[19]

S. Kumar Roy, M. Pervin and G. Wilhelm Weber, Imperfection with inspection policy and variable demand under trade-credit: a deteriorating inventory model, Numer. Algebr. Control Optim., 10 (2020), 45-74.   Google Scholar

[20]

T. H. Lai and S. S. Wei, The edge Hamiltonian path problem is NP-complete for bipartite graphs, Inf. Process. Lett., 46 (1993), 21-26.  doi: 10.1016/0020-0190(93)90191-B.  Google Scholar

[21]

C. P. Lam, J. Xiao and H. Li, Ant colony optimisation for generation of conformance testing sequences using characterising sequences, The 3rd IASTED International Conference on Advances in Computer Science and Technology (ACS2007), (2007), 140–146. Google Scholar

[22]

E. B. De Lima, G. L. Pappa, J. M. De Almeida, M. A. Goncalves and W. Meira, Tuning genetic programming parameters with factorial designs, IEEE World Congr. Comput. Intell., IEEE Congr. Evol. Comput. 2010. Google Scholar

[23]

Y. H. Liu, Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem, Appl. Math. Comput., 216 (2010), 125-137.  doi: 10.1016/j.amc.2010.01.021.  Google Scholar

[24]

S. de Mesquita, A. R. Backes and P. Cortez, Texture analysis and classification using shortest paths in graphs, Pattern Recognit. Lett., 34 (2013), 1314-1319.  doi: 10.1109/TIP.2014.2333655.  Google Scholar

[25]

M. Mobin, S. M. Mousavi, M. Komaki and M. Tavana, A hybrid desirability function approach for tuning parameters in evolutionary optimization algorithms, Meas. J. Int. Meas. Confed., 114 (2018), 417-427.   Google Scholar

[26]

D. C. Montgomery, Design And Analysis of Experiments, 5$^th$ edition, Wiley, New York, 1984.  Google Scholar

[27]

C. M. Papadimitriou, Computational Complexity, 1$^st$ edition, Addison-Wesley, New York, 1994.  Google Scholar

[28]

M. Pervin, S. K. Roy and G. W. Weber, A two-echelon inventory model with stock-dependent demand and variable holding cost for deteriorating items, Numer. Algebr. Control Optim., 7 (2017), 21-50.  doi: 10.3934/naco.2017002.  Google Scholar

[29]

M. Pervin, S. K. Roy and G. W. Weber, An integrated inventory model with variable holding cost under two levels of trade-credit policy, Numer. Algebr. Control Optim., 8 (2018), 169-191.  doi: 10.3934/naco.2018010.  Google Scholar

[30]

B. Richard, Dynamic programming treatment of the travelling salesman problem, J. Assoc. Comput. Mach., 9 (1962), 61-63.  doi: 10.1145/321105.321111.  Google Scholar

[31]

E. Ridge and D. Kudenko, Tuning an algorithm using design of experiments, Experimental Methods for the Analysis of Optimization Algorithms, (eds. T. Bartz-Beielstein, M. Chiarandini, L. Paquete and M. Preuss), Springer, New York, (2010), 265–286. doi: 10.1007/978-3-642-02538-9.  Google Scholar

[32]

M. Salari, M. Reihaneh and M. S. Sabbagh, Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem, Comput. Ind. Eng., 83 (2015), 244-251.   Google Scholar

[33]

R. De Santis, R. Montanari, G. Vignali and E. Bottani, An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses, Eur. J. Oper. Res., 267 (2018), 120-137.  doi: 10.1016/j.ejor.2017.11.017.  Google Scholar

[34]

V. Saw, A. Rahman and W. E. Ong, Shortest path problem on a grid network with unordered intermediate points, J. Phys. Conf. Ser., 893 (2017). doi: 10.1088/1742-6596/893/1/012066.  Google Scholar

[35]

P. I. Stetsyuk, Problem statements for k-node shortest path and k-node shortest cycle in a complete graph, Cybern. Syst. Anal., 52 (2016), 71-75.  doi: 10.1007/s10559-016-9801-x.  Google Scholar

[36]

D. Sudholt and C. Thyssen, Running time analysis of ant colony optimization for shortest path problems, J. Discret. Algorithms, 10 (2012), 165-180.  doi: 10.1016/j.jda.2011.06.002.  Google Scholar

[37]

D. Sudholt and C. Thyssen, A simple ant colony optimizer for stochastic shortest path problems, Algorithmica, 64 (2012), 643-672.  doi: 10.1007/s00453-011-9606-2.  Google Scholar

[38]

T. Vidal, M. Battarra, A. Subramanian and G. Erdogan, Hybrid metaheuristics for the clustered vehicle routing problem, Comput. Oper. Res., 58 (2015), 87-99.  doi: 10.1016/j.cor.2014.10.019.  Google Scholar

[39]

Y. Wang, The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem, Comput. Ind. Eng., 70 (2014), 124-133.   Google Scholar

[40]

J. Xiao, Y. Zhang, X. Jia and X. Zhou, A schedule of join operations to reduce I/O cost in spatial database systems, Data Knowl. Eng., 35 (2000), 299-317.   Google Scholar

[41]

J. Yang, X. Shi, M. Marchese and Y. Liang, Ant colony optimization method for generalized TSP problem, Prog. Nat. Sci., 18 (2008), 1417-1422.  doi: 10.1016/j.pnsc.2008.03.028.  Google Scholar

show all references

References:
[1]

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, 1$^st$ edition, Prentice hall, New York, 1993.  Google Scholar

[2]

M. M. Alipour and S. N. Razavi, A new multiagent reinforcement learning algorithm to solve the symmetric traveling salesman problem, Multiagent Grid Syst., 11 (2015), 107-119.   Google Scholar

[3]

M. M. Alipour, S. N. Razavi, M. R. Feizi Derakhshi and M. A. Balafar, A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem, Neural Comput. Appl., 30 (2018), 2935-2951.   Google Scholar

[4]

B. Appleton and C. Sun, Circular shortest paths by branch and bound, Pattern Recognit., 36 (2003), 2513-2520.   Google Scholar

[5]

A. A. Bertossi, The edge Hamiltonian path problem is NP-complete, Inf. Process. Lett., 13 (1981), 157-159.  doi: 10.1016/0020-0190(81)90048-X.  Google Scholar

[6]

B. Bontoux, C. Artigues and D. Feillet, A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem, Comput. Oper. Res., 37 (2010), 1844-1852.  doi: 10.1016/j.cor.2009.05.004.  Google Scholar

[7]

G. A. Bula, C. Prodhon, F. A. Gonzalez, H. M. Afsar and N. Velasco, Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation, J. Hazard. Mater., 324 (2017), 472-480.   Google Scholar

[8]

E. Cao, M. Lai and H. Yang, Open vehicle routing problem with demand uncertainty and its robust strategies, Expert Syst. Appl., 41 (2014), 3569-3575.   Google Scholar

[9]

T. S. Chang, Y. W. Wan and W. T. Ooi, A stochastic dynamic traveling salesman problem with hard time windows, Eur. J. Oper. Res., 198 (2009), 748-759.  doi: 10.1016/j.ejor.2008.10.012.  Google Scholar

[10]

S. S. Choong, L. P. Wong and C. P. Lim, An artificial bee colony algorithm with a modified choice function for the traveling salesman problem, Swarm Evol. Comput., 44 (2019), 622-635.   Google Scholar

[11]

A. Colorni, M. Dorigo, V. Maniezzo, D. Elettronica and P. Milano, Distributed optimization by ant colonies, The 1991 European Conference on Artificial Life, (1991), 134–142. Google Scholar

[12]

D. Ferone, P. Festa, F. Guerriero and D. Laganá, The constrained shortest path tour problem, Comput. Oper. Res., 74 (2016), 64-77.  doi: 10.1016/j.cor.2016.04.002.  Google Scholar

[13]

D. Ferone, P. Festa, F. Guerriero and D. Laganá, An integer linear programming model for the constrained shortest path tour problem, Electron. Notes Discret. Math., 69 (2018), 141-148.  doi: 10.1016/j.endm.2018.07.019.  Google Scholar

[14]

A. Gunawan, H. C. Lau and Li ndawati, Fine-tuning algorithm parameters using the design of experiments approach, Lect. Notes Comput. Sci., 6683 (2011), 278-292.   Google Scholar

[15]

M. Held and R. M. Karp, A dynamic programming approach to sequencing problems, J. Soc. Ind. Appl. Math., 10 (1962), 196-210.   Google Scholar

[16]

J. Jana and S. Kumar Roy, Solution of matrix games with generalised trapezoidal fuzzy payoffs, Fuzzy Inf. Eng., 10 (2018), 213-224.   Google Scholar

[17]

J. Jana and S. K. Roy, Dual hesitant fuzzy matrix games: based on new similarity measure, Soft Comput., 23 (2019), 8873-8886.   Google Scholar

[18]

M. Kuby, O. M. Araz, M. Palmer and I. Capar, An efficient online mapping tool for finding the shortest feasible path for alternative-fuel vehicles, Int. J. Hydrogen Energy, 39 (2014), 18433-18439.   Google Scholar

[19]

S. Kumar Roy, M. Pervin and G. Wilhelm Weber, Imperfection with inspection policy and variable demand under trade-credit: a deteriorating inventory model, Numer. Algebr. Control Optim., 10 (2020), 45-74.   Google Scholar

[20]

T. H. Lai and S. S. Wei, The edge Hamiltonian path problem is NP-complete for bipartite graphs, Inf. Process. Lett., 46 (1993), 21-26.  doi: 10.1016/0020-0190(93)90191-B.  Google Scholar

[21]

C. P. Lam, J. Xiao and H. Li, Ant colony optimisation for generation of conformance testing sequences using characterising sequences, The 3rd IASTED International Conference on Advances in Computer Science and Technology (ACS2007), (2007), 140–146. Google Scholar

[22]

E. B. De Lima, G. L. Pappa, J. M. De Almeida, M. A. Goncalves and W. Meira, Tuning genetic programming parameters with factorial designs, IEEE World Congr. Comput. Intell., IEEE Congr. Evol. Comput. 2010. Google Scholar

[23]

Y. H. Liu, Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem, Appl. Math. Comput., 216 (2010), 125-137.  doi: 10.1016/j.amc.2010.01.021.  Google Scholar

[24]

S. de Mesquita, A. R. Backes and P. Cortez, Texture analysis and classification using shortest paths in graphs, Pattern Recognit. Lett., 34 (2013), 1314-1319.  doi: 10.1109/TIP.2014.2333655.  Google Scholar

[25]

M. Mobin, S. M. Mousavi, M. Komaki and M. Tavana, A hybrid desirability function approach for tuning parameters in evolutionary optimization algorithms, Meas. J. Int. Meas. Confed., 114 (2018), 417-427.   Google Scholar

[26]

D. C. Montgomery, Design And Analysis of Experiments, 5$^th$ edition, Wiley, New York, 1984.  Google Scholar

[27]

C. M. Papadimitriou, Computational Complexity, 1$^st$ edition, Addison-Wesley, New York, 1994.  Google Scholar

[28]

M. Pervin, S. K. Roy and G. W. Weber, A two-echelon inventory model with stock-dependent demand and variable holding cost for deteriorating items, Numer. Algebr. Control Optim., 7 (2017), 21-50.  doi: 10.3934/naco.2017002.  Google Scholar

[29]

M. Pervin, S. K. Roy and G. W. Weber, An integrated inventory model with variable holding cost under two levels of trade-credit policy, Numer. Algebr. Control Optim., 8 (2018), 169-191.  doi: 10.3934/naco.2018010.  Google Scholar

[30]

B. Richard, Dynamic programming treatment of the travelling salesman problem, J. Assoc. Comput. Mach., 9 (1962), 61-63.  doi: 10.1145/321105.321111.  Google Scholar

[31]

E. Ridge and D. Kudenko, Tuning an algorithm using design of experiments, Experimental Methods for the Analysis of Optimization Algorithms, (eds. T. Bartz-Beielstein, M. Chiarandini, L. Paquete and M. Preuss), Springer, New York, (2010), 265–286. doi: 10.1007/978-3-642-02538-9.  Google Scholar

[32]

M. Salari, M. Reihaneh and M. S. Sabbagh, Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem, Comput. Ind. Eng., 83 (2015), 244-251.   Google Scholar

[33]

R. De Santis, R. Montanari, G. Vignali and E. Bottani, An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses, Eur. J. Oper. Res., 267 (2018), 120-137.  doi: 10.1016/j.ejor.2017.11.017.  Google Scholar

[34]

V. Saw, A. Rahman and W. E. Ong, Shortest path problem on a grid network with unordered intermediate points, J. Phys. Conf. Ser., 893 (2017). doi: 10.1088/1742-6596/893/1/012066.  Google Scholar

[35]

P. I. Stetsyuk, Problem statements for k-node shortest path and k-node shortest cycle in a complete graph, Cybern. Syst. Anal., 52 (2016), 71-75.  doi: 10.1007/s10559-016-9801-x.  Google Scholar

[36]

D. Sudholt and C. Thyssen, Running time analysis of ant colony optimization for shortest path problems, J. Discret. Algorithms, 10 (2012), 165-180.  doi: 10.1016/j.jda.2011.06.002.  Google Scholar

[37]

D. Sudholt and C. Thyssen, A simple ant colony optimizer for stochastic shortest path problems, Algorithmica, 64 (2012), 643-672.  doi: 10.1007/s00453-011-9606-2.  Google Scholar

[38]

T. Vidal, M. Battarra, A. Subramanian and G. Erdogan, Hybrid metaheuristics for the clustered vehicle routing problem, Comput. Oper. Res., 58 (2015), 87-99.  doi: 10.1016/j.cor.2014.10.019.  Google Scholar

[39]

Y. Wang, The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem, Comput. Ind. Eng., 70 (2014), 124-133.   Google Scholar

[40]

J. Xiao, Y. Zhang, X. Jia and X. Zhou, A schedule of join operations to reduce I/O cost in spatial database systems, Data Knowl. Eng., 35 (2000), 299-317.   Google Scholar

[41]

J. Yang, X. Shi, M. Marchese and Y. Liang, Ant colony optimization method for generalized TSP problem, Prog. Nat. Sci., 18 (2008), 1417-1422.  doi: 10.1016/j.pnsc.2008.03.028.  Google Scholar

Figure 1.  The horizontal and orthogonal movements in the grid networks
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The shortest path tree
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The ACO Algorithm for the C-SHP problem
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  The initial neighborhood methods
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The pareto charts of the standardized effects for the responses in the screening phase for the network 200$ \times $200
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The pareto charts of the standardized effects in the network 200$ \times $200 for the responses in Box–Behnken design
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  The optimized fitted response plots for the network 200$ \times $200
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  The solution diagram of ACO algorithm by optimal tuning of parameters
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  The design factors and their levels
factors levels
-1 0 1
A $ \alpha $ 1 7 13
B $ \beta $ 0 6 13
C $ Q $ 1 2 4
D $ \tau (0) $ 0.1 0.5 0.9
E $ \rho $ 0.01 0.5 0.99
F initial solution RO NN1 NN2
G ant number 0.5 1 1.5
Blocks instance size small moderate large
Table Options

Download as excel

factors levels
-1 0 1
A $ \alpha $ 1 7 13
B $ \beta $ 0 6 13
C $ Q $ 1 2 4
D $ \tau (0) $ 0.1 0.5 0.9
E $ \rho $ 0.01 0.5 0.99
F initial solution RO NN1 NN2
G ant number 0.5 1 1.5
Blocks instance size small moderate large
Table 2.  The optimal coded and uncoded settings of the factors
network size factors $ \alpha $ $ \beta $ $ Q $ $ \tau (0) $ $ \rho $ initial solution ant number desirability value
100$ \times $100 optimal coded 1 -1 1 -1 -0.68 0.05 -0.98 0.9640
optimal uncoded 13 0 4 0.1 0.17 NN1 0.5
200$ \times $200 optimal coded -1 -1 -0.99 -0.70 0.68 -0.04 -1 0.9957
optimal uncoded 1 0 1 0.22 0.83 NN1 0.5
400$ \times $400 optimal coded -1 -0.54 -1 1 1 0.15 -1 0.8996
optimal uncoded 1 3 1 0.9 0.99 NN1 0.5
Table Options

Download as excel

network size factors $ \alpha $ $ \beta $ $ Q $ $ \tau (0) $ $ \rho $ initial solution ant number desirability value
100$ \times $100 optimal coded 1 -1 1 -1 -0.68 0.05 -0.98 0.9640
optimal uncoded 13 0 4 0.1 0.17 NN1 0.5
200$ \times $200 optimal coded -1 -1 -0.99 -0.70 0.68 -0.04 -1 0.9957
optimal uncoded 1 0 1 0.22 0.83 NN1 0.5
400$ \times $400 optimal coded -1 -0.54 -1 1 1 0.15 -1 0.8996
optimal uncoded 1 3 1 0.9 0.99 NN1 0.5
Table 3.  The optimal prediction and the confidence intervals of the responses
Network Response Fit SE Fit 95% CI 95% PI
100$ \times $100 Improve 0.2970 0.0848 (0.1226, 0.4713) (0.0829, 0.5111)
CPU Time 18 10.1 (-2.8, 38.8) (-7.6, 43.5)
Opt. Sol. 3608 318 (2954, 4262) (2804, 4412)
200$ \times $200 Improve 0.2119 0.0534 (0.1020, 0.3217) (0.0724, 0.3513)
CPU Time 161.25 4.77 (151.44,171.05) (148.80,173.69)
Opt. Sol. 13719 654 (12375, 15063) (12013, 15425)
400$ \times $400 Improve 0.1605 0.0413 (0.0756, 0.2454) (0.0555, 0.2655)
CPU Time 1763 647 (434, 3092) (119, 3407)
Opt. Sol. 54087 1726 (50540, 57634) (49699, 58474)
Table Options

Download as excel

Network Response Fit SE Fit 95% CI 95% PI
100$ \times $100 Improve 0.2970 0.0848 (0.1226, 0.4713) (0.0829, 0.5111)
CPU Time 18 10.1 (-2.8, 38.8) (-7.6, 43.5)
Opt. Sol. 3608 318 (2954, 4262) (2804, 4412)
200$ \times $200 Improve 0.2119 0.0534 (0.1020, 0.3217) (0.0724, 0.3513)
CPU Time 161.25 4.77 (151.44,171.05) (148.80,173.69)
Opt. Sol. 13719 654 (12375, 15063) (12013, 15425)
400$ \times $400 Improve 0.1605 0.0413 (0.0756, 0.2454) (0.0555, 0.2655)
CPU Time 1763 647 (434, 3092) (119, 3407)
Opt. Sol. 54087 1726 (50540, 57634) (49699, 58474)
[1]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469
[2]

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
[3]

Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 979-987. doi: 10.3934/dcdss.2019066
[4]

Daniel Mckenzie, Steven Damelin. Power weighted shortest paths for clustering Euclidean data. Foundations of Data Science, 2019, 1 (3) : 307-327. doi: 10.3934/fods.2019014
[5]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215
[6]

Pikkala Vijaya Laxmi, Singuluri Indira, Kanithi Jyothsna. Ant colony optimization for optimum service times in a Bernoulli schedule vacation interruption queue with balking and reneging. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1199-1214. doi: 10.3934/jimo.2016.12.1199
[7]

A. Zeblah, Y. Massim, S. Hadjeri, A. Benaissa, H. Hamdaoui. Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony. Journal of Industrial & Management Optimization, 2006, 2 (4) : 467-479. doi: 10.3934/jimo.2006.2.467
[8]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
[9]

Jinlong Guo, Bin Li, Yuandong Ji. A control parametrization based path planning method for the quad-rotor uavs. Journal of Industrial & Management Optimization, 2022, 18 (2) : 1079-1100. doi: 10.3934/jimo.2021009
[10]

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
[11]

Harish Garg. Solving structural engineering design optimization problems using an artificial bee colony algorithm. Journal of Industrial & Management Optimization, 2014, 10 (3) : 777-794. doi: 10.3934/jimo.2014.10.777
[12]

Guoliang Xue, Weiyi Zhang, Tie Wang, Krishnaiyan Thulasiraman. On the partial path protection scheme for WDM optical networks and polynomial time computability of primary and secondary paths. Journal of Industrial & Management Optimization, 2007, 3 (4) : 625-643. doi: 10.3934/jimo.2007.3.625
[13]

Hong-Kun Zhang. Free path of billiards with flat points. Discrete & Continuous Dynamical Systems, 2012, 32 (12) : 4445-4466. doi: 10.3934/dcds.2012.32.4445
[14]

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
[15]

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391
[16]

Louis Caccetta, Ian Loosen, Volker Rehbock. Computational aspects of the optimal transit path problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 95-105. doi: 10.3934/jimo.2008.4.95
[17]

Lorenzo Brasco, Filippo Santambrogio. An equivalent path functional formulation of branched transportation problems. Discrete & Continuous Dynamical Systems, 2011, 29 (3) : 845-871. doi: 10.3934/dcds.2011.29.845
[18]

Xing Huang, Chang Liu, Feng-Yu Wang. Order preservation for path-distribution dependent SDEs. Communications on Pure & Applied Analysis, 2018, 17 (5) : 2125-2133. doi: 10.3934/cpaa.2018100
[19]

Fumioki Asakura, Andrea Corli. The path decomposition technique for systems of hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 15-32. doi: 10.3934/dcdss.2016.9.15
[20]

J. F. Toland. Path-connectedness in global bifurcation theory. Electronic Research Archive, 2021, 29 (6) : 4199-4213. doi: 10.3934/era.2021079

 Impact Factor: 

Tools

Metrics

  • PDF downloads (277)
  • HTML views (491)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy