# Exploring a Novel Electrical-Modeling-Based Route Planning for Vehicle Guidance

Authors: Rogelio Alejandro Callejas-Molina; Javier Diaz-Carmona; Hector Vazquez-Leal; Darwin Mayorga-Cruz; Raul Lopez-Leal
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This work describes a novel Electrical-Modeling-Based Route Planner (EMBRP) for vehicle guidance within city street networks (maps), which uses an equivalent linear electrical circuit considering traffic flow direction, length, and other physical attributes of the streets as parameters for the mathematical model of the circuit branch resistances. Thus, modeling a city as an electrical circuit results in a system of linear equations, which are solved using a multifrontal method implemented in the Unsymmetric Multifrontal Pack (UMFPACK) library. In addition, a Modified Local Current Comparison Algorithm (MLCCA) is proposed with the aim to find a suitable route meeting the correct traffic flow direction. The EMBRP has the functionality to accept user-defined symbolic models in terms of street parameters extracted from a public database allowing different route planning applications. For instance, low-risk route planning schemes can be explored also routes with multiple origins and a single destination can be plotted using only a single simulation, among other possibilities. The EMBRP is illustrated through the description of nine real case studies. According to the obtained results, suitable planning routes and small computing times are achieved by this proposal. A performance comparison, in terms of memory consumption and computing time, among EMBRP, the heuristic A∗ algorithm and Hspice numeric engine is presented. The smallest computing time was achieved by the EMBRP. The EMBRP can be useful for engineers and researchers studying route planning techniques and new street models for specific applications.


---

## Body

## 1. Introduction

In last decades many solutions for vehicular flow in city street networks have been addressed in reported works. One of such solutions is based on emulating the vehicular flow by an electric current flow within an electric circuit. A street model using an arrangement of potentiometers is proposed in [1], where the electric current value for each circuit branch is adjusted by a calibration process to simulate the distribution, and redistribution, of the traffic flow. In [2], the branch voltages and currents of the electric circuit are considered proportional to the driving time and to the traffic flow (number of vehicles per unit time), respectively. Hence, the equivalent branch resistance value is variable and computed as the ratio of the driving time and vehicular traffic flow. The case of multiple origin positions having a common destination is analyzed in [2], but only as an hypothetical example defined by a resistors network and not considering any cartographic or physical street characteristics. The traffic flow computing on road networks of different regions is performed with a proposed Markov probabilistic model in [3]. In [4], the traffic allocation is obtained considering that the road network has a single concentration node, such that all vehicles departing from any node have a common destination. A deterministic model to simulate stationary and transients traffic conditions of vehicle flow through an electric circuit is proposed in [5]. Whereas, in [6], an electrical circuit analysis is proposed for computing the highways network traffic. It is important to point out that these reported methods are focused on minimizing the travel time between the origin and destination positions with defined vehicle flow conditions and using a fixed proposed model, but neither geographical and cartography data nor physical characteristics of the city network streets are taken into account. This article presents an alternative methodology to the traditional route planning methods based on graphs (Dijkstra [7] and A∗ [8]) and optimization methods (genetic algorithm [9], artificial immune [10], and ant colony optimization [11]). The article is focused on planning a city route by establishing an analogy of the behavior between the vehicular flow presented in city street networks and the current flow in electrical circuits. Likewise, by means of electrical modeling, physical characteristics of the street are assigned to the resistive model to obtain routes for specific purposes. Factors such as distance, current traffic, street width, and available lanes are relevant when selecting a route [12]. Several algorithms have been developed to find the best route between origin and destination positions in a city street network. According to the required needs, a calculated route can be the shortest, the fastest in regard to traffic flow, and the cheapest or the most scenic [13–15]. The foundations of route planning involve the application of graph theory to determine the shortest route, or the minimum weight, that connects two specific vertexes in a road weighted network.A novel Electrical-Modeling-Based Route Planning (EMBRP) relaying on a nonprobabilistic method is proposed in this work. An equivalent electrical resistive circuit is obtained from city street database, where street physical characteristics are used for modeling the branch resistors value. The resulting planning route is comprised by the circuit branches having the highest local electrical currents. A vehicle guidance system using linear resistive grids is reported in [16]. However, there are some fundamental differences between such method and the one proposed in this paper. First, a Modified Local Current Comparison Algorithm (MLCCA) is proposed in order to notably reduce the branch searching time of the one- and two-way streets; meanwhile, only two-way streets are considered in [16]. Second, the EMBRP can solve planning routes from worldwide maps [17], whilst the method in [16] is applied to case studies with manually defined maps. The EMBRP has a dynamic street model definition, which allows users to define their own models for the electrical resistance considering physical street characteristics. An off-line route planner based on grids composed by diodes and resistors to model the traffic flow direction on one- and two-way streets is reported in [18]. Nevertheless, the simulation times are a bottleneck in the electric circuit solving due to the nonlinearity implied in the diode components, mainly for dense maps. In contrast, our proposal is based on a linear resistive grid with a noticeable reduction of computation time. Besides, third-party software (Maple CAS and Hspice circuit simulator) are required in [18], while EMBRP is an own implementation. Finally, the results in [18] are not displayed with a friendly user interface as EMBRP does.The motivation for developing the presented method was to achieve a deterministic tool featuring street modeling focused on researching proposes in city route planning. Most of the reported route planning methods are based on heuristics algorithms and the commercially available ones do not allow own user model definition. The implementation of the described route planning method allows user model definition and even symbolic modeling is possible. The desired deterministic feature was obtained through the use of the electrical circuit representation of the considered city street network.The main contributions of the proposed EMBRP are summarized as follows:(i)
The street modeling available in the EMBRP allows route planning for different applications such as those using symbolic street modeling, which is not covered by already reported works. The symbolic street modeling capability allows researchers to explore potential models for specific applications, where, for instance, route planning can be performed by prioritizing some of the considered street physical characteristics.(ii)
A modification to the Local Current Comparison Algorithm (LCCA) is proposed in the EMBRP so that routes containing one- and two-way streets are represented as linear resistances in the equivalent electrical circuit, in contrast to other reported techniques that use nonlinear components, which notably increases the computational workload in the route planning.Meanwhile, some reported planning methods are limited to specific case studies, the EMBRP implementation includes street information extraction from any city map available in a public database [17] for parsing an equivalent linear electric circuit, where the resistances values are computed from real street physical characteristics. Hence, the route planning in any worldwide city available in [17] is possible. The EMBRP implementation do not relay on any commercial software as some reported works do. For instance, the multifrontal method [19] is employed as a way to deal with the large sparse matrix resulted in the computing of the electrical circuit operation point.The paper organization is as follows. In Section2, the EMBRP is introduced. The main EMBRP stages are described in Section 3. In Section 4, an example describing the mathematical core of the proposed method is illustrated. The case studies are presented in Section 5. A detailed discussion and performance comparison, in terms of required memory and computing time, of the EMBRP with the heuristic A∗ algorithm and Hspice as numerical engine are provided in Section 6. Finally, the conclusions and Appendixes are presented.


## 2. Electrical-Modeling-Based Route Planning (EMBRP)

EMBRP is based on an equivalent linear electrical circuit for city street networks. The streets are represented as branch resistors, while the street intersections as circuit nodes. The desired origin of the route is given as an electric node biased by a direct current (DC) voltage source and the destination as the corresponding electric node connected to an electrical reference, known as ground. Hence, once the circuit is energized, an electrical current flows from the origin node to the grounded destination node throughout the circuit branches. In this work, each street segment between two intersections in the analyzed street network is modeled as an electric circuit branch composed by a linear resistor. If main traffic-flow-affecting variables are considered in the model of the branch resistance values, then the branch currents can be used as a route-searching parameter. The resistor model is used for representing one- and two-way streets, where the resistance valueR is given by street physical characteristics, for instance, the street intersection length. Once the electric circuit operating point is computed, the planning route is obtained by the proposed MLCCA. Whenever the EMBRP is applied under the same conditions, the obtained results will invariably be the same (without the application of any probabilistic scheme). Therefore, this method based on circuit theory is deterministic, which contrasts with other algorithms proposed in the literature [20, 21]. The main EMBRP stages are described in the following section.


## 3. EMBRP Main Blocks

The proposed tool is composed of five main blocks: (a) parsing the information extracted from [17], (b) electrical street modeling, (c) Modified Nodal Analysis (MNA) formulation, (d) operating point calculation, and (e) MLCCA searching.


### 3.1. Parsing Stage

The cartographic and geographic information of the selected street network is obtained and then mapped into an equivalent linear electrical circuit. Parsing stage output is a circuit netlist format modeling the street network. Basic mapping elements are (a) nodes as points defining geographical position; (b) roads as an ordered list of nodes representing a line; (c) relations as a group of nodes, paths, and other elements with common assigned properties, for instance, all those segments that are part of a way; and (d) tags comprising a key and a value pair that may be assigned to nodes, paths, or relations. Figure1 depicts how desired origin and destination positions are marked.Figure 1
Map snapshot.Network map information, street intersections, and traffic flow directions are extracted from [17]. It is important to note that Haklay and Weber [17] provide several extra nodes for each street block to keep the real curvature of the streets. Nevertheless, for visual simplification not all such nodes are displayed in Figure 2. A netlist is obtained from the parsing stage, which is an Hspice-format text file containing the analysis options and circuit description.Figure 2
Streets intersections and traffic flow direction obtained from [17].


### 3.2. Electrical Street Modeling Stage

A simplistic model to describe street characteristics is the block-length model:(1)R=L,where L is the total length between intersections.Nevertheless, the resistor model can be improved by including more street parameters. For instance, a possible user-defined model with three parameters can be defined as(2)R=LTcNc,where L is the street block length, Tc is the road surface type, and Nc is the number of street lanes.The block lengthL is calculated from the street latitudes and longitudes available in [17]. The key highway defines the value of the road surface type Tc, which depends on the street classification, its physical characteristics, and importance in the street network. The number of street lanes Nc can be obtained from [17], field defined as the key lane. The EMBRP allows the street resistance value be defined by a model such as (2) or a symbolically defined mathematical function.


### 3.3. MNA Formulation Stage

In this stage, the linear equation corresponding to the Modified Nodal Analysis (MNA) method [22] (obtained from Kirchhoff’s laws) is formulated from the modeling stage file as follows:(3)Ax=b,where A is the conductances matrix, x is the vector of unknown nodal voltages and currents, and the right-hand side (RHS) of the equation is the stimulus vector b.Equation (3) is generated by using MNA stamps [23], considering as main components the conductance G=1/R (see Figure 3 and Table 1) and the independent voltage source (see Figure 4 and Table 2) connected between node j and k. Stamps from Tables 1 and 2 are a systematic procedure to construct (3).Figure 3
Conductance connected between nodesj and k.Table 1
Conductance stamp.
v
j
v
k
RHS
Node j
G
j
k
−
G
j
k
0
Node k
−
G
j
k
G
j
k
0Figure 4
Voltage source between nodesj and k.Table 2
Voltage source stamp.
v
j
v
k
i
j
k
RHS
Nodej
0
0
1
0
Nodek
0
0
−1
0
Branchjk
1
−1
0
E
j
k


### 3.4. Operating Point Calculation Stage

In this stage the DC operating point of the biased electric circuit is obtained by solving the matrix system generated in the MNA formulation stage. Hence, the stage output is the values set of all circuit nodal voltages and branch currents. In fact, such operation point can be obtained from the resulted netlist by any circuit simulator such as Hspice [24] and Ngspice [25], among others. However, the solution is obtained by using the multifrontal method [26, 27], which is an efficient tool for solving sparse matrices equations that are commonly resulted in the case for electric circuits.The direct method multifrontal was developed by Duff and Reid [19], which is a generalization of the frontal method [28, 29]. In this method, the operations are organized when the sparse matrices are factorized into partial factors consisting of a sequence of dense and small submatrices. This is done with the help of a tree representing the partial factorizations dependencies [30]. The multifrontal method was originally developed to solve symmetric matrices; later, an unsymmetrical multifrontal algorithm was proposed for asymmetric disperse matrices, which is available in the UMFPACK library [31]. The set of linear equations defined in the MNA formulation stage is solved by the UMFPACK as solution engine.


### 3.5. MLCCA Route Searching Stage

Once the DC solution is available, the resulting route is obtained by selecting the branches with the largest node-to-node currents between the origin and the destination. The MLCCA is proposed for searching such largest-current branches, which is a modification of the local current comparison (LCC) algorithm [18]. The searching in the MLCCA is carried out by taking into account only branch currents matching the allowed vehicular flow direction defined in [17]. An illustrative example of the MLCCA is shown in Figure 5. Nodes n1 and n3 correspond to the origin and destination positions, respectively. In the first iteration, the maximum local current for node n1 is searched among the neighbouring branches, which have an allowed traffic flow direction. For this case, the directions of ij3 and ij2 match traffic flow direction, where ij3 has the largest value. As consequence, the ij3 branch is selected. In the second iteration, the largest local current is searched in the adjacent branches of n2. For this case, all the branches current direction of n2 match the corresponding of the traffic flow directions and the selected branch is ik2. Finally, the ground node (n3) is reached in the third iteration; therefore, the resulted planning route is composed of branches ij3 and ik2.Figure 5
MLCCA illustrative example.The MLCCA pseudocode is described as Algorithm1, where Origin_node and Destination_node are the origin and destination nodes, respectively. During each iteration, the algorithm verifies that the direction of the maximum current matches the traffic flow direction; otherwise, such branch is discarded and then same procedure is applied to the next available maximum-current branch. This procedure is repeated from node to node until Destination_node is reached.Algorithm 1: MLCCA procedure to obtain a route after the operating point calculation stage.
Data: User defines origin Origin_node and destination Destination_node nodes
(1)
Initialization;
(2)
A
N
I
K is a list of lists for adjacent nodes where I represent the node and K the adjacent nodes to I;
(3)
C
I
,
K is the local current from I node; to K node;
(4)
i
=
O
r
i
g
i
n
_
n
o
d
e;
(5)
c
o
n
t
=
0;
(6)
while i!=Destination_node do
(7)
k = node with the highest local current in the list of nodes ANi
(8)
IfLocal current Ci,k do respect the correct direction of traffic?then
(9)
i=k;
(10)
cont=cont+1
(11)
Routecont=k
(12)
else
(13)
Eliminatek node from ANi list  /∗ If adjacents nodes are all discarded a failure of the algotithm is declared ∗/
(14)
end
(15)
end
Result: ArrayRoute saves the planned route


### 3.6. General Description of the Main Stages

The general block diagram of the EMBRP tool is depicted in Figure6. Firstly, the selection of the area of interest and the street geographic information are read from the database [17]. Then, the netlist file of the linear circuit equivalent to the considered street network is obtained in the parsing stage (Section 3.1). The origin and destination nodes are chosen in this stage. Next, in the electrical street modeling stage, the street model for the branch resistor values is defined considering the street physical characteristics. A symbolic-defined model can also be given by the user (Section 3.2). The mapping of the resulted electrical circuit into the MNA matrix system is carried out in the MNA formulation stage (Section 3.3), which is solved in the operation point calculation stage through the multifrontal method (Section 3.4). Once the operating point of the electrical circuit is known, the resulting route is sequentially obtained using MLCCA (Section 3.5) and displayed using [32].Figure 6
Block diagram of EMBRP.


## 3.1. Parsing Stage

The cartographic and geographic information of the selected street network is obtained and then mapped into an equivalent linear electrical circuit. Parsing stage output is a circuit netlist format modeling the street network. Basic mapping elements are (a) nodes as points defining geographical position; (b) roads as an ordered list of nodes representing a line; (c) relations as a group of nodes, paths, and other elements with common assigned properties, for instance, all those segments that are part of a way; and (d) tags comprising a key and a value pair that may be assigned to nodes, paths, or relations. Figure1 depicts how desired origin and destination positions are marked.Figure 1
Map snapshot.Network map information, street intersections, and traffic flow directions are extracted from [17]. It is important to note that Haklay and Weber [17] provide several extra nodes for each street block to keep the real curvature of the streets. Nevertheless, for visual simplification not all such nodes are displayed in Figure 2. A netlist is obtained from the parsing stage, which is an Hspice-format text file containing the analysis options and circuit description.Figure 2
Streets intersections and traffic flow direction obtained from [17].


## 3.2. Electrical Street Modeling Stage

A simplistic model to describe street characteristics is the block-length model:(1)R=L,where L is the total length between intersections.Nevertheless, the resistor model can be improved by including more street parameters. For instance, a possible user-defined model with three parameters can be defined as(2)R=LTcNc,where L is the street block length, Tc is the road surface type, and Nc is the number of street lanes.The block lengthL is calculated from the street latitudes and longitudes available in [17]. The key highway defines the value of the road surface type Tc, which depends on the street classification, its physical characteristics, and importance in the street network. The number of street lanes Nc can be obtained from [17], field defined as the key lane. The EMBRP allows the street resistance value be defined by a model such as (2) or a symbolically defined mathematical function.


## 3.3. MNA Formulation Stage

In this stage, the linear equation corresponding to the Modified Nodal Analysis (MNA) method [22] (obtained from Kirchhoff’s laws) is formulated from the modeling stage file as follows:(3)Ax=b,where A is the conductances matrix, x is the vector of unknown nodal voltages and currents, and the right-hand side (RHS) of the equation is the stimulus vector b.Equation (3) is generated by using MNA stamps [23], considering as main components the conductance G=1/R (see Figure 3 and Table 1) and the independent voltage source (see Figure 4 and Table 2) connected between node j and k. Stamps from Tables 1 and 2 are a systematic procedure to construct (3).Figure 3
Conductance connected between nodesj and k.Table 1
Conductance stamp.
v
j
v
k
RHS
Node j
G
j
k
−
G
j
k
0
Node k
−
G
j
k
G
j
k
0Figure 4
Voltage source between nodesj and k.Table 2
Voltage source stamp.
v
j
v
k
i
j
k
RHS
Nodej
0
0
1
0
Nodek
0
0
−1
0
Branchjk
1
−1
0
E
j
k


## 3.4. Operating Point Calculation Stage

In this stage the DC operating point of the biased electric circuit is obtained by solving the matrix system generated in the MNA formulation stage. Hence, the stage output is the values set of all circuit nodal voltages and branch currents. In fact, such operation point can be obtained from the resulted netlist by any circuit simulator such as Hspice [24] and Ngspice [25], among others. However, the solution is obtained by using the multifrontal method [26, 27], which is an efficient tool for solving sparse matrices equations that are commonly resulted in the case for electric circuits.The direct method multifrontal was developed by Duff and Reid [19], which is a generalization of the frontal method [28, 29]. In this method, the operations are organized when the sparse matrices are factorized into partial factors consisting of a sequence of dense and small submatrices. This is done with the help of a tree representing the partial factorizations dependencies [30]. The multifrontal method was originally developed to solve symmetric matrices; later, an unsymmetrical multifrontal algorithm was proposed for asymmetric disperse matrices, which is available in the UMFPACK library [31]. The set of linear equations defined in the MNA formulation stage is solved by the UMFPACK as solution engine.


## 3.5. MLCCA Route Searching Stage

Once the DC solution is available, the resulting route is obtained by selecting the branches with the largest node-to-node currents between the origin and the destination. The MLCCA is proposed for searching such largest-current branches, which is a modification of the local current comparison (LCC) algorithm [18]. The searching in the MLCCA is carried out by taking into account only branch currents matching the allowed vehicular flow direction defined in [17]. An illustrative example of the MLCCA is shown in Figure 5. Nodes n1 and n3 correspond to the origin and destination positions, respectively. In the first iteration, the maximum local current for node n1 is searched among the neighbouring branches, which have an allowed traffic flow direction. For this case, the directions of ij3 and ij2 match traffic flow direction, where ij3 has the largest value. As consequence, the ij3 branch is selected. In the second iteration, the largest local current is searched in the adjacent branches of n2. For this case, all the branches current direction of n2 match the corresponding of the traffic flow directions and the selected branch is ik2. Finally, the ground node (n3) is reached in the third iteration; therefore, the resulted planning route is composed of branches ij3 and ik2.Figure 5
MLCCA illustrative example.The MLCCA pseudocode is described as Algorithm1, where Origin_node and Destination_node are the origin and destination nodes, respectively. During each iteration, the algorithm verifies that the direction of the maximum current matches the traffic flow direction; otherwise, such branch is discarded and then same procedure is applied to the next available maximum-current branch. This procedure is repeated from node to node until Destination_node is reached.Algorithm 1: MLCCA procedure to obtain a route after the operating point calculation stage.
Data: User defines origin Origin_node and destination Destination_node nodes
(1)
Initialization;
(2)
A
N
I
K is a list of lists for adjacent nodes where I represent the node and K the adjacent nodes to I;
(3)
C
I
,
K is the local current from I node; to K node;
(4)
i
=
O
r
i
g
i
n
_
n
o
d
e;
(5)
c
o
n
t
=
0;
(6)
while i!=Destination_node do
(7)
k = node with the highest local current in the list of nodes ANi
(8)
IfLocal current Ci,k do respect the correct direction of traffic?then
(9)
i=k;
(10)
cont=cont+1
(11)
Routecont=k
(12)
else
(13)
Eliminatek node from ANi list  /∗ If adjacents nodes are all discarded a failure of the algotithm is declared ∗/
(14)
end
(15)
end
Result: ArrayRoute saves the planned route


## 3.6. General Description of the Main Stages

The general block diagram of the EMBRP tool is depicted in Figure6. Firstly, the selection of the area of interest and the street geographic information are read from the database [17]. Then, the netlist file of the linear circuit equivalent to the considered street network is obtained in the parsing stage (Section 3.1). The origin and destination nodes are chosen in this stage. Next, in the electrical street modeling stage, the street model for the branch resistor values is defined considering the street physical characteristics. A symbolic-defined model can also be given by the user (Section 3.2). The mapping of the resulted electrical circuit into the MNA matrix system is carried out in the MNA formulation stage (Section 3.3), which is solved in the operation point calculation stage through the multifrontal method (Section 3.4). Once the operating point of the electrical circuit is known, the resulting route is sequentially obtained using MLCCA (Section 3.5) and displayed using [32].Figure 6
Block diagram of EMBRP.


## 4. Illustrative Example

In this section, each of the EMBRP stages are illustrated by one simplistic example. The desired origin and destination positions are highlighted in the map of Figure7. The maximum longitude and latitude of the selected area are shown in the lower left frame. The nodes are obtained in the parsing stage, which are depicted in Figure 8.Figure 7
Origin and destination positions for illustrative example.Figure 8
Parsed map nodes for illustrative example.The street curvature is represented by using several extra nodes, as shown in Figure8. In order to simplify the streets visualization and even more important to reduce the computational time, the redundant nodes are eliminated in the parsing stage. The resulting nodes for the illustrative example are shown in Figure 9. However, the street block length L is computed as the sum of the distances among the consecutive redundant nodes within the street block using the Haversine formula [33, 34]. The visualization of the intersection nodes and the direction of traffic flow are depicted in Figure 9. Next, the corresponding equivalent linear electric circuit obtained from the parsing stage is depicted in Figure 10. It is important to remark that we added an extra voltage source (VG) of zero volts to ground and a 10E6 Ohms extragrounded resistance (G20,G17,G16,G18, and G15) to each unconnected pin. As it is observed that the origin node is energized by a voltage source (VE) of 50 Volts and the destination node is grounded.Figure 9
Intersection nodes and traffic flow directions.Figure 10
Equivalent linear electrical circuit for an illustrative example.In this illustrative example, the resistor values are assigned using the block-length model defined in (1). The origin and destination nodes are V1 and V2, respectively. The MNA matrix system of the obtained electrical circuit is given by(4)A=G12,1300−G12−G13000000001000000G15,60000−G600010−G140000G1,14,2−G1,200000000−G90000−G1,2G1,10,2,3,9−G300−G100000000000−G3G3,4,5−G4−G5000000000000−G4G16,40000000000−G600−G50G5,6,7−G700000−G110000−G1000−G7G10,11,70000−G80000000000G17,8000G14,8,90000−G14−G90000−G80000G11,1800000000−G11000−G1200G12,1900000000000−G13000G13,200000000000100000000000000000001000000000,x=V1V2V3V4V5V6V7V8V9V10V11V12V13iVEiVG,b=0000000000000VEVG,where Gi,j,…,k=Gi+Gj+⋯+Gk. It is important to note that conductances (G=1/R) are used in order to simplify the notation.Now, the node voltages are obtained by solving (4) with the multifrontal method. The resulted node voltages and branch currents are shown in Table 3. The directions of both the circuit branch currents and traffic flow for the corresponding streets are depicted in Figure 11.Table 3
The resulted nodal voltages and branch currents for the illustrative example.
Nodal voltages (volts)
Branch
Current (A)
V
1
=
50
V
1
,
V
3
0.15092
V
2
=
0
V
1
,
V
13
4.99e − 6
V
3
=
45.8791
V
12
,
V
1
−4.90e − 6
V
4
=
36.3290
V
3
,
V
4
0.10780
V
5
=
28.3137
V
10
,
V
3
−0.04312
V
6
=
28.3134
V
9
,
V
10
−3.9368e − 6
V
13
=
49.9992
V
10
,
V
4
−0.04312
V
7
=
22.5878
V
4
,
V
5
0.07607
V
8
=
30.7788
V
4
,
V
8
0.074849
V
9
=
39.3688
V
8
,
V
11
3.086e − 6
V
10
=
39.3690
V
7
,
V
8
−0.07484
V
11
=
30.7778
V
7
,
V
2
0.15091
V
12
=
49.9992
V
5
,
V
7
0.07607
V
6
,
V
5
−2.8313e − 6
i
V
E
=
−
0.15093
AFigure 11
Branch currents and traffic flow directions.The resulting route obtained by applying the MLCCA is composed of the branchesV1−V3, V3−V4, V4−V5, V5−V7, and V7−V2, which is depicted in Figure 12. Finally, [32] is employed to produce a friendly visualization, as shown in Figure 13.Figure 12
Resulted planning route.Figure 13
Visualization using [32] (origin: red circle and destination: green circle).


## 5. Case Studies

The described method was applied to five case studies from different cities. The route was computed using a 64 bits Intel Core i5 2.4 GHz processor PC with 4 GB of RAM. Software platform is Python 2.7 running on the Microsoft Windows 7 operating system.


### 5.1. Block-Length Model

This case study is performed using an extracted map from Xalapa city at the state of Veracruz in Mexico. Route planning computing was carried out considering the block-length model (1). The resulting route using the proposed EMBRP is shown in Figure 14 through [32]. The obtained route has a total length of 2.271 km between origin (red icon) and destination (green icon) positions. As a comparison, the route was planned by the A∗ algorithm with a resulting distance of 2.311 km. Both resulting routes are depicted in Figure 14.Figure 14
Resulting planning route for the block-length model (blue route) and A∗ algorithm (green route) in the case study.


### 5.2. A Three-Parameter Model

In this case study, the city network, the origin, and the destination positions are the same as the ones selected for last case study, but the street model is considering the additional parametersNc and Tc (see (2)). The resulting route is depicted in Figure 15 (A-Route), which is compared with the obtained route using (1) (B-Route). As it is observed, the resulting route goes thorough a main street (Adolfo Ruiz Cortines), which is the one having more street lanes. This is because the greater Nc value, the smaller equivalent resistance value and the higher electric branch current. Here, the resulting route is not necessarily the shortest one, but the one with more traffic flow capacity. Meanwhile, the use of the block-length model (1) would result a shorter length route, but probably using secondary or tertiary streets. The total route distance for the three-parameter modeling case study (2) is 3.0617 km and the corresponding distance to the block-length modeling is 2.271 km, which results in a noticeable distance difference, but with a remarkable change in terms of flow traffic capacity.Figure 15
Resulting routes with the three-parameter model (A-route) and block-length model (B-route).


### 5.3. Exploring a Low-Risk Route Planning Scheme

Most of the commercial map navigation products (Google Street maps and AutoNavi Map, among others) provide a route planning service, considering only a single metric such as distance or traveling time, being these the most used. Nevertheless, a critical issue such as safety traveling along the resulting route is not generally taken into consideration [35]. As a matter of hypothetical application for the street modeling capability of the EMBRP, route planning for avoiding certain zones in a city is described. This may be useful to skip dangerous zones for drivers who are not aware of the risk for such zones, for instance, flooded areas and crime affected zones, among others. We will consider the map reported in [18] to propose a hypothetical risk zone defined as the set of streets depicted in red lines (see Figure 16). To consider the zone as a risk one, its streets are modeled as branch resistors with values given by(5)R=L+fr,where L is the street block length and fr is a risk factor.Figure 16
Comparison of risk-zone avoiding (A-route) and block-length modeling (B-route).The resulting route for both the low-risk route planning (A-route) and the block-length modeling (B-route) are shown in Figure16. It can be noticed that the risk zone is effectively avoided in A-route; meanwhile, the resulting B-route goes through the risk zone. It is necessary to note that fr was set to 10 M Ohms for this hypothetical study case, though, such value discourages but not forbids the planned route to cross the risk zone. This is a kind of soft rule; thus, if a user is required to be more or less strict, fr must be adjusted in concordance.


### 5.4. User-Defined Symbolic Models for Research Purposes

The EMBRP allows user-defined symbolic models as a function of the street physical characteristics. The use of two symbolic-defined models is described in this case study, where the origin and destination positions are marked as a red and green icon, respectively, in the street network at Los Angeles, California, USA, as shown in Figure17. The branch resistance value is defined by the following functions:(6)f1R=R1H,(7)f2R=1RH,where R is given by (2) and H is the road type. The considered values of H and Tc are shown in Table 4. Those values are empirical and were defined considering the street relevance and the number of street lanes and materials. Hence, further research is required to optimize such values.Figure 17
Resulting routes by the defined symbolic models: B-route (6) and A-route (7).Table 4
Proposed values forH and Tc street parameters.
H
Value
T
c
Value
Motorway
4
Dirt road
5
Trunk
4
Cobblestone
4
Primary
3
Unpaved
2.5
Secondary
2
Paving stones
2
Tertiary
1
Concrete
0.3
Residential
0.5
Paved
0.3
Asphalt
0.2The resulting planning routes for models (6) (B-route) and (7) (A-route) are displayed in Figure 17. As it is observed, a priority to secondary streets is given in route B, while main streets are prioritized in route A. The obtained route differences agree with expected results, since models (6) and (7) are opposite. On one side, model (6) can be useful when users need to avoid main streets, for instance, in cases of social disturbs or traffic congestions. On the other side, the use of model (7) is helpful to users requiring roads with main streets as a priority. Thus, user-defined symbolic models are an interesting instrument for the research of new models and route planning strategies.


### 5.5. Multiple Origins with a Single Destination

In this case study, an interesting advantage of the used resistive grid approach is presented, where new routes can be obtained by reusing the already obtained solution of the MNA matrix system. A possible scenario of such solution reuse is road planning for multiple origin positions having a common destination position within a single simulation. The considered case study is shown in Figure18, where the block-length model was used and the obtained routes [A,B,C, and D] have different origin positions and the same destination position. It is important to remark that the original simulation was performed for route D, and the routes A, B, and C are obtained by reusing the operating point of the original simulation. As expected, the use of the block-length model resulted in short-distance roads.Figure 18
Resulting roads for multiple origins with a common destination position.The main advantage of reusing the already computed electric circuit solution is that the planning of any route within the given street network is done just by the MLCCA, which searching time is noticeably lower than the solution computing time. The solution computing time for this study case was 0.0279 seconds and the MLCCA searching times for each planning route are shown in Table5.Table 5
MLCCA searching time for the case study.
Origin
MLCCA time (sec)
A
0.00155
B
0.00137
C
0.00165
D
0.00152


## 5.1. Block-Length Model

This case study is performed using an extracted map from Xalapa city at the state of Veracruz in Mexico. Route planning computing was carried out considering the block-length model (1). The resulting route using the proposed EMBRP is shown in Figure 14 through [32]. The obtained route has a total length of 2.271 km between origin (red icon) and destination (green icon) positions. As a comparison, the route was planned by the A∗ algorithm with a resulting distance of 2.311 km. Both resulting routes are depicted in Figure 14.Figure 14
Resulting planning route for the block-length model (blue route) and A∗ algorithm (green route) in the case study.


## 5.2. A Three-Parameter Model

In this case study, the city network, the origin, and the destination positions are the same as the ones selected for last case study, but the street model is considering the additional parametersNc and Tc (see (2)). The resulting route is depicted in Figure 15 (A-Route), which is compared with the obtained route using (1) (B-Route). As it is observed, the resulting route goes thorough a main street (Adolfo Ruiz Cortines), which is the one having more street lanes. This is because the greater Nc value, the smaller equivalent resistance value and the higher electric branch current. Here, the resulting route is not necessarily the shortest one, but the one with more traffic flow capacity. Meanwhile, the use of the block-length model (1) would result a shorter length route, but probably using secondary or tertiary streets. The total route distance for the three-parameter modeling case study (2) is 3.0617 km and the corresponding distance to the block-length modeling is 2.271 km, which results in a noticeable distance difference, but with a remarkable change in terms of flow traffic capacity.Figure 15
Resulting routes with the three-parameter model (A-route) and block-length model (B-route).


## 5.3. Exploring a Low-Risk Route Planning Scheme

Most of the commercial map navigation products (Google Street maps and AutoNavi Map, among others) provide a route planning service, considering only a single metric such as distance or traveling time, being these the most used. Nevertheless, a critical issue such as safety traveling along the resulting route is not generally taken into consideration [35]. As a matter of hypothetical application for the street modeling capability of the EMBRP, route planning for avoiding certain zones in a city is described. This may be useful to skip dangerous zones for drivers who are not aware of the risk for such zones, for instance, flooded areas and crime affected zones, among others. We will consider the map reported in [18] to propose a hypothetical risk zone defined as the set of streets depicted in red lines (see Figure 16). To consider the zone as a risk one, its streets are modeled as branch resistors with values given by(5)R=L+fr,where L is the street block length and fr is a risk factor.Figure 16
Comparison of risk-zone avoiding (A-route) and block-length modeling (B-route).The resulting route for both the low-risk route planning (A-route) and the block-length modeling (B-route) are shown in Figure16. It can be noticed that the risk zone is effectively avoided in A-route; meanwhile, the resulting B-route goes through the risk zone. It is necessary to note that fr was set to 10 M Ohms for this hypothetical study case, though, such value discourages but not forbids the planned route to cross the risk zone. This is a kind of soft rule; thus, if a user is required to be more or less strict, fr must be adjusted in concordance.


## 5.4. User-Defined Symbolic Models for Research Purposes

The EMBRP allows user-defined symbolic models as a function of the street physical characteristics. The use of two symbolic-defined models is described in this case study, where the origin and destination positions are marked as a red and green icon, respectively, in the street network at Los Angeles, California, USA, as shown in Figure17. The branch resistance value is defined by the following functions:(6)f1R=R1H,(7)f2R=1RH,where R is given by (2) and H is the road type. The considered values of H and Tc are shown in Table 4. Those values are empirical and were defined considering the street relevance and the number of street lanes and materials. Hence, further research is required to optimize such values.Figure 17
Resulting routes by the defined symbolic models: B-route (6) and A-route (7).Table 4
Proposed values forH and Tc street parameters.
H
Value
T
c
Value
Motorway
4
Dirt road
5
Trunk
4
Cobblestone
4
Primary
3
Unpaved
2.5
Secondary
2
Paving stones
2
Tertiary
1
Concrete
0.3
Residential
0.5
Paved
0.3
Asphalt
0.2The resulting planning routes for models (6) (B-route) and (7) (A-route) are displayed in Figure 17. As it is observed, a priority to secondary streets is given in route B, while main streets are prioritized in route A. The obtained route differences agree with expected results, since models (6) and (7) are opposite. On one side, model (6) can be useful when users need to avoid main streets, for instance, in cases of social disturbs or traffic congestions. On the other side, the use of model (7) is helpful to users requiring roads with main streets as a priority. Thus, user-defined symbolic models are an interesting instrument for the research of new models and route planning strategies.


## 5.5. Multiple Origins with a Single Destination

In this case study, an interesting advantage of the used resistive grid approach is presented, where new routes can be obtained by reusing the already obtained solution of the MNA matrix system. A possible scenario of such solution reuse is road planning for multiple origin positions having a common destination position within a single simulation. The considered case study is shown in Figure18, where the block-length model was used and the obtained routes [A,B,C, and D] have different origin positions and the same destination position. It is important to remark that the original simulation was performed for route D, and the routes A, B, and C are obtained by reusing the operating point of the original simulation. As expected, the use of the block-length model resulted in short-distance roads.Figure 18
Resulting roads for multiple origins with a common destination position.The main advantage of reusing the already computed electric circuit solution is that the planning of any route within the given street network is done just by the MLCCA, which searching time is noticeably lower than the solution computing time. The solution computing time for this study case was 0.0279 seconds and the MLCCA searching times for each planning route are shown in Table5.Table 5
MLCCA searching time for the case study.
Origin
MLCCA time (sec)
A
0.00155
B
0.00137
C
0.00165
D
0.00152


## 6. Discussion and Numerical Comparisons

The EMBRP is described as a route planning method for vehicle guidance within a city map that is based on an equivalent electric circuit representation of the city street network. Several case studies were performed to show the capabilities of the proposed method. The study cases presented in Sections5.2 and 5.3 are the route planning with a modeling of block-length (1) and three street physically parameters (2), respectively. The main difference between the resulting routes is that a higher priority to shortest paths is given in the block-length model, even if it means the use of secondary and tertiary streets. On the other side, the three-parameter model prioritizes main avenues with more street lanes discouraging the use of secondary and tertiary streets. The EMBRP has the capability of model definition by the user allowing the exploration of new route planning schemes for specific purposes not available in other route planning methods. For instance, low-risk road planning as depicted in the case study of Section 5.3. To achieve a low-risk route planning, a variable of risk fr was included in the resistance model (see (5)). A higher resistivity for the circuit branches associated to the risk zone is generated by this risk variable; therefore, the resulting planning route circumvents such risk zone; in fact, such zone is avoided because of the MLCCA. The study case described in Section 5.4 shows how user’s defined-models can be exploited to propose route planning schemes focused on avoiding main streets or the opposite giving priority to main streets. Users may require avoiding main streets because of social disturbs, traffic bottlenecks, or traffic jams. In addition, Section 5.5 presented a case study to show how circuit theory can be exploited in order to reuse the already-solved operation DC point within a strategy of multiple origin positions and a common destination position. The main advantage is that the route planning time for such strategy is given only by the MLCCA searching time that is noticeably lower than the operating point calculation; even more, a substantially reduction in energy consumption is expected because MLCCA performs only comparisons (see Algorithm 1), whilst the operating point calculation implies a lot of multiplications and divisions. The MLCCA searching time as a function of the number of circuit nodes is shown in Figure 19. A piece-wise linear increase of the MLCCA searching time with respect to the number of nodes is noticed. On the contrary, the solution computing time for the EMBRP as a function of the circuit nodes is compared with the HSPICE computing time in Figure 20. As can be observed the MLCCA searching time is much lower than the solution computing time. For instance, the MLCCA computing time for 4121 nodes, see Figure 19, is 0.003229 seconds in contrast to the 0.0220 seconds for EMBRP solution time, see Figure 20. This means that MLCCA is 6.5 faster than the solution computing time. One potential application of multiple origins with a common destination may be focused on disaster shelters, hospitals, or evacuation points’ route planning.Figure 19
MLCCA searching time.Figure 20
Solution computing time for EMBRP and HSPICE numeric engine.The total EMBRP computing time as a function of the number of circuit nodes is compared with the computing time of the heuristic A∗ algorithm in Figure21. As it can be noted, the EMBRP computing time is noticeably lower than the corresponding to the heuristic A∗ algorithm. This is because the key characteristic of the A∗ algorithm is to search all equally meritorious paths to find the optimal one that can be mitigated by relaxing the admissibility criterion. However, in the worst case, the A∗ algorithm computing time increases exponentially with respect to the number of nodes. In contrast, the worst case of the multifrontal method complexity is On3, where n is the number of equations. Also, a complexity of Opn2 is reported in [36], where p is a problem-related parameter by a tolerance for the matrix approximations. In addition, the mutifrontal method is remarkably faster than the Hspice circuit simulator for solving the MNA matrix system, see Figure 20.Figure 21
Route planning time for EMBRP and heuristic A∗ algorithm.Nevertheless, the required memory resources for the EMBRP is higher than the corresponding to the heuristic A∗ algorithm (see Figure22) and HSPICE circuit simulator (see Figure 23), mainly due to its multifrontal numerical engine. Therefore, further research work should be focused on decreasing memory resources and computing time of the multifrontal method, for instance, exploring parallel processing or other implementation technique [37–41]. Moreover, the use of new street symbolic models in terms of novel parameters can be researched as future work, parameters such as touristic requirements, evacuation routes, low-risk routes defined in real time, multiple destination positions, and user-defined preference, among others.Figure 22
Required memory resources for EMBRP and heuristic A∗ algorithm.Figure 23
Required memory resources for EMBPR circuit solving stage and Hspice.A numeric comparison of Figures20–23 are shown in Appendix A. The resulting routes using the models described in Sections 5.1–5.3 and 5.5 for four additional case studies are depicted in Appendix B. A performance comparison with the nonlinear resistive network approach reported in [18] is also presented. The resulting route distances using the EMBRP and A∗ algorithm for each one of the ten cases are compared in Table 6, where the total distance for EMBRP was computed using the Harvesine formula for street length.Table 6
Total resulting route distances using EMBRP and A∗ algorithm.
Nodes
EMBRP
A∗
725
926.93
950 m
1164
2.297
2.968 km
1255
2.545
2.261 km
1736
1.589
1.736 km
2026
2.226
2.311 km
2624
3.472
3.351 km
3049
3.852
2.808 km
3335
3.178
3.238 km
3403
2.310
1.996 km
4121
3.402
3.057 km


## 7. Conclusions

The described EMBRP is based on an analogy between a city street network and a linear electrical circuit. The resulting route is achieved by searching the branches having the local maximum branch currents within the electrical circuit, where the branch resistance values are defined from street physical characteristics obtained from [17].The proposed MLCCA algorithm is a good solution for route searching within the electrical circuit because it allows the representation of one- and two-way streets as linear branch resistances in the electrical circuit. Hence, the electrical circuit complexity is notably reduced compared with a nonlinear modeling approach reported in other works.According to the results obtained from the presented case studies, the EMBRP allows to explore novel symbolic street models for researching solutions in new and interesting route planning schemes. This feature will allow researchers to explore new ideas in street symbolic modeling.The described route searching in an already-solved electrical circuit allows to reduce the EMBRP total route searching time for special applications, such as multiple origin and a single destination scheme. An interesting future work would be the application for multiple origins and multiple destinies with a small route searching time.The route planning computing time of the proposed EMBRP was smaller than using the heuristic A∗ algorithm, but a higher memory resource was required by the EMBRP. As future work, research about memory resource reduction for EMBRP by optimizing the multifrontal method is recommended. Further research about new symbolic street models including real time variables is also left as future work.



---

*Source: 4348964-2020-05-05.xml*