Discrete heat transfer search for solving travelling salesman problem

Poonam Savsani; Mohamed A. Tawhid

doi:10.3934/mfc.2018012

Article Contents

2018, Volume 1, Issue 3: 265-280. Doi: 10.3934/mfc.2018012

This issue Previous Article Total

$\{k\}$

-domination in special graphs Next Article Improve symmetry of arbiter in APUF

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
^* Corresponding author: Mohamed A. Tawhid

Received: October 31, 2017

Revised: January 31, 2018

Published: July 2018

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 1^st author is supported by NSERC.

Abstract Full Text(HTML) Figure(4) / Table(4) Related Papers Cited by

Abstract

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:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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

| Show Table

DownLoad: CSV

Table 2. Comparison of average tours of DHTS with other state of the art algorithms for different TSP cases

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Table 4. DHTS comparison with DIWO [51]

TSP	PD % average
TSP	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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. E. Bellman and S. E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 2015.
[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.
[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.
[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.
[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.
[6]	G. A. Croes, A method for solving traveling-salesman problems, Operations Research, 6 (1958), 791-812. doi: 10.1287/opre.6.6.791.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[40]	J. Shu, Z. Zhao and Q. Dai, Genetic algorithm for TSP, Operations Research and Management Science, 1 (2004), 4.
[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.
[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.
[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.
[44]	P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications, Society for Industrial and Applied Mathematics, 2014. doi: 10.1137/1.9781611973594.
[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.
[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.
[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.
[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.
[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.
[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.
[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.