Solution of Multiple Travelling Salesman Problem using Particle Swarm Optimization based Algorithms
DOI:
https://doi.org/10.18201//ijisae.2019252784Keywords:
2-opt algorithm, grasp algorithm, multiple travelling salesman problem, particle swarm optimizationAbstract
Nowadays, the systems that are inspired by biological structures have gained importance and attracted the attention of researchers. The Multiple Travelling Salesman Problem (MTSP) is an extended version of the TSP. The aim in the MTSP is to find the tours for m salesmen, who all start and end at the depot, such that each intermediate node is visited exactly once and the total cost of visiting nodes is minimized. The Particle Swarm Optimization (PSO) algorithm which is a meta-heuristic algorithm based on the social behaviour of birds. In this article, 2 algorithms based on PSO, called APSO and HAPSO, were proposed to solve the MTSP. The APSO algorithm is based on the PSO and 2-opt algorithms, the path-relink and swap operators. While the HAPSO algorithm is based on the GRASP, PSO and 2-opt algorithms, the path-relink and swap operators. In the experiments, 5 TSP instances are used and the algorithms are compared with the GA and ACO algorithms. According to the results, the HAPSO algorithm has the better performance than the other algorithms on the most instances. Moreover the HAPSO algorithm produces more stable results than the APSO algorithm and the performance of the HAPSO algorithm is better in all the MTSP instances. Therefore, the HAPSO algorithm is more robust than the APSO algorithm.
Downloads
References
V.V. Nabiyev, Yapay zeka: insan-bilgisayar etkileşimi, Seçkin Yayıncılık, 2012.
M. Dorigo, T. Stützle, Ant Colony Optimization, Bradford Book, 2004.
G. Gutin, A.P. Punnen, The traveling salesman problem and its variations, Springer Science & Business Media, 2006.
A.E. Carter, C.T. Ragsdale, Scheduling pre-printed newspaper advertising inserts using genetic algorithms, Omega, 30 (2002) 415-421.
S. Gorenstein, Printing press scheduling for multi-edition periodicals, Management Science, 16 (1970) B-373-B-383.
A. Baykasoğlu, B.K. Özbel, Multiple traveling salesman game for cost allocation: a case problem for school bus services, in: LM-SCM 2016 XIV. International Logistics and Supply Chain Congress, 2016, pp. 64.
F. Wex, G. Schryen, S. Feuerriegel, D. Neumann, Emergency response in natural disaster management: Allocation and scheduling of rescue units, European Journal of Operational Research, 235 (2014) 697-708.
T. Zhang, W. Gruver, M.H. Smith, Team scheduling by genetic search, in: Intelligent Processing and Manufacturing of Materials, 1999. IPMM'99. Proceedings of the Second International Conference on, IEEE, 1999, pp. 839-844.
D.S. Mankowska, F. Meisel, C. Bierwirth, The home health care routing and scheduling problem with interdependent services, Health care management science, 17 (2014) 15-30.
G.A. Croes, A method for solving traveling-salesman problems, Operations research, 6 (1958) 791-812.
J. Kennedy, R. Eberhart, Particle Swarm Optimization, in: IEEE International Conference on Neural Networks, 1995, pp. 1942-1948.
J.H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, MIT press, 1992.
T.A. Feo, M.G. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations research letters, 8 (1989) 67-71.
D. Karaboga, B. Basturk, A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, Journal of global optimization, 39 (2007) 459-471.
M. Dorigo, L.M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, Evolutionary Computation, IEEE Transactions on, 1 (1997) 53-66.
Ş. Gülcü, H. Kodaz, A novel parallel multi-swarm algorithm based on comprehensive learning particle swarm optimization, Engineering Applications of Artificial Intelligence, 45 (2015) 33-45.
Ş. Gülcü, M. Mahi, Ö.K. Baykan, H. Kodaz, A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem, Soft Computing, 22 (2018) 1669-1685.
A.E. Carter, Design and application of genetic algorithms for the multiple traveling salesperson assignment problem, in, Citeseer, 2003.
P. Junjie, W. Dingwei, An ant colony optimization algorithm for multiple travelling salesman problem, in: Innovative Computing, Information and Control, 2006. ICICIC'06. First International Conference on, IEEE, 2006, pp. 210-213.
J.-w. Dang, Y.-p. Wang, S.-x. Zhao, Study on a novel genetic algorithm for the combinatorial optimization problem, in: Control, Automation and Systems, 2007. ICCAS'07. International Conference on, IEEE, 2007, pp. 2538-2541.
T. Bektas, The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34 (2006) 209-219.
T. Bektaş, Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing, European Journal of Operational Research, 216 (2012) 83-93.
R. Ponraj, G. Amalanathan, Optimizing multiple travelling salesman problem considering the road capacity, Journal of computer science, 10 (2014) 680.
S. Yuan, B. Skinner, S. Huang, D. Liu, A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms, European Journal of Operational Research, 228 (2013) 72-82.
M. Hou, D. Liu, A novel method for solving the multiple traveling salesmen problem with multiple depots, Chinese science bulletin, 57 (2012) 1886-1892.
A. Király, J. Abonyi, Redesign of the supply of mobile mechanics based on a novel genetic optimization algorithm using Google Maps API, Engineering Applications of Artificial Intelligence, 38 (2015) 122-130.
R. Necula, M. Breaban, M. Raschip, Tackling the bi-criteria facet of multiple traveling salesman problem with ant colony systems, in: 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE, 2015, pp. 873-880.
H. Zhou, M. Song, W. Pedrycz, A comparative study of improved GA and PSO in solving multiple traveling salesmen problem, Applied Soft Computing, 64 (2018) 564-580.
Q. Yu, D. Wang, D. Lin, Y. Li, C. Wu, A novel two-level hybrid algorithm for multiple traveling salesman problems, in: International Conference in Swarm Intelligence, Springer, 2012, pp. 497-503.
M. Shabanpour, M. Yadollahi, M.M. Hasani, A New Method to Solve the Multi Traveling Salesman Problem with the Combination of Genetic Algorithm and Clustering, IJCSNS, 17 (2017) 221.
T. Kalaycı, Yapay zeka teknikleri kullanan üç boyutlu grafik yazılımları için “extensıble 3d”(x3d) ile bir altyapı oluşturulması ve gerçekleştirimi, Yüksek Lisans Tezi, Ege Üniversitesi, (2006).
D. Donald, Traveling salesman problem, theory and applications, InTech, Rijeka, 2011.
G. Reinelt, TSPLIB—A traveling salesman problem library, ORSA journal on computing, 3 (1991) 376-384.
G. Reinelt, TSP library, in, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/, 1995, last accessed march 2018.
O. Bozorg-Haddad, M. Solgi, H.A. Loáiciga, Meta-heuristic and evolutionary algorithms for engineering optimization, John Wiley & Sons, 2017.
M. Nouiri, A. Bekrar, A. Jemai, S. Niar, A.C. Ammari, An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem, Journal of Intelligent Manufacturing, 29 (2018) 603-615.
A. AminShokravi, H. Eskandar, A.M. Derakhsh, H.N. Rad, A. Ghanadi, The potential application of particle swarm optimization algorithm for forecasting the air-overpressure induced by mine blasting, Engineering with Computers, 34 (2018) 277-285.
S. Gulcu, H. Kodaz, The estimation of the electricity energy demand using particle swarm optimization algorithm: A case study of Turkey, Procedia computer science, 111 (2017) 64-70.
J.H. Lee, J.-Y. Song, D.-W. Kim, J.-W. Kim, Y.-J. Kim, S.-Y. Jung, Particle swarm optimization algorithm with intelligent particle number control for optimal design of electric machines, IEEE Transactions on Industrial Electronics, 65 (2018) 1791-1798.
M. Hajihassani, D.J. Armaghani, R. Kalatehjari, Applications of particle swarm optimization in geotechnical engineering: a comprehensive review, Geotechnical and Geological Engineering, 36 (2018) 705-722.
G.-d. Qu, Z.-h. Lou, Application of particle swarm algorithm in the optimal allocation of regional water resources based on immune evolutionary algorithm, Journal of Shanghai Jiaotong University (Science), 18 (2013) 634-640.
H.H. Balci, J.F. Valenzuela, Scheduling electric power generators using particle swarm optimization combined with the Lagrangian relaxation method, International Journal of Applied Mathematics and Computer Science, 14 (2004) 411-421.
S. Gaur, S. Ch, D. Graillot, B.R. Chahar, D.N. Kumar, Application of artificial neural networks and particle swarm optimization for the management of groundwater resources, Water resources management, 27 (2013) 927-941.
Y. Zhang, D.-w. Gong, J. Cheng, Multi-objective particle swarm optimization approach for cost-based feature selection in classification, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 14 (2017) 64-75.
J. Izquierdo, I. Montalvo, R. Pérez, V.S. Fuertes, Design optimization of wastewater collection networks by PSO, Computers & Mathematics with Applications, 56 (2008) 777-784.
E.-G. Talbi, Metaheuristics: from design to implementation, John Wiley & Sons, 2009.
M. Gendreau, J.-Y. Potvin, Handbook of metaheuristics, Springer, 2010.
E. Alba, Parallel metaheuristics: a new class of algorithms, John Wiley & Sons, 2005.
D.S. Johnson, L.A. McGeoch, The traveling salesman problem: A case study in local optimization, Local search in combinatorial optimization, 1 (1997) 215-310.
F. Glover, Parametric combinations of local job shop rule, in: ONR Research Memorandum, Carnegie Mellon University, Pittsburgh, PA, 1963.
M.G.C. Resende, C.C. Ribeiro, F. Glover, R. Martí, Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications, in: M. Gendreau, J.-Y. Potvin (Eds.) Handbook of Metaheuristics, Springer US, Boston, MA, 2010, pp. 87-107.
M. Latah, Solving multiple TSP problem by K-means and crossover based modified ACO algorithm, IJERT, 5 (2016) 430-434.
Downloads
Published
How to Cite
Issue
Section
License
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
