Improve Performance the Discrete Fruit Fly Optimization Algorithm (FOA) for symmetric travelling salesman problem (TSP)
Article Sidebar
Main Article Content
Abstract
The study of optimizing solutions for the Traveling Salesman Problem (TSP) using the Fruit Fly Optimization Algorithm (FOA) involves solving routing problems with a metaheuristic approach. The research focuses on improving the original FOA solution by adjusting parameters and increasing the dimensions to three-dimensional (3D) and higher-dimensional spaces (Hyper Dimensional). Additionally, it includes modifications such as Swap, Swop, and Insertion positions. Each modification considers 2-Opt (two-position), 3-Opt (three-position), and a combination of 2-3 Opt (two and three-position). The initial configuration is set using the Saving method. The analysis of the problem is divided into three parts. 1) Identifying the optimal variables for parameter setting. 2) Self-learning optimization using a single-objective approach for solving the TSP and 3) Analysis to 9 TSP datasets using a single-objective approach while comparing results with 10 other algorithms.
The research findings indicate that the three-dimensional incorporating a modified 2-3 opt switching scheme and utilizing the savings method for initial population configuration, represents the optimal algorithm. This enhancement was achieved by extending the parameter dimensions from the original two-dimensional (2D) space to a 3D space within the (X, Y, Z). The expansion into Hyper Dimensional improves the performance of the FOA by providing greater parametric flexibility. Based on tests 9 standard TSP datasets, 2 algorithms ranked first(1th). These are 1) FOA3twothree17S, which produced the best results in terms of solutions closest to the optimal solution for 4 datasets, namely Dantzig42, att48, st70, and Eil76, with deviation percentages of -2.780, 1.655, 3.659, and 4.617, respectively. and 2) FOA2twothree14S, which achieved the best result for 1 dataset, berlin52, with a deviation percentage of 3.437. in line with the research objectives. The increased number of parameters allows the algorithm to adjust positions more effectively to approach optimal solutions compared to the FOA original. Furthermore, the integration of 2-Opt, 3-Opt, and 2-3 Opt exchanges, combined with the Savings method for initializing the population, helps guide the search toward solutions near the optimal, while also reducing computational time required to obtain high-quality solutions.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
Almufti, S., & Shaban, A. A. (2025). Comparative analysis of metaheuristic algorithms for solving the traveling salesman problems. International Journal of Scientific World, 7(1), 1–5.
Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2007). The traveling salesman problem: A computational study. Princeton University Press.
Bellman, R. (1962). Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1), 61–63.
Crişan, G. C., Pintea, C., & Pop, P. C. (2020). Studying heuristics adaptation to a specific degree of fuzziness. In 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE) (pp. 1–7). IEEE.
Crişan, P., Pintea, S., & Pop, F. (2020). Fruit fly optimization algorithm for traveling salesperson problem. International Journal of Computer Applications, 107(18), 1–6.
Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. BioSystems, 43(2), 73–81.
Gendreau, M., & Potvin, J. Y. (2010). Handbook of metaheuristics. Springer.
Han, X., Liu, Q., Wang, H., & Wang, L. (2018). Novel fruit fly optimization algorithm with trend search and co-evolution. Knowledge-Based Systems, 141, 1–17.
Holland, J. H. (1992). Adaptation in natural and artificial systems. MIT Press.
Huang, C., Li, X., & Wen, Y. (2021). An OTSU image segmentation based on fruitfly optimization algorithm. Alexandria Engineering Journal, 60(1), 183–188.
Huang, L., Wang, G. C., Bai, T., & Wang, Z. (2017). An improved fruit fly optimization algorithm for solving traveling salesman problem. Frontiers of Information Technology & Electronic Engineering, 18(10), 1525–1533.
Huang, Y., & Su, T. (2017). Optimizing fruit fly algorithm to solve TSP problem. In 2017 International Conference on Computer Systems, Electronics and Control (ICCSEC) (pp. 1409–1411). IEEE.
Iscan, H., & Gunduz, M. (2017). An application of fruit fly optimization algorithm for traveling salesman problem. Procedia Computer Science, 111, 58–63.
Jiang, Z. B., & Yang, Q. (2016). A discrete fruit fly optimization algorithm for the traveling salesman problem. PLOS ONE, 11(11).
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN’95 – International Conference on Neural Networks (Vol. 4, pp. 1942–1948). IEEE.
Laporte, G. (2010). Fifty years of vehicle routing. Transportation Science, 43(4), 408–416.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1985). The traveling salesman problem: A guided tour of combinatorial optimization. Wiley.
Li, H. Z., Guo, S., Li, C. J., & Sun, J. Q. (2013). A hybrid annual power load forecasting model based on generalized regression neural network with fruit fly optimization algorithm. Knowledge-Based Systems, 37, 378–387.
Li, X., Zhang, J., & Wang, Y. (2018). A modified fruit fly optimization algorithm for global optimization. Applied Intelligence, 48(7), 1851–1865.
Lin, S. M. (2013). Analysis of service satisfaction in web auction logistics service using a combination of fruit fly optimization algorithm and general regression neural network. Neural Computing and Applications, 22, 783–791.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498–516.
Liu, Y., Chen, X., & Dib, O. (2023). Application of hybrid metaheuristic algorithms including FOA and PSO to traveling salesman problem. In Intelligent Computing and Optimization Conference (pp. 3–18). Springer.
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46–61.
Mousavi, S. M., Sadeghi, J., Niaki, S. T. A., Alikar, N., Bahreininejad, A., & Metselaar, H. S. C. (2014). Two parameter-tuned meta-heuristics for a discounted inventory control problem in a fuzzy environment. Information Sciences, 276, 42–62.
Pan, Q. K., Sang, H. Y., Duan, J. H., & Gao, L. (2014). An improved fruit fly optimization algorithm for continuous function optimization problems. Knowledge-Based Systems, 62, 69–83.
Pan, W. T. (2012). A new fruit fly optimization algorithm: Taking the financial distress model as an example. Knowledge-Based Systems, 26, 69–74.
Pasandideh, S. H. R., Niaki, S. T. A., & Mousavi, S. M. (2013). Two metaheuristics to solve a multi-item multiperiod inventory control problem under storage constraint and discounts. The International Journal of Advanced Manufacturing Technology, 69(5), 1671–1684.
Ranjan, R. K., & Kumar, V. (2023). A systematic review on fruit fly optimization algorithm and its applications. Artificial Intelligence Review, 56, 13015–13069.
Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384.
Reinelt, G. (1995). TSPLIB95: A library of sample instances for the TSP (and related problems). Universität Heidelberg.
Shan, D., Cao, G., & Dong, H. (2013). LGMS-FOA: An improved fruit fly optimization algorithm for solving optimization problems. Mathematical Problems in Engineering, 2013(1), 108768.
University of Heidelberg. (n.d.). TSPLIB95: Traveling Salesman Problem library. Institut für Informatik, Universität Heidelberg. Retrieved August 23, 2025.
Wang, G., Ma, L., & Chen, J. (2017). A bilevel improved fruit fly optimization algorithm for the nonlinear bilevel programming problem. Knowledge-Based Systems, 138, 113–123.
Wang, X., Li, H., & Yang, J. (2019). An improved fruit fly optimization algorithm for solving combinatorial optimization problems. Expert Systems with Applications, 127, 20–35.
Xu, H., & Chen, Y. (2020). A chaotic fruit fly optimization algorithm for solving the traveling salesman problem. Computers & Industrial Engineering, 142, 106372.
Zhang, L., Wang, S., & Liu, B. (2015). Fruit fly optimization algorithm for feature selection in classification. Knowledge-Based Systems, 89, 275–286.
Zhang, Y., Wang, H., & Li, J. (2023). Adaptive fruit fly optimization algorithm for solving discrete traveling salesman problems. Applied Soft Computing, 137, 110436.
Zheng, X. L., Wang, L., & Wang, S. Y. (2014). A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem. Knowledge-Based Systems, 57, 95–103.
