# Optimal Paths on Urban Networks Using Travelling Times Prevision

Authors: Alfredo Cutolo; Carmine De Nicola; Rosanna Manzo; Luigi Rarità
Journal: Modelling and Simulation in Engineering
 (2012)

---

## Abstract

We deal with an algorithm that, once origin and destination are fixed,
individuates the route that permits to reach the destination in the shortest time,
respecting an assigned maximal travel time, and with risks measure below a given
threshold. A fluid dynamic model for road networks, according to initial car densities
on roads and traffic coefficients at junctions, forecasts the future traffic evolution,
giving dynamical weights to a constrainedK shortest path algorithm. Simulations
are performed on a case study to test the efficiency of the proposed procedure.


---

## Body

## 1. Introduction

Traffic congestion on networks occurs in presence of an excess use of vehicles on a portion of roadway and is characterized by stopped or stop-and-go traffic, slower speeds, longer trip times, and increased queueing. Incidents (such as accidents or even a single car breaking heavily in a previously smooth flow) may cause ripple effects which then spread out and create a sustained traffic jam. The presence of hard congestions on urban networks provoke delays, which may result in late arrival and interference with emergency vehicles passage to reach their destinations. The shortest path is not often the less congested one and/or the most safe one, so it is crucial to forecast travel times and to find the shortest path taking into account the traffic conditions and the risks along the path.Finding theK shortest paths is a classical network optimization problem and it has a great practical interest, with a wide variety of real world applications, such as transport, communication, and distribution networks, for which finding alternative paths plays an important role, in particular when some nodes are temporarily unreachable through the optimal route, because some links are obstructed or unavailable.In such a context, we propose an algorithm that, once an origino and a destination d on a graph are fixed, identifies the path that connects o and d and minimizes forecasted travel times, satisfying a maximal travel time and a maximal accepted risks threshold. In particular, following [1] and considering additional constraints on risk levels and dynamical travel times, we use a particular extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem (see, e.g., [2, 3]). The aim is to satisfy the user request: a driver could prefer a route with minimal travel time even if the trip is not safe, a longer but with no risks trip, or a safe and short path.Here the travel times are estimated using a fluid dynamic model (see [4, 5]), where the cars evolution on each road is given by a conservation law [6–8], while the dynamics at junctions is uniquely solved adopting the following rules: the incoming traffic at a node is distributed to outgoing roads according to some fixed distribution coefficients; drivers behave so as to maximize the flux through the junction. A further rule (yielding criterion) is needed if the number of incoming roads is greater than that of outgoing ones.The algorithm, that allows to identify the optimal path, is as follows. Fix an origino and a destination d in a road network graph. From the initial densities on roads, we predict future densities and then travelling times on all network roads. The latter are the weights of a Constrained K-Shortest Paths algorithm (CKSPa). Using a further procedure (analyzed in [9]), that computes the trajectory of a car on a network, we compute the time t1 at which a car reaches the successive node s1. At t1, if the current density conditions are different from the forecasted ones, average density values on roads are computed invoking again the simulator with new initial conditions and the new densities are used as weights (travel times) that the CKSPa needs to select the optimal arc among those outgoing from s1. The time t2 a car needs to cover the latter arc is computed; at t2, new weights are obtained by the density values and the CKSPa indicates the new arc of the optimal path; and so on, until the destination o is reached.The goodness of this procedure is studied via simulations (numerics are obtained using [10–12]). We consider the case study of a portion of the Caltanissetta urban network, in Italy, and determine through the CKSPa the optimal route connecting an origin o and a destination d. It is shown that the time to cross the optimal route is lower than times needed to cover all the other possible paths joining o and d. Notice that the optimal path is time-variable, as weights continuously change due to the densities evolutions on road. Hence different paths are found if the travel starts in different times with different traffic conditions.We remark that the fluid dynamic model needs real traffic data as initial densities on the road network in order to obtain simulations reproducing real phenomena. Then, the idea is to get data detected by special sensors installed in some points of each road or by databases containing traffic information. A procedure to reconstruct the initial density by detected real traffic data and to calibrate the fluid dynamic model is shown in [13].The paper is organized as follows. Section2 reports the model for urban networks, giving details about the construction of Riemann Solvers at junctions and numerical schemes for densities on roads. In Section 3, the Constrained K-Shortest Paths Problem is described. The integration of the fluid dynamic model and the CKSPa is presented in Section 4. Finally Section 5 deals with simulations for the case study. The paper ends in Section 6 through conclusions.


## 2. Fluid-Dynamic Traffic Flow Model

A road network is described by a couple(ℐ,𝒥), where ℐ is the set of roads, modelled by intervals [ai,bi]⊂ℝ, i=1,…,N, and 𝒥 the collection of junctions. On each road, the traffic evolution is given by the conservation law:(1)∂tρ+∂xf(ρ)=0,
where ρ=ρ(t,x)∈[0,ρmax] represents the cars density, ρmax is the maximal density, while f(ρ)=ρv(ρ) is the flux with v(ρ) the average velocity. We assume that(F)
f is a strictly concave C2 function such that f(0)=f(ρmax)=0.Choosing a decreasing velocity functionv(ρ)=vmax(1-ρ/ρmax), ρ∈[0,ρmax], and setting vmax=ρmax=1, a flux function ensuring (F) is(2)f(ρ)=ρ(1-ρ),ρ∈[0,1],
which has a unique maximum σ=1/2.Dynamics at junctions is described solving Riemann Problems (RPs) and Cauchy Problems with a constant initial datum for each incoming and outgoing road (see [4, 5]).Fix a junctionJ of n×m type (n incoming roads Iφ, φ=1,…,n, and m outgoing roads Iψ, ψ=n+1,…,n+m) and an initial datum ρ0=(ρ1,0,…,ρn,0,ρn+1,0,…,ρn+m,0).Definition 1.
A Riemann Solver (RS) for the junctionJ is a map RS:[0,1]n×[0,1]m→[0,1]n×[0,1]m that associates to ρ0 a vector ρ̂=(ρ̂1,…,ρ̂n,0,ρ̂n+1,…,ρ̂n+m) so that the solution on an incoming road Iφ is the wave (ρφ,0,ρ̂φ) and on an outgoing one Iψ is the wave (ρ̂ψ,ρψ,0). We require the following conditions hold: (C1) RS(RS(ρ0))=RS(ρ0); (C2) on each road Iφ the wave (ρφ,0,ρ̂φ) has negative speed, while on each road Iψ the wave (ρ̂ψ,ρψ,0) has positive speed.Ifm≥n, a possible RS at J is defined by the following rules:(A)
Car traffic is distributed atJ according to some coefficients, collected in a traffic distribution matrix A=(αψ,φ), φ=1,…,n,  ψ=n+1,…,n+m, 0<αψ,φ<1, ∑ψ=n+1n+mαψ,φ=1. The φ column of A indicates the percentages of traffic that, from the incoming road Iφ, distribute to the outgoing roads.(B)
Fulfilling (A), drivers maximize the flux throughJ.If n>m, a further rule (a yielding criterion) is necessary:(C)
Assume that not all cars can enter the outgoing roads, and letC be the amount that can do it. Then, pφC cars come from the first incoming road Iφ, where pφ∈]0,1[ is the right of way parameter of road Iφ, φ=1,…,n, and ∑φ=1npφ=1.Assuming an initial datum ρ0 and the flux function (2), the solution ρ̂=f-1(γ̂) to the RS at J is defined by
(3)ρ̂φ∈{{ρφ,0}∪]τ(ρφ,0),1],if0≤ρφ,0≤12,[12,1],if12≤ρφ,0≤1,ρ̂ψ∈{[0,12],if0≤ρψ,0≤12,{ρψ,0}∪[0,τ(ρψ,0)[,if12≤ρψ,0≤1,
where τ:[0,1]→[0,1] is the map such that f(τ(ρ))=f(ρ) for every ρ∈[0,1] and τ(ρ)≠ρ for every ρ∈[0,1]∖{1/2}.


### 2.1. Riemann Solvers

Focus on a junctionJ of n×m type. We indicate the cars density on incoming and outgoing roads, respectively, by ρφ(t,x)∈[0,1], (t,x)∈ℝ+×Iφ, ρψ(t,x)∈[0,1], (t,x)∈ℝ+×Iψ. From condition (C2), fixing the flux function (2) and assuming ρ0=(ρ1,0,…,ρn,0,ρn+1,0,…,ρn+m,0) as the initial datum of an RP at J, the maximal flux values on roads are defined by(4)γφmax⁡={f(ρφ,0),if0≤ρφ,0≤12,f(12),if12≤ρφ,0≤1,γψmax⁡={f(12),if0≤ρψ,0≤12,f(ρψ,0),if12≤ρψ,0≤1.


#### 2.1.1. A1×1 Junction

For a1×1 junction, with incoming road indicated by 1 and outgoing one by 2, the flux solution to the RP at J is γ̂=(γ̂a,γ̂a), where γ̂a=min{γamax,γbmax}.


#### 2.1.2. A1×2 Junction

Consider a1×2 junction and label the incoming road by 1 and outgoing roads by 2 and 3. If α∈]0,1[ and 1-α indicate, respectively, the percentage of cars that, from road 1, goes to the outgoing roads 2 and 3, the flux solution to the RP at J is γ̂=(γ̂1,αγ̂1,(1-α)γ̂1), where γ̂1=min{γ1max,γ2max/α,γ3max/(1-α)}.


#### 2.1.3. A2×1 Junction

Fix a2×1 junction and indicate by 1 and 2 the incoming roads, and by 3 the outgoing road. In this case, we have only a right of way parameter, p. Since, from rule (B), the aim is to maximize the through traffic, we set γ̂3=min{γ1max+γ2max,γ3max}. Introduce the following conditions:(A1)
pγ3max<γ1max;(A2)
(1-p)γ3max<γ2max.Ifγ̂3=γ1max+γ2max, then γ̂=(γ1max,γ2max,γ1max+γ2max). If γ̂3=γ3max, we have the following:(i)
γ̂=(pγ3max,(1-p)γ3max,γ3max), when (A1) and (A2) are both satisfied;(ii)
γ̂=(γ3max-γ2max,γ2max,γ3max), when (A1) is satisfied and (A2) does not hold;(iii)
γ̂=(γ1max,γ3max-γ1max,γ3max), when (A1) is not satisfied and (A2) holds.Conditions (A1) and (A2) are never both false, otherwiseγ3max>γ1max+γ2max.


#### 2.1.4. A2×2 Junction

For a junction of  2 × 2 type, with incoming roads 1 and 2, and outgoing roads 3 and 4, the traffic distribution matrixA assumes the form:(5)A=(α3,1α3,2α4,1α4,2)
where α3,1 and α3,2 are the probabilities that drivers go, respectively, from road 1 and road 2 to road 3 and α4,1=1-α3,1, α4,2=1-α3,2. Let us suppose that α3,1≠α3,2 in order to ensure uniqueness of solutions.From rule (A), it follows thatγ̂3=α3,1γ̂1+α3,2γ̂2, γ̂4=(1-α3,1)γ̂1+(1-α3,2)γ̂2. From rule (B), we have that the incoming fluxes γ̂φ, φ=1,2, are solutions of the linear programming problem max (γ1+γ2), with 0≤γφ≤γφmax, φ=1,2, 0≤α3,1γ1+α3,2γ2≤γ3max, 0≤(1-α3,1)γ1+(1-α3,2)γ2≤γ4max.Observe that, for all the examined junctions types, onceγ̂ is known, ρ̂ is found by (3).


### 2.2. Numerical Approximations

To construct numerical approximations for the densityρ(t,x), whose evolution is ruled by (1), we apply the Godunov scheme (see [10–12]). Assume the flux (2). We introduce a numerical grid with(i)
Δx being the space grid size on each road Ii;(ii)
Δt being the time grid size on the time interval [0,T¯];(iii)
L and M, respectively, being the number of time and space nodes of the grid;(iv)
(tl,xm)=(lΔt,mΔx), for l=0,1,…,L and m=0,1,…,M, being the grid points.Using the notationρml=ρ(tl,xm), the Godunov scheme is expressed as follows:(6)ρml+1=ρml-ΔtΔx(fG(ρml,ρm+1l)-fG(ρm-1l,ρml)),l=0,1,…,L-1,m=0,1,…,M,
where Δt and Δx satisfy the CFL condition Δt≤Δx/2, and fG(u,v) is the numerical flux given by(7)fG(u,v)={min⁡(f(u),f(v)),u≤v,f(u),v<u<12,f(12),v<12<u,f(v),12<v<u.Boundary conditions are imposed for incoming roads not linked on the left and outgoing roads not linked on the right. In particular, for roads connected at the right endpoint, the interaction at a junction is given by(8)ρMl+1=ρMl-ΔtΔx(γ̂φ-fG(ρM-1l,ρMl)),
while, for roads connected at the left endpoint, we have(9)ρ0l+1=ρ0l-ΔtΔx(fG(ρ0l,ρ1l)-γ̂ψ),
where γ̂φ and γ̂ψ are the fluxes, respectively, on incoming and outgoing roads, computed using RSs at junctions.


## 2.1. Riemann Solvers

Focus on a junctionJ of n×m type. We indicate the cars density on incoming and outgoing roads, respectively, by ρφ(t,x)∈[0,1], (t,x)∈ℝ+×Iφ, ρψ(t,x)∈[0,1], (t,x)∈ℝ+×Iψ. From condition (C2), fixing the flux function (2) and assuming ρ0=(ρ1,0,…,ρn,0,ρn+1,0,…,ρn+m,0) as the initial datum of an RP at J, the maximal flux values on roads are defined by(4)γφmax⁡={f(ρφ,0),if0≤ρφ,0≤12,f(12),if12≤ρφ,0≤1,γψmax⁡={f(12),if0≤ρψ,0≤12,f(ρψ,0),if12≤ρψ,0≤1.


### 2.1.1. A1×1 Junction

For a1×1 junction, with incoming road indicated by 1 and outgoing one by 2, the flux solution to the RP at J is γ̂=(γ̂a,γ̂a), where γ̂a=min{γamax,γbmax}.


### 2.1.2. A1×2 Junction

Consider a1×2 junction and label the incoming road by 1 and outgoing roads by 2 and 3. If α∈]0,1[ and 1-α indicate, respectively, the percentage of cars that, from road 1, goes to the outgoing roads 2 and 3, the flux solution to the RP at J is γ̂=(γ̂1,αγ̂1,(1-α)γ̂1), where γ̂1=min{γ1max,γ2max/α,γ3max/(1-α)}.


### 2.1.3. A2×1 Junction

Fix a2×1 junction and indicate by 1 and 2 the incoming roads, and by 3 the outgoing road. In this case, we have only a right of way parameter, p. Since, from rule (B), the aim is to maximize the through traffic, we set γ̂3=min{γ1max+γ2max,γ3max}. Introduce the following conditions:(A1)
pγ3max<γ1max;(A2)
(1-p)γ3max<γ2max.Ifγ̂3=γ1max+γ2max, then γ̂=(γ1max,γ2max,γ1max+γ2max). If γ̂3=γ3max, we have the following:(i)
γ̂=(pγ3max,(1-p)γ3max,γ3max), when (A1) and (A2) are both satisfied;(ii)
γ̂=(γ3max-γ2max,γ2max,γ3max), when (A1) is satisfied and (A2) does not hold;(iii)
γ̂=(γ1max,γ3max-γ1max,γ3max), when (A1) is not satisfied and (A2) holds.Conditions (A1) and (A2) are never both false, otherwiseγ3max>γ1max+γ2max.


### 2.1.4. A2×2 Junction

For a junction of  2 × 2 type, with incoming roads 1 and 2, and outgoing roads 3 and 4, the traffic distribution matrixA assumes the form:(5)A=(α3,1α3,2α4,1α4,2)
where α3,1 and α3,2 are the probabilities that drivers go, respectively, from road 1 and road 2 to road 3 and α4,1=1-α3,1, α4,2=1-α3,2. Let us suppose that α3,1≠α3,2 in order to ensure uniqueness of solutions.From rule (A), it follows thatγ̂3=α3,1γ̂1+α3,2γ̂2, γ̂4=(1-α3,1)γ̂1+(1-α3,2)γ̂2. From rule (B), we have that the incoming fluxes γ̂φ, φ=1,2, are solutions of the linear programming problem max (γ1+γ2), with 0≤γφ≤γφmax, φ=1,2, 0≤α3,1γ1+α3,2γ2≤γ3max, 0≤(1-α3,1)γ1+(1-α3,2)γ2≤γ4max.Observe that, for all the examined junctions types, onceγ̂ is known, ρ̂ is found by (3).


## 2.1.1. A1×1 Junction

For a1×1 junction, with incoming road indicated by 1 and outgoing one by 2, the flux solution to the RP at J is γ̂=(γ̂a,γ̂a), where γ̂a=min{γamax,γbmax}.


## 2.1.2. A1×2 Junction

Consider a1×2 junction and label the incoming road by 1 and outgoing roads by 2 and 3. If α∈]0,1[ and 1-α indicate, respectively, the percentage of cars that, from road 1, goes to the outgoing roads 2 and 3, the flux solution to the RP at J is γ̂=(γ̂1,αγ̂1,(1-α)γ̂1), where γ̂1=min{γ1max,γ2max/α,γ3max/(1-α)}.


## 2.1.3. A2×1 Junction

Fix a2×1 junction and indicate by 1 and 2 the incoming roads, and by 3 the outgoing road. In this case, we have only a right of way parameter, p. Since, from rule (B), the aim is to maximize the through traffic, we set γ̂3=min{γ1max+γ2max,γ3max}. Introduce the following conditions:(A1)
pγ3max<γ1max;(A2)
(1-p)γ3max<γ2max.Ifγ̂3=γ1max+γ2max, then γ̂=(γ1max,γ2max,γ1max+γ2max). If γ̂3=γ3max, we have the following:(i)
γ̂=(pγ3max,(1-p)γ3max,γ3max), when (A1) and (A2) are both satisfied;(ii)
γ̂=(γ3max-γ2max,γ2max,γ3max), when (A1) is satisfied and (A2) does not hold;(iii)
γ̂=(γ1max,γ3max-γ1max,γ3max), when (A1) is not satisfied and (A2) holds.Conditions (A1) and (A2) are never both false, otherwiseγ3max>γ1max+γ2max.


## 2.1.4. A2×2 Junction

For a junction of  2 × 2 type, with incoming roads 1 and 2, and outgoing roads 3 and 4, the traffic distribution matrixA assumes the form:(5)A=(α3,1α3,2α4,1α4,2)
where α3,1 and α3,2 are the probabilities that drivers go, respectively, from road 1 and road 2 to road 3 and α4,1=1-α3,1, α4,2=1-α3,2. Let us suppose that α3,1≠α3,2 in order to ensure uniqueness of solutions.From rule (A), it follows thatγ̂3=α3,1γ̂1+α3,2γ̂2, γ̂4=(1-α3,1)γ̂1+(1-α3,2)γ̂2. From rule (B), we have that the incoming fluxes γ̂φ, φ=1,2, are solutions of the linear programming problem max (γ1+γ2), with 0≤γφ≤γφmax, φ=1,2, 0≤α3,1γ1+α3,2γ2≤γ3max, 0≤(1-α3,1)γ1+(1-α3,2)γ2≤γ4max.Observe that, for all the examined junctions types, onceγ̂ is known, ρ̂ is found by (3).


## 2.2. Numerical Approximations

To construct numerical approximations for the densityρ(t,x), whose evolution is ruled by (1), we apply the Godunov scheme (see [10–12]). Assume the flux (2). We introduce a numerical grid with(i)
Δx being the space grid size on each road Ii;(ii)
Δt being the time grid size on the time interval [0,T¯];(iii)
L and M, respectively, being the number of time and space nodes of the grid;(iv)
(tl,xm)=(lΔt,mΔx), for l=0,1,…,L and m=0,1,…,M, being the grid points.Using the notationρml=ρ(tl,xm), the Godunov scheme is expressed as follows:(6)ρml+1=ρml-ΔtΔx(fG(ρml,ρm+1l)-fG(ρm-1l,ρml)),l=0,1,…,L-1,m=0,1,…,M,
where Δt and Δx satisfy the CFL condition Δt≤Δx/2, and fG(u,v) is the numerical flux given by(7)fG(u,v)={min⁡(f(u),f(v)),u≤v,f(u),v<u<12,f(12),v<12<u,f(v),12<v<u.Boundary conditions are imposed for incoming roads not linked on the left and outgoing roads not linked on the right. In particular, for roads connected at the right endpoint, the interaction at a junction is given by(8)ρMl+1=ρMl-ΔtΔx(γ̂φ-fG(ρM-1l,ρMl)),
while, for roads connected at the left endpoint, we have(9)ρ0l+1=ρ0l-ΔtΔx(fG(ρ0l,ρ1l)-γ̂ψ),
where γ̂φ and γ̂ψ are the fluxes, respectively, on incoming and outgoing roads, computed using RSs at junctions.


## 3. Constrained K-Shortest Paths Problem

Consider a road network(ℐ,𝒥) and an integer K>1. Assigned an origin o and a destination d, according to the user profile and hence the available travelling time and the maximal accepted risk, the problem of finding K alternative paths from o to d is known as ConstrainedK-Shortest Paths Problem, CKSPP. In particular, we refer to a specified constraints class, the Recursive Path Constraints, RPC, which considers more arcs in one time, evaluating their admissibility, conditioned on the presence of previous arcs in the path.We deal with a modification of the study proposed in [1], taking into account(i)
an origino and a destination d;(ii)
a maximal numberKmax of paths to generate;(iii)
time instant in which the request by the user occurs;(iv)
predicted travel timestij, dependent on the day hours, for the arc I=(i,j)∈ℐ, that connects nodes i and jbelonging to 𝒥;(v)
riskrij for the arc I=(i,j)∈ℐ, joining nodes i and jin 𝒥; the risk measure goes from 0 (extremely safe) to 10 (extremely unsafe);(vi)
a maximal timeT to complete the path;(vii)
a maximal risk levelR.The aim is to individuateK paths (K≤Kmax) from the origin o to the destination d which minimize the travelling time, under constraints on the maximal path time and the risk level. We indicate by rj(k) the risk to reach the node j through the k-th path P(k), by wj(k) the number of occurrence of node j in the k-th path, and by dj(k) an upper bound for the length of the k-th path from the origin o to the node j.Ak-th path is admissible if rj(k)≤R and wj(k)≤1 for all j∈𝒥.In what follows we use the following dominance criterion: letP1(k) and P2(k) be two k-th paths to which labels (d1(k),r1(k),P1(k)) and (d2(k),r2(k),P2(k)) are associated. Then, P1(k) dominates P2(k) if: d2(k)≥d1(k); r2(k)≥r1(k); |P2(k)|≥|P1(k)|; at least one inequality is satisfied in strict sense.We report the pseudocode of the proposed algorithm. Initially,(10)do(k)=0,k=1,…,Kmax⁡,dd(k)=∞,∀d≠o,k=1,…,Kmax⁡,J(1)={o},J(k)=∅,∀k≠1.
For all ξ=1,…,Kmax,(1)
remove a nodei from 𝒥(ξ);(11)∀j∈J∖{o}:{(i,j)∈I,wj(ξ)=0,di(ξ)+tij≤T,ri(ξ)+rij≤R};
find, if it is possible, the smallest index k¯≤Kmax such that(a)
if(12)dj(k¯)=di(ξ)+tij,(di(ξ)+tij,ri(ξ)+rij,P(ξ)∪j)dominates(dj(k¯),rj(k¯),P(k¯)),
set(13)dj(k¯)⟵di(ξ)+tij;rj(k¯)⟵ri(ξ)+rij;wj(k¯)⟵wj(ξ)+1;dj(k¯)⟵di(ξ)+tij;P(k¯)⟵P(k¯)∪j.
Erase the paths (dj(k),rj(k),P(k)), k=k¯+1,…,k̃, dominated by (dj(k¯),rj(k¯),P(k¯)), where k̃ is the greatest index such that k¯≤k̃, and dj(k̃)<∞.Update in coherent waydj(k), rj(k), and wj(k) for all k such that (dj(k),rj(k),P(k)) is not dominated;(b)
if(14)dj(k¯)>di(ξ)+tij,(di(ξ)+tij,ri(ξ)+rij,P(ξ)∪j)dominates(dj(k¯-1),rj(k¯-1),P(k¯-1)),set(15)dj(k¯)⟵di(ξ)+tij;rj(k¯)⟵ri(ξ)+rij;wj(k¯)⟵wj(ξ)+1;P(k¯)⟵P(k¯)∪j.
Erase the paths (dj(k),rj(k),P(k)), k=k¯+1,…,k̃, dominated by (dj(k¯),rj(k¯),P(k¯)), where k̃ is the greatest index such that k¯≤k̃, and dj(k̃)=∞.Update in coherent waydj(k), rj(k), and wj(k) for all k such that (dj(k),rj(k),P(k)) is not dominated; for all k=k¯,…,k̃+1: if (dj(k),rj(k),P(k)) has been erased, remove j from 𝒥(k); otherwise, if j∉𝒥(k), add j to 𝒥(k).(2)
if𝒥(ξ)≠∅, go to Step 1.According to the node selection policy adopted in Step 1, a label setting method is used (see [1]), in which, at each iteration, the node i exiting 𝒥(ξ), ξ=1,…,Kmax is the node with the minimum label. Due to the assumption of the nonnegative arc lengths, node i, once removed, has a permanent label value.


## 4. Integration of Traffic Flow Simulator with CKSPa

Fix an origino and a destination d in a urban network graph. The optimal route, joining o and d, is found using the CKSPa and weighting the arcs with travel times.As risk coefficients we consider earthquakes, high accidents rate, landslides, floods, high crime zones, and so forth. To each arc we associate a risk, given as the average value on all risk parameters related to the arc with values ranging from 0 to 10. The latter are obtained from historical series.Variable travel times are computed using the fluid-dynamic model. Fixing the arcI=(i,j)∈ℐ, that connects nodes i and j belonging to 𝒥, the time to cross I, namely, the weight tij, follows the relation:(16)tij(t)=∫Idxv(ρI(t,x)),
with v(ρI)=1-ρI being the velocity and LI being the length of I.Since the traffic conditions can change during the trip, when the passenger is near a junction, a new simulation is invoked if current densities are different from those predicted by the model. The time in which a single vehicle reaches the junctions is estimated considering that the position of the car driver,x=x(t), along a arc is obtained solving the Cauchy problem:(17){ẋ=v(ρ(t,x)),x(tin)=xin,
where xin is the initial position at the initial time tin (see [9]).For finding the optimal route on the network in a generic time instantt0, the CKSPa individuates, among all possible arcs exiting from the origin o, the arc Iψ with minimal travel time toψ(t0) connecting o with the node ψ. The second arc of the optimal path is found estimating the time t1 a car needs to cross the arc Iψ according to (17). At the time instant t1, arc weights are updated using (16) invoking a new simulation if it is necessary and the CKSPa indicates, among all arcs exiting from the node ψ, the arc Iψ′, that connects the nodes ψ and ψ′ with weight tψψ′(t1). The time t2 a car needs to cover Iψ′ is computed again using (17); at t2, new arc weights (if it is necessary) are obtained and the CKSPa determines the new arc of the optimal path; and so on, until the destination d is reached.Notice that the choice of the initial timet0 strongly influences the evolution of the optimal path. This is a direct consequence of the temporal evolution of densities on arcs.


## 5. A Case Study

The case study is a portion of the real urban network in Caltanissetta, Italy. In Figure1, we report the geographical map of the chosen network, inside the rectangle, with origin and destination points.Figure 1
Map of a portion of Caltanissetta city.The network as in the graph of Figure2 consists of 47 nodes, labelled as ji, i=1,…,47, and 13 roads, identified by 86 segments (see Table 1). We have 10 incoming roads (1, 5, 24, 35, 40, 47, 52, 57, 69, 83) and 11 outgoing ones (2, 4, 22, 26, 30, 36, 38, 45, 51, 55, 65), while the others are inner.Table 1
Correspondence among roads names and numbers in the graph of Figure2.
Real roadGraph roads/segmentsVia Giuseppe Mulè1, 2Via Luigi Monaco3–14, 32, 33, 36, 37, 41–43Via Luigi Russo38–40Via Poggio S. Elia29–31, 34, 35Via della Regione15, 17–25, 27, 28Via Cittadella26Via Aci16, 64, 67, 68, 81Via Malta65, 66, 73, 74, 77–80, 82, 84–86Corso Italia83Via Galatea69–72, 75, 76Via Leone XIII54–61Via Due Fontane44–50, 53, 62, 63Via Sd151, 52Figure 2
Graph associated to the Caltanissetta network.Fixing the origino=j2 and the destination d=j32, four different paths Pi, i=1,2,3,4, indicated as sequential ordered sets of roads, connect o and d:(18)P1=Λ1∪Λ2,P2=Λ1∪Λ3,P3=Λ4∪Λ2,P4=Λ4∪Λ3,
where Λ1, Λ2, Λ3, and Λ4 are defined as(19)Λ1={7,9,11,12,13,15,17},Λ2={18,19,20,21},Λ3={67,68,70,71,76,82,84,21},Λ4={7,43,44,46,48,50,53,56,58,60,13,15,17}.
Risk parameters for all road segments are in Table 2.Table 2
Risks for all road segments.
Graph roads/segmentsRisk3, 8, 10, 29, 31, 34, 41–44, 59, 60, 70, 71, 7616, 7, 9, 11–13, 16, 23, 25, 27–29, 33, 37, 39, 48–50, 53, 56, 58, 61–63, 67, 68, 75, 81, 82, 84–86214, 15, 17–21, 46, 54, 64, 72, 74366, 73, 77, 78, 804795The analysis of the various paths is made considering six different simulation cases whose characteristics are the following.Case A
Initial conditions are zero for all roads (namely empty network); boundary data: 0.1 for road 35; 0.2 for roads 1, 5, 40, 47, 52, and 57; 0.4 for road 24, 69, and 83; 1 for all outgoing roads; and maximal timeT and maximal risk level R equal to 200 and 100, respectively.Case B
Initial conditions are zero for all roads; boundary data: 0.1 for road 35; 0.2 for roads 1, 5, 40, 47, 52, 57, 69, and 83; 0.4 for roads 24; 1 for all outgoing roads; and maximal time and maximal risk as in Case A.Case C
Initial conditions are zero for all roads, with the exception of roads 70, 71, 76, and 82 with initial datum 0.3; roads 67 and 68, for which the initial datum is 0.4; roads 9, 11 and 12 with initial datum 0.7; boundary data: 0.01 for roads 47, 52, and 57; 0.1 for road 35; 0.2 for roads 1, 5, and 40; 0.3 for roads 69 and 83; 0.4 for road 24; 1 for all outgoing roads; and maximal time as in Case A and maximal risk levelR=400.Case D
Initial conditions are zero for all roads, with the exception of roads 13 and 15 with initial datum 0.5; roads 9, 11, and 12, for which the initial datum is 0.7; roads 18, 19 and 20 with initial datum 0.9; boundary data: 0.01 for roads 52, 57, 69, and 83; 0.1 for roads 1, 5, 24, 35, 40, and 47; and 1 for all outgoing roads. Maximal time as in Case A and maximal risk levelR are equal to 500.Case E
Initial conditions, boundary data, and maximal time are as in Case A; maximal risk level isR=29.Case F
Initial conditions, boundary data, and maximal time are as in Case A; maximal risk level isR=31.Notice that a boundary datum equal toρmax=1 on outgoing roads indicates that high congestion phenomena may occur when the car traffic flows out of the network. Moreover, the difference in initial conditions discriminates the traffic behaviour, hence leading to a probable different choice of the optimal path.For all previous simulation cases, right of way parameters and distribution coefficients are chosen as in Tables3, 4, and 5.Table 3
Right of way parameters for2×1 junctions.
Nodes2×1Right of way parametersj2p5=0.6p6=0.4j6p39=0.6p40=0.4j10p12=0.6p60=0.4j18p46=0.4p47=0.6j21p50=0.7p52=0.3j23p56=0.4p57=0.6j26p16=0.3p27=0.7j31p23=0.7p24=0.3j33p20=0.6p84=0.4j35p82=0.6p83=0.4j37p75=0.4p86=0.6j41p68=0.7p69=0.3j44p79=0.6p81=0.4j45p77=0.6p78=0.4j47p73=0.4p74=0.6Table 4
Right of way parameters for1×2 junctions.
Nodes1×2Distribution coefficientsj3α2=0.3α3=0.7j4α42=0.8α8=0.2j8α10=0.3α11=0.7j11α14=0.3α15=0.7j14α30=0.3α31=0.7j16α44=1j19α49=0.3α63=0.7j24α59=0.4α60=0.6j28α18=0.4α67=0.6j29α19=0.7α78=0.3j30α26=0.4α27=0.6j32α22=0.4α23=0.6j34α20=0.7α85=0.3j36α86=1j38α75=0.4α82=0.6j39α72=0.6α76=0.4j40α71=1j43α64=0.4α65=0.6j46α73=0.4α81=0.6Table 5
Distribution parameters for2×2 junctions.
Nodes2×2Distribution coefficientsj1α6,1=0.3α4,1=0.7α6,3=0.7α4,3=0.3j5α9,7=0.8α43,7=0.2α9,8=0.8α43,8=0.2j7α38,10=0.2α39,10=0.8α38,37=0.7α39,37=0.3j9α12,11=0.6α61,11=0.4α12,33=0.3α61,33=0.7j12α29,14=0.3α32,14=0.7α29,28=0.4α32,28=0.6j13α33,32=0.8α37,32=0.2α33,34=0.3α37,34=0.7j15α36,31=0.3α34,31=0.7α36,35=0.2α34,35=0.8j17α45,44=0.1α46,44=0.9α45,63=0.2α46,63=0.8j20α50,48=0.6α51,48=0.4α50,49=0.6α51,49=0.4j22α55,53=0.4α56,53=0.6α55,54=0.6α56,54=0.4j25α54,59=0.4α62,59=0.6α54,61=0.4α62,61=0.6j27α16,15=0.3α17,15=0.7α16,64=0.1α17,64=0.9j42α66,67=0.4α68,67=0.6α66,80=0.6α68,80=0.4


### 5.1. Simulation Results

Densities on network roads are evaluated numerically by the Godunov scheme, with space stepΔx=0.1 and time step determined by the CFL condition.For each simulation case we have a different optimal path, as reported in Table6, due to the different evolution of densities when different maximal risk levels and initial and boundary conditions are used. The maximal travel time constraint is satisfied in all cases by the optimal path.Table 6
Different optimal paths for different simulation cases.
CaseABCDEFPathP2P1P3P4P1P2The goodness of the obtained results is also confirmed estimating the timeTod a car needs to reach the destination j32, starting from the origin j2 (numerics are in [9]), in the different cases for all the alternative paths (see Table 7, where lengths in Kilometers and the sum of risks along paths, Sr, are also reported).Table 7
Tod for different paths and simulation cases.
PathCase A, E, FCase BCase CCase DP1 (Km 1.725), Sr = 2813.6413.6829.7629.44P2 (Km 1.675), Sr = 3013.1214.7632.7628.16P3 (Km 2.351), Sr = 3845.2033.9621.6422.04P4 (Km 2.331), Sr = 4036.5635.7624.4421.36First of all, notice that, as maximal risk levels are very high for Cases A, B, C, and D, the computation of the optimal path in such cases is influenced only by timesTod. In Case A, the optimal path is the shortest one, P2, unlike Case C, where the optimal route has the highest length. In fact for Case C, P2 is more congested than P1, P3, and P4.Cases A, E, and F have the same timesTod as they have the same initial conditions and boundary data but a different maximal risk level. However, while Cases A and F have the same optimal route P2, since it respects risk constraint, in Case E, due to the maximal risk level, lower than those of Cases A and F, P1 is the better path. Notice that the determination of K-Shortest Paths together with the computation of the total risk associated to each path allows to choose not the optimal path in terms of travel times but the one with a lower level risk, and a Tod not far from the lowest one.We make a further analysis on the density evolutions for some roads of the junctionj5. Notice that, from road 7, a driver can choose road 9 or 43. In Figures 3 and 4, we report the behaviour of densities on such roads for simulation Cases B and C.Comparison among density evolutions for road segments 9 (a) and 43 (b), Case C.
(a)(b)Comparison among density evolutions for road segments 9 (a) and 43 (b), Case B.
(a)(b)In Case C, road 43 belongs to the optimal pathP3 and its density grows slowly, as the one of road 9 does. Indeed, the density values on the two roads are very different; road 9 has a higher traffic due to the superpositions of more rarefaction traffic waves with respect to road 43 with 0.060828 and 0.413329 maximal densities on roads 43 and 9, respectively.Case B is more interesting. Road 9 belonging to the optimal pathP1 has a quick evolution of density with respect to the one of road 43. High-density fluctuations are the result of dynamics at junctions j4,j5, and j6: road 8 shock waves coming from roads 41 and traffic flow coming from road 40. In particular the maximal value of the density reached on road 9 is 0.346572, while on road 43 the density is less than or equal to 0.060384. This does not contradict the fact that the average travel time is minimized going on road 9, since the path P1 is less congested than the paths P3 and P4, determined by the choice of road 43 at junction j5.


## 5.1. Simulation Results

Densities on network roads are evaluated numerically by the Godunov scheme, with space stepΔx=0.1 and time step determined by the CFL condition.For each simulation case we have a different optimal path, as reported in Table6, due to the different evolution of densities when different maximal risk levels and initial and boundary conditions are used. The maximal travel time constraint is satisfied in all cases by the optimal path.Table 6
Different optimal paths for different simulation cases.
CaseABCDEFPathP2P1P3P4P1P2The goodness of the obtained results is also confirmed estimating the timeTod a car needs to reach the destination j32, starting from the origin j2 (numerics are in [9]), in the different cases for all the alternative paths (see Table 7, where lengths in Kilometers and the sum of risks along paths, Sr, are also reported).Table 7
Tod for different paths and simulation cases.
PathCase A, E, FCase BCase CCase DP1 (Km 1.725), Sr = 2813.6413.6829.7629.44P2 (Km 1.675), Sr = 3013.1214.7632.7628.16P3 (Km 2.351), Sr = 3845.2033.9621.6422.04P4 (Km 2.331), Sr = 4036.5635.7624.4421.36First of all, notice that, as maximal risk levels are very high for Cases A, B, C, and D, the computation of the optimal path in such cases is influenced only by timesTod. In Case A, the optimal path is the shortest one, P2, unlike Case C, where the optimal route has the highest length. In fact for Case C, P2 is more congested than P1, P3, and P4.Cases A, E, and F have the same timesTod as they have the same initial conditions and boundary data but a different maximal risk level. However, while Cases A and F have the same optimal route P2, since it respects risk constraint, in Case E, due to the maximal risk level, lower than those of Cases A and F, P1 is the better path. Notice that the determination of K-Shortest Paths together with the computation of the total risk associated to each path allows to choose not the optimal path in terms of travel times but the one with a lower level risk, and a Tod not far from the lowest one.We make a further analysis on the density evolutions for some roads of the junctionj5. Notice that, from road 7, a driver can choose road 9 or 43. In Figures 3 and 4, we report the behaviour of densities on such roads for simulation Cases B and C.Comparison among density evolutions for road segments 9 (a) and 43 (b), Case C.
(a)(b)Comparison among density evolutions for road segments 9 (a) and 43 (b), Case B.
(a)(b)In Case C, road 43 belongs to the optimal pathP3 and its density grows slowly, as the one of road 9 does. Indeed, the density values on the two roads are very different; road 9 has a higher traffic due to the superpositions of more rarefaction traffic waves with respect to road 43 with 0.060828 and 0.413329 maximal densities on roads 43 and 9, respectively.Case B is more interesting. Road 9 belonging to the optimal pathP1 has a quick evolution of density with respect to the one of road 43. High-density fluctuations are the result of dynamics at junctions j4,j5, and j6: road 8 shock waves coming from roads 41 and traffic flow coming from road 40. In particular the maximal value of the density reached on road 9 is 0.346572, while on road 43 the density is less than or equal to 0.060384. This does not contradict the fact that the average travel time is minimized going on road 9, since the path P1 is less congested than the paths P3 and P4, determined by the choice of road 43 at junction j5.


## 6. Conclusions

In this paper, it is proposed an algorithm that, given an origino and a destination d on a road network graph, computes the K optimal paths to follow using a modified version of a CKSPa, whose weights are determined by a fluid-dynamic model for road networks.The procedure for finding the best paths has been tested via simulations on a real portion of the urban network in Caltanissetta, Italy. The optimal path connectingo and d has been evaluated using as weights the predicted travel times along roads, respecting the constraints on the maximal travelling time and the maximal risk coefficient accepted on the path. The goodness of the optimal path has been confirmed determining the trajectory of a car on it; it is proven that the time to cross the optimal route is lower than times needed to cover all the other possible paths connecting o and d. The dependence of the algorithm from the traffic conditions has been analyzed.



---

*Source: 564168-2012-03-29.xml*