American Institute of Mathematical Sciences

Advanced
August  2018, 1(3): 265-280. doi: 10.3934/mfc.2018012

Discrete heat transfer search for solving travelling salesman problem

Poonam Savsani 1,2, and  Mohamed A. Tawhid 3,,

1. 

Department of Industrial Engineering, Pandit Deendayal Petroleum University, Gandinagar, Gujarat, India
2. 

Postdoctoral Fellow, Department of Mathematics and Statistics, Faculty of Science, ThompsonRivers University, Kamloops, BC, Canada V2C 0C8
3. 

Department of Mathematics and Statistics, Faculty of Science, Thompson Rivers University, Kamloops, BC, Canada V2C 0C8

* Corresponding author: Mohamed A. Tawhid

Received  November 2017 Revised  February 2018 Published  July 2018

Fund Project: We are grateful to the anonymous reviewers for constructive feedback and insightful suggestions which greatly improved this article. The research of the 2nd author is supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC). The postdoctoral fellowship of the 1st author is supported by NSERC

Within the academic circle the Traveling Salesman Problem (TSP), this is one of the most major NP-hard problems that have been a primary topic of discussion for years. Developing efficient algorithms to solve TSP have been the goal of many individuals, and so this has been addressed efficiently in this article. Here, a discrete heat transfer search (DHTS) is proposed to solve TSP. DHTS uses three distinct phases to update the city tours namely, conduction, convection, and radiation. Each phase performs a certain function as the conduction phase is a replica of the 2-Opt local search technique, the convection phase exchanges the random city with the finest city tour, and the radiation phase exchanges the random city among two separate city tours without compromising the basics of HTS algorithm. Bench test problems taken from TSPLIB successfully test the algorithm and demonstrate the fact that the proposed algorithm can attain results near the optimal values, and do so within an acceptable duration.

Keywords: Ravelling salesman problems, discrete heat transfer search algorithm, NP-hard, combinatorial optimization problem, meta-heuristic.
Mathematics Subject Classification: Primary: 68R01, 68T20, 68W20, 90B15, 90C56.
Citation: 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
References:
[1] R. E. Bellman and S. E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 2015. Google Scholar
[2]

P. Berman and M. Karpinski, 8/7-approximation algorithm for (1, 2)-TSP, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, Society for Industrial and Applied Mathematics, (2006), 641-648. doi: 10.1145/1109557.1109627. Google Scholar

[3]

S. M. Chen and C. Y. Chien, Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques, Expert Systems with Applications, 38 (2011), 14439-14450. doi: 10.1016/j.eswa.2011.04.163. Google Scholar

[4]

J. Cirasella, D. S. Johnson, L. A. McGeoch and W. Zhang, The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, Algorithm Engineering and Experimentation, 2153 (2011), 32-59. doi: 10.1007/3-540-44808-X_3. Google Scholar

[5]

S. Climer and W. Zhang, Cut-and-solve: An iterative search strategy for combinatorial optimization problems, Artificial Intelligence, 170 (2006), 714-738. doi: 10.1016/j.artint.2006.02.005. Google Scholar

[6]

G. A. Croes, A method for solving traveling-salesman problems, Operations Research, 6 (1958), 791-812. doi: 10.1287/opre.6.6.791. Google Scholar

[7]

S. O. Degertekin and L Lamberti, Heat transfer search algorithm for sizing optimization of truss structures, Latin American Journal of Solids and Structures, 14 (2017), 373-397. doi: 10.1590/1679-78253297. Google Scholar

[8]

G. Dong, W. W. Guo and K. Tickle, Solving the traveling salesman problem using cooperative genetic ant systems, Expert Systems with Applications, 39 (2012), 5006-5011. doi: 10.1016/j.eswa.2011.10.012. Google Scholar

[9]

B. Escario, J. F. Jimenez and J. M. Giron-Sierra, Ant colony extended: Experiments on the travelling salesman problem, Expert Systems with Applications, 42 (2015), 390-410. doi: 10.1016/j.eswa.2014.07.054. Google Scholar

[10]

P. Gang, I. Iimura and S. Nakayama, An evolutionary multiple heuristic with genetic local search for solving TSP, International Journal of Information Technology, 14 (2008), 1-11. Google Scholar

[11]

M. Gunduz and M. S. Kiran, A hierarchic approach based on swarm intelligence to solve the traveling salesman problem, Turkish Journal of Electrical Engineering & Computer Sciences, 23 (2015), 103-117. Google Scholar

[12]

T. Guo and Z. Michalewicz, Invor-over operator for the TSP-proceedings of the 5th parallel problem solving from nature conference, (1998), 1498-1520.Google Scholar

[13]

F. Han, Q. H. Ling and D. S. Huang, An improved approximation approach incorporating particle swarm optimization and a priori information into neural networks, Neural Computing and Applications, 19 (2010), 255-261. doi: 10.1007/s00521-009-0274-y. Google Scholar

[14]

K. Helsgaun, An effective implementation of the Lin Kernighan traveling salesman heuristic, European Journal of Operational Research, 126 (2000), 106-130. doi: 10.1016/S0377-2217(99)00284-2. Google Scholar

[15]

D. S. Huang and J. X. Du, A constructive hybrid structure optimization methodology for radial basis probabilistic neural networks, IEEE Transactions on Neural Networks, 19 (2008), 2099-2115. doi: 10.1109/TNN.2008.2004370. Google Scholar

[16]

J. E. Hunt and D. E. Cooke, Learning using an artificial immune system, Journal of Network and Computer Applications, 19 (1996), 189-212. doi: 10.1006/jnca.1996.0014. Google Scholar

[17]

D. S. Johnson and L. A. McGeoch, Experimental analysis of heuristics for the STSP, The Traveling Salesman Problem and its Variations, Springer, Boston, MA, 12 (2002), 369-443. doi: 10.1007/0-306-48213-4_9. Google Scholar

[18]

K. Jun-man and Z. Yi, Application of an improved ant colony optimization on generalized traveling salesman problem, Energy Procedia, 17 (2012), 319-325. doi: 10.1016/j.egypro.2012.02.101. Google Scholar

[19]

W. Junqiang and O. Aijia, A hybrid algorithm of ACO and delete-cross method for TSP, Industrial Control and Electronics Engineering (ICICEE), 2012 International Conference on. IEEE, (2012), 694-1696. Google Scholar

[20]

J. Junzhong, H. Zhen, L. Chunnian and D. Qigu, An ant colony algorithm based on Multiple-Grain representation for the traveling salesman problems, Journal of Computer Research and Development, 3 (2010), 9. Google Scholar

[21]

J. Kennedy and R. C. Eberhart, A discrete binary version of the particle swarm algorithm, Systems, Man, and Cybernetics, Computational Cybernetics and Simulation., 1997 IEEE International Conference on, IEEE, 5 (1997), 4104-4108.Google Scholar

[22]

S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671. Google Scholar

[23]

E. L. Lawler and D. E. Wood, Branch-and-bound methods: A survey, Operations Research, 14 (1966), 699-719. doi: 10.1287/opre.14.4.699. Google Scholar

[24]

S. Lin, Computer solutions of the traveling salesman problem, The Bell System Technical Journal, 44 (1965), 2245-2269. doi: 10.1002/j.1538-7305.1965.tb04146.x. Google Scholar

[25]

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. Google Scholar

[26]

X. Liu and C. Xiu, A novel hysteretic chaotic neural network and its applications, Neurocomputing, 70 (2007), 2561-2565. doi: 10.1016/j.neucom.2007.02.002. Google Scholar

[27]

M. Mahi, K. Baykan and H. Kodaz, A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem, Applied Soft Computing, 30 (2015), 484-490. doi: 10.1016/j.asoc.2015.01.068. Google Scholar

[28]

Y. Marinakis, M. Marinaki and G. Dounias, Honey bees mating optimization algorithm for the Euclidean traveling salesman problem, Information Sciences, 181 (2011), 4684-4698. doi: 10.1016/j.ins.2010.06.032. Google Scholar

[29]

T. A. S. Masutti and L. N. de Castro, A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem, Information Sciences, 179 (2009), 1454-1468. doi: 10.1016/j.ins.2008.12.016. Google Scholar

[30]

P. Merz and B. Freisleben, Genetic local search for the TSP: New results, Evolutionary Computation, 1997., IEEE International Conference on. IEEE, 159-164 1997. doi: 10.1109/ICEC.1997.592288. Google Scholar

[31]

E. Osaba, X. S. Yang, F. Diaz, P. Lopez-Garcia and R. Carballedo, An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems, Engineering Applications of Artificial Intelligence, 48 (2016), 59-71. doi: 10.1016/j.engappai.2015.10.006. Google Scholar

[32]

Z. A. Othman, A. I. Srour, A. R. Hamdan and P. Y. Ling, Performance water flow-like algorithm for TSP by improving its local search, International Journal of Advancements in Computing Technology, 5 (2013), 126. Google Scholar

[33]

X. Ouyang, Y. Zhou and Q. Luo, A novel discrete cuckoo search algorithm for spherical traveling salesman problem, Applied Mathematics & Information Sciences, 7 (2013), 777-784. doi: 10.12785/amis/070248. Google Scholar

[34]

R. Pasti and L. N. de Castro, A neuro-immune network for solving the traveling salesman problem, Neural Networks, 2006. IJCNN'06, International Joint Conference on IEEE, (pp. 3760-3766, 2006.Google Scholar

[35]

V. K. Patel and V. J. Savsani, Heat transfer search (HTS): A novel optimization algorithm, Nformation Sciences, 324 (2015), 217-246. doi: 10.1016/j.ins.2015.06.044. Google Scholar

[36]

M. Peker, B. EN and P. Y. Kumru, An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method, Turkish Journal of Electrical Engineering & Computer Sciences, 21 (2013), 2015-2036. doi: 10.3906/elk-1109-44. Google Scholar

[37]

A. Rodríguez and R. Ruiz, The effect of the asymmetry of road transportation networks on the traveling salesman problem, Computers & Operations Research, 39 (2012), 1566-1576. doi: 10.1016/j.cor.2011.09.005. Google Scholar

[38]

Y. Saji and M. E. Riffi, A novel discrete bat algorithm for solving the travelling salesman problem, Neural Computing and Applications, 27 (2016), 1853-1866. doi: 10.1007/s00521-015-1978-9. Google Scholar

[39]

F. Samanlioglu, W. G. Ferrell Jr and M. E. Kurz, A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem, Computers & Industrial Engineering, 55 (2008), 439-449. doi: 10.1016/j.cie.2008.01.005. Google Scholar

[40]

J. Shu, Z. Zhao and Q. Dai, Genetic algorithm for TSP, Operations Research and Management Science, 1 (2004), 4. Google Scholar

[41]

L. V. Snyder and M. S. Daskin, A random-key genetic algorithm for the generalized traveling salesman problem, European Journal of Operational Research, 174 (2006), 38-53. doi: 10.1016/j.ejor.2004.09.057. Google Scholar

[42]

M. A. Tawhid and V. Savsani, ϵ-constraint heat transfer search (ϵ-HTS) algorithm for solving multi-objective engineering design problems, Journal of Computational Design and Engineering, 5 (2018), 104-119. Google Scholar

[43]

G. Tejani, V. Savsani and V. Patel, Modified sub-population based heat transfer search algorithm for structural optimization, International Journal of Applied Metaheuristic Computing (IJAMC), 8 (2017), 1-23. Google Scholar

[44]

P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications, Society for Industrial and Applied Mathematics, 2014. doi: 10.1137/1.9781611973594. Google Scholar

[45]

C. F. Tsai, C. W. Tsai and C. C. Tseng, A new hybrid heuristic approach for solving large traveling salesman problem, Information Sciences, 166 (2004), 67-81. doi: 10.1016/j.ins.2003.11.008. Google Scholar

[46]

Y. Wang, The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem, Computers Industrial Engineering, 70 (2014), 124-133. doi: 10.1016/j.cie.2014.01.015. Google Scholar

[47]

J. Yang, X. Shi, M. Marchese and Y. Liang, An ant colony optimization method for generalized TSP problem, Progress in Natural Science, 18 (2008), 1417-1422. doi: 10.1016/j.pnsc.2008.03.028. Google Scholar

[48]

J. Yang, C Wu, H. P. Lee and Y. Liang, Solving traveling salesman problems using generalized chromosome genetic algorithm, Progress in Natural Science, 18 (2008), 887-892. doi: 10.1016/j.pnsc.2008.01.030. Google Scholar

[49]

W. Zhang and R. E. Korf, A study of complexity transitions on the asymmetric traveling salesman problem, Artificial Intelligence, 81 (1996), 223-239. doi: 10.1016/0004-3702(95)00054-2. Google Scholar

[50]

Y. Q. Zhou, Z. X. Huang and H. X. Liu, Discrete glowworm swarm optimization algorithm for TSP problem, Dianzi Xuebao(Acta Electronica Sinica), 40 (2012), 1164-1170. Google Scholar

[51]

Y. Zhou, Q. Luo, H. Chen, A. He and J. Wu, A discrete invasive weed optimization algorithm for solving traveling salesman problem, Neurocomputing, 151 (2015), 1227-1236. doi: 10.1016/j.neucom.2014.01.078. Google Scholar

show all references

References:
[1] R. E. Bellman and S. E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 2015. Google Scholar
[2]

P. Berman and M. Karpinski, 8/7-approximation algorithm for (1, 2)-TSP, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, Society for Industrial and Applied Mathematics, (2006), 641-648. doi: 10.1145/1109557.1109627. Google Scholar

[3]

S. M. Chen and C. Y. Chien, Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques, Expert Systems with Applications, 38 (2011), 14439-14450. doi: 10.1016/j.eswa.2011.04.163. Google Scholar

[4]

J. Cirasella, D. S. Johnson, L. A. McGeoch and W. Zhang, The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, Algorithm Engineering and Experimentation, 2153 (2011), 32-59. doi: 10.1007/3-540-44808-X_3. Google Scholar

[5]

S. Climer and W. Zhang, Cut-and-solve: An iterative search strategy for combinatorial optimization problems, Artificial Intelligence, 170 (2006), 714-738. doi: 10.1016/j.artint.2006.02.005. Google Scholar

[6]

G. A. Croes, A method for solving traveling-salesman problems, Operations Research, 6 (1958), 791-812. doi: 10.1287/opre.6.6.791. Google Scholar

[7]

S. O. Degertekin and L Lamberti, Heat transfer search algorithm for sizing optimization of truss structures, Latin American Journal of Solids and Structures, 14 (2017), 373-397. doi: 10.1590/1679-78253297. Google Scholar

[8]

G. Dong, W. W. Guo and K. Tickle, Solving the traveling salesman problem using cooperative genetic ant systems, Expert Systems with Applications, 39 (2012), 5006-5011. doi: 10.1016/j.eswa.2011.10.012. Google Scholar

[9]

B. Escario, J. F. Jimenez and J. M. Giron-Sierra, Ant colony extended: Experiments on the travelling salesman problem, Expert Systems with Applications, 42 (2015), 390-410. doi: 10.1016/j.eswa.2014.07.054. Google Scholar

[10]

P. Gang, I. Iimura and S. Nakayama, An evolutionary multiple heuristic with genetic local search for solving TSP, International Journal of Information Technology, 14 (2008), 1-11. Google Scholar

[11]

M. Gunduz and M. S. Kiran, A hierarchic approach based on swarm intelligence to solve the traveling salesman problem, Turkish Journal of Electrical Engineering & Computer Sciences, 23 (2015), 103-117. Google Scholar

[12]

T. Guo and Z. Michalewicz, Invor-over operator for the TSP-proceedings of the 5th parallel problem solving from nature conference, (1998), 1498-1520.Google Scholar

[13]

F. Han, Q. H. Ling and D. S. Huang, An improved approximation approach incorporating particle swarm optimization and a priori information into neural networks, Neural Computing and Applications, 19 (2010), 255-261. doi: 10.1007/s00521-009-0274-y. Google Scholar

[14]

K. Helsgaun, An effective implementation of the Lin Kernighan traveling salesman heuristic, European Journal of Operational Research, 126 (2000), 106-130. doi: 10.1016/S0377-2217(99)00284-2. Google Scholar

[15]

D. S. Huang and J. X. Du, A constructive hybrid structure optimization methodology for radial basis probabilistic neural networks, IEEE Transactions on Neural Networks, 19 (2008), 2099-2115. doi: 10.1109/TNN.2008.2004370. Google Scholar

[16]

J. E. Hunt and D. E. Cooke, Learning using an artificial immune system, Journal of Network and Computer Applications, 19 (1996), 189-212. doi: 10.1006/jnca.1996.0014. Google Scholar

[17]

D. S. Johnson and L. A. McGeoch, Experimental analysis of heuristics for the STSP, The Traveling Salesman Problem and its Variations, Springer, Boston, MA, 12 (2002), 369-443. doi: 10.1007/0-306-48213-4_9. Google Scholar

[18]

K. Jun-man and Z. Yi, Application of an improved ant colony optimization on generalized traveling salesman problem, Energy Procedia, 17 (2012), 319-325. doi: 10.1016/j.egypro.2012.02.101. Google Scholar

[19]

W. Junqiang and O. Aijia, A hybrid algorithm of ACO and delete-cross method for TSP, Industrial Control and Electronics Engineering (ICICEE), 2012 International Conference on. IEEE, (2012), 694-1696. Google Scholar

[20]

J. Junzhong, H. Zhen, L. Chunnian and D. Qigu, An ant colony algorithm based on Multiple-Grain representation for the traveling salesman problems, Journal of Computer Research and Development, 3 (2010), 9. Google Scholar

[21]

J. Kennedy and R. C. Eberhart, A discrete binary version of the particle swarm algorithm, Systems, Man, and Cybernetics, Computational Cybernetics and Simulation., 1997 IEEE International Conference on, IEEE, 5 (1997), 4104-4108.Google Scholar

[22]

S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671. Google Scholar

[23]

E. L. Lawler and D. E. Wood, Branch-and-bound methods: A survey, Operations Research, 14 (1966), 699-719. doi: 10.1287/opre.14.4.699. Google Scholar

[24]

S. Lin, Computer solutions of the traveling salesman problem, The Bell System Technical Journal, 44 (1965), 2245-2269. doi: 10.1002/j.1538-7305.1965.tb04146.x. Google Scholar

[25]

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. Google Scholar

[26]

X. Liu and C. Xiu, A novel hysteretic chaotic neural network and its applications, Neurocomputing, 70 (2007), 2561-2565. doi: 10.1016/j.neucom.2007.02.002. Google Scholar

[27]

M. Mahi, K. Baykan and H. Kodaz, A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem, Applied Soft Computing, 30 (2015), 484-490. doi: 10.1016/j.asoc.2015.01.068. Google Scholar

[28]

Y. Marinakis, M. Marinaki and G. Dounias, Honey bees mating optimization algorithm for the Euclidean traveling salesman problem, Information Sciences, 181 (2011), 4684-4698. doi: 10.1016/j.ins.2010.06.032. Google Scholar

[29]

T. A. S. Masutti and L. N. de Castro, A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem, Information Sciences, 179 (2009), 1454-1468. doi: 10.1016/j.ins.2008.12.016. Google Scholar

[30]

P. Merz and B. Freisleben, Genetic local search for the TSP: New results, Evolutionary Computation, 1997., IEEE International Conference on. IEEE, 159-164 1997. doi: 10.1109/ICEC.1997.592288. Google Scholar

[31]

E. Osaba, X. S. Yang, F. Diaz, P. Lopez-Garcia and R. Carballedo, An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems, Engineering Applications of Artificial Intelligence, 48 (2016), 59-71. doi: 10.1016/j.engappai.2015.10.006. Google Scholar

[32]

Z. A. Othman, A. I. Srour, A. R. Hamdan and P. Y. Ling, Performance water flow-like algorithm for TSP by improving its local search, International Journal of Advancements in Computing Technology, 5 (2013), 126. Google Scholar

[33]

X. Ouyang, Y. Zhou and Q. Luo, A novel discrete cuckoo search algorithm for spherical traveling salesman problem, Applied Mathematics & Information Sciences, 7 (2013), 777-784. doi: 10.12785/amis/070248. Google Scholar

[34]

R. Pasti and L. N. de Castro, A neuro-immune network for solving the traveling salesman problem, Neural Networks, 2006. IJCNN'06, International Joint Conference on IEEE, (pp. 3760-3766, 2006.Google Scholar

[35]

V. K. Patel and V. J. Savsani, Heat transfer search (HTS): A novel optimization algorithm, Nformation Sciences, 324 (2015), 217-246. doi: 10.1016/j.ins.2015.06.044. Google Scholar

[36]

M. Peker, B. EN and P. Y. Kumru, An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method, Turkish Journal of Electrical Engineering & Computer Sciences, 21 (2013), 2015-2036. doi: 10.3906/elk-1109-44. Google Scholar

[37]

A. Rodríguez and R. Ruiz, The effect of the asymmetry of road transportation networks on the traveling salesman problem, Computers & Operations Research, 39 (2012), 1566-1576. doi: 10.1016/j.cor.2011.09.005. Google Scholar

[38]

Y. Saji and M. E. Riffi, A novel discrete bat algorithm for solving the travelling salesman problem, Neural Computing and Applications, 27 (2016), 1853-1866. doi: 10.1007/s00521-015-1978-9. Google Scholar

[39]

F. Samanlioglu, W. G. Ferrell Jr and M. E. Kurz, A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem, Computers & Industrial Engineering, 55 (2008), 439-449. doi: 10.1016/j.cie.2008.01.005. Google Scholar

[40]

J. Shu, Z. Zhao and Q. Dai, Genetic algorithm for TSP, Operations Research and Management Science, 1 (2004), 4. Google Scholar

[41]

L. V. Snyder and M. S. Daskin, A random-key genetic algorithm for the generalized traveling salesman problem, European Journal of Operational Research, 174 (2006), 38-53. doi: 10.1016/j.ejor.2004.09.057. Google Scholar

[42]

M. A. Tawhid and V. Savsani, ϵ-constraint heat transfer search (ϵ-HTS) algorithm for solving multi-objective engineering design problems, Journal of Computational Design and Engineering, 5 (2018), 104-119. Google Scholar

[43]

G. Tejani, V. Savsani and V. Patel, Modified sub-population based heat transfer search algorithm for structural optimization, International Journal of Applied Metaheuristic Computing (IJAMC), 8 (2017), 1-23. Google Scholar

[44]

P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications, Society for Industrial and Applied Mathematics, 2014. doi: 10.1137/1.9781611973594. Google Scholar

[45]

C. F. Tsai, C. W. Tsai and C. C. Tseng, A new hybrid heuristic approach for solving large traveling salesman problem, Information Sciences, 166 (2004), 67-81. doi: 10.1016/j.ins.2003.11.008. Google Scholar

[46]

Y. Wang, The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem, Computers Industrial Engineering, 70 (2014), 124-133. doi: 10.1016/j.cie.2014.01.015. Google Scholar

[47]

J. Yang, X. Shi, M. Marchese and Y. Liang, An ant colony optimization method for generalized TSP problem, Progress in Natural Science, 18 (2008), 1417-1422. doi: 10.1016/j.pnsc.2008.03.028. Google Scholar

[48]

J. Yang, C Wu, H. P. Lee and Y. Liang, Solving traveling salesman problems using generalized chromosome genetic algorithm, Progress in Natural Science, 18 (2008), 887-892. doi: 10.1016/j.pnsc.2008.01.030. Google Scholar

[49]

W. Zhang and R. E. Korf, A study of complexity transitions on the asymmetric traveling salesman problem, Artificial Intelligence, 81 (1996), 223-239. doi: 10.1016/0004-3702(95)00054-2. Google Scholar

[50]

Y. Q. Zhou, Z. X. Huang and H. X. Liu, Discrete glowworm swarm optimization algorithm for TSP problem, Dianzi Xuebao(Acta Electronica Sinica), 40 (2012), 1164-1170. Google Scholar

[51]

Y. Zhou, Q. Luo, H. Chen, A. He and J. Wu, A discrete invasive weed optimization algorithm for solving traveling salesman problem, Neurocomputing, 151 (2015), 1227-1236. doi: 10.1016/j.neucom.2014.01.078. Google Scholar

Figure 1.  Comparison of obtained best solutions with the known optimum solutions
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Comparisons of mean value to the known best solutions
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The percentage deviation for the mean and the best solutions
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  The Graphical representation of the comparisons between the proposed DHTS and DIWO [51]
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Results of the DHTS algorithm for symmetric TSP instances from TSPLIB
TSP best worst mean std pDbest% pDavg% Optimal
eil51 426 428 426.5 0.707107 0 0.117371 426
berlin52 7542 7542 7542 0 0 0 7542
st70 675 675 675 0 0 0 675
pr76 108159 108159 108159 0 0 0 108159
eil76 538 541 538.7 1.05935 0 0.130112 538
kroA100 21282 21282 21282 0 0 0 21282
kroB100 22141 22272 22181.2 48.6091 0 0.181564 22141
kroC100 20749 20769 20751.4 6.310485 0 0.011567 20749
kroD100 21294 21390.74 21329.86 40.56808 0 0.168416 21294
kroE100 22068 22146.06 22099.21 33.72459 0 0.141432 22068
eil101 629 641 631.1 3.928528 0 0.333863 629
lin105 14379 14401 14381.2 6.957011 0 0.0153 14379
pr107 44303 44387 44319.8 35.41751 0 0.037921 44303
pr124 59030 59246 59083.6 62.49836 0 0.090801 59030
bier127 118282 118728 118502 195.1689 0 0.185996 118282
ch130 6111 6174 6138.7 15.78361 0.016367 0.469722 6110
pr136 96830 97785 97341.6 290.5234 0.059935 0.5886 96772
pr144 58537 58590 58544 17.02286 0 0.011958 58537
ch150 6528 6555 6543.7 10.56251 0 0.240502 6528
kroA150 26524 26670 26585.3 51.37671 0 0.231111 26524
kroB150 26141 26239 26187.9 37.07485 0.042097 0.221584 26130
pr152 73682 73818 73736.4 70.2301 0 0.073831 73682
rat195 2332 2344 2337 3.972125 0.38743 0.602669 2323
d198 15789 15867 15832 19.94437 0.057034 0.329531 15780
kroA200 29375 29483 29418.6 39.05324 0.023835 0.172296 29368
kroB200 29470 29618 29522.2 42.52529 0.112104 0.289432 29437
ts225 126643 127077 126802.3 158.4326 0 0.125787 126643
tsp225 3916 3940 3926.5 7.877535 0 0.268131 3916
pr226 80369 80652 80443.9 101.4062 0 0.093195 80369
gil262 2380 2401 2390.3 6.733828 0.084104 0.517241 2378
pr264 49135 49382 49184 103.3054 0 0.099725 49135
a280 2579 2608 2583.4 8.896941 0 0.170609 2579
pr299 48266 48481 48323.7 71.55736 0.155631 0.275363 48191
lin318 42171 42506 42351.1 112.7893 0.337862 0.766376 42029
rd400 15400 15521 15447.4 43.6379 0.778745 1.088934 15281
fl417 11876 11895 11886.9 6.590397 0.126465 0.218363 11861
pr439 107682 107998 107733.6 95.59312 0.4337 0.481827 107217
rat575 6845 6907 6855.2 18.37752 1.063044 1.213642 6773
rat783 8941 8956 8946.7 4.715224 1.533046 1.597774 8806
pr1002 262385 264241 263159.6 636.4372 1.289351 1.588373 259045
nrw1379 57724 57950 57846.8 57.97662 1.917441 2.134256 56638
Table Options

Download as excel

TSP best worst mean std pDbest% pDavg% Optimal
eil51 426 428 426.5 0.707107 0 0.117371 426
berlin52 7542 7542 7542 0 0 0 7542
st70 675 675 675 0 0 0 675
pr76 108159 108159 108159 0 0 0 108159
eil76 538 541 538.7 1.05935 0 0.130112 538
kroA100 21282 21282 21282 0 0 0 21282
kroB100 22141 22272 22181.2 48.6091 0 0.181564 22141
kroC100 20749 20769 20751.4 6.310485 0 0.011567 20749
kroD100 21294 21390.74 21329.86 40.56808 0 0.168416 21294
kroE100 22068 22146.06 22099.21 33.72459 0 0.141432 22068
eil101 629 641 631.1 3.928528 0 0.333863 629
lin105 14379 14401 14381.2 6.957011 0 0.0153 14379
pr107 44303 44387 44319.8 35.41751 0 0.037921 44303
pr124 59030 59246 59083.6 62.49836 0 0.090801 59030
bier127 118282 118728 118502 195.1689 0 0.185996 118282
ch130 6111 6174 6138.7 15.78361 0.016367 0.469722 6110
pr136 96830 97785 97341.6 290.5234 0.059935 0.5886 96772
pr144 58537 58590 58544 17.02286 0 0.011958 58537
ch150 6528 6555 6543.7 10.56251 0 0.240502 6528
kroA150 26524 26670 26585.3 51.37671 0 0.231111 26524
kroB150 26141 26239 26187.9 37.07485 0.042097 0.221584 26130
pr152 73682 73818 73736.4 70.2301 0 0.073831 73682
rat195 2332 2344 2337 3.972125 0.38743 0.602669 2323
d198 15789 15867 15832 19.94437 0.057034 0.329531 15780
kroA200 29375 29483 29418.6 39.05324 0.023835 0.172296 29368
kroB200 29470 29618 29522.2 42.52529 0.112104 0.289432 29437
ts225 126643 127077 126802.3 158.4326 0 0.125787 126643
tsp225 3916 3940 3926.5 7.877535 0 0.268131 3916
pr226 80369 80652 80443.9 101.4062 0 0.093195 80369
gil262 2380 2401 2390.3 6.733828 0.084104 0.517241 2378
pr264 49135 49382 49184 103.3054 0 0.099725 49135
a280 2579 2608 2583.4 8.896941 0 0.170609 2579
pr299 48266 48481 48323.7 71.55736 0.155631 0.275363 48191
lin318 42171 42506 42351.1 112.7893 0.337862 0.766376 42029
rd400 15400 15521 15447.4 43.6379 0.778745 1.088934 15281
fl417 11876 11895 11886.9 6.590397 0.126465 0.218363 11861
pr439 107682 107998 107733.6 95.59312 0.4337 0.481827 107217
rat575 6845 6907 6855.2 18.37752 1.063044 1.213642 6773
rat783 8941 8956 8946.7 4.715224 1.533046 1.597774 8806
pr1002 262385 264241 263159.6 636.4372 1.289351 1.588373 259045
nrw1379 57724 57950 57846.8 57.97662 1.917441 2.134256 56638
Table 2.  Comparison of average tours of DHTS with other state of the art algorithms for different TSP cases
Table Options

Download as excel

Table 3.  Comparison of DHTS with neuro-immune network [34], GCGA with local search [48], Massutti and Castro's method [29], GSA ant-colony system with PSO [3], HGA [46], ACE [9] and improved BA [31]
TSP Optimm DHTS neuro immune network(Pasti, & Castro, 2006) GCGA with local search(Yang et al., 2008) Massutti and Castro's method, (2009) GSA ant-colony system with PSO(Chen & Chien, 2011) HGA(Wang, 2014) ACE(Escario et al., 2015) improved BA(Osaba et al., 2016)
eil51 426 426.5 438.7 430 437.47 427.27 429.19 426.818 428.1
berlin52 7542 7542 8073.97 7932.5 7542 7544.37 7543.04 7542
st70 675 675 678 677.39 676.418 679.1
pr76 108159 108159 108942 108255.94 108251
eil76 538 538.7 556.1 551 556.33 540.2 546.06 538.311 548.1
kroA100 21282 21282 21868.47 21543 21522.73 21370.47 21312.45 21298.6 21445.3
kroB100 22141 22181.2 22853.6 22542 22661.47 22282.87 22506.4
kroC100 20749 20751.4 21231.6 21025 20971.23 20878.97 20812.22 21050
kroD100 21294 21329.8626 22027.87 21809 21697.37 21620.47 21344.67 21593.4
kroE100 22068 22099.2113 22815.5 22379 22715.63 22183.47 22349.6
eil101 629 631.1 654.83 646 648.63 635.23 644.82 633.619 646.4
lin105 14379 14381.2 14702.23 14544 14400.17 14406.37 14422.89 14385.5
pr107 44303 44319.8 44909 44341.67 44793.8
pr124 59030 59083.6 59141 59094.13 59412.1
bier127 118282 118502 121780.33 120412 120886.33 119421.83
ch130 6110 6138.7 6231.77 6282.4 6205.63 6130.277 6153.96
pr136 96772 97341.6 99505 97019.291 99351.2
pr144 58537 58544 58564 58537.22 58876.2
ch150 6528 6543.7 6753.2 6738.37 6557.69 6550
kroA150 26524 26585.3 27346.43 27298 27355.97 26899.2 26597.78
kroB150 26130 26187.9 26752.13 26682 26631.87 26448.33 26335.85
pr152 73682 73736.4 74582 73765.7 73766.8 74676.9
rat195 2323 2337 2420 2356.02
d198 15780 15832 16084 15963 15813.3
kroA200 29368 29418.6 30257.53 29910 30190.27 29738.73 29458.809
kroB200 29437 29522.2 30415.6 30627 30135 30035.23 29583.38
ts225 126643 126802.3 128016 128295.65
tsp225 3916 3926.5 3892.88
pr226 80369 80443.9 80969 80534.39
gil262 2378 2390.3 2515
pr264 49135 49184 50344 49163.26 50908.3
pr299 48191 48323.7 50812 49757.66 49674.1
lin318 42029 42351.1 43704.97 44191 43696.87 43002.9 42877.24
rd400 15281 15447.4 16420 16143.96
fl417 11861 11886.9 12243
pr439 107217 107733.6 113787 111209.97
rat575 6773 6855.2 7125 7115.67 6933.87
rat783 8806 8946.7 9326 9343.77 9079.23
Table Options

Download as excel

TSP Optimm DHTS neuro immune network(Pasti, & Castro, 2006) GCGA with local search(Yang et al., 2008) Massutti and Castro's method, (2009) GSA ant-colony system with PSO(Chen & Chien, 2011) HGA(Wang, 2014) ACE(Escario et al., 2015) improved BA(Osaba et al., 2016)
eil51 426 426.5 438.7 430 437.47 427.27 429.19 426.818 428.1
berlin52 7542 7542 8073.97 7932.5 7542 7544.37 7543.04 7542
st70 675 675 678 677.39 676.418 679.1
pr76 108159 108159 108942 108255.94 108251
eil76 538 538.7 556.1 551 556.33 540.2 546.06 538.311 548.1
kroA100 21282 21282 21868.47 21543 21522.73 21370.47 21312.45 21298.6 21445.3
kroB100 22141 22181.2 22853.6 22542 22661.47 22282.87 22506.4
kroC100 20749 20751.4 21231.6 21025 20971.23 20878.97 20812.22 21050
kroD100 21294 21329.8626 22027.87 21809 21697.37 21620.47 21344.67 21593.4
kroE100 22068 22099.2113 22815.5 22379 22715.63 22183.47 22349.6
eil101 629 631.1 654.83 646 648.63 635.23 644.82 633.619 646.4
lin105 14379 14381.2 14702.23 14544 14400.17 14406.37 14422.89 14385.5
pr107 44303 44319.8 44909 44341.67 44793.8
pr124 59030 59083.6 59141 59094.13 59412.1
bier127 118282 118502 121780.33 120412 120886.33 119421.83
ch130 6110 6138.7 6231.77 6282.4 6205.63 6130.277 6153.96
pr136 96772 97341.6 99505 97019.291 99351.2
pr144 58537 58544 58564 58537.22 58876.2
ch150 6528 6543.7 6753.2 6738.37 6557.69 6550
kroA150 26524 26585.3 27346.43 27298 27355.97 26899.2 26597.78
kroB150 26130 26187.9 26752.13 26682 26631.87 26448.33 26335.85
pr152 73682 73736.4 74582 73765.7 73766.8 74676.9
rat195 2323 2337 2420 2356.02
d198 15780 15832 16084 15963 15813.3
kroA200 29368 29418.6 30257.53 29910 30190.27 29738.73 29458.809
kroB200 29437 29522.2 30415.6 30627 30135 30035.23 29583.38
ts225 126643 126802.3 128016 128295.65
tsp225 3916 3926.5 3892.88
pr226 80369 80443.9 80969 80534.39
gil262 2378 2390.3 2515
pr264 49135 49184 50344 49163.26 50908.3
pr299 48191 48323.7 50812 49757.66 49674.1
lin318 42029 42351.1 43704.97 44191 43696.87 43002.9 42877.24
rd400 15281 15447.4 16420 16143.96
fl417 11861 11886.9 12243
pr439 107217 107733.6 113787 111209.97
rat575 6773 6855.2 7125 7115.67 6933.87
rat783 8806 8946.7 9326 9343.77 9079.23
Table 4.  DHTS comparison with DIWO [51]
TSP PD % average
DIWO (Zhou et al., 2015) Proposed DHTS
eil51 0.6999 0.117371
berlin52 0.0313 0
st70 0.3125 0
kroA100 0.0375 0
kroB100 0.8816 0.181564
pr107 0.4837 0.037921
pr136 0.94 0.5886
kroA150 0.778 0.231111
kroB150 0.3229 0.221584
d198 0.6691 0.329531
tsp225 2.3949 0.268131
pr226 0.2238 0.093195
rd400 2.4229 1.088934
pr1002 3.1873 1.588373
Table Options

Download as excel

TSP PD % average
DIWO (Zhou et al., 2015) Proposed DHTS
eil51 0.6999 0.117371
berlin52 0.0313 0
st70 0.3125 0
kroA100 0.0375 0
kroB100 0.8816 0.181564
pr107 0.4837 0.037921
pr136 0.94 0.5886
kroA150 0.778 0.231111
kroB150 0.3229 0.221584
d198 0.6691 0.329531
tsp225 2.3949 0.268131
pr226 0.2238 0.093195
rd400 2.4229 1.088934
pr1002 3.1873 1.588373
[1]

Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029
[2]

Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435
[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]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457
[5]

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

Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1
[7]

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

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

Liangliang Sun, Fangjun Luan, Yu Ying, Kun Mao. Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1431-1448. doi: 10.3934/jimo.2016081
[10]

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

Grégoire Allaire, Zakaria Habibi. Second order corrector in the homogenization of a conductive-radiative heat transfer problem. Discrete & Continuous Dynamical Systems - B, 2013, 18 (1) : 1-36. doi: 10.3934/dcdsb.2013.18.1
[12]

Mao Chen, Xiangyang Tang, Zhizhong Zeng, Sanya Liu. An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2018164
[13]

T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53
[14]

Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157
[15]

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

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, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030
[17]

Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial & Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543
[18]

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[19]

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

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647

 Impact Factor: 

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences