Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру
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...
Saved in:
| Date: | 2026 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2026
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/365264 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1869472196137582592 |
|---|---|
| author | Ivokhin, Eugene Yushtin, Konstantin Adzhubey, Larisa |
| author_facet | Ivokhin, Eugene Yushtin, Konstantin Adzhubey, Larisa |
| author_institution_txt_mv | [
{
"author": "Eugene Ivokhin",
"institution": "Taras Shevchenko National University of Kyiv, Kyiv"
},
{
"author": "Konstantin Yushtin",
"institution": "Taras Shevchenko National University of Kyiv, Kyiv"
},
{
"author": "Larisa Adzhubey",
"institution": "Taras Shevchenko National University of Kyiv, Kyiv"
}
] |
| author_sort | Ivokhin, Eugene |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2026-06-30T06:14:59Z |
| description | 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. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2026.2.08 |
| first_indexed | 2026-07-01T01:00:18Z |
| format | Article |
| fulltext |
E. V. Ivohin, K. E. Yushtin, L. T. Adzhubey, 2026
Системні дослідження та інформаційні технології, 2026, № 2 123
TIДC
МЕТОДИ АНАЛІЗУ ТА УПРАВЛІННЯ
СИСТЕМАМИ В УМОВАХ РИЗИКУ
І НЕВИЗНАЧЕНОСТІ
UDC 004.942:519.85
DOI: 10.20535/SRIT.2308-8893.2026.2.08
THE DYNAMIC PROGRAMMING METHOD
APPLICATION TO THE SOLUTION
OF ONE FUZZY SALESMAN PROBLEM
E.V. IVOHIN, K.E. YUSHTIN, L.T. ADZHUBEY
Abstract. 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.
Keywords: fuzzy traveling salesman problem, trapezoidal fuzzy numbers,
defuzzification, modelling, optimization, dynamic programming.
INTRODUCTION
The problems of modern logistics have certain features that lead to difficulties in
solving various logistical problems, some of which can be solved due to the
management department work. Other tasks require the analysis and optimization of
logistics operations, including planning, coordination and control of the movement
and storage of goods, services and information. The involvement of mathematical
approaches for solving logistics problems is gaining widespread implementation,
the specific content of which depends on the nature of the problem and the available
data. Sometimes it is possible to find unconventional methods of solving known
problems, one of which is the traveling salesman’s problem.
The traveling salesman’s problem was first formulated by the Irish
mathematician V.R. Hamilton in the 19th century. The problem describes the need
to draw up a route within a given set of interconnected points (cities) that form the
transport network of a specific region. A traveling salesman needs to make a route
according to which he has to visit all the cities in the network, satisfying the
condition that the total distance of the route or the total time of the travelling are
minimal. The peculiarity of the problem is that the route must contain all the points
specified in the problem, and each of the points must be visited no more than once.
The salesman’s problem is a combinatorial problem that can be solved using
mathematical programming methods. For certainty, the cities can be numbered as
E. V. Ivohin, K. E. Yushtin, L. T. Adzhubey
ISSN 1681–6048 System Research & Information Technologies, 2026, № 2 124
1,2,3, ,n , then the route of the traveling salesman can be described by a cyclic
sequence of city numbers )j,j,...,j,(j=t 1n21 , thereby njj ,...,1 are different
numbers. Any permutation of numbers presented in this form represents a possible
problem solution, and therefore there are 1 !n possible ways to construct its
route. The traveling salesman’s problem is to choose the route that is optimal
in terms of trip cost or trip duration, which satisfies some given constraints.
In the real world, the concept of the duration or cost of travel between
individual points of the transport network cannot have fixed values, they should
be determined approximately. Often these values affected by the influence of
subjective analysis regarding estimates of time periods or the cost of moving
along sections of the route. This leads to the necessity of considering
uncertainty and its formalization based on various methodologies. One of the
approaches used in this case is to involve the methods of the theory of fuzzy
sets and numbers.
In this case, the objective function coefficients and constraints, which describe
the uncertainty, make it possible to formalize the inaccuracy of the numerical
characteristics of the optimization problem. Optimization problem statements with
inherently fuzzy data are fuzzy optimization problems, one of which is the fuzzy
traveling salesman problem (FTSP).
Traditional problems of solving optimization tasks become significantly more
complicated in cases where imprecise parameters are considered, which limits the
possibility of applying known approaches to problem-solving. The need to find
optimal solutions, the importance of effectively solving the traveling salesman’s
problem under conditions of uncertainty and inaccuracy prompt the search for
different methods and algorithms for solving the problem in question.
The fuzzy sets theory, as one of the approaches to the formalization of uncertainty,
was proposed by L. Zade [1]. Its application for solving applied optimization problems is
reflected in many studies [2–8]. Among the publications devoted to the traveling
salesman problem, we highlight the research [2], which discusses the ways of “solving
the fuzzy traveling salesman problem with various membership functions”. The paper [3]
proposed the concept of decision-making in a fuzzy environment. The study [4] is
devoted to methods of solving fuzzy linear programming problems taking into account
several objective functions. On the other hand, many different methods have been
proposed for solving the classic traveling salesman problem, as a combinatorial problem,
based on greedy and heuristic approaches that allow finding local optimal solutions
(for example, [5, 6]). Therefore, the combination of these methods with the possibility
of using fuzzy numbers to account for uncertainty in optimization tasks presents both
theoretical and practical interest.
The goal of the this article is to develop an algorithm for solving the
traveling salesman problem with a fuzzy defined travel times in a transport
network. The object of the study is the process of finding the optimal route
for the fuzzy traveling salesman problem with a minimum travel time.
The subject of the study is the development of an effective algorithm for
solving the fuzzy traveling salesman problem, provided that the time of
movement between individual cities along the route is presented in the form
of trapezoidal fuzzy numbers. The approach is based on the application of the
dynamic programming method.
The dynamic programming method application to the solution of one fuzzy salesman problem
Системні дослідження та інформаційні технології, 2026, № 2 125
GENERAL CONCEPTS OF FUZZY SETS AND FUZZY NUMBERS
Definition 1. [9] A fuzzy set A
~
of a universal set X is the set of pairs
,
A
A x x , where : 0,1
A
X is a mapping of the set X into a unit
interval 0,1 and is called a membership function of the fuzzy set A
~
.
The membership function value
A
x for an element x X is called the
membership degree. The interpretation of the membership degree
A
x is a
subjective measure of degree of an element x X conformity to the concept, the
content of which is formalized by a fuzzy set A
~
.
Definition 2. A fuzzy set A
~
is called convex [9] if
1 min ,
A A A
x y x y for any arbitrary , , 0,1x y X .
As a universal set X let us consider the set of real numbers, i.e. 1X R .
Definition 3.[9] A fuzzy set A
~
defined on the set of real numbers 1R is a
fuzzy number if the following conditions are met:
1) the set A
~
is convex;
2) the set A
~
is normal, in this context, there exists x R such that 1
A
x ;
3) the membership function
A
x is upper semicontinuous;
4) support of a fuzzy number sup p A is a subset of the universal set 1R .
Definition 4. [9], Fig. 1. A trapezoidal fuzzy number A
~
is an ordered tiple of
four real numbers 1 2 3 4 1 2 3 4, , , ,a a a a a a a a that defines the membership
function
A
x to the form:
1
1 2
2 1
2 3
4
3 4
4 3
,
1,
,
A
x a
when a x a
a a
x when a x a
a x
when a x a
a a
Fig. 1. Trapezoidal fuzzy number
E. V. Ivohin, K. E. Yushtin, L. T. Adzhubey
ISSN 1681–6048 System Research & Information Technologies, 2026, № 2 126
If the approach based on the Gaussian-like distribution with corresponding
characteristics is applied to the definition of a fuzzy number, then in the
generalized case, the trapezoidal fuzzy number can be represented in a slightly
different form:
1 2 3 4 2 3, , , , , , , , ,A a a a a a a m w , (1)
where the midpoint 2 3
2
a a
m
and half-width of the plateau 3 2
2
a a
w
are
used, and the coefficients 2 1a a and 4 3a a determine the width of left
and right boundaries of the fuzzy number 1 2 3 4, , ,A a a a a , respectively.
ARITHMETIC OPERATIONS WITH TRAPEZOIDAL FUZZY NUMBERS
Let’s define operations with fuzzy numbers based on the description above. As the
midpoint, the usual arithmetic mean value of the plateau boundaries is taken, the
left and right distributions are considered according to the lattice rule, according
to which for arbitrary real numbers ,a b we put max ,a b a b and
min ,a b a b .
For arbitrary trapezoidal fuzzy numbers 1 2 3 4, , ,A a a a a and
1 2 3 4, , ,B b b b b , that written in the form 1 1( ), ( ), ,A m A w A and
2 2( ), ( ), ,B m B w B , we define the following operations of addition,
subtraction, multiplication, and division, which in the general case are denoted by
the symbol :
, , ,A B m A B w A B A B A B .
Finally we have
1 2 1 2, , ,A B m A m B w A w B ,
1 2 1 2, , ,A B m A m B w A w B ,
2 3 3 2 1 1 2 2 3 1 4 2* , , ,A B a m B b w A b m A a m B b a b a ,
3 3 2 3 3 2 3 3( / / , / ( ) / ,A B m A b w B a b b w B a b b w A b
1 3 2 1 3 4 1 1 2 3 1 2/ / , / / )b a b b b a b b
The dynamic programming method application to the solution of one fuzzy salesman problem
Системні дослідження та інформаційні технології, 2026, № 2 127
ORDERING OF TRAPEZOIDAL FUZZY NUMBERS
For the implementation of comparison operations and ranking of fuzzy numbers, it
is natural to use a method based on the median average value. In other words, if a
ranking function : F R R with a median average value of the form
2 3
2 4
a a
A
is defined for each 1 2 3 4, , ,A a a a a F R ,
then for any two trapezoidal fuzzy numbers 1 2 3 4, , ,A a a a a and
1 2 3 4, , ,B b b b b we have the following possible comparison options:
BA
~~
then and only then, if BA
~~
;
BA
~~
then and only then, if BA
~~
;
BA
~~
then and only then, if BA
~~
.
THE PROCEDURE OF DEFUZZIFICATION OF TRAPEZOIDAL FUZZY
NUMBERS
The processes of handling fuzzy numbers involve a defuzzification stage –
converting a fuzzy result into a precise (numerical) value. This is an important step
in the methodology of applying a fuzzy approach, especially in tasks of fuzzy
control and fuzzy business logic, where it is necessary to transform fuzzy solutions
into specific events or numerical values. There are various defuzzification methods,
among which the most commons are: the method of center of gravity (CoG) or
centroid and the method of mean maximum (MoM). To conduct a comparison of
the research results, we will use the center of gravity method. In this method, the
defuzzification point is calculated as the center of gravity of the fuzzy set. For a
discrete set, the formula looks like this:
n
i
i
n
i
ii
x
xx
CoG
1
1
,
where ix are the points in the result space, and ix is the membership degree
for each point. In the case of a continuous distribution, the formula looks like this:
4
1
4
1
a
a
a
a
dxx
dxxx
CoG
.
MATHEMATICAL FORMULATION OF FUZZY TRAVELING SALESMAN
PROBLEM
Let’s return to the traveling salesman problem. If the route duration of the salesman
is considered as the criterion of the problem, the task is clearly defined. A different
E. V. Ivohin, K. E. Yushtin, L. T. Adzhubey
ISSN 1681–6048 System Research & Information Technologies, 2026, № 2 128
situation arises when searching for the fastest route considering the fuzzy
formalization of travel time between individual points in the city network. In this
case, we have a fuzzy traveling salesman problem.
In the case of the fuzzy traveling salesman problem stating, it is necessary to
find a cyclic permutation of the city numbers that the salesman needs to visit,
according to which the time cost will be minimal, considering the standard
constraint, that each point must be visited no more than once and return to the
starting point. The mathematical formulation of the fuzzy traveling salesman
problem can be written as follows: it is necessary to minimize the objective
function, taking into account the above-mentioned method of comparing fuzzy
numbers:
n
i
n
j
ijijxt
1 1
~
,
where the time costs for moving between points are given in the form of a matrix
with elements as trapezoidal fuzzy numbers, and the possible paths of movement
between cities are determined by the subject to the fulfillment of the constraints:
1
1
n
ij
i
x
for all 1,2,...,j n ,
1
1
n
ij
j
x
for all 1,2,...,i n ,
1i j ijv v nx n , 1 i j n ,
0ijx or 1 for all , 1, 2,...,i j n .
For software implementation in the matrix T, the elements iit must be set with
large positive numbers in order to obtain values in solution 0iix for all
1,2,....,i n .
DYNAMIC PROGRAMMING ALGORITHM FOR SOLVING THE FUZZY
TRAVELING SALESMAN PROBLEM
Let us consider the traveling salesman problem with fuzzy defined travel durations
between individual cities, which are presented in the form of trapezoidal fuzzy
numbers. One of the approaches to solving traveling salesman problems is based
on the use of the dynamic programming method, the main idea of which is to divide
the input task into subtasks and memorize solutions to avoid repeated calculations.
This allows constructing an optimal solution for the large problem based on optimal
solutions connections of individual subproblems or based on the solutions of some
recursive sequence of nested calculations.
The essence of the main principle of dynamic programming is as follows.
A multi-step (multi-stage) process of searching the optimization problem solution
is considered, an arbitrary step of which can be described in the form )],(,[ xP ,
where is the state that characterizes the current content of the problem, the
function ),( xP defines the state transformation procedure (transition function),
and x is the solution vector. Obviously, the transition function depends on the state
variable and the vector of independent variables x .
The dynamic programming method application to the solution of one fuzzy salesman problem
Системні дослідження та інформаційні технології, 2026, № 2 129
Assume that at each step of the search process there is an opportunity to
choose a solution vector x from some feasible set. Let nx is the vector of variables
chosen at the n -th step. Then we get the sequence of changes in the state of the
problem in the form: 0 (initial state); ); 1 1( , )n n nP x , 2,3,...n .
Let us consider processes in which the variable vectors nx , 2,3,...n , are
chosen in such a way as to maximize a certain predetermined criterion function
1 2 1 2( , ,..., , , ,..., )N NR x x x . We will call the solution to be optimal if it
corresponds the maximum of the given criterion function.
Considering the generalized nature of the accepted definition of the criterion
function R , we should note that the solution vectors nx , 2,3,...n , must depend
on the current state of the system, as well as on previous and subsequent states and
solutions. However, there are criterion functions of a special structure in which the
solution depends only on the current state. In this special but very important case,
the optimal strategy is determined by the Bellman’s optimality principle [10],
which forms the basis of the dynamic programming method: an optimal strategy
has the property that, whatever the initial states and the first solution, the
subsequent solutions constitute an optimal strategy in relation to the initial state
obtained as a result of the first solution.
Let’s consider the problem of maximizing the function of a special structure
1 2 1 2
1
( , ,..., , , ,..., ) ( , )
N
N N n n n
n
R x x x g x
, (2)
where ( , )ng x – the solution selection function at the n -th step, Nn ...,,2,1 .
Suppose that ( )nf is the maximum value of the criterion function R, starting
from the state , in steps 2,3,...,n N , respectively. Then Bellman’s principle of
optimality can be written in the following form:
1
( ) max ( , ),
( ) max{ ( , ) ( ( , ))},
1.
N N
x
n n n
x
f g x
f g x f P x
n N
(3)
The equations set (3) is called the Belman equation (the basic functional
equation of dynamic programming method) [10].
One of the implementations of the dynamic programming method for solving
the traveling salesman problem is the Held–Karp algorithm [11], which is known
to have time complexity 2 2nO n and space complexity 2nO n , which makes it
much faster than a complete search, especially on relatively small sets of input data.
To formalize the approach for solving the traveling salesman problem on the
set of cities in the network, let’s define a graph ( , )G S E , where S is the set of
vertices (nodes), E is the set of edges.
Let ,C S i denote the duration of the shortest salesman path starting and
finishing in i -th city (node) by the constraint of visiting each city in current subset
S of node set S only once, S S . Then the value ,C S i can be calculated using
the following formula:
E. V. Ivohin, K. E. Yushtin, L. T. Adzhubey
ISSN 1681–6048 System Research & Information Technologies, 2026, № 2 130
,
, min ( \{ }, )ij
j S j i
C S i C S i j t
,
where S is a subset of all cities, except for some initial one, which determines the
state of the problem; i and j – numbers of cities in the set S ; ijt – duration of
time from city i to city j ; \ { ],C S i j – duration of the shortest path along which
the traveling salesman visits all cities in S , excepting i -th city, starting and
finishing in the j -th city.
Just as in the case of the deterministic traveling salesman problem, for the
fuzzy variant, this approach is implemented on the basis of the construction of a
state space tree that contains all possible paths. If the matrix of the duration of
movements for example, has the form
Т=
(0.5,1,2,3.5) (1.5,2,2.5,3.5) (2,2.5,3,4)
(0.5,1,2,3.5) (2,3,4,5.5) (1.5,2,2.8,3.9)
(1.5,2,2.5,3.5) (2,3,4,5.5) (1,2,2.5,3)
(2,2.5,3,4) (1.5,2,2.8,3.9) (1,2,2.5,3)
,
then the state space tree in this case will have the form shown in Fig. 2
Fig. 2. State space tree for the traveling salesman problem with the displacement matrix (3)
Then the following algorithm can be applied to solve the fuzzy salesman
problem using the dynamic programming method:
Step 1. Let’s transform the duration of each movement specified in the matrix
T in a modified form (1) 1 2 3 4 2 3, , , , , , , , ,A a a a a a a m w .
Step 2. Let’s build a tree of the state space with any arbitrary node as the main
one, and the other nodes are considered as branches. This diagram will contain all
possible routes for travel.
The dynamic programming method application to the solution of one fuzzy salesman problem
Системні дослідження та інформаційні технології, 2026, № 2 131
Step 3. Let’s apply the formulated algorithm based on the implementation of
the dynamic programming principle (2) to find the optimal path under the
conditions of performing arithmetic operations on fuzzy numbers.
Step 4. We will determine the shortest route based on the defuzzification of
the obtained fuzzy values, which, according to the problem constraints, will pass
through each city only once and return to the initial node.
NUMERICAL EXPERIMENT RESULTS
As a first example, consider the deterministic traveling salesman problem with a
given set of travel durations on a network of 11 cities, which was presented in [12].
The corresponding NRAF network in this case has the form (Fig. 3).
Fig. 3. An example of a network of cities with travel time for the specific traveling salesman problem
The optimal route calculated by the dynamic programming method and full
search in both cases is 156 time units, which is implemented by the following
sequence of visits to cities
1 2 6 10 11 8 5 9 7 4 3 1 .
Numerical calculations were carried out to evaluate and compare the
effectiveness of algorithms. For the given network (non-existent paths in the
corresponding matrix T were coded with a time value of 1000), the average
calculation time based on a complete search was approximately 1 seconds, and for
the dynamic programming method – 6 ms.
In the case of using fuzzy values of the duration of movement between nodes
for the traveling salesman problem with matrix T (3), the corresponding indicators
for both methods practically do not differ.
As part of a more complex numerical experiment, sets of cities on the plane
were generated from points, corresponding matrices of time durations of
movements were obtained, for which fuzzy representations were randomly formed.
The given calculations (Table) demonstrate the effectiveness of calculations by the
full-search method and the dynamic programming method.
Indicators of time costs for calculating the optimal path
City quantity Complete search, s Dynamic programming method, ms
11 0.948 5.484
12 10.73 7.976
13 133.75 14.15
14 1910.7 29.45
15 28851 70.38
E. V. Ivohin, K. E. Yushtin, L. T. Adzhubey
ISSN 1681–6048 System Research & Information Technologies, 2026, № 2 132
CONCLUSIONS
An approach for constructing a solution to the fuzzy traveling salesman problem is
proposed, provided that the time of movement between individual cities along the
route is presented in the form of trapezoidal fuzzy numbers. The approach is based
on the application of the dynamic programming method, which made it possible to
formulate a practical algorithm for solving the fuzzy traveling salesman problem.
Approximation methods for fuzzy numbers, arithmetic operations and ways to
arrange fuzzy numbers are presented. A method for transforming trapezoidal fuzzy
numbers based on the Gaussian approach is proposed. The implementation of the
algorithm uses the technique of building a state space tree using an original
computing scheme that implements the principle of dynamic programming in the
form of an algorithm with the considered practical implementation of arithmetic
operations on fuzzy numbers. The proposed methodology has been illustrated with
examples.
REFERENCES
1. 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
2. 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
3. R.E. Bellman, L.A. Zadeh, “Decision making in fuzzy environment,” Management
science, vol. 17, no. 4, pp. 141–164, 1970.
4. 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
5. N. Christofides, “Vehicle Routing,” in The Traveling Salesman Problem. John Wiley,
1985, pp. 431–448.
6. 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
7. 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
8. Тien-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
9. 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.
10. 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
11. 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.
The dynamic programming method application to the solution of one fuzzy salesman problem
Системні дослідження та інформаційні технології, 2026, № 2 133
12. 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
Received 15.03.2024
INFORMATION ON THE ARTICLE
Eugene V. Ivokhin, ORCID: 0000-0002-5826-7408, Taras Shevchenko National Univer-
sity of Kyiv, Ukraine, e-mail: ivohin@univ.kiev.ua
Konstantin E. Yushtin, ORCID: 0009-0001-9881-2343, Taras Shevchenko National
University of Kyiv, Ukraine, e-mail: konstantin.yushtin@gmail.com
Larisa T. Adzhubey, ORCID: 0000-0002-8487-0884, Taras Shevchenko National Univer-
sity of Kyiv, Ukraine, e-mail: adzhybey@ukr.net
ЗАСТОСУВАННЯ МЕТОДУ ДИНАМІЧНОГО ПРОГРАМУВАННЯ ДО
РОЗВ’ЯЗАННЯ ОДНІЄЇ НЕЧІТКОЇ ЗАДАЧІ КОМІВОЯЖЕРУ/ Є.В. Івохін,
К.Е. Юштін, Л.Т. Аджубей
Анотація. Запропоновано підхід для розв’язування задачі комівояжера на
основі застосування методу динамічного програмування з метою визначення
найкоротшого за тривалістю маршруту з урахуванням нечітко заданого часу на
переміщення між окремими пунктами. Наведено способи апроксимації нечітких
величин, арифметичних дій та способів впорядкування нечітких чисел.
Розглянуто постановку задачі з трапецієподібними нечіткими числами.
Запропоновано форму подання таких нечітких чисел на основі гаусоподібного
підходу. Використано методи дерева простору станів і динамічного
програмування. Запропоновану методику проілюстровано прикладом.
Ключові слова: нечітка задача комівояжера, трапецієподібні нечіткі числа,
дефазифікація, моделювання, оптимізація, динамічне програмування.
https://doi.org/10.15588/1607-3274-2023-3-14
8 (2) (1).pdf
UDC 004.942:519.85
DOI: 10.20535/SRIT.2308-8893.2026.2.08
THE DYNAMIC PROGRAMMING METHOD APPLICATION TO THE SOLUTION OF ONE FUZZY SALESMAN PROBLEM
E.V. IVOHIN, K.E. YUSHTIN, L.T. ADZHUBEY
INTRODUCTION
GENERAL CONCEPTS OF FUZZY SETS AND FUZZY NUMBERS
ORDERING OF TRAPEZOIDAL FUZZY NUMBERS
THE PROCEDURE OF DEFUZZIFICATION OF TRAPEZOIDAL FUZZY NUMBERS
MATHEMATICAL FORMULATION OF FUZZY TRAVELING SALESMAN PROBLEM
DYNAMIC PROGRAMMING ALGORITHM FOR SOLVING THE FUZZY TRAVELING SALESMAN PROBLEM
NUMERICAL EXPERIMENT RESULTS
CONCLUSIONS
REFERENCES
8 (2) (2).pdf
ARITHMETIC OPERATIONS WITH TRAPEZOIDAL FUZZY NUMBERS
|
| id | journaliasakpiua-article-365264 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-07-01T01:00:18Z |
| publishDate | 2026 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/55/b51d611b2a979f97f4b28a74115f2d55.pdf |
| spelling | journaliasakpiua-article-3652642026-06-30T06:14:59Z The dynamic programming method application to the solution of one fuzzy salesman problem Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру Ivokhin, Eugene Yushtin, Konstantin Adzhubey, Larisa нечітка задача комівояжера трапецієподібні нечіткі числа дефазифікація моделювання оптимізація динамічне програмування fuzzy traveling salesman problem trapezoidal fuzzy numbers defuzzification modelling optimization dynamic programming 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. Запропоновано підхід для розв’язування задачі комівояжера на основі застосування методу динамічного програмування з метою визначення найкоротшого за тривалістю маршруту з урахуванням нечітко заданого часу на переміщення між окремими пунктами. Наведено способи апроксимації нечітких величин, арифметичних дій та способів впорядкування нечітких чисел. Розглянуто постановку задачі з трапецієподібними нечіткими числами. Запропоновано форму подання таких нечітких чисел на основі гаусоподібного підходу. Використано методи дерева простору станів і динамічного програмування. Запропоновану методику проілюстровано прикладом. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2026-06-30 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/365264 10.20535/SRIT.2308-8893.2026.2.08 System research and information technologies; No. 2 (2026); 123-133 Системные исследования и информационные технологии; № 2 (2026); 123-133 Системні дослідження та інформаційні технології; № 2 (2026); 123-133 2308-8893 1681-6048 en https://journal.iasa.kpi.ua/article/view/365264/350713 |
| spellingShingle | нечітка задача комівояжера трапецієподібні нечіткі числа дефазифікація моделювання оптимізація динамічне програмування Ivokhin, Eugene Yushtin, Konstantin Adzhubey, Larisa Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру |
| title | Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру |
| title_alt | The dynamic programming method application to the solution of one fuzzy salesman problem |
| title_full | Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру |
| title_fullStr | Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру |
| title_full_unstemmed | Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру |
| title_short | Застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру |
| title_sort | застосування методу динамічного програмування до розв’язання однієї нечіткої задачі комівояжеру |
| topic | нечітка задача комівояжера трапецієподібні нечіткі числа дефазифікація моделювання оптимізація динамічне програмування |
| topic_facet | нечітка задача комівояжера трапецієподібні нечіткі числа дефазифікація моделювання оптимізація динамічне програмування fuzzy traveling salesman problem trapezoidal fuzzy numbers defuzzification modelling optimization dynamic programming |
| url | https://journal.iasa.kpi.ua/article/view/365264 |
| work_keys_str_mv | AT ivokhineugene thedynamicprogrammingmethodapplicationtothesolutionofonefuzzysalesmanproblem AT yushtinkonstantin thedynamicprogrammingmethodapplicationtothesolutionofonefuzzysalesmanproblem AT adzhubeylarisa thedynamicprogrammingmethodapplicationtothesolutionofonefuzzysalesmanproblem AT ivokhineugene zastosuvannâmetodudinamíčnogoprogramuvannâdorozvâzannâodníêínečítkoízadačíkomívoâžeru AT yushtinkonstantin zastosuvannâmetodudinamíčnogoprogramuvannâdorozvâzannâodníêínečítkoízadačíkomívoâžeru AT adzhubeylarisa zastosuvannâmetodudinamíčnogoprogramuvannâdorozvâzannâodníêínečítkoízadačíkomívoâžeru AT ivokhineugene dynamicprogrammingmethodapplicationtothesolutionofonefuzzysalesmanproblem AT yushtinkonstantin dynamicprogrammingmethodapplicationtothesolutionofonefuzzysalesmanproblem AT adzhubeylarisa dynamicprogrammingmethodapplicationtothesolutionofonefuzzysalesmanproblem |