On the Convergence of an Efficient and Robust Dynamic Neural
Network Concept with Application to Solving Traveling Salesman
Problems
ELNUR NOROV1, SHAKHZOD TASHMETOV1, KHABIBULLO NOSIROV1,
MAKHIRAKHON RAKHMATULLAEVA1, AHMED YUSUPOV1,
JEAN CHAMBERLAIN CHEDJOU2*
1Department of Television and Radio Broadcasting System,
Tashkent University of Information Technologies (TUIT),
Tashkent 100084, Amir Temur Avenue 108,
UZBEKISTAN
2Department of Smart Systems Technologies, University of Klagenfurt,
Universitätsstraße 65/67, 9020 Klagenfurt,
AUSTRIA
*Corresponding author
Abstract: - In our previous contributions [20, 21, 22], we have clearly demonstrated that the dynamic neural
network concept (DNN-concept) for solving shortest path problems (SPP) and traveling salesman problems
(TSP) outperforms the best heuristic methods proposed by the literature. However, in our numerous
contributions and also according to the literature, the effects of the step sizes of both “decision neurons” and
“multiplier neurons” on the convergence properties of the “DNN-concept” are still not investigated. The aim of
our contribution is to enrich the literature by investigating, for the first time, the convergence properties of the
DNN-concept for solving traveling salesman problems. We develop a mathematical model for the efficient and
robust solving the traveling salesman problem (TSP). Based on the numerical study, the convergence properties
of the model developed (i.e., the DNN-concept for solving TSP) is investigated. Ranges (or windows) of
variation of the parameters of the developed mathematical model are determined (identified) to ensure
(guarantee) the detection of the exact TSP solution/tour. In order to validate the mathematical model developed
for solving TSP, a bifurcation analysis is carried out using the developed mathematical model. Various
bifurcation diagrams are obtained numerically. The bifurcation diagrams obtained reveal the ranges of variation
of some key parameters of the model developed to ensure (or guarantee) the convergence of the DNN-concept
to the exact TSP-solution (i.e., global minimum). Concrete examples of graphs are considered and various
numerical simulations are performed as proof of concept. Finally, a comparison of the results obtained with the
results published in [17]-[18] lead to a very good agreement.
Key-Words: - Dynamic Neural Network, Bifurcation analysis, Convergence to exact TSP solutions.
Received: April 12, 2022. Revised: October 27, 2022. Accepted: November 21, 2022. Published: December 31, 2022.
1 Introduction
During the past couple of decades the traveling
salesman problem (TSP) has been studied in many
fields of science and engineering, leading to a great
variety of applications such as: ordering-picking in
a warehouse [1], hot rolling scheduling [2], ship
scheduling [3], pickup and delivery [4], carrier-
vehicle systems [5], information processing [6],
optimization of drone-assisted parcel delivery [7],
optimization of traffic factors [8], data clustering
[9], X-ray crystallography [10], printed circuit board
production [11], in-vehicle route guidance [12],
automated guided vehicle systems [13], multipath
traffic assignment [14], traffic light control [15],
real-time traffic information [16], just to name a
few. These applications witness the tremendous
attention devoted during the past couple of decades
to the development of new methods and algorithms
for solving TSP. However most of the traditional
methods and algorithms so far developed are
generally prone to limitations/drawbacks described
in [20, 21, 22]. These limitations/drawbacks do
justify the focus (in this paper) on the development
of a new concept for solving TSP. Some well known
limitations of traditional methods and algorithms
are: the weak robustness, low accuracy, weak
stability, poor flexibility, low scalability potential,
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
285
Volume 21, 2022
and failures to converge to the exact/true TSP
solution/tour. One can refer to [20, 21, 22] for a full
description of the drawbacks/limitations of the
heuristic methods. The new DNN solver concept
developed (in this paper) is a systematic analytical
framework, which does efficiently satisfy all key
performance metrics (i.e., robustness, accuracy,
flexibility, scalability, convergence to the exact TSP
solution, subtours avoidance in TSP, etc.). A further
limitation of the traditional
methods/concepts/algorithms for solving TSP is the
fact that they do not provide a systematic analytical
framework, which could be used to handle or
overcome the aforementioned limitations.
Further significant studies on the topic addressed in
this paper can be found in [24-25]. These references
provide a theoretical framework that might help
understanding the modeling framework developed
in this paper.
This paper is a contribution to the development
of a systematic analytical concept which efficiently
addresses and overcomes the aforementioned
limitations (drawbacks) of the traditional concepts,
methods, and algorithms for solving TSP. The main
focus is on the mathematical modeling of the TSP
problem and the analysis of the convergence of the
resulting differential equations obtained as the
mathematical model of the DNN-concept for
solving TSP problems. A mathematical theory is
developed to guarantee the convergence of the
DNN- concept to the exact traveling salesman
solution. The bifurcation analysis is further carried
out in order to depict (or determine) the ranges of
the control-parameters in which the convergence to
the exact TSP-solutions is always ensured. Many
bifurcation diagrams are obtained and depicted (i.e.,
represented) in order to confirm the convergence of
the DNN concept to exact TSP solutions.
The paper is organized as follows. Section 2
focuses on the mathematical modeling of the TSP
problem. A full description of the modeling
methodology leading to the derivation of the
mathematical model of the novel TSP solver-system
(i.e., the DNN concept for solving TSP) is given.
The mathematical model obtained is expressed in
the form of coupled ordinary differential equations
(ODE). Section 3 is focused on the numerical
investigation of the convergence of the
mathematical model developed to the exact TSP
solution. The numerical study is mainly focused on
the bifurcation analysis, aiming at determining and
depicting the suitable values and/or ranges/windows
of the parameters (or coefficients) of the
mathematical model of the DNN concept for which
the convergence to the exact TSP solution is ensured
(guaranteed). Various bifurcation diagrams are
obtained in terms of the control-parameters of
bifurcation, which are the step sizes of both decision
neurons and multiplier neurons. The resulting
bifurcation diagrams (obtained numerically) clearly
reveal the effects of the decision and multiplier
neurons on the convergence of the DNN concept to
the exact TSP solution. Section 4 is devoted to
concluding remarks and outlook. In the outlook,
several open research questions of interest for
further investigations are briefly formulated.
2 Mathematical Modeling of the TSP
In subsections below we present the full details of
the procedure leading to the derivation of the
mathematical model of the DNN-concept for
solving TSP (expressed into the form of coupled
ordinary differential equations ODEs).
2.1 Objective function
The TSP in any given graph network is
formulated by the objective function expressed in
(1). The function represents the total cost
corresponding to the full size of . The integers
and are the indexes of nodes in and, is the
magnitude of .
(1)
The generalized form of (1) is given by (2). The
symbol denotes the elementwise product (called
Hadamard-product).
(2)
where and
are respectively the states and weights of all edges
of ( is the size of ). The components of are
binary numbers and thus is a binary vector. The
components of equal to “1” reveal the edges
belonging to the TSP solution/tour, and components
of equal to “0” stand for those edges which do
not belong to the TSP solution/tour.
2.2 Constraints
The objective function in (2) is subject to a series
constraints, which are formulated to fulfill all key
requirements related to TSP.
In our recent contribution (see [20]) we have
defined the general condition for assigning attributes
to nodes by (3). The notation stands for all
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
286
Volume 21, 2022
incoming edges to a node with index . Similarly,
the notation stands for all outgoing edges
from a node with index .
(3)
2.2.1 Constraint 1
This constraint insures the belonging of each node
of to the TSP solution. To fulfil (or achieve) this
constraint, each node of is assigned the attribute
of intermediate node by choosing in (3) [20].
Thus, applying (3) to all nodes of (under the
condition ) leads to the general form (4).
(4)
The symbol in (4) stands for the incidence matrix
of .
Remark 1. For the sake of providing a clear
understanding of some fundamental issues like: a)
the modeling procedure, b) the constraints
formulated, c) the mathematical models obtained,
and d) the parameters of the mathematical models
obtained, we will be using (throughout the paper),
for illustrative purposes, the example of the six-city
graph network published in references [17]-[18] (see
Fig. 1).
The elements/values in rows 1 to 6 and columns
1 to 30 of the matrix (see below) correspond to
the specific case of Fig. 1. In row 1 of the values
reveal the connection to of the outgoing
edges (from ) denoted , , , , and. The
values reveal the connection to of the
incoming edges (to ) denoted , , , ,
and. Similarly, the columns 11 and 12 of the
matrix reveal the connection of and by the
pair of parallel edges (, ).
Fig. 1: Topology of a six-city graph published in
[17]-[18]. This is a completed bidirectional graph of
magnitude 6 and size 30. The states of edges are
denoted by and the weights (i.e. edges costs) are
. Examples of TSP tours are displayed in green
color (the TSP solution proposed in [17]) and red
color (the TSP solution proposed in [18]).
Remark 2. The procedure (described above) to
determine the incidence matrix is applicable to
any graph network regardless of the topology,
size and magnitude of the graph.
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
287
Volume 21, 2022
2.2.2 Constraint 2
This constraint ensures the connection of each node
of by exactly “one incoming edge” and “one
outgoing edge”. This constraint is modeled by (5),
assuming (4) is satisfied. Thus the constraints 1 and
2 are complementary [20].
(5)
Applying (5) to all nodes of leads to the general
form (6).
(6)
The quantity in (6) denotes the absolute value of
.
2.2.3 Constraint 3
This constraint is formulated to avoid the
simultaneous belonging of parallel edges
to the TSP solution/tour. This
constraint is modeled by applying (7) to each pair of
parallel edges. Let’s mention that parallel edges are
edges expressing the bidirectional communication
between each pair of nodes.
(7)
According to (7) each pair of parallel edges can take
only one of the states
; thus the case
which corresponds to parallel edges is surely
avoided under condition (7). An illustrative example
of applying (7) to parallel edges
,,…, in
Fig.1 is as follows:
,,..,
. Applying (7) to all parallel edges of
denoted by leads to the
general expression (8).
(8)
The matrix is of size and expresses
the connectivity of all pairs of parallel edges
in the graph . Let’s
mention here that, in the general form, the last pair
of parallel edges in the graph is obtained for
and this corresponds to .
Remark 3. In the matrix , only the pairs of parallel
edges denoted by , , , , and
are represented. These pairs correspond
respectively to , , ,
and in Fig. 1. One can deduce for the
full size of Fig. 1. Note that the form of is
standard. Thus, holds for any graph regardless
of the topology, size, and magnitude.
Remark 4. Note that the constraint formulated in (8)
holds even for a numbering of edges which is
different from the numbering chosen in the example
of Fig. 1; in case the numbering differs from that
currently used in Fig. 1, one obtains a matrix D
which is not a diagonal matrix, but which still
satisfies the constraint formulated in (8). For the
sake of generalization and to facilitate programming
or algorithmic-coding (in case we may consider a
complex graph network, e.g., graph of huge size and
fully connected), expressing the matrix D into
diagonal form is convenient (highly recommended).
2.2.4 Constraint 4
This constraint is formulated to avoid subtours in
the TSP solution. Thus the condition (9) is used to
ensure (or guarantee) only TSP solutions/tours with
single- cycles.
(9)
In (9), stands for edges belonging to a given
subtour , and is the total number of edges in the
subtour .
The expression (9) is applicable to any graph
of known topology. The knowledge of the graph
topology leads to the straightforward determination
of the sizes of subtours in . Indeed the subtours of
are obtained according to (9) when the
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
288
Volume 21, 2022
characteristic relation is fulfilled.
The quantity stands for the magnitude of .
In [19] the inequality
is
proposed for the subtour elimination constraints
(SEC), where is a non-empty subset of the set of
nodes of graph and is a binary variable
revealing the state of edges- connectivity. The
advantage of (9) when compared to the SEC in [19]
is that (9) is used both for the determination of all
possible subtours and for the elimination of the
subtours. Further advantage is that the equality
constraint (9) is appropriate for the modeling of our
Neuro-Processor solver while in contrast the
inequality constraints SEC in [19] is not appropriate
for the mathematical modeling of TSP by ordinary
differential equations.
We now consider Fig. 1 to illustrate the
application of (9). Let us mention that in the specific
case of Fig. 1, for all subtours . Further, a
total of 20 possible TSP solutions (each of which is
made-up of a pair of subtours) can be found in Fig.
1. The TSP solutions with two cycles (called multi-
tours TSP) are surely avoided when the condition
(9) is satisfied. Amongst the TSP solutions with two
cycles (in Fig. 1), let us mention, just for
illustration, the pair of subtours made-up of edges
and with edges ().
Another TSP solution with two cycles (in Fig. 1) is
with edges and
with
().
Remark 5. A total of 40 subtours corresponding to
20 TSP solutions (with two cycles each) co-exist in
Fig. 1 with several other TSP solutions with single-
cycles. Thus, (9) is applied to eliminate subtours and
thus ensure only TSP solutions with single-cycles in
a given graph network with known topology.
For a given graph , the subtours are
expressed through the matrix . Worth mentioning
is that can be easily determined for any given graph
network of known topology.
We now consider Fig. 1 as a particular/specific
example to illustrate the procedure leading to the
determination of . The subtour (see first row of )
is made-up of edges (). According to (9) the
subtour is avoided by the following analytic equation:
It clearly appears that this equation does not admit as
solution the case (corresponding to
)
Overall, for any given graph network, the
application of (9) to all subtours of the graph leads
to the general form (10).
(10)
where is the state vector of the
edges in .
The symbol denotes the elementwise product.
The constraint modeled by (10) is used to eliminate
the subtours described by the matrix . is of
size and can be obtained for a given graph
network . is the size of and is the total
number of subtours in . Note that in the
specific case of Fig. 1. Also note that only 7
subtours are represented in . The full matrix
corresponding to Fig. 1 can be deduced by
representing all the subtours. As already defined
above, stands for the total number of edges in a
given subtour . The range of variation of is
, where stands for the magnitude of
. In the particular case of Fig. 1, we have as
all the 40 subtours identified are each with three
edges.
2.2.5 Constraint 5
This constraint expressed into the general form (11)
ensures the binarization of all edges of [20].
(11)
where is the state vector of edges
in .
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
289
Volume 21, 2022
2.2.6 Constraint 6
This constraint improves the robustness of the
binarization constraint (11). According to [20], the
improvement of the robustness of the convergence
properties of all edges of to binary variables (i.e.
“1” and/or “0”) is ensured by the augmented
Lagrange method. This method is derived from (11)
by introducing an additive penalty force expressed
in the form of quadratic energy. This justifies the
constraint expressed in the general form (12). This
constraint was also reported in our references [20].
(12)
The next section is concerned with the
formulation of the Lagrange function as the total
energy of the system (see our Refs. [20], [21], [22],
[23]).
2.3 The Basic Differential Multiplier Method
We now transform the constrained optimization
problem into an unconstrained optimization
problem. This is done by expressing the Lagrange
function as a combination of the objective function
with the formulated constraints. The overall
procedure consists of introducing new vectors of
multiplier variables , , , , , and for the
six groups of constraints (4), (6), (8), (10), (11) and
(12). Combining the objective function (2) with
these constraints leads to the Lagrange function
denoted by .
(13)
Eq. (13) is now used to obtain the model for solving
TSP. The Basic Differential Multiplier Method
(BDMM) expressed in (14) is used to obtain the set
of coupled ordinary differential equations describing
the mathematical model for solving TSP. More
details on the application of BDMM is also provided
in our refs.[20], [21], [22], [23].
(14)
The expression (14) corresponds to a neural network
with anti-symmetric connections between the
vectors of multiplier neurons (also called multiplier
variables) ,, and all components
of the vector of decision neurons (also called
decision variables) . The step
sizes for updating decision variables and multiplier
variables are denoted by and
respectively.
Using (13), the partial derivatives are calculated in
the BDMM model in (14) and, the resulting
mathematical model obtained is expressed in (15).
(15)
In Eq. (15), the quantities , , and
denote
the transpose of matrices , , and , respectively.
3 Numerical Study
The aim of the numerical study is twofold.
Validating the mathematical model obtained
in this work (see (15)) for solving the
traveling salesman problem (TSP). This is
achieved by comparing the numerical
results obtained when solving the TSP in
Fig. 1 using Eq. (15) with the results
published in refs. [17]-[18].
Determining the ranges of parameters
(decision variable) and
(multiplier variables) for which the
mathematical model in Eq. (15) always
converges to the exact TSP solution. This is
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
290
Volume 21, 2022
achieved by carrying out a bifurcation
analysis. This analysis consists of varying
the control parameters of bifurcation and
in order to depict (i.e.,
identify and detect) the regions in which the
mathematical model in Eq. (15) always
converges to the exact/true TSP solution.
In order to compare our results with the published
results, we use the same values of weights (i.e.,
costs of edges) proposed in [18] for the six-city
graph in Fig. 1: ; ;
; ; ;
; ;
; ; ;
; ;
; ; .
The numerical simulation of (15) is performed using
the following values of parameters: ;
; ; ; .
The 4th order Runge-Kutta algorithm is used for the
numerical solving of (15) using the step size
. The results of obtained as numerical
solutions of (15) are depicted in Fig.2. As it appears
in Fig. 2 the system (15) undergoes a short transient
behavior characterized by damped oscillations,
followed by the detection of subtours S1, S2, and
S3. Finally the system (15) converges to the optimal
TSP tour characterized by the following binary
values obtained as numerical solutions of (15):
(see Fig. 2).
The remaining components of are equal zero (see
Fig. 2). Thus the trajectory in red color (see Fig.1)
corresponds to the “optimal TSP- tour” denoted
The total
cost of the optimal TSP solution/tour corresponding
to the values of is . These results
are confirmed by [18].
We now consider the bifurcation analysis through
the numerical solving of (15). The following values
are used: ; ; ;
; ; ; . The results
obtained as solution of (15) are used to plot the 3D-
bifurcation diagram in Fig. 3. As already mentioned,
the components of converge to binary values (see
illustrative examples in Fig. 2). These values are
used to evaluate the total cost of the optimal TSP
solution using the expression (13).
Fig. 2: Results of the numerical solution of the DNN
model (15). Damped oscillations occur during the
following transitions: ; ;
(corresponding to
the end of the optimization process).
As it appears in Fig. 3 the monitoring (i.e., the
variation) of the selected bifurcation parameters in
windows/ranges and
clearly shows that the optimal TSP- tour (also
called exact/true TSP- tour) corresponds to the total
cost of . This value depicted in Fig. 3 by
blue color cells represents the global minimum point
at which the exact/true TSP- tour is obtained. Also,
several TSP- tours with the total cost of
are depicted in Fig. 3. The TSP-tours with total
costs correspond to local minima which
are very close to the optimal TSP- tour. Therefore,
as the chosen (or selected) bifurcation parameters
and are varied (i.e., monitored), the convergence
of the optimization algorithm alternates between the
exact/true TSP- solution/tour (global minimum with
the total cost of ) and several other TSP-
tours (corresponding to local minima) with the total
costs () which are very close to the cost of
the global minimum.
Worth mentioning is that the alternation of the
convergence of the optimization algorithm from the
global minimum to several closest local minima
(and vice-versa) is a challenging situation
commonly faced (or encountered) by the classical
optimization algorithms (e.g., traditional neural
networks, genetic and heuristic algorithms, etc.).
This situation is clearly reported in [18]. Thus,
based on the results in Fig. 3, it is clearly
demonstrated that using the new mathematical
model developed in (15), a suitable choice of the
bifurcation parameters and can help to
overcome the aforementioned challenging situation.
For example (see Fig. 3) a suitable choice of the
following chosen/selected two bifurcation
parameters in the ranges and
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
291
Volume 21, 2022
ensures (or guarantees) the
convergence of the mathematical model in (15) to
the exact/true TSP- tour corresponding to the global
minimum (see blue cells in Fig. 3). This
is a pro (advantage) of the mathematical model in
(15) as it is clearly demonstrated (through Fig. 3)
that a suitable choice of the parameters of the
mathematical model in (15) can help avoiding
convergence to local minima and thereby ensuring
sure convergence to the unique global minimum
corresponding to the exact TSP- solution/tour.
Fig. 3: A 3D-representation of the results of the
bifurcation analysis (in terms of α and ) obtained
using the mathematical model in (15). The total cost
of the optimal TSP tour is . This
corresponds to the global minimum (Blue cells).
The pics (or pulses) correspond to (total
cost of local minima which are very close to the
global minimum). The parameters used are:
α; ; ; ; ;
; ; . One can easily
identify from this figure the ranges (or windows) of
parameters leading to the sure convergence of the
DNN-solver in (15) to the exact TSP solution/tour.
For the sake of benchmarking it should be
mentioned that this application example is published
in [18] and also that the same optimal TSP-tour
denoted by
(see red lines in Fig. 1) with the total cost
is obtained. This shows the good agreement between
the DNN model developed in this work (see Eq.
(15)) and the GA and SA algorithms used in [18].
Similarly to the previous comment (on Fig. 3)
regarding the guarantee of convergence of the DNN
model in Eq. (15) to the exact TSP solution/tour, it
can be found, according to Fig. 4, that the choice of
the following chosen/selected bifurcation
parameters in the ranges and
ensures (or guarantees) the convergence of
the DNN model in Eq. (15) to the exact TSP- tour
corresponding to the global minimum
(see blue cells in Fig. 4). The pics/pulses in Fig. 4
correspond to TSP- tours representing closest local
minima with
Fig. 4. A 3D-representation of the results of the
bifurcation analysis (in terms of and )
obtained using the new DNN model in (15). The
total cost of the optimal TSP tour is . This
corresponds to the global minimum (Blue cells).
Pics (or Pulses) correspond to (this total
cost corresponds to local minima very close to the
global minimum). The values of parameters used
are: α; ; ;
; . One can
easily identify from this figure the ranges (or
windows) of parameters leading to the sure
convergence of the DNN-solver in (15) to the exact
TSP solution/tour.
4 Conclusion
This paper has developed a new dynamic neural
network (DNN) solver concept for the efficient
solving of traveling salesman problems (TSP). The
modelling of TSP has been carried out and a
mathematical model of the new DNN- solver has
been obtained in the form of coupled nonlinear
ordinary differential equations.
To validate the DNN-solver model developed in
this paper, two application examples published in
[17]-[18] have been considered. The DNN model
developed has been used to solve the
aforementioned application examples. Using the
same values of parameters as in [17]-[18], a
bifurcation analysis has been carried out
numerically based on the mathematical model
developed in this work for solving TSP. Using this
mathematical model, the ranges/windows of the
system parameters have been identified (or detected)
under which the mathematical model developed
surely and always converges to the exact TSP
solution/tour. Finally, a comparison of the TSP
solution obtained using the mathematical model
developed with the results published in [17]-[18]
has led to a very good agreement.
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
292
Volume 21, 2022
An ongoing work (this for outlook) currently
under consideration is the development of a
theoretical framework for the analytical
investigation of the convergence in order to ensure
(or guarantee) the convergence of the new DNN-
solver concept developed to the exact TSP solution.
The guarantee of convergence has been done in this
work numerically. Therefore, it would be very
interesting and even challenging to develop a
universal and scalable theoretical framework that
could help derive and propose the analytical
conditions that will ensure (or guarantee) the
convergence of the DNN-solver to the exact TSP
solution/tour. This could be a significant
contribution to the enrichment of the literature as
this analysis has not yet been considered by the
literature regarding TSP solving.
Acknowledgement:
The first two authors would like to acknowledge the
scholarship obtained in the frame of the
ERASMUS+ mobility, that has facilitated a six-
month research visit in Klagenfurt under the
supervision of Prof. Jean Chamberlain Chedjou,
during which this work was initiated and completed.
The authors of this work are grateful for the
valuable comments of the anonymous reviewers,
which have greatly improved the quality of this
work.
References:
[1] H. D. Ratliff and A. S. Rosenthal, “Order-
Picking in a Rectangular Warehouse: A
Solvable Case for the Travelling Salesman
Problem,” Operations Research, Vol. 31,
1983, pp. 507-52.
[2] L. Tang, J. Liu, A. Rong and Z. Yang, “A
multiple traveling salesman problem model
for hot rolling scheduling in Shangai Baoshan
Iron and Steel Complex,” European Journal
of Operational Research, Vol. 124, 2000, pp.
267–282.
[3] K. Fagerholt and M. Christiansen, “A
travelling salesman problem with allocation,
time window and precedence constraints—an
application to ship scheduling,” Int. Trans.
Oper. Res., Vol. 7, 2000, pp. 231–244.
[4] G. Mosheiov, “The traveling salesman
problem with pickup and delivery,” Eur. J.
Oper. Res., Vol. 79, 1994, pp. 299–310.
[5] E. Garone, J.-F. Determe and R. Naldi,
“Generalized Traveling Salesman Problem for
Carrier-Vehicle Systems,” Journal of
Guidance, Control, and Dynamics, Vol. 37,
2014, pp. 766–774.
[6] X. Kong and C. D. Schunn, “Global vs. local
information processing in visual/spatial
problem solving: The case of traveling
salesman problem,” Cognitive Systems
Research, Vol. 8, 2007, pp. 192–207.
[7] C. C. Murray and A. G. Chu, “The flying
sidekick traveling salesman problem:
Optimization of drone-assisted parcel
delivery,” Transportation Research Part C:
Emerging Technologies, Vol. 54, 2015, pp.
86-109.
[8] M. Mavrovouniotis and S. Yang, “Ant colony
optimization with immigrants’ schemes for
the dynamic travelling salesman problem with
traffic factors,” Applied Soft Computing, Vol.
13, 2013, pp. 4023-4037.
[9] J. K. Lenstra, “Clustering a Data Array and
the Traveling-Salesman Problem,” Operations
Research, Vol. 22, 1974, pp. 413–414.
[10] R. E. Bland, and D. E. Shallcross, “Large
traveling salesman problem arising from
experiments in X-ray crystallography: a
preliminary report on computation,”
Operations Research Letters, Vol. 8, 1989,
pp. 125-128.
[11] G. Reinelt, “A Case Study: TSPs in Printed
Circuit Board Production: The Traveling
Salesman,” Lecture Notes in Computer
Science book series (LNCS), Vol. 840, 2001,
pp. 187–199.
[12] L. Fu, “An adaptive routing algorithm for in-
vehicle route guidance systems with real-time
information,” Methodological, Vol. 35, 2001,
pp. 749–765.
[13] R. J. Gaskins and J. M. A. Tanchoco, “Flow
path design for automated guided vehicle
systems,” International Journal of Production
Research, Vol. 25, 1987, pp. 667–676.
[14] R. B. Dial, “A probabilistic multipath traffic
assignment model which obviates path
enumeration,” Transportation research, Vol.
5, 1971, pp. 83–111.
[15] W. Wen, “A dynamic and automatic traffic
light control expert system for solving the
road congestion problem,” Expert Systems
with Applications, Vol. 34, 2008, pp. 2370-
2381.
[16] T. Cheong and C. C. White, III, “Dynamic
traveling salesman problem: Value of real-
time traffic information,” IEEE Trans. Intell.
Transp. Syst., Vol. 13, 2012, pp. 619-630.
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
293
Volume 21, 2022
[17] M. Niendorf, P. T. Kabamba and A. R.
Girard, “Stability of Solutions to Classes of
Traveling Salesman Problems,” IEEE Trans.
Cybern., Vol. 46, 2016, pp. 973–985.
[18] J. Li, M.-C. Zhou, Q. Sun, X. Dai and X. Yu,
“Colored Traveling Salesman Problem,“
IEEE Trans. Cybern., Vol. 45, 2015, pp.
2390–2401.
[19] XU. Pferschy and R. Staněk, “Generating
subtour elimination constraints for the TSP
from pure integer solutions,” Central
European J. Oper. Res., Vol. 25, 2017, pp.
231–260.
[20] Jean Chamberlain Chedjou, and Kyandoghere
Kyamakya, “An efficient, scalable, and robust
neuro-processor-based concept for solving
single-cycle traveling salesman problems in
complex and dynamically reconfigurable
graph networks,” IEEE Access, Vol. 8, 2020,
pp. 42297-42324.
[21] Jean Chamberlain Chedjou, and Kyandoghere
Kyamakya, “A universal concept for robust
solving of shortest path problems in
dynamically reconfigurable graphs,”
Mathematical Problems in Engineering, Vol.
2015, 2015, pp. 1-23.
[22] Jean Chamberlain Chedjou, and Kyandoghere
Kyamakya, “Benchmarking a recurrent neural
network based efficient shortest path problem
(SPP) solver concept under difficult dynamic
parameter settings conditions,”
Neurocomputing Elsevier, Vol. 196, 2016, pp.
175-209.
[23] J. C. Chedjou and K. Kyamakya, “A universal
concept based on cellular neural networks for
ultrafast and flexible solving of differential
equations,” IEEE Trans. Neural Netw. Learn.
Syst., Vol. 46, n0. 4, pp. 749-762, April 2015.
[24] Abd Elhakim Lamairia, "Nonexistence
Results of Global Solutions for Fractional
Order Integral Equations on the Heisenberg
Group", WSEAS Transactions on
Systems, vol. 21, pp. 382-386, 2022.
[25] Nongluk Viriyapong, "Modification of
Sumudu Decomposition Method for
Nonlinear Fractional Volterra Integro-
Differential Equations", WSEAS
Transactions on Mathematics, vol. 21, pp.
187-195, 2022.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
Prof. Jean Chamberlain Chedjou, defined and
proposed the research topic as supervisor (external).
He also checked the correctness of the mathematical
formulas and the wording of the submitted article.
Prof. Ahmed Yusupov, checked the simulation
algorithms and the issues related to graph theory.
Prof. Nosirov Khabibullo is the local supervisor. He
helped checking the developed algorithms and
review debugging.
Prof. Makhirakhon Rakhmatullaeva is a
mathematician. She conducted a thorough
verification of the correctness of all mathematical
formulas. She also proposed the idea how to check
the convergence to the unique solution which is the
global minimum.
MSc. Tashmetov Shakhzod, contributed to
numerical coding by developing the MATLAB
codes used for numerical study. He also performed
mathematical calculations and contributed to the
writing of the article.
MSc. Norov Elnur, contributed to numerical coding
by developing the MATLAB codes used for
numerical study. He also performed mathematical
calculations and contributed to the writing of the
article.
WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS
DOI: 10.37394/23201.2022.21.31
Elnur Norov, Shakhzod Tashmetov,
Khabibullo Nosirov, Makhirakhon Rakhmatullaeva,
Ahmed Yusupov, Jean Chamberlain Chedjou
E-ISSN: 2224-266X
294
Volume 21, 2022
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
Conflict of Interest
The authors have no conflicts of interest to declare
that are relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
The first two authors would like to acknowledge the
scholarship obtained in the frame of the
ERASMUS+ mobility, that has facilitated a six-
month research visit in Klagenfurt under the
supervision of Prof. Jean Chamberlain Chedjou,
during which this work was initiated and completed.
