The Traveling Salesman Problem (TSP) is one of the most widely studied NP-hard combinatorial optimization problems.
Traditional Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA) trapped into the local minimum
without reaching the optimum solution. To avoid this problem, we propose the new Discrete Velocity Propelled Averaged Crossover
(DVPAC) to reinforce the diversity in the search space while keeping the optimum searching direction. This will be applied in solving
used in solving practical very large scale TSP in different countries. Practical experiment shows that our DVPAC can provide very
satisfactory solutions and outperforms other algorithms
Tarek Aboueldahab : was born in April 1971
and was obtained Bachelor degree in 1993
and Master degree in 1998 from electronics
and communications department, Faculty of
Engineering, Cairo University, He is the head
manager of Research and Development in
the Ministry of Transport, Cairo, Egypt. He is
also a member in International Congress of
Global science and Technology. His field of
interest includes artificial intelligence techniques and their relevant
applications.
Abdul-Hadi N. Ahmed : is a Prof.,
obtaining both M.Sc. and Ph.D.
degrees from Florida State Uni. In USA
and has published over 100 articles in
prestigious journals around the world in
many areas such as probability,
stochastic processes, reliability
engineering, operational research and
mathematical statistics. He is a holder
of King Faisal award of mathematics
In this paper, we proposed a new hybrid algorithm based
on particle swarm optimization, genetic algorithm, and
simulated annealing to solve large scale TSP. This
algorithm is inspired by Discrete Velocity Propelled
Averaged Crossover (DVPAC) depending on dividing the swarm into discarded and breeding portions. Well known
benchmarking countries have been utilized for proving its
efficiency in dealing with large scale TSP. In future work,
this algorithm will be extended form the standard TSP to
deal with practical cases of large number of cities like
Railway Traveler Salesman Problem (RTSP). Also, it
could be applied to other large scale practical real life
problems like fuel consumption and petrol delivery
system.
[1] M. Bellmore and G. L. Nemhauser, "The traveling
salesman problem: a survey", Operation Research, vol.
16, 1986, pp.538-558.
[2] G. Reinelt, The Traveling Salesman: Computational
Solutions for TSP Applications. Springer-Verlag,1994.
[3] D. S. Johnson and L. A. McGeoch, "The traveling
salesman problem: a case study in local optimization",
Local Search in Combinatorial Optimization, Wiley,
1997, pp.215-310.
[4] E. H. L. Aarts, J. H. M. Korst, and P. J. M. Laarhoven, "A
quantitative analysis of the simulated annealing
algorithm: a case study for the traveling salesman
problem", J. of Stats Phys, vol. 50, 1988, pp.189-206.
[5] Knox, J. (1994). "Particle Swarm Optimization
performance on the symmetric traveling salesman
problem" Computers& Operations Research, 21 (8), 867-
876 .
[6] Johnson, D. S., & McGeoch, L. A. (1997). The traveling
salesman problem: A case study in local optimization.
Local search in combinatorial optimization, 1 , 215-310 .
[7] Çunka ¸S, M., & Özsa ?glam, M. Y. (2009).
A comparative study on particle swarm optimization and
genetic algorithms for traveling salesman problems."
Cybernetics and Systems: An International Journal, 40
(6), 490-507.
[8] Fang, L., Chen, P., & Liu, S. (2007). "Particle swarm
optimization with simulated annealing for TSP". In
Proceedings of the 6th WSEAS international conference
on artificial intelligence, knowledge engineering and data
bases (AIKED'07) (pp. 206-210)
[9] Chen, S. M., & Chien, C. Y. (2011). Solving the traveling
salesman problem based on the genetic simulated
annealing ant colony system with particle swarm
optimization techniques. Expert Systems with
Applications, 38 (12), 14439-14450
[10] Katayama, K. , Sakamoto, H. , & Narihisa H. (20 0 0).
The efficiency of hybrid mutation genetic algorithm for
the travelling salesman problem .Mathematical and
Computer Modelling, 31 (10), 197-203.
[11] Wang, J., Ersoy, O. K. , He, M. , & Wang, F. (2016).
"Multi-offspring genetic algorithm and its application to
the traveling salesman problem" Applied Soft Computing,
43, 415-423 .
[12] Tarek Aboueldahab and Mahumod Fakhreldin. Prediction
of Stock Market Indices using Hybrid Genetic Algorithm/
Particle Swarm Optimization with Perturbation Term
ICSI 2011: International Conference on swarm
intelligence
[13] T. Aboueldahab "Short term wind speed prediction using
a new hybrid model with passive congregation term".
International Journal of Computers and Technology, vol.
3, no. 2, pp. 211-217, October 2012.
[14] Kirkpatrick, S., Gelatt, C. D., &Vecchi, M. P. (1983).
"Optimization by simulated annealing." Science, 220
(4598), 671-680.
[15] KENNEDY J. and EBERHART R.C. Particle swarm
optimization, Proceedings of IEEE International
Conference on Neural Networks, Piscataway, NJ,
pp.1942-1948, 1995.
[16] H. Holland, Adaptation in Natural and Artificial Systems,
Ann Arbor, The University of Michigan Press, 1975.
[17] SETTLES M., and SOULE T., Breeding Swarm: A
ga/pso hybrid, In Genetic and Evolutionary Computation
Conference (GECCO). pp. 161-168. Washington, USA
2005.
[18] SETTLES M., NATHAN P., and SOULE T., "Breeding
Swarms: A New Approach to Recurrent Neural Network
Training". Proceeding of the Genetic and Evolutionary
Computation Conference (GECCO-2005). pp. 185- 192,
2005.
[19] The traveling salesman problem. Available in:
http://www.tsp.gatech.edu/.
[20] http://issr.cu.edu.eg/en/research/solving-researchproblems/
salesmantravelling/
