The dynamic programming method application to the solution of one fuzzy salesman problem
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2026.2.08Keywords:
fuzzy traveling salesman problem, trapezoidal fuzzy numbers, defuzzification, modelling, optimization, dynamic programmingAbstract
A method for solving the traveling salesman problem is proposed, utilizing dynamic programming to determine the shortest duration route, considering the fuzzy representation of travel time between individual points. Approaches for the approximation of fuzzy values, arithmetic operations, and methods for ordering fuzzy numbers are presented. The problem formulation with trapezoidal fuzzy numbers is considered. A representation form of such fuzzy numbers based on a Gaussian-like approach is proposed. Methods of the state space tree and dynamic programming are employed. The proposed technique is illustrated with an example.
References
L.A. Zadeh, “Fuzzy sets,” Information and Control, vol. 8, issue 3, pp. 338–353, 1965. doi: https://doi.org/10.1016/S0019-9958(65)90241-X
A. Kumar, A. Gupta, “Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions,” Fuzzy Information and Engineering, vol. 3, issue 1, pp. 3–21, 2011. doi: https://doi.org/10.1007/s12543-011-0062-0
R.E. Bellman, L.A. Zadeh, “Decision making in fuzzy environment,” Management science, vol. 17, no. 4, pp. 141–164, 1970.
H.-J. Zimmermann, “Fuzzy programming and linear programming with several objective functions,” Fuzzy Sets and Systems, vol. 1, issue 1, pp. 45–55, 1978. doi: https://doi.org/10.1016/0165-0114(78)90031-3
N. Christofides, “Vehicle Routing,” in The Traveling Salesman Problem. John Wiley, 1985, pp. 431–448.
G.B. Dantzig, D.R. Fulkerson, S.M. Johnson, “Solution of a Large-scale Traveling Salesman Problem,” Journal of the Operations Research Society of America, vol. 2, no. 4, 1954. doi: https://doi.org/10.1287/opre.2.4.393
I. Elamvazuthi, T. Ganesan, P. Vasant, J.F. Webb, “Application of a fuzzy programming technique to production planning in the textile industry,” International Journal of Computer Science and Information Security, vol. 6, no. 3, pp. 238–243, 2009. doi: https://doi.org/10.48550/arXiv.1001.2277
Tien-Fu Liang, “Applying interactive fuzzy multi-objective Linear programming to transportation planning decisions,” Journal of Information and Optimization Sciences, vol. 27, issue 1, pp. 107–126, 2006. doi: https://doi.org/10.1080/02522667.2006.10699682
Bablu Jana, Tapan Kumar Roy, “Multi-Objective Fuzzy Linear Programming and Its Application in Transportation Model,” Tamsui Oxford Journal of Mathematical Sciences, vol. 21, no. 2, pp. 243–268, 2005.
R. Bellman, “Dynamic programming treatment of the travelling salesman problem,” Journal of the ACM, vol. 9, issue 1, pp. 61–63, 1962. doi: https://doi.org/10.1145/321105.321111
M. Held, R.M. Karp, “A dynamic programming approach to sequencing problems,” Proceedings of the 16th ACM National Meeting, ACM ‘61, New York, NY, USA, 1961, pp. 71201–71204.
E.V. Ivohin, V.V. Gavrylenko, K.E. Ivohina, “On the recursive algorithm for solving the traveling salesman problem on the basis of the data flow optimization method,” Radio Electronics, Computer Science, Control, no. 3, pp. 141–147, 2023. doi: https://doi.org/10.15588/1607-3274-2023-3-14
