A Theoretical and Computational Study of a Defuzzification Function for the Generalized Fuzzy Single-Depot Multiple Traveling Salesman Problem

Authors

  • Madineh Farnam Department of Electrical Engineering, Shohadaye Hoveizeh Campus of Technology, Shahid Chamran University of Ahvaz, Dasht-e Azadegan, Khuzestan, Iran.
  • Sara Ahmadi * Department of Mathematics, Farhangian University, Tehran, Iran.

https://doi.org/10.22105/raise.vi.99

Abstract

This study addresses the single-depot Multiple Traveling Salesman Problem (mTSP) under uncertainty, where travel costs are expressed as generalized trapezoidal fuzzy numbers. A two-stage parametric approach is adopted: first, a defuzzification function  converts the fuzzy costs into crisp values; second, a corrected Mixed-Integer Linear Programming (MILP) model, equipped with strict sequencing constraints to enforce tour-length limits, is solved to obtain optimal routes. The primary theoretical contribution is a rigorous analysis of the defuzzification function , including proofs of its continuity, strict monotonic decrease with respect to the risk parameter , positivity under mild conditions, convexity, and concavity properties thereby establishing a sound mathematical basis for its use. The method is demonstrated on 7-city, 2-salesman instance with tour-length bounds  and . Experiments for  reveal that total cost declines strictly as  increases (from 116.62 to 8.81), and the optimal tour configuration switches at , illustrating how the parameter  acts as a risk‑attitude lever that can fundamentally alter operational plans. The approach provides decision‑makers with a transparent, quantitative tool to explore cost–risk trade‑offs in fuzzy routing problems

Keywords:

Multiple traveling salesman problem, Generalized trapezoidal fuzzy numbers, Defuzzification function, Mixed-integer linear programming, Risk analysis

References

  1. [1] Reinelt, G. (1994). The traveling salesman. Springer Berlin, Heidelberg. https://doi.org/10.1007/3-540-48661-5
  2. [2] Bektas, T. (2006). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega, 34(3), 209–219. https://doi.org/10.1016/j.omega.2004.10.004
  3. [3] Angel, R. D., Caudle, W. L., Noonan, R., & Whinston, A. (1972). Computer-assisted school bus scheduling. Management science, 18(6), 279–288. https://doi.org/10.1287/mnsc.18.6.B279
  4. [4] Ann, S., Kim, Y., & Ahn, J. (2015). Area allocation algorithm for multiple UAVs area coverage based on clustering and graph method. IFAC-papersonline, 48(9), 204–209. https://doi.org/10.1016/j.ifacol.2015.08.084
  5. [5] Tang, L., Liu, J., Rong, A., & Yang, Z. (2000). A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European journal of operational research, 124(2), 267–282. https://doi.org/10.1016/S0377-2217(99)00380-X
  6. [6] Murray, C. C., & Raj, R. (2020). The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation research part c: Emerging technologies, 110, 368–398. https://doi.org/10.1016/j.trc.2019.11.003
  7. [7] Srikakulapu, R., & U, V. (2018). Optimized design of collector topology for offshore wind farm based on ant colony optimization with multiple travelling salesman problem. Journal of modern power systems and clean energy, 6(6), 1181–1192. https://doi.org/10.1007/s40565-018-0386-4
  8. [8] Baltz, A., El Ouali, M., Jäger, G., Sauerland, V., & Srivastav, A. (2015). Exact and heuristic algorithms for the travelling salesman problem with multiple time windows and hotel selection. Journal of the operational research society, 66(4), 615–626. https://doi.org/10.1057/jors.2014.17
  9. [9] Markevich, E. A., & Trushechkin, A. S. (2019). Quantum branch-and-bound algorithm and its application to the travelling salesman problem. Journal of mathematical sciences, 241(2), 168–184. https://doi.org/10.1007/s10958-019-04415-6
  10. [10] Pereira, A. H., & Urrutia, S. (2018). Formulations and algorithms for the pickup and delivery traveling salesman problem with multiple stacks. Computers & operations research, 93, 1–14. https://doi.org/10.1016/j.cor.2018.01.005
  11. [11] Miller, D. L., & Pekny, J. F. (1991). Exact solution of large asymmetric traveling salesman problems. Science, 251(4995), 754–761. 10.1126/science.251.4995.754
  12. [12] Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley Longman Publishing Co., Inc.75 Arlington Street, Suite 300 Boston, MAUnited States. https://dl.acm.org/doi/book/10.5555/534133
  13. [13] Malmborg, C. J. (1996). A genetic algorithm for service level based vehicle scheduling. European journal of operational research, 93(1), 121–134. https://doi.org/10.1016/0377-2217(95)00185-9
  14. [14] Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial intelligence review, 13(2), 129–170. https://doi.org/10.1023/A:1006529012972
  15. [15] Yousefikhoshbakht, M., Didehvar, F., & Rahmati, F. (2013). Modification of the ant colony optimization for solving the multiple traveling salesman problem. Romanian journal of information science and technology, 16(1), 65–80. https://romjist.ro/content/pdf/05-myousefikhoshbakht.pdf
  16. [16] Tirkolaee, E. B., Alinaghian, M., Hosseinabadi, A. A. R., Sasi, M. B., & Sangaiah, A. K. (2019). An improved ant colony optimization for the multi-trip capacitated arc routing problem. Computers & electrical engineering, 77, 457–470. https://doi.org/10.1016/j.compeleceng.2018.01.040
  17. [17] Nguyen, K. H., & Ock, C. Y. (2013). Word sense disambiguation as a traveling salesman problem. Artificial intelligence review, 40(4), 405–427. https://doi.org/10.1007/s10462-011-9288-9
  18. [18] Wang, Y., Chen, Y., & Lin, Y. (2017). Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem. Computers & industrial engineering, 106, 105–122. https://doi.org/10.1016/j.cie.2016.12.017
  19. [19] Jiang, C., Wan, Z., & Peng, Z. (2020). A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert systems with applications, 139, 112867. https://doi.org/10.1016/j.eswa.2019.112867
  20. [20] Alinaghian, M., Tirkolaee, E. B., Dezaki, Z. K., Hejazi, S. R., & Ding, W. (2021). An augmented Tabu search algorithm for the green inventory-routing problem with time windows. Swarm and evolutionary computation, 60, 100802. https://doi.org/10.1016/j.swevo.2020.100802
  21. [21] Hatamlou, A. (2017). Solving travelling salesman problem using heart algorithm. International journal of applied evolutionary computation (IJAEC), 8(4), 32–42. https://doi.org/10.4018/IJAEC.2017100103
  22. [22] Dubois, D., & Prade, H. (1979). Operations in a fuzzy-valued logic. Information and control, 43(2), 224–240. https://doi.org/10.1016/S0019-9958(79)90730-7
  23. [23] Zimmermann, H. J. (2011). Fuzzy set theory—and its applications. Springer Science & Business Media. https://doi.org/10.1007/978-94-010-0646-0
  24. [24] Feng, H. M., & Liao, K. L. (2014). Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problems. Information sciences, 270, 204–225. https://doi.org/10.1016/j.ins.2014.02.098
  25. [25] Trigui, S., Cheikhrouhou, O., Koubaa, A., Baroudi, U., & Youssef, H. (2017). FL-MTSP: A fuzzy logic approach to solve the multi-objective multiple traveling salesman problem for multi-robot systems. Soft computing, 21(24), 7351–7362. https://doi.org/10.1007/s00500-016-2279-7
  26. [26] Shi, Y., Boudouh, T., & Grunder, O. (2017). A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert systems with applications, 72, 160–176. https://doi.org/10.1016/j.eswa.2016.12.013
  27. [27] Farnam, M., & Darehmiraki, M. (2023). Fuzzy data clustering using FCM algorithm based on a parametric distance measure. Journal of fuzzy systems and applications, 5(2), 93-119.(In Persian). https://civilica.com/doc/1602543/

Published

2026-08-25

Issue

Vol. 3 No. 2 (2026): Research Annals of Industrial and Systems Engineering

Section

Articles

How to Cite

Farnam, M., & Ahmadi, S. . (2026). A Theoretical and Computational Study of a Defuzzification Function for the Generalized Fuzzy Single-Depot Multiple Traveling Salesman Problem. Research Annals of Industrial and Systems Engineering, 3(2), 146–159. https://doi.org/10.22105/raise.vi.99