# 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] 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