Development of an optimal route algorithm based on separable
criteria: distance and time
Sagdulla Fayzullaev
1
, Nozimaxon Karimova
2
, Ubaydulla Fayzullaev
2
, Feruza Zokirova
2
1
Renaissance University of Education, Samarkand darvoza Str., Tashkent, 100069 Uzbekistan.
2
Tashkent State Technical University named after Islam Karimov, University 2, Tashkent, 100069 Uzbekistan.
sagdulla@gmail.com, nozimaxon.karimova@mail.ru, ubay86@mail.ru)
https://doi.org/10.5281/zenodo.10471273
Keywords:
Dijkstra's algorithm, graph theory, distance, time, separable criteria,
Lagrange polynomial, delay matrix.
Abstract:
This paper considers the problem of finding the shortest paths between all vertices of a weighted undirected
sparse graph. A “graph disassembly and reassembly” algorithm is proposed, which uses the solution of a
problem on a low-dimensional graph to obtain a solution for the original graph. A comparison of the proposed
algorithm with one of the fast classical algorithms on open access data is provided. The complexity of the
original problem is notably reduced by the proposed algorithm such that it can be scaled to large networks. In
addition to the sub-gradient Lagrangian multiplier updating strategy integrated with projection, a novel one
based on the deep-cut ellipsoid method is proposed as well.
1 INTRODUCTION
Known for solving the problem are: the city's
road network, the place of departure and the
destination. It is necessary to select the optimal
route and all the routes close to it from the point of
departure to the destination, which take into account
the real situation on the roads: possible traffic
congestion and options for bypassing it, delays in
front of traffic lights at intersections, different
speeds of traffic on certain sections of the city’s road
network. Time, distance traveled, etc. can serve as a
criterion for choosing a route. In reality, the shortest
route in terms of distance is not always optimal in
terms of time, fuel consumption, etc. It is very
difficult to reduce these criteria to one. Often the
criterion for the optimality of a path is quite difficult
to formalize. On the other hand, any mathematical
model does not take into account many external
factors that influence the result, since the situation
on the road may change. Therefore, not only the
optimal path is considered, but also all routes close
to the optimal one in a given range, so that the user
can choose the most suitable one when making the
final choice.
There are a number of implemented
programs that allow you to search for the shortest
route along the road network on an electronic map
[1-5]. The considered systems use various criteria
for the optimality of the path - from the criterion of
the shortest distance to complex criteria for
estimating time, taking into account information
about traffic jams. The mentioned works mainly
consider algorithms for searching only the optimal
path. Only in [6] an algorithm for searching K routes
for deviation from the optimal one is described
based on the optimal route passing through K
vertices of the graph.
Algorithm for solving. The algorithm for
solving the problem consists of two stages.
Determining the shortest travel route in time is
reduced to solving the well-known problem of the
shortest path on a directed graph. To solve it, a well-
known algorithm is used, based on placing marks on
the vertices of the graph [10]. To determine the set
of all routes close to the optimal, an algorithm is
used. based on the method of sequential analysis of
options and the use of the rule for rejecting
unpromising options before obtaining a final
decision.
As is known in Dijkstra's algorithm, to find
the shortest path, temporary or permanent marks are
assigned to the vertices of the graph. Labels define
for a vertex the upper bound on the length of the
path from the vertex to the current one. The values
of the temporary markings of the vertices gradually
decrease. The marking value determines the
possible length of the path from the initial to this
vertex. At each step of the algorithm, only one of
the marks with the minimum value at the level under
consideration is selected as a constant [11]. This
means that the label value is the length of the
shortest path from a vertex to the current vertex.
2 REVIEW OF LITERATURE THE
Classical shortest path problem involves
computing the path of minimum cost–time on a
network with deterministic arc costs. The need to
capture inherent network uncertainty led to the
study of the stochastic shortest path problem (SSPP)
within the context of decision making under
uncertainty. Stochastic routing models are intended
to provide commuters with either a priori path
guidance or adaptive en route guidance. Both
versions of the problem have been extensively
studied, and existing approaches are reviewed in
two parts, the first dealing with the objective of least
expected travel time (LET) and the second dealing
with reliability-based formulations. One class of
adaptive LET path problems assumes that the
traversal time on a link will become known
(deterministic) on arrival at its tail (starting) node.
Polychronopoulos and Tsitsiklis [15] proposed a
dynamic programming (DP) approach (exponential)
to compute the adaptive LET path, and Cheung
proposed a label correcting algorithm for the same
problem [14]. The second class of LET problems
assumes that the link travel time distribution is
conditional on arrival time at the link entrance
[stochastic time varying (STV) networks]. Miller-
Hooks
and
Mahmassani
proposed
a
nondeterministic polynomial label correcting
algorithm (discrete travel time distribution) for the
a priori path problem [16]. The adaptive path variant
for a continuous link travel time distribution was
examined by Hall, who proposed a non-polynomial
DP-based algorithm [17]. In addition, Miller-Hooks
proposed a label setting algorithm for the discrete
version of the problem [18]. As a result of the
absence of the Markovian property, finding LET
paths on STV networks is computationally difficult
even with the assumption of independence [18].
Reliability-based stochastic routing has been
studied primarily in the context of finding a priori
optimal paths. Frank in his seminal paper, proposed
an algorithm to compute the continuous probability
distribution of the minimum travel time [19].
However, shortest paths are identified through
paired comparisons within an already enumerated
path set. Nie and Wu introduced a concept of
“locally reliable” paths and proposed a label
correcting algorithm to compute the set of locally
reliable paths (nondominated with respect to
reliability at varying thresholds) for static
independent link travel time distributions [20]. In
contrast, the problem of computing an optimal
reliability strategy (policy) has received scant
attention. A notable exception is Fan and Nie, who
proposed a DP-based algorithm [21]. Another
widely used approach (incorporating reliability)
uses the maximum expected utility (MEU) criterion
of Von Neumann and 84 Transportation Research
Record 2196 Morgenstern [22]. Here, a random
utility that is a function of link costs is assigned to
each path, with the optimal path being one that
maximizes expected path utility. Computing the
MEU path for nonlinear utility functions is
nontrivial, and existing pruning-based approaches
assume independence of links [22]. The mean
variance trade-off was more explicitly addressed in
the mean variance routing model proposed by Sen
et. al. [23]. Their model is noteworthy for its
consideration of correlations between link travel
times although this advancement comes at the
expense of computational efficiency, making the
proposed integer programming based solution
algorithm ill suited to large networks. The SSPP has
also been studied in the context of robust
optimization [24]. The robust path is one that
minimizes path robust deviation (maximum
difference between path cost and the corresponding
shortest path cost, over all scenarios) or worst-case
performance. Pseudopolynomial algorithms are
proposed by Yu and Yang [24]. However, such
robust routing problems are NP-hard even under
restrictive assumptions [16]. Other definitions of
optimality
based
on
first-order
stochastic
dominance and definite stochastic dominance are
investigated by Miller-Hooks and Mahmassani
[16]. They propose label correcting algorithms and
heuristics to find nondominated paths under the
stochastic dominance rules. In summary, only a few
studies consider the objectives of optimizing
reliability explicitly or implicitly. Further, most
existing approaches make a restrictive assumption
of independent link travel times (e.g., [13], [15],
[19]). Many investigations on the optimal reliability
problem use a pure Monte Carlo–based approach
along with optimization heuristics. There seems to
be insufficient understanding of and evidence on the
computational performance and accuracy of these
heuristics for networks with general correlation
patterns. In addition, several empirical issues
concerning the ORP problem remain to be
addressed systematically. For instance, how many
paths and draws are needed to obtain optimal or
near-optimal solutions? How well does the least
expected time path perform in relation to the
reliability objective? What is the consequence of
neglecting correlations while determining the ORP?
How does the nature and magnitude of benefits of
the ORP depend on the threshold for computing
reliability? This work seeks to address the
limitations and issues above by proposing a new
algorithm to determine the ORP and conducting
computational experiments on various networks.
3 MATERIALS AND METHODS
Finding the shortest path from one point to
the second point is considered by Dijkstrom and an
algorithm for determining the shortest path based on
graph theory is proposed. The algorithm suggests
that there is a directed graph
𝐺(𝑉, 𝐸)
with vertices
𝑉 = 𝑉
1
, 𝑉
2
… 𝑉
𝑛
and accordingly, adjacent edges
𝐸 = 𝑒
1
, 𝑒
2
… 𝑒
𝑚
. Here, the time to cover the
proposed route
(𝑆)
in units is considered constant,
which depends only on the distance at a constant
speed, i.e.
𝐶 =
𝑆
𝑡
constant and
𝑡 =
𝑆
𝐶
. From this we
can conclude that the route travel time is a uniformly
distributed value (choice of a certain speed).
The present time, if we consider as the
vertices of the graphs how the destinations and the
time spent to cover the distance depend on the
situation on the roads, especially when there are
traffic jams (traffic jams) of cars at intersections. In
such cases, the distribution function of the time to
reach the destination has non-uniform distributions.
Then the choice of the optimal (depending on
distance and time) route is based on the
simultaneous selection of criteria regarding distance
and time:
𝑅(𝑀
∗
) = min
1≤𝑖≤𝑛
(𝑀
1
, 𝑀
2
, 𝑀
3
, … 𝑀
𝑛
)
(1)
𝑅(𝑇
∗
) = min
1≤𝑖≤𝑛
(𝑇(𝑀
1
), 𝑇(𝑀
2
), 𝑇(𝑀
3
), … 𝑇(𝑀
𝑛
))
(2)
that is, based on sickness, the criteria can be
combined
𝑅(𝑀
0
) = min(𝑅(𝑀
∗
), 𝑅(𝑇(𝑀
∗
))) =
min(𝑅(𝑀
∗
) + 𝑅(𝑇(𝑀
∗
)))
(3)
where,
𝑀
∗
– the route is the shortest path with the
minimum distance;
𝑀
0
– the fastest route to reach the goal.
Delays on the roads depend on the chosen
route and the initial travel time.
𝑡
0
Let
𝑓(𝑡
0
, 𝑀
𝑖
)
be the distribution density of
the random number of time it takes to cover the
distance along the route
𝑀
𝑖
. In order to determine
the behavior of the route distribution density
function, it is necessary to carry out experiments to
determine the parameters of the function in the form
of the table1.
Table 1. Behavior of the density function of
the route distribution
𝑡
0
beginning
movement
𝑀
1
𝑀
2
𝑀
3
...
𝑀
𝑛
𝑡
1
𝜏
1,1
𝜏
1,2
𝜏
1,3
𝜏
1,𝑛
𝑡
2
𝜏
2,1
𝜏
2,2
𝜏
2,3
𝜏
2,𝑛
...
𝑡
𝑘
𝜏
𝑘,1
𝜏
𝑘,2
𝜏
𝑘,3
𝜏
𝑘,𝑛
Where,
𝑘
– number of breakdowns of the loaded
time period per day.
For
example:
𝑡
1,𝑖
= 7, 𝑡
2,𝑖
= 8, 𝑡
3,𝑖
=
9, 𝑡
4,𝑖
= 10, 𝑡
5,𝑖
= 11, 𝑡
6,𝑖
= 12, 𝑡
7,𝑖
= 13, 𝑡
8,𝑖
=
14, 𝑡
9,𝑖
= 15, 𝑡
10,𝑖
= 16, 𝑡
11,𝑖
= 17, 𝑡
12,𝑖
=
18, 𝑡
13,𝑖
= 19, 𝑡
14,𝑖
= 20, 𝑡
15,𝑖
= 21, 𝑡
16,𝑖
=
22, 𝑡
17,𝑖
= 23;
If
𝑘 = 24
then
𝑡
𝑘,𝑖
= 𝑘 where 𝑘 = 1 ÷ 24; 𝑖 =
1 ÷ 𝑛;
After the experiment, the distribution
density can be determined
𝑦
𝑖
(𝑡) = 𝑓(𝑡, 𝑀
𝑖
)
where
𝑓(𝑡, 𝑀
𝑖
)
is a Lagrange polynomial
(k-1)
of
that degree.
Figure 1:
Density distribution graph.
Then the choice of the optimal route is
determined by minimizing the function
𝑍(𝑡) = min
1≤𝑖≤𝑛
(𝑓(𝑡, 𝑀
𝑖
) + 𝑀
𝑖
)
.
The function depends only on the start time
of movement. This function reaches its value only
in , which is determined by solving the equation
𝑍(𝑡)min𝑡
∗
𝑑𝑍(𝑡)
𝑑𝑡
= 0
Solving the equation means when to drive
and what route to take to get to your destination
quickly.
Let there be
𝑑𝐷
𝑖,𝑗
traffic lights on the
𝑀
𝑖
route (
𝑗 = 1 ÷ 𝑗
𝑖
) and the average delay at a traffic
light depend on the time of day
𝑍
𝑖,𝑗
(𝑡)
where
𝑡 ∈
[0; 24]
.
It can be confirmed experimentally that the
graph of the function
𝑍
𝑖,𝑗
(𝑡)
has the following form.
Figure 2:
graph of the function
𝑍
𝑖,𝑗
(𝑡)
After determining the shortest route from vertex
𝑉
𝑖
to vertices
𝑉
𝑗
(𝑖 = 1 − 𝑛; 𝑗 = 1 − 𝑛)
,
𝑑
𝑖,𝑗
can be
determined and can be represented as a matrix.
(Table 2)
Table 2. Traffic light matrix
𝑉
1
𝑉
2
...
𝑉
𝑛−1
𝑉
𝑛
𝑉
1
0
𝑑
1,2
𝑑
1,𝑛−1
𝑑
1,𝑛
D=
𝑉
2
𝑑
2,1
0
𝑑
2,𝑛−1
𝑑
2,𝑛
...
𝑉
𝑛−1
𝑑
𝑛−1,1
𝑑
𝑛−1,2
0
𝑑
𝑛−1,𝑛
𝑉
𝑛
𝑑
𝑛,1
𝑑
𝑛,2
𝑑
𝑛,𝑛−1
0
D – traffic light matrix.
If the graph is undirected then we can
assume
𝑑
𝑖,𝑗
= 𝑑
𝑗,𝑖
i.e. The street is two-way. But for
those who are oriented, it is not necessary, and this
means that there is a one-way street on the route.
Now let's create a delay matrix
𝑍(𝑡)
..
𝑀
1
..
𝑀
2
–––
𝑀
3
minutes
time
minutes
𝑡
hours
𝑍
𝑖,𝑗
(𝑡)
elay schedule
A erage minimum delay
Table 3. delay matrix
𝑍(𝑡)
𝑉
1
𝑉
2
...
𝑉
𝑛−1
𝑉
𝑛
𝑉
1
0
𝑍
1,2
(𝑡)
𝑍
1,𝑛−1
(𝑡)
𝑍
1,𝑛
(𝑡)
𝑍(𝑡)
=
𝑉
2
𝑍
2,1
(𝑡)
0
𝑍
2,𝑛−1
(𝑡)
𝑍
2,𝑛
(𝑡)
...
𝑉
𝑛−1
𝑍
𝑛−1,1
(𝑡)
𝑍
𝑛−1,2
(𝑡)
0
𝑍
𝑛−1,𝑛
(𝑡)
𝑉
𝑛
𝑍
𝑛,1
(𝑡)
𝑍
𝑛,2
(𝑡)
𝑍
𝑛,𝑛−1
(𝑡)
0
4 CONCLUSIONS
In this paper, we studied the mean-standard
deviation reliable shortest path problem with link
travel time correlations. Thanks to the matrix
decomposition technique, it becomes possible to
introduce continuous variables to establish the
relationship between the covariance matrix and the
original binary variables. Combined with the
Lagrangian relaxation method, we decompose the
non-linear and non-additive original problem into
two sub-problems. One of which is a standard
shortest path problem that can be solved efficiently
with labeling algorithms and the other convex
optimization problem is proved to show its optimal
solution which further saves computational time.
The complete algorithm was proposed with both
sub-gradient and deep-cut ellipsoid method for
updating Lagrangian multipliers. An illustrative
example was provided to shed light on the
mechanism of the proposed algorithm with two
different Lagrangian multiplier updating strategies.
Large-scale tests were also conducted to evaluate
the computational performances. We compared the
relative gap, running time and average iteration with
the existing methods in the literature.
With the increasing research and practical
interests on the variablity of traffic conditions, the
significant decrease in the computational time of the
reliable shortest path problem provides promises for
further comprehensive studies and real applications.
The contributions of this study include the proposal
of the Lagrangian substitution solution method
based on eigendecomposition that has not been
studied in the literature, the efficiency improvement
from OA method and sampling based and sub-
gradient projection based Lagrangian relaxation
method, and the comparison between the widely
adopted sub-gradient method and deep-cut ellipsoid
method for Lagrangian multiplier updating and its
implications.
REFERENCES
[1]
http://www.mapquest.com/routeplanner:Find
the
shortest path from A to B to Z.
[2]
http://www.pocketgis.biz: Automatic route tracing
on an electronic map.
[3]
http://www.mobimap.ru/item/2139302137/mobim
ap-moscow.jad: City map for phones with Java.
[4]
http://autosputnik.com/products/autosputnik/list/:E
lectronic
map: Satellite navigation.
[5]
http://mosmap.ru/software/gis-mosmap-
integrator.htm: Electronic maps of Russian cities
and route planning.
[6]
Christofides N. Graph theory. Algorithmic
approach. – M.: Mir, 1978. – 432 p.
[7]
Stepanov V.P. On mathematical modeling of the
city road network for choosing a travel route:
Abstract. doc. scientific conf. MSTU im. N.E.
Bauman. - M, 2005, p.110-111.
[8]
Stepanov V.P. On mathematical modeling of the
road network. // New information technologies in
automated systems: Materials of the thirteenth
scientific and practical seminar. – MIEM. M., 2010,
p. 237 – 243.
[9]
Moiseev N.N. Numerical methods in the theory of
optimal systems. – M.: Nauka, 1971. – 424 p.
[10]
U. Fayzullaev, Sh. Tashmatova, and K. Kurbanova.
Separability-based selection of cost-effective
control of multistep processes in limited time and
money. Journal of Physics: Conference Series 2131
(2021)
032110.
doi:10.1088/1742-
6596/2131/3/032110
[11]
S.X. Fayzullaev, N.A. Karimova, U.S. Fayzullaev,
and N.Z Tojikhujaeva. Representation of a
mathematical model of chemical-technological
processes with acceleration through a continuous
function. E3S Web of Conferences 383, 04050
(2023).
[12]
Bates, J., J. Polak, P. Jones, and A. Cook. The
Valuation of Reliability for Personal Travel.
Transportation Research Part E, Vol. 37, 2001, pp.
191–229.
[13]
Mirchandani, P. B., and H. Soroush. Optimal Paths
in Probabilistic Networks: A Case with Temporary
Preferences. Computers and Operations Research,
Vol. 12, 1985, pp. 365–381.
[14]
Cheung, R. K. Iterative Methods for Dynamic
Stochastic Shortest Path Problems. Naval Research
Logistics, Vol. 45, No. 8, 1998, pp. 769–789.
[15]
Polychronopoulos, G. H., and J. N. Tsitsiklis.
Stochastic Shortest Path Problems with Recourse.
Networks, Vol. 27, No. 2, 1996, pp. 133–143.
[16]
Miller-Hooks, E. D., and H. S. Mahmassani. Path
Comparisons for A Priori and Time-Adaptive
Decisions in Stochastic, Time-Varying Networks.
European Journal of Operational Research, Vol.
146, No. 2, 2003, pp. 67–82.
[17]
Hall, R. The Fastest Path Through a Network with
Random
TimeDependent
Travel
Times.
Transportation Science, Vol. 20, No. 3, 1986, pp.
182–188.
[18]
Miller-Hooks, E. D. Adaptive Least-Expected Time
Paths in Stochastic, Time-Varying Transportation
and Data Networks. Networks, Vol. 37, No. 1,
2001, pp. 35–52.
[19]
Frank, H. Shortest Paths in Probabilistic Graphs.
Operations Research, Vol. 17, No. 4, 1969, pp. 583–
599.
[20]
Nie, Y. (Marco), and X. Wu. Shortest Path Problem
Considering
OnTime
Arrival
Probability.
Transportation Research Part B, Vol. 43, 2009, pp.
597–613.
[21]
Fan, Y., and Y. Nie. Optimal Routing for
Maximizing the Travel Time Reliability. Networks
and Spatial Economics, Vol. 6, 2006, pp. 333–344.
[22]
Von Neumann, J., and O. Morgenstern. Theory of
Games and Economic Behavior, 3rd ed. Princeton
University Press, 1980.
[23]
Sen, S., R. Pillai, S. Joshi, and A. Rathi. A Mean-
Variance Model for Route Guidance in Advanced
Traveler Information Systems. Transportation
Science, Vol. 35, No. 1, 2001, pp. 37–49.
[24]
Yu, G., and J. Yang. On the Robust Shortest Path
Problem. Computers and Operations Research, Vol.
25, No. 6, 1998, pp. 457–468.
[25]
Li, R. Examining Travel Time Variability Using
AVI Data. CIATR report. 2004.
[26]
Yen, J. Y. Finding the K Shortest Loopless Paths in
a Network. Management Science, Vol. 17, 1971,
pp. 712–716.
[27]
Martins, E. D. Q. V., J. M. P. Paixa, M. S. Rosa, and
J. L. E. Santos. The Determination of the Path with
Minimum-Cost Norm Value. Networks, Vol. 41,
No. 4, 2003, pp. 184–196.
