# American Institute of Mathematical Sciences

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

## Discrete heat transfer search for solving travelling salesman problem

 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.

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:

show all references

##### References:
Comparison of obtained best solutions with the known optimum solutions
Comparisons of mean value to the known best solutions
The percentage deviation for the mean and the best solutions
The Graphical representation of the comparisons between the proposed DHTS and DIWO [51]
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
 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
Comparison of average tours of DHTS with other state of the art algorithms for different TSP cases
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
 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
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
 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] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [2] Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 [3] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [4] M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 [5] Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002 [6] Chueh-Hsin Chang, Chiun-Chuan Chen, Chih-Chiang Huang. Traveling wave solutions of a free boundary problem with latent heat effect. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021028 [7] Marek Macák, Róbert Čunderlík, Karol Mikula, Zuzana Minarechová. Computational optimization in solving the geodetic boundary value problems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 987-999. doi: 10.3934/dcdss.2020381 [8] Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021003 [9] Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 [10] Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046 [11] Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018 [12] Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117 [13] Larissa Fardigola, Kateryna Khalina. Controllability problems for the heat equation on a half-axis with a bounded control in the Neumann boundary condition. Mathematical Control & Related Fields, 2021, 11 (1) : 211-236. doi: 10.3934/mcrf.2020034 [14] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [15] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [16] Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391 [17] Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135 [18] Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006 [19] Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134 [20] Mario Pulvirenti, Sergio Simonella. On the cardinality of collisional clusters for hard spheres at low density. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021021

Impact Factor:

## Tools

Article outline

Figures and Tables