Single Objective Mayfly Algorithm with Balancing Parameter for Multiple Traveling Salesman Problem

Keywords: MTSP, Optimization Algorithm, Mayfly Algorithm, Balancing Parameter

Abstract

The Multiple Travelling Salesman Problem (MTSP) is a challenging combinatorial problem that involves multiple salesman visiting a set of cities, each exactly once, starting and ending at the same depot. The aim is to determine the optimal route with minimal cost and node cuts for each salesman while ensuring that at least one salesman visits each city. As the problem is NP-Hard, a single-objective metaheuristic algorithm, called the Mayfly Algorithm, inspired by the collective behavior of mayflies, is employed to solve the problem using the TSPlib95 test data. Since the Mayfly Algorithm employs a single fitness function, a balancing parameter is added to perform multiobjective optimization. Three balancing parameters in the optimization process: SumRoute represents the total cost of all salesmen travelling, StdRoute balances each salesman cost, and StdNodes balances the number of nodes for each salesman. The values of these parameters are determined based on the results of various tests, as they significantly impact the MTSP optimization process. With the appropriate parameter values, the single-objective Mayfly Algorithm can produce optimal solutions and avoid premature convergence. Overall, the Mayfly Algorithm shows promise as a practical approach to solving the MTSP problem. Using multiobjective optimization with balancing parameters enables the algorithm to achieve optimal results and avoid convergence issues. The TSPlib95 dataset provides a robust testing ground for evaluating the algorithm’s effectiveness, demonstrating its ability to solve MTSP effectively with multiple salesman.

Downloads

Download data is not yet available.

Author Biographies

YOGA DWI WAHYU NUGRAHA, Institut Sains dan Teknologi Terpadu Surabaya

YOGA DWI WAHYU NUGRAHA was born in Lamongan on May 4, 1994. He completed his bachelor’s degree in Information Engineering in 2016 at the Islamic University of Lamongan, East Java. Currently, he is pursuing a postgraduate program in Information Technology at the Integrated Science and Technology Institute (ISTTS) of Surabaya, East Java.

He currently works as a teacher at Vocational High School 1 Beji, Pasuruan, teaching Informatics. In addition to his teaching role, he is also conducting research in the field of soft computing. His research focuses on the development of optimization algorithms for logistics services.

HENDRAWAN ARMANTO, Institut Sains dan Teknologi Terpadu Surabaya

HENDRAWAN ARMANTO was born at Surabaya, 27 February 1986. His Bachelor Degree with a major in Computer Science graduated from Sekolah Tinggi Teknik Surabaya, Indonesia in 2008 and he got his master’s degree with a major in Information Technology in 2013 from the same university.

Right now, he is a LECTURER and RESEARCHER at Institut Sains dan Teknologi Terpadu  Surabaya but before he has experience as SOFTWARE DEVELOPER, GAME DEVELOPER, and DATA ANALYST. As a researcher, he publishes some articles in Conferences or Jurnal. His last 3 papers are “Facial Expression Recognition with CNN and Wavelet”, “GPU Programming based Genetic Algorithm and Whale Optimization Library”, and “MVPA And GA Comparison for State Space Optimization at Classic Tetris Game Agent Problem”. His current and previous research is “Game”, “Evolutionary Algorithm”, and “Artificial Intelligence”.

Mr. Armanto is a member of the Association for Computing Machinery (ACM) from 2012 until now.

YOSI KRISTIAN, Institut Sains dan Teknologi Terpadu Surabaya

YOSI KRISTIAN receive his bachelor degree in computer science and master degree in information technology from Sekolah Tinggi Teknik Surabaya

(STTS), Surabaya, Indonesia, in 2004 and 2008 respectively. He receive his Ph.D degree on Electrical Engineering from Institut Teknologi Sepuluh Nopember (ITS), Surabaya, Indonesia. He joined as a faculty member in STTS since 2004, and currently as an Associate Profesor in Department of Computer Science. His current research interests include Machine Learning, Intelligent System, and Computer Vision.

References

[1] O. Cheikhrouhou and I. Khoufi, “A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy,” Computer Science Review , vol. 40, p. 100369, May 2021, doi: 10.1016/j.cosrev.2021.100369.
[2] K. -M. Lo, W. -Y. Yi, P. -K. Wong, K. -S. Leung, Y. Leung, and S. -T. Mak, “A Genetic Algorithm with New Local Operators for Multiple Traveling Salesman Problems:,” IJCIS , vol. 11, no. 1, p. 692, 2018, doi: 10.2991/ijcis.11.1.53.
[3] G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,” European Journal of Operational Research , vol. 59, no. 2, pp. 231–247, Jun. 1992, doi: 10.1016/0377-2217(92)90138-Y.
[4] SD Gulcu and HK Ornek, “Solution of Multiple Traveling Salesman Problem using Particle Swarm Optimization based Algorithms,” International Journal of Intelligent Systems and Applications in Engineering .
[5] J. Wang, OK Ersoy, M. He, and F. Wang, “Multi-offspring genetic algorithm and its application to the traveling salesman problem,” Applied Soft Computing , vol. 43, pp. 415–423, Jun. 2016, doi: 10.1016/j.asoc.2016.02.021.
[6] 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 , vol. 48, pp. 59–71, Feb. 2016, doi: 10.1016/j.engappai.2015.10.006.
[7] Y. Saji and M. Barkatou, “A discrete bat algorithm based on Lévy flights for Euclidean traveling salesman problem,” Expert Systems with Applications , vol. 172, p. 114639, Jun. 2021, doi: 10.1016/j.eswa.2021.114639.
[8] FS Gharehchopogh and B. Abdollahzadeh, “An efficient harris hawk optimization algorithm for solving the traveling salesman problem,” Cluster Comput , vol. 25, no. 3, pp. 1981–2005, Jun. 2022, doi: 10.1007/s10586-021-03304-5.
[9] X. Xu, H. Yuan, M. Liptrott, and M. Trovati, “Two phase heuristic algorithm for the multiple-travelling salesman problem,” Soft Comput , vol. 22, no. 19, pp. 6567–6581, Oct. 2018, doi: 10.1007/s00500-017-2705-5.
[10] K. Zervoudakis and S. Tsafarakis, “A mayfly optimization algorithm,” Computers & Industrial Engineering , vol. 145, p. 106559, Jul. 2020, doi: 10.1016/j.cie.2020.106559.
[11] M. Mahrach, G. Miranda, C. León, and E. Segredo, “Comparison between Single and Multiobjective Evolutionary Algorithms to Solve the Knapsack Problem and the Traveling Salesman Problem,” Mathematics , vol . 8, no. 11, p. 2018, Nov. 2020, doi: 10.3390/math8112018.
[12] G. Gutin and AP Punnen, Eds., The traveling salesman problem and its variations . in Combinatorial optimization, no. 12. New York: Springer, 2007.
[13] AV Eremeev and YV Kovalenko, “A memetic algorithm with optimal recombination for the asymmetric traveling salesman problem,” Memetic Comp. , vol. 12, no. 1, pp. 23–36, Mar. 2020, doi: 10.1007/s12293-019-00291-4.
[14] X. Chen, P. Zhang, G. Du, and F. Li, “Ant Colony Optimization Based Memetic Algorithm to Solve Bi-Objective Multiple Traveling Salesmen Problem for Multi-Robot Systems,” IEEE Access , vol . 6, pp. 21745–21757, 2018, doi: 10.1109/ACCESS.2018.2828499.
[15] Z. Lu, K. Zhang, J. He, and Y. Niu, “Applying K-means Clustering and Genetic Algorithm for Solving MTSP,” in Bio-inspired Computing – Theories and Applications , M. Gong, L. Pan, T. Song, and G. Zhang, Eds., in Communications in Computer and Information Science, vol. 682. Singapore: Springer Singapore, 2016, pp. 278–284. doi: 10.1007/978-981-10-3614-9_34.
[16] S. Karimah, AW Widodo, and I. Cholissodin, “Optimization of Multiple Traveling Salesman Problems in Drinking Water Distribution Using Genetic Algorithms (Case Study: UD. Tosa Malang)”.
[17] MA Al-Furhud and Z. Hussain, “Genetic Algorithms for the Multiple Traveling Salesman Problem,” IJACSA , vol. 11, no. 7, 2020, doi: 10.14569/IJACSA.2020.0110768.
[18] J. Kaabi and Y. Harrath, “Permutation rules and genetic algorithms to solve the traveling salesman problem,” Arab Journal of Basic and Applied Sciences , vol. 26, no. 1, pp. 283–291, Jan. 2019, doi: 10.1080/25765299.2019.1615172.
[19] E. Ghadiri Sufi, S. Soltani - Mohammadi, and H. Mokhtari, “Optimizing the exploratory drilling rig route based on the Multiobjective Multiple Traveling Salesman Problem,” Int J Min Geo Eng , no. Online First, May 2022, doi: 10.22059/ijmge.2022.332178.594934.
[20] Y. Harrath, AF Salman, A. Alqaddoumi, H. Hasan, and A. Radhi, “A hybrid novel approach for solving the multiple traveling salesmen problem,” Arab Journal of Basic and Applied Sciences , vol. 26, no. 1, pp. 103–112, Jan. 2019, doi: 10.1080/25765299.2019.1565193.
[21] B. Uddin and T. Uddin, “Solving Constraint Satisfaction Problems in TSP using GA and DFS algorithms,” vol. 7, no. 11, 2020.
[22] H. Zhou, M. Song, and W. Pedrycz, “A comparative study of improved GA and PSO in solving multiple traveling salesmen problems,” Applied Soft Computing , vol. 64, pp. 564–580, Mar. 2018, doi: 10.1016/j.asoc.2017.12.031.
[23] P. Venkatesh, G. Srivastava, and A. Singh, “A general variable neighborhood search algorithm for the k-traveling salesman problem,” Procedia Computer Science , vol. 143, pp. 189–196, 2018, doi: 10.1016/j.procs.2018.10.375.
[24] P. Venkatesh and A. Singh, “Two metaheuristic approaches for the multiple traveling salesperson problem,” Applied Soft Computing , vol. 26, pp. 74–89, Jan. 2015, doi: 10.1016/j.asoc.2014.09.029.
[25] Y. Huang, X. -N. Shen, and X. You, “A discrete shuffled frog-leaping algorithm based on heuristic information for traveling salesman problems,” Applied Soft Computing , vol. 102, p. 107085, Apr. 2021, doi: 10.1016/j.asoc.2021.107085.
[26] K. Panwar and K. Deep, “Discrete Gray Wolf Optimizer for symmetric traveling salesman problem,” Applied Soft Computing , vol. 105, p. 107298, Jul. 2021, doi: 10.1016/j.asoc.2021.107298.
[27] Z. Daoqing and J. Mingyan, “Parallel discrete lion swarm optimization algorithm for solving traveling salesman problems,” J. of Syst. Eng. electrons. , vol. 31, no. 4, pp. 751–760, Aug. 2020, doi: 10.23919/JSEE.2020.000050.
[28] K. Michalak, “Evolutionary Algorithm Using Random Immigrants for the Multiobjective Traveling Salesman Problem,” Procedia Computer Science , vol. 192, pp. 1461–1470, 2021, doi: 10.1016/j.procs.2021.08.150.
[29] T. Bhattacharyya, B. Chatterjee, PK Singh, JH Yoon, ZW Geem, and R. Sarkar, “Mayfly in Harmony: A New Hybrid Meta-Heuristic Feature Selection Algorithm,” IEEE Access , vol . 8, pp. 195929–195945, 2020, doi: 10.1109/ACCESS.2020.3031718.
[30] Reinelt, G., 1995. Tsplib95. Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR), Heidelberg, 338, pp.1-16.
Published
2023-07-08
How to Cite
[1]
YOGA DWI WAHYU NUGRAHA, HENDRAWAN ARMANTO, and YOSI KRISTIAN, “Single Objective Mayfly Algorithm with Balancing Parameter for Multiple Traveling Salesman Problem”, j.electron.electromedical.eng.med.inform, vol. 5, no. 3, pp. 193-204, Jul. 2023.
Section
Electronics