Single Objective Mayfly Algorithm with Balancing Parameter for Multiple Traveling Salesman Problem
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.
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.
[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.
Issue
Section
Electronics
Copyright (c) 2023 Yoga Dwi Wahyu Nugraha, Hendrawan Armanto, Yosi Kristian
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-ShareAlikel 4.0 International (CC BY-SA 4.0) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
.png)
.png)
.png)
.png)
.png)
