Source: http://aimsciences.org/article/doi/10.3934/mfc.2018012
Timestamp: 2019-04-24 19:59:56+00:00

Document:
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.
 R. E. Bellman and S. E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 2015.
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.
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.
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.
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.
G. A. Croes, A method for solving traveling-salesman problems, Operations Research, 6 (1958), 791-812. doi: 10.1287/opre.6.6.791.
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.
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.
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.
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.
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.
T. Guo and Z. Michalewicz, Invor-over operator for the TSP-proceedings of the 5th parallel problem solving from nature conference, (1998), 1498-1520.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
J. Shu, Z. Zhao and Q. Dai, Genetic algorithm for TSP, Operations Research and Management Science, 1 (2004), 4.
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.
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.
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.
P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications, Society for Industrial and Applied Mathematics, 2014. doi: 10.1137/1.9781611973594.
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.
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.
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.
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.
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.
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.
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.

References: V. 
 V. 
 V. 
 V. 
 V. 
 V.