Fast Shortest Path Routing in Transportation
Networks with Time-Dependent Road Speeds
Costas K. Constantinou∗ , Georgios Ellinas∗† , Christos Panayiotou∗† and Marios Polycarpou∗†
∗ KIOS

Research Center for Intelligent Systems and Networks
of Electrical and Computer Engineering
University of Cyprus
Emails: {constantinou.k.costas, gellinas, christosp, mpolycar}@ucy.ac.cy
† Department

arXiv:1408.4113v6 [] 7 Jan 2016

Abstract
The current paper deals with the subject of shortest path routing in transportation networks (in terms of travelling time), where
the speed in several of the network’s roads is a function of the time interval. The main contribution of the paper is a procedure
that is faster compared to the conventional approaches, that derives the road’s traversal time according to the time instant of
departure, for the case where the road’s speed has a constant value inside each time interval (in general, different value for each
time interval). Furthermore, the case where the road’s speed is a linear function of time inside each time interval (in general,
different linear function for each time interval) is investigated. A procedure that derives the road’s traversal time according to
the time instant of departure is proposed for this case as well. The proposed procedures are combined with Dijkstra’s algorithm
and the resulting algorithms, that are practically applicable and of low complexity, provide optimal shortest path routing in the
networks under investigation.

I. I NTRODUCTION
In the current paper, the subject of shortest path routing in transportation networks where the roads’ speed is function of
time, is investigated. This category of networks is met in practice, since the speed in network’s roads can be available for
several time instants, either directly measured, or derived from vehicle density measurements [1].
The objective of this work was the development of low-complexity, practically applicable algorithms for fast derivation of
shortest paths (in terms of travelling time) in the networks under investigation.
Section II gives the notation, definitions and assumptions used throughout the paper. In general, a transportation network is
modelled as a directed graph, where the nodes, arcs of the graph represent the network junctions, roads respectively. A cost
is assigned to each arc, that in the current work represents the travelling time on the arc (called “traversal time” as well). For
the classical case, where the network is time-independent (called static as well), this cost is constant over time for every arc,
derived by dividing the length of the arc with the speed in it. For the case investigated here, the network is time-dependent, i.e.,
this cost is a function of time, depending on the time instant of departure. Therefore, for shortest path routing in time-dependent
networks an additional calculation must be performed compared to static networks: the calculation of the travelling time on
the network’s arcs according to the time instant of departure.
Throughout the paper it is considered that the time horizon is split into non-overlapping time intervals, and the speed in a
network’s arc depends on the time interval. This model was firstly presented in [2]. More details on this, as well as the reasons
why this model was adopted for the work proposed here, can be found in Section III, where the main models for the networks
under investigation, are presented.
The main contribution of the current paper can be found in Sections IV and V.
In Section IV, a procedure is proposed, that derives the arc’s (road’s) traversal time according to the time instant of departure,
for the case where the speed in the arc has a constant value inside each time interval (in general, a different value for each time
interval). The proposed procedure is faster compared to the conventional approaches. More precisely, if we consider that the
time horizon is split into K time slots, the computational complexity of the proposed procedure is of order O(log K), whereas
the complexity of the fastest existing approach is of order O(K). Special cases are also investigated, where the complexity of
the proposed procedure can be further decreased if certain constraints are valid for the network graph.
In Section V, the general case of speed being an arbitrary function of time inside the time interval is investigated, and
a procedure is proposed that derives the road’s traversal time according to the time instant of departure, for the case where
the speed in the arc is linear function of time inside each time interval (in general, a different linear function for each time
interval). To the best of our knowledge, relevant methods for this case do not exist in the literature.
The proposed methods are combined with Dijkstra’s algorithm and the resulting algorithms, that are practically applicable
and of low complexity, provide optimal shortest path routing in the networks under investigation.
The paper finishes with Section VI, where the conclusions are presented, as well as possible future research.

II. N OTATION , D EFINITIONS , A SSUMPTIONS
Throughout the paper the network is modelled as a directed graph G = (N, A), consisting of n = |N | nodes (road junctions)
and m = |A| arcs (roads). The arc originating from node x and end at node y is denoted by < xy >, and its length (i.e., actual
length of the corresponding road) by dxy . The speed in < xy > is denoted by v xy . A node y is considered to be adjacent to
x if < xy > exists in the graph.
The cost cxy (or “traversal time” or “travelling time”) of arc < xy > is defined as the time needed to traverse it, i.e., to
move from node x to y. Consequently, the term “shortest path” from node x to node y refers to the path of the minimum
travelling time from x to y. For the case of static networks, the cost of an arc is constant over time, equal to dxy /v xy for arc
< xy >. For time-dependent networks, it is a function of the time instant of departure (τ ) from node x, and it is denoted by
cxy (τ ). Therefore, for shortest path routing in time-dependent networks an additional calculation must be performed compared
to static networks: the calculation of cxy (τ ) according to the time instant of departure from x.
Throughout the paper, it is considered that the speed in the network’s roads has been measured for certain time instants1 ,
during a large time interval (e.g., an entire year). In this way, a speed-pattern can be derived for each road. These patterns
constitute an estimation of the time-dependent network graph.
III. E XISTING M ODELS OF T IME -D EPENDENT T RANSPORTATION N ETWORKS
In this Section, the two main models of time-dependent transportation networks are presented.
A. Flow Speed Model (FSM)
One approach to model a time-dependent network is to use the Flow Speed Model (FSM), proposed in [2]. In the FSM, for
each network arc a temporal area from t = 0 to t = T is partitioned into (in general not equal) non-overlapped time intervals,
and the speed depends on the time interval. The time division is the same for every network arc. The (k + 1)th time interval
is denoted by [τk , τk+1 ), with k ∈ N and 0 ≤ k ≤ K − 1, τ0 = 0 and τK = T . The number of time intervals is equal to K.
The speed in arbitrary arc < xy > is considered to be constant inside each time interval and it is denoted by vkxy for time
interval [τk , τk+1 ). Let the set of speeds vkxy and time intervals [τk , τk+1 ), 0 ≤ k ≤ K − 1, for arc < xy > be denoted by V xy
and T xy respectively, and V = ∪∀<xy>∈A V xy and T = ∪∀<xy>∈A T xy . Then, for the FSM the network graph is denoted by
G = (N, A, T, V ).
xy
For t > T , it can be considered either that vkxy = vK−1
(i.e., the network is static for t > T ), or that vkxy is periodic with
period equal to T .
The FSM always satisfies the First-In-First-Out (FIFO) property, as proven in [2]. In simple words, the FIFO property has
the following meaning: Consider two vehicles A and B that depart from node x and traverse arc < xy >, with B having
greater time instant of departure from x, compared to A. Then, B will have greater time instant of arrival at y, compared to
A.
As stated in Section II, for routing purposes in time-dependent networks, the derivation of arc traversal time must be
performed. In the FSM, this is performed as follows.
1) Procedure for Derivation of Arc Traversal Time (AT T ): The traversal time cxy (τ ) of arc < xy > if τ is the time instant
of departure from x can be derived as follows (AT T xy (τ ) procedure2 ):
1) Locate index k such that τk ≤ τ < τk+1
xy
2) If (vkxy · (τk+1 − τ ) ≥ dxy ) cxy (τ ) = vdxy
k
Else {
3) a) i) a = dxy − vkxy · (τk+1 − τ )
ii) k ∗ = k + 1
b) While (vkxy∗ · (τk∗ +1 − τk∗ ) < a) {
i) a ← a − vkxy∗ · (τk∗ +1 − τk∗ )
ii) k ∗ ← k ∗ + 1 }
4) cxy (τ ) = (τk∗ − τ ) + vaxy∗ }
k

The necessity of the aforementioned procedure is due to the fact that a single time interval may not be enough for the
derivation of the arc traversal time. This occurs when the distance that can be traversed from the time instant of departure till
the end of the corresponding time interval, is less than the length of the arc.
Step 1 of the AT T procedure needs O(K) time, if the time intervals are checked sequentially. The order of the number
of the time intervals that are checked during the while loop (step 3b) is O(K). Therefore, the order of the computational
complexity of the AT T procedure is O(K).
1 Either
2 This

directly measured, or derived from vehicle density measurements [1]
procedure was initially proposed in [2]; the one presented in the current paper is an equivalent form of the one in [2].

m/s 12
v

10
8
6
4
2
0

Fig. 1.

0 5 10 15 20 25 30 35 40 45 50 t

s

Example of derivation of arc traversal time (d = 250m, τ = 2s)

The example of Figure 1 illustrates the operation of the AT T procedure. Here, the length dxy of arc < xy > is equal to
170m and the departure time τ from x is equal to 6s. The first five time intervals are [τ0 , τ1 ) = [0, 10), [τ1 , τ2 ) = [10, 15),
[τ2 , τ3 ) = [15, 30), [τ3 , τ4 ) = [30, 40), [τ4 , τ5 ) = [40, 50). These along with their corresponding speed are given in Figure 1.
For this example, the AT T procedure performs as follows:
1) The departure time τ = 6s lies into time interval [τ0 , τ1 ) = [0, 10) ⇒ k = 0
2) The distance that can be traversed from τ = 6s until the end of this time interval is equal to v0xy ·(τ1 −τ ) = 10·(10−6) =
40m. Since it is smaller than the length of the arc, the procedure is continued.
3) a) i) a = dxy − v0xy · (τ1 − τ ) = 170 − 40 = 130m
ii) k ∗ = 1
b) • v1xy · (τ2 − τ1 ) = 6 · (15 − 10) = 30m < a = 130m ⇒
i) a = 130 − 30 = 100m
ii) k ∗ = 2
xy
• v2 · (τ3 − τ2 ) = 8 · (30 − 15) = 120m > a = 100m ⇒ exit from the while loop
xy
4) c (6) = (τ2 − τ ) + a/v2xy = (15 − 6) + 100/8 = 9 + 12.5 = 21.5s
The traversal time is equal to 21.5s and the time instant of arrival at node y is equal to 6 + 21.5 = 27.5s.
2) Applicability of the FSM for Networks under Investigation: The application of the FSM for the networks investigated
in the current paper, is straightforward. The time instants for partitioning the temporal area are the ones where the speed has
been measured. As stated previously, in [2] the time division is the same for every network arc. In general, it may be different.
In the current paper, for simplicity, we make the same assumption as in [2], i.e., that the time division is the same for every
arc. Nevertheless, the generalisation is straightforward, as can be seen from the description of the AT T procedure.
In [2], as stated previously, the speed is considered to be constant in every time interval. Up to Section IV, this assumption
is adopted. The general case of the speed being a function of time inside a time interval, is investigated in Section V.
In [2], the AT T procedure is combined with Dijkstra’s algorithm [3], and the resulting algorithm (called Time-DependentDijkstra (TD-Dijkstra) hereafter) is as follows.
3) Time-Dependent Dijkstra’s Algorithm: As stated in Section II, for the networks under investigation, the calculation of
cxy (τ ) must be performed during the execution of any shortest path routing algorithm. In [2], where the FSM model and the
AT T procedure were proposed, the latter is combined with Dijkstra’s algorithm [3] and the resulting algorithm (TD-Dijkstra)
is suitable for shortest path routing in networks with time-dependent road speeds. The input of TD-Dijkstra is the network
graph G = (N, A, T, V ) and the source node, and the output is the shortest path from the source to every other network node.
For the execution of TD-Dijkstra, the following are used.
• s: Source.
• W (x): Label of node x.
• p(x): Predecessor of node x.
• Gx : Set of nodes adjacent to node x.
• gx : Number of nodes adjacent to node x (i.e., gx = |Gx |).
The exact steps of TD-Dijkstra are:
1) a) W (s) = 0
b) p(s) = 0
c) N ∗ = N − {s}

d) ∀x ∈ N ∗ :
i) If (x ∈ Gs )
{ Run AT T sx (W (s)); W (x) = csx (W (s)); p(x) = s }
ii) Else { W (x) = ∞; p(x) = 0 }
2) While (N ∗ 6= ∅){
a) Find x ∈ N ∗ such that ∀x0 ∈ N ∗ : W (x) ≤ W (x0 )
b) N ∗ ← N ∗ − {x}
c) ∀x0 ∈ (N ∗ ∩ Gx ):
0
i) Run AT T xx (W (x))
0
ii) If (W (x) + cxx (W (x)) < W (x0 ))
0
{ W (x0 ) = W (x) + cxx (W (x)); p(x0 ) = x } }
The TD-Dijkstra algorithm functions as the classical Dijkstra’s algorithm, with the difference that the AT T procedure is
used in steps 1(d)i and 2(c)i for the derivation of the arc’s cost according to the time instant of departure.
On termination of the algorithm, the label W (x) of a node x gives the cost of the shortest path from the source to this
node, and p(x) gives its predecessor in this path.
Since the computational complexity of the AT T procedure is of order
Pn O(K), step 1 requires O(nK) time and each iteration
of step 2 requires O(n + gx K) time. Therefore, due to the fact that x=1 gx = m, the complexity of TD-Dijkstra is of order
O(nK + n2 + mK) = O(n2 + mK).
The D-Dijkstra is, to the best of our knowledge, the fastest existing algorithm for shortest path routing in the networks
investigated in the current paper.
B. Traversal Time Model (TTM)
Another approach to model a time-dependent network, is to use the Traversal Time Model (TTM). In the TTM, the traversal
time function f xy (τ ) is utilised, where f xy (τ ) is equal to the time needed to traverse arc < xy >, if τ is the time instant of
departure from node x. The TTM may or may not satisfy the FIFO property. This model was initially proposed in [4] and
was exploited in several other papers, such as in [5], [6], [7], [8], [9], [10], [11], [12].
Function f xy (τ ) can be defined so as to have either integer-valued or real-valued domain and range, leading to discrete- or
continuous-time-dependent networks respectively.
If f xy (τ ) is defined so as to have integer-valued domain and range (first variation of the TTM), the network is discrete-time
and f xy (τ ) is known for every τ ∈ N , 0 ≤ τ ≤ T . This variation can be found in [12] as well as other sources.
For real-valued domain and range of f xy (τ ) (second variation of the TTM), the network is continuous-time and f xy (τ ) is
known for several time instants denoted by τk , with 0 ≤ τk ≤ T , k ∈ N and 0 ≤ k ≤ K, τ0 = 0 and τK = T .
These time instants, in general, are different for each arc. Work that utilises this variation of the TTM can be found in
[5]-[11] and possibly in other sources. In the aforementioned papers, f xy (τ ) is considered to be a piecewise linear function
of time, having the time instants τk where it is known, as breakpoints. For a time instant τ for which f xy (τ ) is unknown, it
is derived by linear interpolation between the consecutive breakpoints τk , τk+1 such that τk < τ < τk+1 :

⇒

xy
)−f xy (τk )
f xy (τ )−f xy (τk )
= f (ττk+1
τ −τk
k+1 −τk
xy
)−f xy (τk )
f xy (τ ) = f (ττk+1
· (τ − τk ) + f xy (τk )
k+1 −τk

(1)
(2)

Equation 1 can be derived from the tangent of angle θ of Figure 2.
For both variations, for τ > T either it can be considered that f xy (τ ) = f xy (T ) (i.e., the network is static for τ > T ), or
it can be considered that f xy (τ ) is periodic with period equal to T .
1) Applicability of the TTM for Networks Under Investigation: For optimal routing in the networks under investigation the
continuous-time variation of the TTM must be used, since the time instant of departure from a network node can have any
arbitrary value. The derivation of f xy (τ ) for the time instants the speed has been measured, can be performed using the AT T
procedure of the FSM. For the calculation of cxy (τ 0 ) for τ 0 not equal to one of the aforementioned time instants, the assumption
that f xy (τ ) is piecewise linear, must be valid. However, the following example shows that for the networks investigated in the
current paper, this is not always true.
Consider the example of Figure 1. Here, if the AT T procedure is applied for τ equal to 0s, 10s, the derived f xy (τ ) is
equal to 20s, 22s, respectively. Using equation 2, f xy (6) = 21.2s. However, cxy (6) = 21.5s 6= f xy (6), as derived in Section
III-A1. Therefore, for this example, the assumption that f xy (τ ) is piecewise linear, is not valid.
Consequently, the FSM is utilised for the routing algorithms proposed in the following Section.

f(t)

f(τk+1)

f(τ)
θ

f(τk)

τk

τ

Fig. 2.

τk+1

t

Derivation of equation 1

IV. FAST S HORTEST PATH ROUTING A LGORITHMS
The design of a procedure that functions as the AT T 3 but with lower computational complexity compared to the AT T , can
lead to algorithms for faster shortest path routing in the networks under investigation, compared to TD-Dijkstra.
As stated in Section III-A1, the complexity of the AT T procedure is of order O(K) due to steps 1 and 3b. When the AT T
procedure is executed, the index of the time interval where the time instant of arrival lies in, can be kept [2]. In more detail,
after the execution of the AT T for the derivation of the time instant τ ∗ = τ + cxy (τ ) of arrival at node y of the arbitrary
arc < xy >, the index k ∗ such that tk∗ ≤ τ ∗ < tk∗ +1 can be kept, since it is known from the last iteration of step 3(b)ii of
the AT T (let the index that is kept, be denoted by I). For each one of the upcoming executions of the AT T in step 2(c)i of
TD-Dijkstra, performed for every z such that z ∈ (N ∗ ∩ Gy ), index k at step 1 is equal to I. Therefore,
• For the first execution of the AT T (step 1(d)i of TD-Dijkstra) the index k of step 1 of the AT T is known (it is equal to
0), and
• For any upcoming execution of the AT T (step 2(c)i of TD-Dijkstra) the index k of step 1 of the AT T is known as
described previously
The result is that the complexity of step 1 of the AT T is of order O(1) if for every execution of the AT T , the index of
the time interval where the time instant of arrival lies in, is kept.
Consequently, any attempt to decrease the complexity of the AT T procedure must concentrate on the reduction of the
complexity of step 3b of it. At this step, variable k ∗ is increased by one at each iteration, (sequential search is performed over
k ∗ ) until the last necessary time interval is located, i.e., the time interval where the time instant of arrival τ ∗ at node y (of
< xy >), lies in (i.e., [tk∗ , tk∗ +1 ) such that tk∗ ≤ τ ∗ < tk∗ +1 ).
An initial thought for decreasing the complexity would be to perform binary search [13] over variable k ∗ instead of sequential
search, to locate the last necessary time interval. However, this will not lead to lower complexity, since at each iteration of the
binary search, the check whether tk∗ ≤ τ ∗ < tk∗ +1 will need O(K) time4 , thus not decreasing the complexity of the AT T
procedure.
To achieve reduction of the complexity of the AT T procedure using binary search over k, a pair of new variables, named
effective length and additive effective length, are introduced in the current paper. They are defined as follows.
A. Effective Length, Additive Effective Length
•

The effective length lkxy is defined as the distance that can be traversed on arc < xy > during the time interval [tk , tk+1 ).
Therefore,
lkxy = vkxy · (tk+1 − tk )
Note that in general, lkxy can be greater, equal or less than the actual length dxy of arc < xy >.

3 i.e.,

that derives the cost of an arc according to the time instant of departure
at each iteration of this check, the initial while loop, i.e., with sequential search on k∗ , must be executed.

4 Since

(3)

•

Pi
xy
xy
The additive effective length Lxy
i of the time interval [ti , ti+1 ) for arc < xy > is defined as Li =
k=0 lk , i.e., is the
sum of the effective lengths from the first time interval [t0 , ti+1 ) up to the [ti , ti+1 ), including the latter. In other words,
it is equal to the distance that is traversed from time instant t0 to ti+1 . For i ≤ j,
Lxy
j

−

Lxy
i

=

j
X
k=0

lkxy

−

i
X
k=0

lkxy

=

j
X

lkxy

(4)

k=i+1

xy
Therefore, the difference Lxy
j − Li is equal to the distance that is traversed from time instant ti+1 to tj+1 .
In the following Section, a new procedure is proposed, named Fast AT T procedure (F AT T ), that utilises the additive
effective length for fast calculation of the arc traversal time.

B. Fast AT T Procedure (F AT T )
The exact steps of the F AT T xy (τ ) procedure for arc < xy > and τ as time instant of departure from node x, are as follows.
1) Steps of the F AT T xy (τ ) Procedure:
1) Locate index k such that τk ≤ τ < τk+1
xy
2) If (vkxy · (τk+1 − τ ) ≥ dxy ) cxy (τ ) = vdxy
k
Else {
3) a) i) a = dxy − vkxy · (τk+1 − τ )
c
ii) k ∗ = b (k+1)+K
2
iii) a0 = 0
b) While (a0 = 0) {
(k+1)+k∗
xy
xy
∗
• If (a < Lk∗ −1 − Lk ) k ← b
c
2
xy
xy
k∗ +K
∗
• Else If (a > Lk∗ − Lk ) k ← b 2 c
xy
xy
xy
xy
xy
xy
0
• Else If (Lk∗ −1 − Lk ≤ a ≤ Lk∗ − Lk ) a = Lk∗ −1 − Lk }
0
}
4) cxy (τ ) = (τk∗ − τ ) + a−a
xy
vk
∗
τ
2) Description of F AT Txy
Procedure:
• Steps 1 and 2: They are identical to the ones of the AT T procedure.
• Step 3(a): (i) If the procedure is continued to step 3, a is set so as to be equal to the residual distance of arc < xy >,
if the distance traversed from time instant τ to τk+1 is subtracted from dxy . The traversal of distance dxy with τ as the
time instant of departure, is equivalent to traversing distance a with τk+1 as the time instant of departure.
(ii) For the binary search over k ∗ (i.e., the index of the time interval [τk∗ , τk∗ +1 ) where the time instant of arrival lies
in), k ∗ is initialised with the value b (k+1)+K
c.
2
(iii) Variable a0 is set to zero and it is used in steps 3(b) and 4.
∗
• Step 3(b): Binary search over k is performed, to locate the time interval [τk∗ , τk∗ +1 ) where the time instant of arrival
xy
∗
lies in. According to equation 4, Lxy
k∗ − Lk is equal to the distance traversed on < xy > from τk+1 to τk +1 .
xy
xy
– If a < Lk∗ −1 − Lk , then distance a (with τk+1 as time instant of departure) will be traversed prior to τk∗ . Index k ∗
∗
c.
is too large, consequently, k ∗ ← b (k+1)+k
2
∗
xy
– If a > Lxy
−
L
,
then
distance
a
will
be
traversed
after τk∗ +1 . Index k ∗ is too small, consequently, k ∗ ← b k +K
k∗
k
2 c.
xy
xy
xy
xy
∗
∗
– If Lk∗ −1 − Lk ≤ a ≤ Lk∗ − Lk , index k is the “correct” one (i.e., for the time instant of arrival τ , τk∗ ≤ τ ∗ ≤
xy
τk∗ +1 ). Consequently, binary search is terminated and variable a0 is set to Lxy
k∗ −1 − Lk . The procedure exits the
while loop.
0
0
• Step 4: Distance a is the part of a that is traversed from τk+1 to τk∗ . The residual distance, i.e., a − a , will be traversed
in time interval [τk∗ , τk∗ +1 ), i.e., with speed vkxy∗ . Therefore, the traversal time of < xy > with τ as time instant of
0
0
xy
departure, is equal to the traversal time up to time instant τk∗ , plus a−a
(τ ) = (τk∗ − τ ) + a−a
xy , i.e., c
xy .
vk
vk
∗
∗
To further clarify the proposed procedure, note that:
xy
xy
xy
xy
xy
xy
a−a0
a−a0
a−a0
a−a0
• For the quantity
xy , 0 ≤
xy ≤ l ∗ . If a = L ∗
xy = 0. If a = L ∗ − L
xy = l ∗ .
k
k −1 − Lk , then vk
k
k , then vk
k
vk
vk
∗
∗
∗
∗
∗
• The way values are assigned to k , permits the latter to vary from k + 1 to K − 1, i.e., being in accordance to the fact
that the arrival time (if the procedure has moved to step 3) will lie in a time interval from [τk+1 , τk+1 ) to [τK−1 , τK ).
The utilisation of the additive effective length in the proposed F AT T procedure leads to O(1) time for each iteration of
the while loop of step 3(b). Therefore, the complexity of the F AT T procedure is of order O(log K), since O(log X) is the
complexity of binary search over X ordered objects [13].
If the F AT T procedure is used in TD-Dijkstra instead of the AT T , the resulting algorithm, called Fast Time-DependentDijkstra (FTD-Dijkstra), has complexity of order O(n2 + m log K), compared to O(n2 + mK) of TD-Dijkstra.
The derivation of the additive effective length for arc < xy > can be performed using the following proposed AELxy
procedure, applied to arc < xy >.

TABLE I
C OMPLEXITY OF EXISTING AND PROPOSED ALGORITHMS
ALGORITHM
Exist.
Prop.
Prop.
Prop.
Prop.

TD-Dijkstra
FTD-Dijkstra
B-FTD-Dijkstra (Q ≥ K)
B-FTD-Dijkstra (1 < Q < K)
B-FTD-Dijkstra (Q ≤ 1)

PREPROC.

SPACE

QUERY

O(mK)
O(mK)
O(mK)
O(mK)

O(mK)
O(mK)
O(mK)
O(mK)
O(mK)

O(mK + n2 )
O(m log K + n log n)
O(m log K + n log n)
O(m log Q + n log n)
O(m + n log n)

C. AELxy Procedure
xy
1) Lxy
0 = l0 , i = 1
2) While (i ≤ K − 1)
xy
xy
a) Lxy
i = Li−1 + li
b) i ← i + 1
Procedure AEL has O(K) computational complexity; the same stands for space complexity. Therefore, the preprocessing
computational complexity of FTD-Dijkstra is O(mK).
The space complexity is also O(mK), equal to the case where the AEL procedure is not applied, since the network consists
of m arcs, each one consisting of K time intervals with their corresponding speeds.
A faster implementation can be performed, if Fibonacci heaps are utilised [14], [13]. Under this data structure, the amortised
complexity of the selection of the node with the minimum cost (step 2a of TD-Dijkstra) is O(log n), leading to computational
complexity of O(m log K + n log n) for FTD-Dijkstra. The latter complexity can be further decreased if specific constraints
are valid for the network graph, as detailed below.

D. Special Cases
xy

Consider the case where the effective lengths are bounded below, i.e., lixy ≥ dQ ∀ < xy >∈ A and ∀i : 0 ≤ i ≤ K − 1.
Without loss of generality, consider that Q is integer. Then, in step 3(b) of the F AT T procedure, Q consecutive time intervals
are enough for the traversal of distance a5 , since:
P(k+1)+(Q−1)
k+1

lixy ≥

≥ ((k + 1) + (Q − 1) − (k + 1) + 1) ·
=Q·

dxy
Q

=d

xy

dxy
Q

=

>a

(5)

Therefore, the binary search in step 3(b) of the F AT T procedure can be constrained in the area from k + 1 up to k + 1 + Q,
instead of up to K. This leads to computational complexity of order O(log Q) for the F AT T procedure and, consequently
to O(m log Q + n log n) for FTD-Dijkstra. If Q < K, then this complexity is lower compared to O(m log K + n log n). The
resulting algorithm is named Bounded-FTD-Dijkstra (B-FTD-Dijkstra).
If the network has the property that for every arc, every time interval has effective length at least as large as the distance
i
of the arc, i.e., lxy
≥ dxy ∀ < xy >∈ A and ∀i : 0 ≤ i ≤ K − 1, then Q ≤ 1 and B-FTD-Dijkstra has complexity of
O(m + n log n), i.e., equal to the one of classical Dijkstra’s algorithm [3], [14].
The complexity of the existing TD-Dijkstra algorithm as well as of the proposed FTD-Dijkstra and B-FTD-Dijkstra
algorithms, is given in Table I. It must be stated that all the algorithms of Table I (existing and proposed) are optimal
for the networks under investigation.
V. G ENERAL C ASE OF S PEED AS F UNCTION OF T IME I NSIDE THE T IME I NTERVAL
Up to this point, it was assumed (as in [2]) that the speed is considered to be constant inside every time interval. In this
Section, the manipulation of the general case of speed being a function
of time inside a time interval is proposed. Let this
R
function be gkxy (t) for time interval [τk , τk+1 ) and arc < xy >, and gkxy (t) = Gxy
k (t). This general case can be handled by
generalising the notion of effective length (equation 3) as follows:
Z τk+1
xy
xy
lk =
gkxy (t)dt = Gxy
(6)
k (τk+1 ) − Gk (τk )
τk

5 with

τk+1 as time instant of departure, as explained previously

A. Special Case: Constant Speed Inside the Time Interval
The (already investigated) special case of speed being constant in every time interval [τk , τk+1 ), equal to the one measured
at time instant τk (i.e., gkxy (t) = vkxy ) is derived from equation 6 as follows:
lkxy

Z

τk+1

=
τk

gkxy (t)dt

=

vkxy

τk+1

Z

τk

dt = vkxy · (tk+1 − tk )

(7)

Let the F AAT procedure for this case be Constant F AAT (C − F AAT ). Then, C − F AAT is exactly the one presented
in Section IV-B.
B. Special Case: Linear Speed Inside the Time Interval
For the case of speed measurements (as described in Section II), it is more natural to assume that the speed in the arbitrary time
xy
interval [τk , τk+1 ) of arc < xy >6 is a linear function of time (gkxy (t)), taking the values gkxy (τk ) = vkxy and gkxy (τk+1 ) = vk+1
,
xy
rather than being constant, equal to vk for the entire time interval [τk , τk+1 ). To the best of our knowledge, work on this case
cannot be found in the literature for the networks under investigation.
Under the aforementioned assumption, gkxy (t) is derived as follows:
xy
xy
vk+1
−vk
τk+1 −τk
xy
vk+1
−v xy
xy
xy
⇒ gk (t) − vk = τk+1 −τkk · (t − τk )
xy
xy
xy
v xy −vk
vk+1
−vk
xy
⇒ gkxy (t) = τk+1
t
+
(v
−
k
τk+1 −τk τk )
k+1 −τk
xy
xy
xy
xy
v
v
−v
τ
k+1 −vk+1 τk
k
k
⇒ gkxy (t) = τk+1
t
+
τk+1 −τk
k+1 −τk
xy
xy
gk
(t)−vk
t−τk

=

(8)

(9)

If we set,
xy
xy
vk+1
−vk
τk+1 −τk =
xy
xy
vk
τk+1 −vk+1
τk
τk+1 −τk

Rkxy

(10)

= Skxy

(11)

gkxy (t) = Rkxy t + Skxy

(12)

then,

⇒

Gxy
k (t)

=

2
Rkxy t2

+

Skxy t

(13)

From equations 6 and 13, the effective length is derived as follows:
lkxy = Rkxy

2
τk+1
2

+ Skxy τk+1 − Rkxy

τk2
2

− Skxy τk

(14)

Let the F AAT procedure for the current case be Linear F AAT (L − F AAT ). Then, L − F AAT is derived from F AAT
as follows.
•
•

Step 1 remains the same as in F AAT .
In step 2 of the F AAT , vkxy · (τk+1 − τ ) is equal to the distance traversed from τ to τk+1 . This distance in L − F AAT
is given by
R τk+1
τ

gkxy (t)dt = Rkxy

2
τk+1
2

2

+ Skxy τk+1 − Rkxy τ2 − Skxy τ

(15)

– If this distance is equal to or larger than dxy , then the traversal time cxy (τ ) is given by the solution of equation 16,
as follows (where for simplicity, in the intermediate steps for the derivation of equation 17 from equation 16, cxy (τ ),
Rkxy , Skxy and dxy are written as c, R, S and d respectively).
6 where

xy
the speed has been measured at time instants τk and τk+1 with measured values equal to vkxy and vk+1
respectively

R τ +cxy (τ )
⇒

τ
(τ +c)2
R 2
2

gkxy (t)dt = dxy
k

+ S(τ + c) −

2
R τ2 −
2

(16)
Sτ = d

⇒ R(τ + c) + 2S(τ + c) − Rτ − 2Sτ = 2d
⇒ Rτ 2 + Rc2 + 2Rτ c + 2Sτ + 2Sc − Rτ 2 − 2Sτ = 2d
⇒ Rc2 + 2(Rτ + S)c − 2d = 0
√
−2(Rτ +S)± 4(Rτ +S)2 +8Rd
⇒c=
2R
√
xy
xy xy
xy
τ +Skxy )2 +2Rk
d
−(Rk
τ +Skxy )± (Rk
xy
⇒ c (τ ) =
xy
R

(17)

k

– If this distance is less than dxy , the procedure continues to step 3.
•
•

τ2

2

In step 3(a)i, a is set to dxy − Rkxy k+1
Skxy τk+1 − Rkxy τ2 − Skxy τ . Steps 3(a)ii, 3(a)iii and 3(b) remain the same.
2 +
0
is the time needed to traverse distance a − a0 , where this distance is traversed
In step 4 of the F AAT , the quantity a−a
xy
vk
∗
inside time interval [τk∗ , τk∗ +1 ). This time in L − F AAT is given by
R τk∗ +cxy (τ )
τk ∗

⇒ cxy (τk∗ ) =

gkxy∗ (t)dt = a − a0
√ xy
xy
xy

xy
−(Rk
∗ τk∗ +Sk∗ )±

xy
0
(Rk∗ τk∗ +Sk∗ )2 +2Rk
∗ (a−a )
xy
Rk
∗

(18)
(19)

The intermediate steps for derivation of equation 19 from eq. 18 are omitted since they are analogous to derivation of
equation 17 from eq. 16.
Considering the above analysis, the exact steps of the proposed L − F AAT procedure are as follows.
1) Steps of the L − F AT T xy (τ ) Procedure:
1) Locate index k such that τk ≤ τ < τk+1
τ2
xy
xy
xy τ 2
xy
2) If (Rkxy k+1
2 + Sk τk+1 − Rk 2 − Sk τ ≥ d )
cxy (τ ) =

xy
−(Rk
τ +Skxy )±

√

xy
xy xy
(Rk
τ +Skxy )2 +2Rk
d
xy
Rk

Else {
τ2
xy
xy τ 2
xy
3) a) i) a = dxy − Rkxy k+1
2 + Sk τk+1 − Rk 2 − Sk τ
(k+1)+K
∗
ii) k = b
c
2
iii) a0 = 0
b) While (a0 = 0) {
(k+1)+k∗
xy
xy
∗
• If (a < Lk∗ −1 − Lk ) k ← b
c
2
xy
xy
k∗ +K
∗
• Else If (a > Lk∗ − Lk ) k ← b 2 c
xy
xy
xy
xy
xy
xy
0
• Else If (Lk∗ −1 − Lk ≤ a ≤ Lk∗ − Lk ) a = Lk∗ −1 − Lk }
4)
√ xy
xy
xy
xy
2
0
−(Rk
(Rk∗ τk∗ +Skxy
∗ τk∗ +Sk∗ )±
∗ ) +2Rk∗ (a−a )
cxy (τk∗ ) =
xy
R ∗
k

}
The computational complexity of the proposed L − F AAT procedure is O(log K). The routing algorithms for this case are
derived from the ones proposed for the case of constant speeds inside the time interval (Section IV) just by substituting the
F AAT procedure with the L − F AAT .
Note that the F AAT procedure can be modified analogously for the case of speed being an alternative function of time
(rather than linear) inside the time interval.
C. Validity of the FIFO Property for the Generalised Case
In [2], it was proven that the FSM satisfies the FIFO property for the case of constant speeds inside the time interval. In
this Section, it is proven that the FIFO property is also valid for the general case of speed being an arbitrary function of time
(gkxy (t)) inside the time interval.
Consider that for the arbitrary arc < xy >, two vehicles 1, 2 depart from node x on time instants τ1 , τ2 > τ1 respectively,
and arrive at node y on time instants τ10 , τ20 respectively. Obviously, τ10 > τ1 and τ20 > τ2 .

TABLE II
C OMPLEXITY OF EXISTING AND PROPOSED PROCEDURES

Speed inside the time interval

Existing procedure

Proposed procedure

constant value
linear function of time

O(K)
−

O(log K)
O(log K)

To prove that the FIFO property is valid, it must be proven that τ20 > τ10 . The following cases are possible:
•
•

τ 0 >τ2

2
τ2 ≥ τ10 ==
=⇒ τ20 > τ10
τ1 < τ2 < τ10 . The distance dxy is traversed from time instant τ1 to τ10 , and it can be split into distances a and b
(a + b = dxy ), where a is the distance traversed from τ1 to τ2 and b is the distance traversed from τ2 to τ10 . Then,

τ2 > τ1 ⇒ a > 0 ⇒ b < dxy

(20)

From equation 20, it is concluded that the time from τ2 to τ10 is not enough to traverse the whole arc < xy >. Therefore,
vehicle 2 that departs from node x at time instant τ2 will arrive at node y at τ20 > τ10 .
The computational complexity of the existing and proposed procedures for the derivation of the road’s traversal time according
to the time instant of departure, for both the investigated cases of speed having constant value or being a linear function of
time inside the time interval, are presented in Table II.
VI. C ONCLUSIONS
In the current paper, the problem of shortest path routing in transportation networks (in terms of travelling time) where the
speed in several of the network’s roads is a function of the time interval, was investigated. More precisely, it was considered that
the time horizon was split into time intervals, and the speed depended on the time interval. Fast procedures for the derivation
of the road’s traversal time according to the time instant of departure have been proposed. For the case of the speed having
a constant value inside each time interval (in general, different value for each time interval), the proposed procedure is faster
compared to the conventional approaches. Furthermore, for the case of the speed being a linear function of time inside each
time interval (in general, different linear function for each time interval), a procedure is also proposed and, to the best of our
knowledge, relevant approaches cannot be found in the literature.
The proposed procedures were combined with Dijkstra’s algorithm and the resulting algorithms, that are practically applicable
and of low complexity, provide optimal shortest path routing in the networks under investigation.
Future research will focus on the combination of the proposed procedures with more advanced shortest path routing algorithms
that were designed for static networks, in order to derive their versions for time-dependent networks as modelled in the current
paper. Examples of such algorithms are A* [15], Contraction Hierarchies [16], SHARC routing [17]. Although time-dependent
versions of these algorithms can be found in the literature (e.g., [11] for the time-dependent version of Contraction Hierarchies),
these have been designed under the assumption that the traversal time function f xy (τ ) (Section III-B) is a piecewise linear
function of τ . However, as shown in Section III-B1, for time-dependent networks as modelled in the current paper, this is not
always valid.
ACKNOWLEDGMENTS
This work was co-funded by the European Regional Development Fund and the Republic of Cyprus through the Research
Promotion Foundation (Project New Infrastructure/Strategic/0308/26).
R EFERENCES
[1] A. D. May, Traffic flow fundamentals, Prentice Hall, 1990.
[2] K. Sung, M. G. Bell, M. Seong, and S. Park, Shortest paths in a network with time-dependent flow speeds, European Journal of Operational Research,
vol. 121, no. 1, pp. 3239, 2000.
[3] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol. 1, pp. 269271, 1959
[4] K. Cooke and E. Halsey, The shortest route through a network with time-dependent internodal transit times, Journal of Mathematical Analysis and
Applications, vol. 14, no. 3, pp. 493498, 1966.
[5] D. Delling, Time-dependent SHARC-routing, Algorithmica, vol. 60, no. 1, pp. 6094, 2011.
[6] G. Nannicini, D. Delling, D. Schultes, and L. Liberti, Bidirectional A* search on time-dependent road networks, Networks, vol. 59, no. 2, pp. 240251,
2012.
[7] D. Delling and G. Nannicini, Core routing on dynamic time-dependent road networks, INFORMS J. on Computing, vol. 24, no. 2, pp. 187201, Apr.
2012.
[8] D. Delling, P. Sanders, D. Schultes, and D. Wagner, Algorithmics of large and complex networks, J. Lerner, D. Wagner, and K. A. Zweig, Eds. Berlin,
Heidelberg: Springer-Verlag, 2009, ch. Engineering Route Planning Algorithms, pp. 117139.

[9] D. Delling and D. Wagner, Time-dependent route planning, in Robust and Online Large-Scale Optimization, ser. Lecture Notes in Computer Science,
R. Ahuja, R. Mhring, and C. Zaroliagis, Eds. Springer Berlin Heidelberg, 2009, vol. 5868, pp. 207230.
[10] B. Ding, J. X. Yu, and L. Qin, Finding time-dependent shortest paths over large graphs, in Proceedings of the 11th International Conference on Extending
Database Technology: Advances in Database Technology, ser. EDBT 08. New York, NY, USA: ACM, 2008, pp. 205216.
[11] G. V. Batz, R. Geisberger, P. Sanders, and C. Vetter, Minimum time-dependent travel times with contraction hierarchies, J. Exp. Algorithmics, vol. 18,
pp. 1.4:1.11.4:1.43, Apr. 2013.
[12] I. Chabini and S. Lan, Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks, Trans.
Intell. Transport. Sys., vol. 3, no. 1, pp. 6074, Mar. 2002.
[13] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Upper Saddle River, NJ, USA: Prentice-Hall, Inc.,
1993.
[14] M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, vol. 34, no. 3, pp. 596615, Jul.
1987.
[15] P. E. Hart, N. J. Nilsson, and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science
and Cybernetics, vol. SSC-4(2), pp. 100107, 1968.
[16] R. Geisberger, P. Sanders, D. Schultes, and D. Delling, Contraction hierarchies: Faster and simpler hierarchical routing in road networks, in Proceedings
of the 7th International Conference on Experimental Algorithms, ser. WEA08. Berlin, Heidelberg: Springer-Verlag, 2008, pp. 319333.
[17] R. Bauer and D. Delling, SHARC: Fast and robust unidirectional routing, J. Exp. Algorithmics, vol. 14, pp. 4:2.44:2.29, Jan. 2010.

