# Multiagent Routing Simulation with Partial Smart Vehicles Penetration

Authors: Bogumił Kamiński; Łukasz Kraiński; Atefeh Mashatan; Paweł Prałat; Przemysław Szufel
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

The invention and implementation of smart connected cars will change the way how the transportation networks in cities around the world operate. This technological shift will not happen instantaneously—for many years, both human-driven and smart connected vehicles will coexist. In this paper, using a multiagent simulation framework, we model a complex urban transportation system that involves heterogeneous participants. Vehicles are assigned into two groups: the first one consists of smart cars and the second one involves regular ones. Vehicles in the former group are capable of rerouting in response to changes in the observed traffic while regular ones rely on historical information only. The goal of the paper is to analyze the effect of changing smart cars penetration on system characteristics, in particular, the total travelling time. The smart car routing algorithm proposed in this paper reduced travelling time up to 30%. Analysis has shown that the behaviour of the system and optimal configuration of underlying algorithms change dynamically with smart vehicles penetration level.


---

## Body

## 1. Introduction

Due to an increasing number of traffic participants, especially in urban areas, the current transportation infrastructure becomes insufficient. Big cities suffer great economic losses and resident dissatisfaction from congestion and reliability issues [1]. As a result, Traffic Management Systems (TMS) effectively increasing road network efficiency are in high demand. With the advancing technology, the available solutions become more comprehensive and provide a faster, dynamic feedback. Although the vehicular technologies are in a period of an intense development, innovations require many years to become common in the automotive market. According to Lazard and Roland Berger, the penetration of highly automated vehicles in 2035 will reach between 5% and 26% accordingly in pessimistic and optimistic scenarios [2]. Since the transition from manual to automated vehicles will span many years, computer simulations provide valuable tool for testing the performance and the behaviour of novel systems in various conditions [3, 4]. With the increasing smart cars penetration, beneficial effects of the underlying management system are expected to increase as well. However, this important issue is rarely addressed by researchers who tend to assume a full system coverage [5, 6]. Smart vehicles penetration rate has already been applied to study particular transportation characteristics, e.g., traffic flow stability for mixture of connected and autonomous vehicles [7] or reaching travelling time optimum in artificial Pigou’s and Braess’ networks while using social network data [8]. Nevertheless, implementation of penetration rate in real-world urban setting simulation is still not covered in detail in the literature.The contribution of this paper is to examine impact of changing smart cars penetration on various transportation system characteristics, in particular the total travelling time. Experiments are conducted using a multiagent congestion detection and routing simulationSmartTransitionSim.jl developed for this research project. The code is available with Open-Source license on GitHub (https://github.com/KrainskiL/SmartTransitionSim.jl).The transportation process in traffic models is commonly programmed either on individual participant level, e.g., vehicles, pedestrians (microscopic), as groups of similar individuals (mesoscopic), or on system-wide level (macroscopic). Advanced frameworks combine concepts of multiple layers and model interactions between them [9, 10]. The agent-based modelling is well suited for microscopic simulations of traffic patterns since virtual agents naturally and intuitively represent traffic participants [11, 12]. Moreover, the multiagent models are becoming more popular also due to increasing availability of dedicated simulation software, e.g., SUMO, MATSim, SMARTS frameworks. However, accurate and detailed simulation of individual’s behaviour often requires high computing power and may render big scale simulations not feasible [13]. Researchers address performance problems by developing efficient algorithms using high-performance languages and incorporating modern computing techniques (e.g., distributed and cloud computing) in their implementations [14]. In the introduced framework, we adopted purely microscopic approach and focused heavily on performance optimization (more details can be found in Section 2.3).The concept of agent-based modelling connects well with the current TMS research trend based on two-way communication between an external infrastructure and vehicles (V2I) and between multiple vehicles (V2V). A theoretical design assumes implementation of the system within Vehicular Ad Hoc Network (VANET) consisted of three main components: in-vehicle On-Board Units (OBU) embedded with sensors, processing units and wireless interfaces, Road Side Units (RSU) creating communication infrastructure, and Traffic Management Center providing centralized processing power and storage [15]. Based on components used in a system design, solutions can be classified into infrastructure-free and infrastructure-based. The infrastructure-free systems are decentralized and rely on V2V communication to share information about traffic in close vicinity to vehicle. In contrast, centralized infrastructure-based systems focus on utilizing RSUs and an optional Traffic Management Center (TMC) to provide vehicles with wide area traffic data through V2I communication. De Souza also provides second breakdown level based on delivered service [16]:(1)
Infrastructure-free: (a) cooperative congestion detection, (b) congestion avoidance, and (c) accident detection and warning(2)
Infrastructure-based: (a) traffic light management, (b) route suggestion, (c) congestion detection, and (d) rerouting and speed adjustmentThe conceptual VANET design may be adopted in real-world applications using modern communication and computing technologies. Researchers and engineers are preparing technical background for vehicular networks by developing dedicated standards (e.g., IEEE 802.11, IEEE 1609.2) and testing various communication technologies like LTE or DSRC in a transportation environment [17]. The most recent research focuses on 5G compliant technologies which have become a competitive alternative due to the high capacity, ubiquitous coverage, and high reliability. The Next Generation Mobile Alliance propose strict requirements for the 5G-based technology, in particular 100% coverage, 99.99% network availability, and up to 1 ms round-trip delay, which are sufficient for wide range of VANET-based applications [18, 19]. In recent report, Crainic et al. pinpoint other key technologies (e.g., cloud computing, smart grids) required for successful development of intelligent transportation infrastructure and smart cities projects in general [20].Despite solid technical foundations, the majority of TMS projects are on proof-of-concept or experimental level [21, 22].However, initial tests have shown promising results. For example, both dynamic truck platooning system and vehicles routing Eco-Signal Operations provide fuel consumption decrease up to 10% [23, 24]. Additionally, already running in a dynamic fashion, traffic light management system called Midtown in Motion reduces overall travel time during rush hours by 10% [25].Psychological and social aspects of transportation are usually neglected in Traffic Management Systems design which focuses on simple and quantitative measures of performance. From the perspective of the society, TMS should take into consideration overall welfare and happiness. As highlighted at the beginning of this section, spending too much time travelling in congested and uncomfortable conditions reduces well-being of the participating commuters [26]. Importance of personal transportation drives researchers to study determinants of traffic participant decisions and travel satisfaction. Often quantitative notion of the value (the cost) of time is used in research [22, 27]. Standard factors breakdown assumes that the travel time unit cost varies according to type of trips, traveler preferences, and travel conditions [28]. The majority of reports classify trips as work/business or nonwork/personal, but depending on the methodology used more detailed structures may be used [29]. For inferring quantitative conclusions about traveler preferences, often questionnaire-based approach is used [30, 31]. Research has shown that the cost of time rises significantly if the total travelling time surpasses 90 minutes per day [32]. That conclusion aligns with Marchetti’s Constant rule, which states that people aim to travel one hour each day and switch attention to other transportation characteristics (e.g., trip conditions) when travelling less than that [33–35]. Unfavorable traffic conditions, especially unexpectedly congested roads, further increase the cost of the travelling time. For highly congested traffic, the value of time may grow up to 50% for automobile users and 100% for bus passengers, pedestrians, and cyclists [36]. Analyses of transportation reliability impact by government agencies show that the uncertainty of trip length and occurrence of unexpected delays result in an additional time cost increase [37, 38].Taking the above described factors into account, in this paper we test how the increasing adoption ofsmart cars, which can adaptively update their routing decisions using information obtained from a TMS, influences the expected congestion and ultimately total travelling time of commuters. In Section 2 we discuss the design of the agent-based simulation we have developed. Next, in Section 3, we present the details of the experiment we have conducted using this simulation and in Section 4 we discuss the obtained results. Finally, Section 5 concludes and presents outlooks for further research.


## 2. Simulation Details

In this section we describe our approach to modelling of the traffic system and what our assumptions are about agent behaviour rules and communication capabilities. Finally, we describe the design of the simulation framework we have developed that implements these assumptions.


### 2.1. Traffic System

We assume that the road network is represented by a directed graphG=V,E that consists of the set of n vertices V=v1,v2,…,vn representing junctions and the set of k edges E=e1,e2,…,ek representing roads. Every edge (directed arc) ei∈E is defined by two vertices ei=vs,ve,vs,ve∈V,vs≠ve corresponding to junctions between given road segments. Additionally, every edge ei is described with the following parameters:(1)
ℓi—road length(2)
Vmaxi—maximum velocity allowed on the i-th road(3)
ρmaxi—maximum vehicles density on the i-th road, that is, the maximum number of vehicles allowed on the i-th road segment, calculated as follows:(1)ρmaxi=ℓisic,wheresi is the number of lanes available on the road segment and c denotes the average space reserved for one vehicle (in meters)The road network is populated with agents representing vehicles moving between selected vertices with respect to edge’s direction. In any given timet, agents are assigned to one edge and move towards ending vertex with current edge velocity value calculated as follows:(2)Vti=Vmaxi−Vmin⋅max1−ρtiρmaxi,0+Vmin,where ρti is the current density on the i-th edge at time t and Vmin is the fixed, minimum speed. The minimum speed is introduced to prevent edge lock-down if maximum density is reached. Let us note that, due to step-wise character of the simulation, density may temporarily exceed maximal density which would result in negative speed value. To address the problem, speed multiplier in equation (2) is bounded from below by zero. The equation we use is a slightly modified version of the classical Lighthill-Whitham-Richards traffic flow model [39, 40]. Vehicles density is common congestion predictor present also in modern traffic flow research [41].The proposed framework is based on discrete-events simulation (DES); thus system state and simulation clock are updated when particular events occur rather than in arbitrary chosen time interval. Discrete-event based approach was reported in earlier research to produce more accurate results compared to standard discrete-time simulations due to character of numerical calculations [42].


### 2.2. Agent Behaviour and Communication Design

An agent represents an individual vehicle travelling in the road networkG from a starting vertex vS to a destination vertex vD. Agents aim to select the optimal route that minimizes the travelling time between the two assigned nodes. The route from nodes vS to vD is defined as a sequence of n consecutively adjacent nodes (or, alternatively, n−1 edges):(3)R=vS≡v1,v2,…,vn−1,vn≡vD,∀i∈1,2,…,n−1vi,vi+1∈E.The time required to traverse thei-th edge in simulation time s is equal to the ratio of the length of the edge and the current speed; that is, tsi=ℓi/Vsi. Hence, the total time, defined as in equation (3), required to travel the route is given by the following formula:(4)tR=∑i=1n−1ℓiVsi.With known travel time on each edge, fastest route is determined using A-star graph traversal algorithm, commonly used in routing simulations [43]. However, velocities in the system change dynamically with agents movement, see equation (2), deprecating initially chosen paths. Depending on how routes overlap, the capacity of a particular road may be utilized more heavily than others, thus creating traffic congestion and slowing down all vehicles present on the edge. This effect is more apparent when multiple agents start from nearby vertices and travel to similar destinations, which resembles rush hours scenario when people commute from office or industry districts to residential areas. Bottlenecks may also naturally appear on big arteries selected by many agents due to high speed limit and convenient location.Each agent is generated with a fixed type:smart or regular. The type determines the individual’s behaviour, available traffic information, and route optimization mechanisms. All agents possess full knowledge of static road network characteristics—segments lengths ℓi and maximum speeds vmaxi. We assume that regular agents calculate travelling time with the average speeds obtained from the “previous day” information about the traffic (short-term memory). Specifically, the average from the “previous day” is calculated based on speeds recorded every 30 seconds in scenario where all agents used speed limits to pick fastest routes with given starting and ending vertices. For smart cars, we assume that vehicles additionally receive full information about the current velocities on roads with fixed time interval and may reroute based on local, on-board calculations, immediately after receiving data.In our framework, we may take that all routing decisions (for both regular and smart cars) are based only on on-board computer calculations; therefore all agents can be considered as autonomous vehicles, differing only with the amount of available information. However, we could equivalently assume that regular cars are human-driven, where a driver makes a routing decision based on historical traffic data. The crucial distinction between regular and smart cars lies in the amount of information they have at the moment of making routing decisions.The utilization of historical data supports more even traffic distribution and, as a result, shorter travelling time in the system. However, the deterministic routing approach may lead to undesired outcomes [44]. For example, agents heading towards a similar direction tend to choose overlapping routes, switching congestion to new area instead of alleviating it. In order to reduce this undesired effect, probabilistic approaches such as the random k-shortest path or the entropy balanced k-shortest path may be implemented [45]. More advanced and computationally intensive algorithms such as metaheuristics can also be applied to the routing problem [46]. In our system, we assume that regular agents apply the k-shortest path algorithm with probabilities assigned using the Boltzmann distribution; see equation (6). Regular vehicles follow initially selected routes until they reach their destinations as they obtain no additional information during the simulation. We designed regular agents to provide a simple representation of currently used vehicular navigation systems.LetR1,R2,…,Rk be a series of k-shortest routes from the next node on agent’s current route to the destination node. Routes are calculated using Yen’s algorithm [47] with an assigned travel time ti based on equation (4). Time values are ordered such that t1≤t2≤⋯≤tk−1≤tk and normalized in order to remove influence of absolute length differences on probability calculations. Normalized time values tiN express fractions of the longest time tk; that is, values are positive and tk=1:(5)tiN=timaxt1,t2,…,tk=titk.The probabilitypi for selecting the i-th route is calculated as in equation (6). The corresponding probability is higher for routes with a shorter travelling time, but the behaviour of the distribution may be controlled by parameter T. If T is close to 0, the probability assigned to the fastest route approaches one, while large values of T yield distributions that are close to uniform. Example of parameter T influence on the routes probabilities is provided in Table 1. Please note that the probabilities are also affected by dynamically changing travelling time on a given set of routes (see equation (4)):Table 1
Probability of picking route in k-shortest path algorithm depending on route’s travelling time and givenT parameter.
Route number
1
2
3
4
5
Travelling time
110
90
70
55
50
Normalized time
1.00
0.82
0.64
0.50
0.45
T = 0.1
0.01
0.10
0.09
0.35
0.55
T = 1
0.14
0.17
0.21
0.24
0.25
T = 10
0.19
0.20
0.20
0.20
0.20(6)
p
i
=
e
−
t
i
N
/
T
∑
j
=
1
k
e
−
t
j
N
/
T
−
1
.The smart agents inherit all route optimization mechanisms from agents of regular type but additionally utilize “smart” rerouting service. We assume that smart vehicles receive full information about the current velocities with fixed time interval and may reroute based on local, on-board calculations, immediately after receiving data; thus frequency of rerouting is controlled with update period value and no other trigger for rerouting is considered. Moreover, the smart individuals predict position where they expect to receive next update and change the route only on short fragment between the next junction and the following junction after predicted location. Such mechanism ensures that rerouting will have a meaningful impact on the time reduction—the smart agents scale decision boundaries based on a point of receiving updated speed values. Routes in thek-shortest path algorithm between two given vertices are calculated on demand but, due to high computational complexity of the algorithm, received set of routes is stored for possible reuse by other agents (see Section 2.3). With accurate weights (velocities), smart agents may divert from congested roads and effectively choose a faster path to their destination instead of relying on a biased estimation used by regular agents. The effectiveness of rerouting is expected to rise with decreasing update interval as agents reroute more frequently.In order to reduce overlap of paths, thek-shortest path algorithm is applied every time rerouting is triggered but routes with time twice as big as shortest route are removed from the set. While rerouting on short distances, time differences between calculated routes are much higher than with distant endpoints. In that case, the k-shortest path algorithm may lead to increased travelling time compared to regular agents. Additionally, in case of one-segment rerouting, path is forcefully extended to two-segment path to introduce viable alternatives for the k-shortest path algorithm.Additional information provided for smart agents comes from a 5G VANET-based Traffic Management System focused on congestion detection and a rerouting service. The proposed solution’s infrastructure (see Figure1) consists of the following components:(1)
In-vehicle On-Board Units (OBUs) capable of calculating new route to destination point and sending vehicle’s velocity to external units(2)
Road Side Units (RSUs) acting as brokers providing partial velocity data to Traffic Management Center (TMC) and aggregated to OBUs(3)
Centralized TMC aggregating and sending back data obtained from RSUsFigure 1
Communication schema in proposed TMS.All infrastructure components are considered to be 5G-grade; thus 100% area coverage, no data loss, and insignificant data delay below 10 ms are assumed. We assumed cellular-based infrastructure due to expected ubiquitousness of the service in large cities. Cellular infrastructure is universal and managed by external telecommunication companies, therefore highly available in urban areas. In that setup, RSUs are equivalent to 5G antennas which provide cellular services for smartphones and other devices. Networks based on other technologies (DSRC, etc.) may require dedicated structures and thus would impact feasibility of the simulation design. However, assuming some alternative communication technology with coverage similar to 5G would not change the outcome of the simulation.


### 2.3. Simulation Framework

We have implemented the simulation framework calledSmartTransitionSim.jl and make the code available with Open Source license on GitHub (https://github.com/KrainskiL/SmartTransitionSim.jl). The simulation software is implemented in the Julia programming language. OpenStreetMapX.jl (https://github.com/pszufe/OpenStreetMapX.jl) package is used for parsing OpenStreetMap map files into directed graph with possibility of caching them for faster execution. The package also provides utility functions to operate on loaded graph, e.g., coordinates conversion and edge characteristic extraction. The Julia language provides a simple but comprehensive syntax, so SmartTransitionSim.jl may be easily modified for personal use. Documentation for the current version is also available in the GitHub repository.The framework was optimized in terms of performance using. Major performance tweaks include the following:(i)
Yen’s algorithm is based on custom, fast A-star implementation—5 times performance improvement over a standard implementation(ii)
Routes calculated by thek-shortest paths algorithm are saved for future reuse (memoization technique)—leading to up to 15 times faster simulation execution in comparison to no-memoization(iii)
Simulations use common, separately generated agents pools—halved overall running timeWe have designed the simulation tool in such a way that the simulations can be executed in a distributed fashion. Additionally, the simulation model has been adjusted to work with KissCluster software (KissCluster is available at https://github.com/pszufe/KissCluster.) that can be used to manage the distributed simulation execution and the data collection process in the Amazon Web Service cloud.Table 2
Simulation input parameters.
Group
Parameter
Description
Agents
N
Number of agents in simulation run
α
Smart agents penetration
VANET
U
Velocities update interval (seconds)
Rerouting
T
Boltzmann distribution regularization parameter
k
Routes calculated ink-shortest path algorithmThe agents are generated with both starting and ending nodes chosen randomly from a given rectangle area, designated by a set of geographic coordinates within provided map bounds. All agents are generated at once and no further vehicles are added during the lifespan of a simulation. With that assumption, the simulation emulates morning or evening rush hours when congestion is usually dense and effective traffic management can provide highest time reduction benefits. User controls “wave” direction with appropriate starting and ending areas. Other input parameters for simulation run are listed in Table2.The population of agents consists ofN individuals with an α fraction of smart agents (smart agents penetration). Smart vehicles receive speeds update every U seconds and reroute by picking one of k fastest routes based on the Boltzmann distribution with a T parameter.The simulation can work in two modes: base and smart (see Figure2). In the base mode, only regular agents occur and VANET functionalities are disabled. The scenario serves as the baseline for comparison with smart scenario where both regular and smart agents occur (Figure 2(b), Algorithm 1). Effectiveness of implemented TMS is measured as the percentage of the total time reduction (difference in the sum of the travelling times of all agents) between the smart and the base scenario with fixed input parameters.Figure 2
Base (a) and smart (b) simulation flow.
(a)
(b)Algorithm 1:Simulation pseudocode.
Data: Transportation network graph, starting/ending area coordinates, parameters (Table 2)
Result: Array of vehicles travel time
(1)
generatevehicles population with source and destination location;
(2)
calculate initial routes (speed limits) and run “previous day” simulation;
(3)
calculate initial routes (average speeds from line 2);
(4)
simulation_clock :
= 0;
(5)
repeat
(6)
event_time, event := findmin(NextEdge(),NextUpdate());
(7)
simulation_clock := simulation_clock + event_time;
(8)
if event = next_edgethen
(9)
UpdateAgentsAndVelocities();
(10)
if node = destination then
(11)
RemoveVehicle();
(12)
end
(13)
end
(14)
if event = next_updatethen
(15)
foreach vehicle ∈ vehicles do
(16)
ifvehicleissmartthen
(17)
KShortestPathRerouting();
(18)
end
(19)
end
(20)
end
(21)
Until active(Vehicle) = 0;


## 2.1. Traffic System

We assume that the road network is represented by a directed graphG=V,E that consists of the set of n vertices V=v1,v2,…,vn representing junctions and the set of k edges E=e1,e2,…,ek representing roads. Every edge (directed arc) ei∈E is defined by two vertices ei=vs,ve,vs,ve∈V,vs≠ve corresponding to junctions between given road segments. Additionally, every edge ei is described with the following parameters:(1)
ℓi—road length(2)
Vmaxi—maximum velocity allowed on the i-th road(3)
ρmaxi—maximum vehicles density on the i-th road, that is, the maximum number of vehicles allowed on the i-th road segment, calculated as follows:(1)ρmaxi=ℓisic,wheresi is the number of lanes available on the road segment and c denotes the average space reserved for one vehicle (in meters)The road network is populated with agents representing vehicles moving between selected vertices with respect to edge’s direction. In any given timet, agents are assigned to one edge and move towards ending vertex with current edge velocity value calculated as follows:(2)Vti=Vmaxi−Vmin⋅max1−ρtiρmaxi,0+Vmin,where ρti is the current density on the i-th edge at time t and Vmin is the fixed, minimum speed. The minimum speed is introduced to prevent edge lock-down if maximum density is reached. Let us note that, due to step-wise character of the simulation, density may temporarily exceed maximal density which would result in negative speed value. To address the problem, speed multiplier in equation (2) is bounded from below by zero. The equation we use is a slightly modified version of the classical Lighthill-Whitham-Richards traffic flow model [39, 40]. Vehicles density is common congestion predictor present also in modern traffic flow research [41].The proposed framework is based on discrete-events simulation (DES); thus system state and simulation clock are updated when particular events occur rather than in arbitrary chosen time interval. Discrete-event based approach was reported in earlier research to produce more accurate results compared to standard discrete-time simulations due to character of numerical calculations [42].


## 2.2. Agent Behaviour and Communication Design

An agent represents an individual vehicle travelling in the road networkG from a starting vertex vS to a destination vertex vD. Agents aim to select the optimal route that minimizes the travelling time between the two assigned nodes. The route from nodes vS to vD is defined as a sequence of n consecutively adjacent nodes (or, alternatively, n−1 edges):(3)R=vS≡v1,v2,…,vn−1,vn≡vD,∀i∈1,2,…,n−1vi,vi+1∈E.The time required to traverse thei-th edge in simulation time s is equal to the ratio of the length of the edge and the current speed; that is, tsi=ℓi/Vsi. Hence, the total time, defined as in equation (3), required to travel the route is given by the following formula:(4)tR=∑i=1n−1ℓiVsi.With known travel time on each edge, fastest route is determined using A-star graph traversal algorithm, commonly used in routing simulations [43]. However, velocities in the system change dynamically with agents movement, see equation (2), deprecating initially chosen paths. Depending on how routes overlap, the capacity of a particular road may be utilized more heavily than others, thus creating traffic congestion and slowing down all vehicles present on the edge. This effect is more apparent when multiple agents start from nearby vertices and travel to similar destinations, which resembles rush hours scenario when people commute from office or industry districts to residential areas. Bottlenecks may also naturally appear on big arteries selected by many agents due to high speed limit and convenient location.Each agent is generated with a fixed type:smart or regular. The type determines the individual’s behaviour, available traffic information, and route optimization mechanisms. All agents possess full knowledge of static road network characteristics—segments lengths ℓi and maximum speeds vmaxi. We assume that regular agents calculate travelling time with the average speeds obtained from the “previous day” information about the traffic (short-term memory). Specifically, the average from the “previous day” is calculated based on speeds recorded every 30 seconds in scenario where all agents used speed limits to pick fastest routes with given starting and ending vertices. For smart cars, we assume that vehicles additionally receive full information about the current velocities on roads with fixed time interval and may reroute based on local, on-board calculations, immediately after receiving data.In our framework, we may take that all routing decisions (for both regular and smart cars) are based only on on-board computer calculations; therefore all agents can be considered as autonomous vehicles, differing only with the amount of available information. However, we could equivalently assume that regular cars are human-driven, where a driver makes a routing decision based on historical traffic data. The crucial distinction between regular and smart cars lies in the amount of information they have at the moment of making routing decisions.The utilization of historical data supports more even traffic distribution and, as a result, shorter travelling time in the system. However, the deterministic routing approach may lead to undesired outcomes [44]. For example, agents heading towards a similar direction tend to choose overlapping routes, switching congestion to new area instead of alleviating it. In order to reduce this undesired effect, probabilistic approaches such as the random k-shortest path or the entropy balanced k-shortest path may be implemented [45]. More advanced and computationally intensive algorithms such as metaheuristics can also be applied to the routing problem [46]. In our system, we assume that regular agents apply the k-shortest path algorithm with probabilities assigned using the Boltzmann distribution; see equation (6). Regular vehicles follow initially selected routes until they reach their destinations as they obtain no additional information during the simulation. We designed regular agents to provide a simple representation of currently used vehicular navigation systems.LetR1,R2,…,Rk be a series of k-shortest routes from the next node on agent’s current route to the destination node. Routes are calculated using Yen’s algorithm [47] with an assigned travel time ti based on equation (4). Time values are ordered such that t1≤t2≤⋯≤tk−1≤tk and normalized in order to remove influence of absolute length differences on probability calculations. Normalized time values tiN express fractions of the longest time tk; that is, values are positive and tk=1:(5)tiN=timaxt1,t2,…,tk=titk.The probabilitypi for selecting the i-th route is calculated as in equation (6). The corresponding probability is higher for routes with a shorter travelling time, but the behaviour of the distribution may be controlled by parameter T. If T is close to 0, the probability assigned to the fastest route approaches one, while large values of T yield distributions that are close to uniform. Example of parameter T influence on the routes probabilities is provided in Table 1. Please note that the probabilities are also affected by dynamically changing travelling time on a given set of routes (see equation (4)):Table 1
Probability of picking route in k-shortest path algorithm depending on route’s travelling time and givenT parameter.
Route number
1
2
3
4
5
Travelling time
110
90
70
55
50
Normalized time
1.00
0.82
0.64
0.50
0.45
T = 0.1
0.01
0.10
0.09
0.35
0.55
T = 1
0.14
0.17
0.21
0.24
0.25
T = 10
0.19
0.20
0.20
0.20
0.20(6)
p
i
=
e
−
t
i
N
/
T
∑
j
=
1
k
e
−
t
j
N
/
T
−
1
.The smart agents inherit all route optimization mechanisms from agents of regular type but additionally utilize “smart” rerouting service. We assume that smart vehicles receive full information about the current velocities with fixed time interval and may reroute based on local, on-board calculations, immediately after receiving data; thus frequency of rerouting is controlled with update period value and no other trigger for rerouting is considered. Moreover, the smart individuals predict position where they expect to receive next update and change the route only on short fragment between the next junction and the following junction after predicted location. Such mechanism ensures that rerouting will have a meaningful impact on the time reduction—the smart agents scale decision boundaries based on a point of receiving updated speed values. Routes in thek-shortest path algorithm between two given vertices are calculated on demand but, due to high computational complexity of the algorithm, received set of routes is stored for possible reuse by other agents (see Section 2.3). With accurate weights (velocities), smart agents may divert from congested roads and effectively choose a faster path to their destination instead of relying on a biased estimation used by regular agents. The effectiveness of rerouting is expected to rise with decreasing update interval as agents reroute more frequently.In order to reduce overlap of paths, thek-shortest path algorithm is applied every time rerouting is triggered but routes with time twice as big as shortest route are removed from the set. While rerouting on short distances, time differences between calculated routes are much higher than with distant endpoints. In that case, the k-shortest path algorithm may lead to increased travelling time compared to regular agents. Additionally, in case of one-segment rerouting, path is forcefully extended to two-segment path to introduce viable alternatives for the k-shortest path algorithm.Additional information provided for smart agents comes from a 5G VANET-based Traffic Management System focused on congestion detection and a rerouting service. The proposed solution’s infrastructure (see Figure1) consists of the following components:(1)
In-vehicle On-Board Units (OBUs) capable of calculating new route to destination point and sending vehicle’s velocity to external units(2)
Road Side Units (RSUs) acting as brokers providing partial velocity data to Traffic Management Center (TMC) and aggregated to OBUs(3)
Centralized TMC aggregating and sending back data obtained from RSUsFigure 1
Communication schema in proposed TMS.All infrastructure components are considered to be 5G-grade; thus 100% area coverage, no data loss, and insignificant data delay below 10 ms are assumed. We assumed cellular-based infrastructure due to expected ubiquitousness of the service in large cities. Cellular infrastructure is universal and managed by external telecommunication companies, therefore highly available in urban areas. In that setup, RSUs are equivalent to 5G antennas which provide cellular services for smartphones and other devices. Networks based on other technologies (DSRC, etc.) may require dedicated structures and thus would impact feasibility of the simulation design. However, assuming some alternative communication technology with coverage similar to 5G would not change the outcome of the simulation.


## 2.3. Simulation Framework

We have implemented the simulation framework calledSmartTransitionSim.jl and make the code available with Open Source license on GitHub (https://github.com/KrainskiL/SmartTransitionSim.jl). The simulation software is implemented in the Julia programming language. OpenStreetMapX.jl (https://github.com/pszufe/OpenStreetMapX.jl) package is used for parsing OpenStreetMap map files into directed graph with possibility of caching them for faster execution. The package also provides utility functions to operate on loaded graph, e.g., coordinates conversion and edge characteristic extraction. The Julia language provides a simple but comprehensive syntax, so SmartTransitionSim.jl may be easily modified for personal use. Documentation for the current version is also available in the GitHub repository.The framework was optimized in terms of performance using. Major performance tweaks include the following:(i)
Yen’s algorithm is based on custom, fast A-star implementation—5 times performance improvement over a standard implementation(ii)
Routes calculated by thek-shortest paths algorithm are saved for future reuse (memoization technique)—leading to up to 15 times faster simulation execution in comparison to no-memoization(iii)
Simulations use common, separately generated agents pools—halved overall running timeWe have designed the simulation tool in such a way that the simulations can be executed in a distributed fashion. Additionally, the simulation model has been adjusted to work with KissCluster software (KissCluster is available at https://github.com/pszufe/KissCluster.) that can be used to manage the distributed simulation execution and the data collection process in the Amazon Web Service cloud.Table 2
Simulation input parameters.
Group
Parameter
Description
Agents
N
Number of agents in simulation run
α
Smart agents penetration
VANET
U
Velocities update interval (seconds)
Rerouting
T
Boltzmann distribution regularization parameter
k
Routes calculated ink-shortest path algorithmThe agents are generated with both starting and ending nodes chosen randomly from a given rectangle area, designated by a set of geographic coordinates within provided map bounds. All agents are generated at once and no further vehicles are added during the lifespan of a simulation. With that assumption, the simulation emulates morning or evening rush hours when congestion is usually dense and effective traffic management can provide highest time reduction benefits. User controls “wave” direction with appropriate starting and ending areas. Other input parameters for simulation run are listed in Table2.The population of agents consists ofN individuals with an α fraction of smart agents (smart agents penetration). Smart vehicles receive speeds update every U seconds and reroute by picking one of k fastest routes based on the Boltzmann distribution with a T parameter.The simulation can work in two modes: base and smart (see Figure2). In the base mode, only regular agents occur and VANET functionalities are disabled. The scenario serves as the baseline for comparison with smart scenario where both regular and smart agents occur (Figure 2(b), Algorithm 1). Effectiveness of implemented TMS is measured as the percentage of the total time reduction (difference in the sum of the travelling times of all agents) between the smart and the base scenario with fixed input parameters.Figure 2
Base (a) and smart (b) simulation flow.
(a)
(b)Algorithm 1:Simulation pseudocode.
Data: Transportation network graph, starting/ending area coordinates, parameters (Table 2)
Result: Array of vehicles travel time
(1)
generatevehicles population with source and destination location;
(2)
calculate initial routes (speed limits) and run “previous day” simulation;
(3)
calculate initial routes (average speeds from line 2);
(4)
simulation_clock :
= 0;
(5)
repeat
(6)
event_time, event := findmin(NextEdge(),NextUpdate());
(7)
simulation_clock := simulation_clock + event_time;
(8)
if event = next_edgethen
(9)
UpdateAgentsAndVelocities();
(10)
if node = destination then
(11)
RemoveVehicle();
(12)
end
(13)
end
(14)
if event = next_updatethen
(15)
foreach vehicle ∈ vehicles do
(16)
ifvehicleissmartthen
(17)
KShortestPathRerouting();
(18)
end
(19)
end
(20)
end
(21)
Until active(Vehicle) = 0;


## 3. Experiment Setup

The evaluation of the proposed model was conducted on a map of San Francisco in California, USA. We assumed scenario of evening commuting from financial (blue area) to residential district (red area) (Figure3). The parameter grid was created as the Cartesian product of the parameters values described in Table 3. On every computing node, common pool of 10,000 agents was generated and sampled by consecutive simulation processes. Due to the probabilistic nature of the model, simulations were repeated 3 times for each parameter combination—in total, 54,000 simulation runs were conducted (the final simulation run took a total of 1,500 AWS EC2 vCPU computational hours. An additional 10,000 vCPU-hours have been used to calibrate and validate the model). Repetitions value was deemed sufficient, considering moderate average coefficient of variation for time reduction (14%). The simulation experiments have been run on a cluster of Amazon Web Services EC2 instances. For the sake of reproducibility, both map data and the script used in the experiment are available on GitHub repository (https://github.com/KrainskiL/SmartTransitionSim.jl/tree/master/example). We also provide a file with map statistics such as summary of the number of lanes, speed limits, and lengths distribution across edges.Figure 3
Agents starting and ending area in San Francisco.Table 3
Simulation parameter sweep setup.
Parameter
α
N
U
k
T
Min
0.05
3000
50
1
0.1
Max
0.85
7500
300
5
10.0
Step
0.05
500
50
1
×
10With described experiment setup, we aim to provide answers for the following questions:(1)
How does the total travelling time within the city change with increasing smart cars penetration and the number of agents? Congestion avoidance mechanisms provide a significant advantage for smart vehicles but, since rerouting decisions are made locally, individuals in smart populations may diminish gains of other smart agents.(2)
Does the route overlap issue occur? That is, is thek-shortest algorithm necessary? If yes, is the algorithm effective in distributing the traffic? Which value of T provides a near-optimal trade-off between an ability to avoid traffic congestion and rerouting to longer paths?(3)
How does the time reduction change with decreasing update period? With more frequent rerouting, vehicles may react more effectively to changes of traffic conditions, although competition mechanism between smart agents may intensify as well.


## 4. Experiment Results

The obtained results prove a significant impact of routes overlap and the smart agents competition problem in scenarios with high smart cars penetration. All time reduction values show the difference between overall travelling time in scenario with a givenα and the base scenario without smart agents α=0. In smart populations with the deterministic rerouting k=1, unmitigated overlap issue tremendously affects TMS efficiency. Travelling time reduction effect is near 0% and exhibits high variance (Figure 4(c)). With a mixed agent structure, system quality is affected by the overlap but routing is effective even with the deterministic approach (Figure 4(b)). In scenarios dominated by regular agents, the competition mechanism has no significant impact on travelling time but results are in general less stable compared to scenarios with higher smart agents ratio (Figure 4(a)).Figure 4
Percentage travelling time reduction for Boltzmann distribution regularization,T, and the number of routes calculated in k-shortest path algorithm, k values with fixed smart agents penetration α. Averaged over all values of N and U parameters with error terms based on average coefficient of variation. (a) α = 0.05, (b) α = 0.5, and (c) α = 0.85.
(a)
(b)
(c)Based on the gathered data, thek-shortest paths algorithm alleviates detrimental effects of overlapping routes. It is worth noting that with smaller smart agents penetration only two routes are required to reach a peak performance while, with high α, similar results were obtained with pool of two, three, or four paths. The behaviour of the algorithm may be also controlled with regularization parameter T. Time reduction for T=1.0 and T=10.0 is similar, while for T=0.1 results are clearly inferior. Since the small value of T favors fast routes, the k-paths algorithm distributes traffic less efficiently.In line with expectations, time reduction effectiveness increases with the number of agents. With 3,000 vehicles, the total travelling time was reduced up to 15% while with 7,500 agents maximum value reached 30%. Independently of the population size, the highest system performance was recorded for the penetration of smart cars around 85% (Figure5). It is worth mentioning that the largest time reduction effect is reached for simulations with k=2 (Figure 5(a)) and performance is declining with increasing k (that is, heatmaps become more yellow). The observation confirms that additional routes in the k-shortest path algorithm do not contribute much to alleviating congestion but create possibility of choosing significantly slower path.Figure 5
The average percentage of time reduction based on the population sizeN and the smart agents penetration α for a fixed number of evaluated routes k. Averaged over all values of T and U parameters. (a) k = 2, (b) k = 3, (c) k = 4, and (d) k = 5.
(a)
(b)
(c)
(d)The results also confirmed that the updating interval plays a key role in increasing the performance of the Traffic Management System. The difference, measured in the percentage of time reduction, between 50 and 300 seconds update period reached up to 10% percent and was higher for smaller population of agents (Figure6(a)). For all population size and smart cars penetration, the biggest leap in system performance occurred between 250- and 200-second update interval. By contrast, for smaller interval values, the difference becomes insignificant (Figures 6(b)–6(d))—update period reaches optimal state near 5 s value. However, since the routing mechanism is closely linked with traversed edges length and map characteristic, the optimal value may change based on set scenario. For 7,500 agents, peak percentage travelling time difference reached 32% for both 50 s and 100 s update intervals, indicating that the optimal update period value is between 50 and 100 seconds. This factor should be taken into account when designing the communication protocol and polling mechanism for communicating vehicles.Figure 6
The average percentage time reduction based on smart agents penetrationα and different levels of information update interval for various population sizes N. (a) N = 3,000, (b) N = 4,500, (c) N = 6,000, and (d) N = 7,500. (Note that the plots do not include data for k=1 and T=0.1).
(a)
(b)
(c)
(d)In order to finish the analysis, let us mention that the simulation framework was validated against multiple scenarios and design settings. Numerous routing rules and agent characteristics (in particular, initial route generation process) were tested and refined. Investigation took into consideration also criteria for starting agents movement, multiple rerouting triggers, and additional VANET infrastructure mechanisms. Throughout the development process, the framework was tested in different map settings (e.g., Warsaw and Winnipeg urban areas) to verify that the simulation design provides consistent, interpretable, and meaningful conclusions. Validation scenarios included analysis of the parameters as in Table3 and various starting and ending areas per each map. We estimate that 50,000 simulation runs were conducted to refine and validate the design. Numerical results obtained from the experiments mentioned above are qualitatively consistent with the presented outcomes; thus in the paper we focused on detailed exposition of San Francisco setup.


## 5. Conclusions

As smart cars adoption will likely take many years, it is important to validate underlying intelligent systems under different penetration rates. In order to fill the gap in the related work, we have developed novel microscopic simulation framework for assessing Traffic Management Systems under varying smart vehicles penetration level. We proposed centralized TMS based on thek-shortest path algorithm and conducted experiments using the framework. The experiments have shown that the proposed service can significantly reduce the travelling time in urban environment. By controlling the simulation parameters, the system performance may be fine-tuned. Moreover, the analysis revealed that an increasing smart cars penetration activates mechanisms connected with the underlying algorithms and the system characteristics may differ depending on the fraction of smart units. In particular, the optimality of the proposed parametrization of path selection probabilities (introduced to avoid a situation where too many agents take the same overlapping routes) depends on the level of smart car penetration. In practice, it means that the smart vehicle movement algorithm should be tuned when the transportation ecosystem changes. Hence, considering that the transition to fully automated vehicles will span a number of years, assessing intermediate effects should be an important stage of designing modern transportation systems. Additionally, simulation results clearly show that, with the increasing volume of traffic, the role of smart vehicles in reducing the congestion is increasing. Moreover, the marginal value of better communication system in reducing the congestion is also increasing with the bigger smart car penetration—again, this value is greater with cities of smart congestion.Future model extensions may include a more sophisticated rerouting algorithm with individuals’ decision based on the regional (vehicle clusters) or global communication between agents and VANET infrastructure. A more advanced design is required to tackle the problem of uneven traffic distribution and the competition between smart agents. Next possible framework modifications include an implementation of the value of time characteristics as a performance measure instead of a simple time reduction. We assume that the value of time of all agents is equal but, from an economic or social point of view, introducing an additional heterogeneity may be beneficial, e.g., higher time cost for public service or delivery vehicles. Another consideration is the generality of the conclusions. Presented outcomes qualitatively held for particular scenario of San Francisco and other experiments in various setups, as described in Section4. Of course, as in any simulation study, the generality and stability of the conclusions is a topic that may be studied deeper in specific contexts of user interest. For this reason, we provide all source codes of the framework we have used as an open-source project to allow interested parties to implement or modify our proposed model in their own research.



---

*Source: 3152020-2020-03-03.xml*