Keywords

1 Introduction

One of the main challenges in the modeling and design of traffic management systems and services is the difficulty of controlling driver’s decision making regarding the choice of their routes, in order to match resources and demand in an optimal and automated way. Currently, Traffic Control System (TCS) coordinate demand through direct intervention in the network, online information systems, panels, regulatory policies or restrictions [21]. Drivers, for their part, are increasingly using advanced agent-based navigation systems that adapt and react in real time to the state of traffic [20]. Thus, the majority of vehicles receive very similar recommendations and stimuli, which make it difficult to optimize demand and transfer situations of congestion [16].

There are many proposals and commercial systems that generate individual route recommendations from data sent by users to a TCS [16]. However, these solutions raise multiple deployment questions due to computational resource demands, complexity, and privacy implications. The active participation of vehicles in the generation of data, and the use of Big Data as an element of mobility management, allow the design of alternative demand control models [13].

Smart-Cities require global perspectives that focus not only on traffic individuals (agents) and their contribution to traffic, but also on collective objectives considering citizens, individual multi-modal mobility, and conflicting group interests, leading to the concept of Urban Computing as described in [28]. This fact involve designing new multi-objective cost functions and the corresponding control models that optimize them.

Our goal is to reduce average travel time of all the vehicles in the traffic network, fulfilling individual, collective and regulatory goals and constraints, reducing congestion times in the network. It describes a novel route guidance model called TWM -Traffic Weighted Multi-maps-, that is shown to be scalable, technically and economically viable, easy to deploy, compatible with existing platforms, and has a low impact on privacy. TWM is structured around a new control paradigm, based on the generation and distribution of complementary cost maps. Every individual agent receives a customized view of the traffic network. Vehicles are grouped in classes (fleets) that share the same network view. The aggregation of individual decision making tends to satisfy the predefined control policy.

TWM proposal takes into account the individual traffic agent ability to take its own decisions (a) for using any of the known algorithms for K-shortest path (Dijkstra, A, A*, or any variant [7, 8, 15]) in case of individual route calculation, or (b) having received a TWM-based route calculation, follow it (that will diverge in many occasions from the standard ones). Compatibility with existing routing frameworks based on route-queries for origin/destination (O/D) is direct, as TWM is then applied at the TCS back-end. TWM model is also of application with hyperpaths calculations.

Research main contributions include: (1) a novel traffic route guidance model based on multimap distribution that enable differentiated route selection for individuals and collectives; (2) a microscopic simulation framework for TWM evaluation and algorithm comparisons, and (3) macroscopic and microscopic performance analysis based on the simulations performed for the most basic algorithm and network model. The research has promising future evolution applying new algorithms, policies and network profiles.

1.1 Literature Review

MuTraff deals with the development of an intelligent traffic control system, made up of the design of congestion management mechanisms, from which many parameters susceptible to optimization and control are derived, such as pollution level, noise footprint, prioritization of vehicle type, contingency plans, etc. [2], combined with a hybrid approach of individual vehicle agents that take into account the routing recommendations based on intention-aware policies [5, 25]. There are numerous proposals aimed at control and optimization of distributed and centralized type that are data driven [14, 24]. [1, 20] show a review of this type of multi-agent systems that address the problem using different approaches: automatic negotiation, distributed optimization, predictive routing, predictive control models, and others.

Among the centralized approaches, the proposals for signaling control stand out, proposing the application of predictive control models (MPC) combined with multi-agent models in the urban management of traffic lights at intersections or dynamic control in the incorporation of traffic flows [17, 18]. More specific proposals deal for example with the differential criteria applied to electric vehicles and charging stations [24, 26].

[4, 12] and others have proposed and evolved the hyperpaths formulation and evaluation where not a single route is received by the vehicle agents, but a tree of alternative routes for each origin and destination. Hyperpaths route calculus focuses on the uncertainty and variability of traffic dynamics, and is evaluated based on historical data and applying different analysis techniques [9, 19]. Our proposal is complementary to this approach as it focus on the network view that every individual receives and used at hyperpaths calculus. Hyper-path is conceived for individual risk-averse policies design (minimizing travel-time variance), in contrast with TWM that is multi-purpose and combines individual, group and global policies.

MuTraff is a centralized architecture that implements a distributed control for TWM in closed loop of routes of the vehicles [16], with capacities of re-planning. MuTraff feedback is not given explicitly at the microscopic level (of individual routes), and both performance and signaling are given at the mesoscopic level.

Standard navigation system offer shortest routes, derived from real-time density information and historical traffic. Agents (vehicles) make decisions individually, taking as a reference the same source of information, which transfers situations of congestion. This is the so-called “common resource distribution problem”, from which the so-called “Minority Game” or “Farol Bar Problem” derives [23]. It is therefore clear that there is a need for more precise control of vehicle routes, that requires precise individuals feedback and/or highly distributed sensor networks [22, 27]. This control could be exercised through individualised management at the microscopic level of each route. However, microscopic control entails problems of scalability, deployment and privacy, so MuTraff proposes an alternative, scalable, non-disruptive control and management methodology with fewer implications for users’ privacy. Agent routing decisions may change during the travel, mainly based on the dynamic information received [6] not affecting the aggregated information available at the TCS.

Similar strategies are used in other routing problems such as IP traffic routing strategies (MSTP, SDN) [11] by using distribution of maps with differentiated link weights (link-costs) and shortest-path routing strategies.

2 TWM - Traffic Weighted Multi-maps

Current vehicle traffic agents share the same traffic network maps (roads, paths) whose main path attributes are their physical conditions (number of lanes, length) and also their logical constraints (max speed, traffic allowance, directional senses and others). When we consider the path cost function we cannot modify physical attributes, but we can definitively modify logical ones. If we replace the max speed concept with a cost function that is different for each traffic group of agents, we could generate differentiated network maps for them. Even more, we could have time-dependent maps for them.

The main feature of our proposal, is to generate a traffic management framework (named MuTraff) that can provide differentiated traffic maps (called Traffic Weighted Maps, TWM) for the same area that can fulfill the specific needs of every traffic class. These maps are delivered to the vehicles, depending on multiple factors that are evaluated in a central-station back-end based on multiple criteria. These maps are to be composed in dynamic way combining several sources: historical data, real-time traffic data, real-time events affecting mobility (non-traffic data, but affecting the demand. For instance, a sport event, or a critical incident), and of course, synthetic data extracted from big-data sources. Figure 1 illustrates the basics for TWM generation.

Fig. 1.
figure 1

TWM generation model.

Full size image

Traffic classes recognize the fact that every type of traffic has specific (a) traffic goals, (b) network constraints, (c) regulations, (d) traffic indicators and (e) individual behaviors, so having a single traffic network map that considers only road descriptions, real-time conditions and traffic density is not enough to cover these specific features. Moreover, though some traffic classes have specific paths (such as bikes), most of the traffic classes share the same paths; management of these specific paths is accomplished by regulation and signaling. But, it can also be covered by specific maps. Multi-map routing strategy shows that this approach is a valid tool to get a better, easy and dynamic traffic management model. Instead of having a heavy set of regulation, signaling, time and geo-fenced constraints that every individual should process, evaluate, and execute, it is easier to have them collected into traffic map collections that are used by the individuals for route selection.

Route selection is the ultimate decision to be taken by traffic individuals and all the preceding issues mentioned can be seen as just factors that influence on it. Traffic individuals behave as agents that take routing decisions based on the available information, their own experience, habits, beliefs, desires and intentions. Available information is formed by the routes proposed by the routing engines, the map information, traffic and road status both real-time and historical data. Multi-maps skew this available information for every fleet, considering the best resource allocation (paths) to conform pseudo-optimal routers that are offered to every fleet. These multi-maps provide a different traffic routing weight for each fleet at each path. For instance, a city center will have different network maps for the fleets taxi, electric vehicles, logistic distributions, and conventional cars. The path weights will be different for each fleet, promoting or penalizing traffic for each path. Of course, these maps can be static or time-dynamic, depending on multiple strategies.

Traffic routes can be generated by the individuals using the network maps and the computing application [16], but also can be generated by a TCS that receives the origin-destination requests for route and delivers a set of possible routes. TWM approach is valid for them as it considers optimal route evaluation against a weighted map. This weighted map can be processed both at the individual and the central station. It is always the individual who decides which route/path to use, but usage of MuTraff will always use a weighted network map.

Individual privacy and data protection is also a main concern in routing systems [10]. No individual route tracking is made as MuTraff is just publishing weighted maps for vehicles groups at certain areas, and then routes and multi-path graphs recommendations contains no individual data. Privacy is preserved. Real-time data is obtained from city sensors and is used to calculated traffic density and congestion.

2.1 Model Formulation

A TWM multimap \(\varPi ^{n}\) is a collection of network maps \(\left[ \mu _{i}^{n}\right] \) referring to the same urban area \(\varTheta ^{n}\) and traffic vehicle groups \(\left[ \varOmega _{k}^{n}\right] \) (called fleets) as denoted in 1. Each urban area should have its own set of multimaps. This area could cover a whole city or just sectors.

$$\begin{aligned} \varPi ^{n}=\left\{ \left[ \mu _{i}^{n}\right] \right\} (\varTheta ^{n},\left[ \varOmega _{k}^{n}\right] ) \end{aligned}$$
(1)

Each map instance \(\mu _{i}^{n}\) that belongs to a multimap \(\varPi ^{n}\) is a version \(\varTheta _{i}^{n}\) of the traffic network \(\varTheta ^{n}\), affected by a time constraint set \(\varGamma _{i}^{n}\) and applicable for some traffic vehicle groups \(\left[ \varOmega _{k}^{n}\right] _{i}\) that are a subset of \(\left[ \varOmega _{k}^{n}\right] \).

Each urban area \(\varTheta ^{n}\) has a standard traffic network representation formed by a graph of geographical nodes \(\eta _{k}^{n}\) connected by edges, being each edge \(\epsilon _{k,j}^{n}\) the traffic link with \(l_{k,j}^{n}\) lanes that connects nodes \(\eta _{k}^{n}\) and \(\eta _{j}^{n}\) with a weight \(\beta _{k,j}^{n}\). MuTraff multimaps use multiple weight distribution functions \(\mathcal {F^{\text {n}}}\) for assigning geographical values to the \(\beta _{k,j}^{n}\) factor for each edge. With this formulation, standard traffic maps use the function \(\mathcal {F_{\text {std }}^{\text {n}}}\) that just consider lane-speed \(S_{k,j}\) for providing the edge weight \(\beta _{k,j}^{n}\).

$$\begin{aligned} \beta _{k,j}^{n}=F_{std}^{n}(\epsilon _{k,j}^{n})=\alpha *S_{k,j} \end{aligned}$$
(2)

In our initial experiments, we have tried statistical distributions such as normal-N 3 to create weight distributions in the maps that allow traffic dispersion in the network, enabling vehicles to use route alternatives recommendations for each fleet \(\left[ \varOmega _{k}^{n}\right] \). We scale weights with factor \(\delta \) (\(\delta _{normal.a.b}=normal(a,b)\)).

$$\begin{aligned} F_{normal.a.b}^{n}(\epsilon _{k,j}^{n})=\alpha *S_{k,j}*(1+\delta _{normal.a.b}) \end{aligned}$$
(3)

There will be a population of \(\left[ \upsilon _{i}^{k}\right] \) vehicles grouped by \(\left[ \varOmega _{k}^{n}\right] \) fleets. Those vehicles that do not belong explicitly to a fleet, will be assigned to the standard \(\varOmega _{0}^{n}\) fleet. The percent of vehicles that use MuTraff at any time is called the adherence factor \(\psi ^{n}\) and is calculated as the percent of vehicles not using \(\varOmega _{0}^{n}\).

Vehicles will generate \(\left[ \mathrm {T_{j}^{k}}\right] \) trips during observations times. Each trip in general is composed by the vehicle identification, the starting timestamp, the starting point (origin node) \(O_{j}\), the final destination point (node) \(D_{j}\) and tuple with possible intermediate stops \(\mathrm {P_{j}}.\)

For the map-distribution approach, depending on each concrete time epoch, each fleet has a specific map \(\mu _{i}^{n}\) that belongs to a multimap \(\varPi ^{n}.\)This map is distributed to its individuals (on-demand or by publication to subscriptions). Vehicles not classified or in general belonging to standard \(\varOmega _{0}^{n}\) fleet will use the standard map \(\varTheta ^{n}\). The vehicle’s agent calculate for each trip the shortest-path \(r(T_{j}^{k})\) route or hyper-path using the corresponding map (standard or ad-hoc received multimap) valid for this time-interval. This calculation will use some of the available routing algorithms (Dijkstra, A*, etc).

The agent confidence factor \(\varphi _{j}\) is a utility function that evolves in time based on previous experiences or available road and traffic information. Agent’s route recommendation usage will vary for every individual based on the confidence factor \(\varphi _{j}\) that should overpass certain subjective threshold \(K^{i}\).

3 Experiments and Results

Though Traffic Weighted Maps (TWM \(\varPi ^{n}\)) effects on traffic are suitable to be integrated with current macro, meso and microscopic traffic simulators [21], they all use \(\varTheta ^{n}\) maps as urban network representation. We have developed MuTraff simulator MTS over SUMO [3] that implements a car-following microscopic simulation environment.

3.1 Experiments Design

GRID16 network is composed of a matrix of horizontal and vertical roads of 16 horizontal \(\times \) 16 vertical paths, with uniform edges of 50 m and single or double lanes. The maximum speed is limited to 50 km/h (13,9 m/s). It uses 5 traffic assignment zones (TAZ [3]): TAZ 1 to 4 are located in the external sides of the grid, TAZ 5 covers the whole grid Fig. 2.

Fig. 2.
figure 2

GRID16 network and TAZ configuration for experiments.

Full size image

The traffic demand we will use in the experiments is composed by 4 different fleets: cars (44%), taxis (33%), buses (11%) and motorbikes (11%). Zones 1–4 generate directional crossing traffic from side to side, originating from one edge TAZ to an opposite edge TAZ (directional), zone 5 generates random internal traffic. As a reference value we will use the XS and M-size for standard traffic demand. TWM parameters used are: 8 maps per TWM, static weights with \(F_{std}^{n}(\epsilon _{k,j}^{n})\) and \(F_{normal.0.5,0.5}^{n}(\epsilon _{k,j}^{n})\) (random distribution centered on 0.5 and amplitude of 0.5, named as random05). Route selection algorithm = Dijkstra.

Current experiments consider global traffic network enhancement. They are checked for the whole network at the end of the simulation and also for each edge in the network at every time-step of the simulation: Routed traffic demand, as number of vehicles successfully routed against the total traffic demand (global and per fleet). Mean and median travel time, as a measure of global travel durations. Mean and median route distance, as a measure of global travel distances. Travel time dispersion, as an histogram of travel durations, to check how many vehicles have been affected during the experiments. Variance would provide us a single measure but a dispersion measure will give us a better insight into how this variance is occurring inside the population.

3.2 Non-TWM Routing in Congested GRID16 Network

This simulation provides the reference for network traffic performance using a full traffic scenario combining internal random and directional traffics without applying the multimap algorithm. Agents use shortest-path algorithm to select the route without predictive routing. Those agents traveling the same trip will use the same route. Figure 3 shows how traffic congestion starts at the edges as traffic is trying to enter the network and progressively the network gets congested. and due to the fact that traffic is fully internal, congestion gets stationary. Getting deeper inside the initial congestion scenario, we can appreciate how preferred edges selected for the trip routes are being blocked (number of halted vehicles).

Fig. 3.
figure 3

Grid16. Full traffic not using multimaps, evolution and details.

Full size image

3.3 TWM Routing Applied to Non-congested GRID16 Network

In order to analyze the effects of TWM on the congested network, we will use several drivers confidence factors to reflect TWM adoption (\(\psi ^{n}\) 5%, 10%, 20%, 50% and 100%). Simulation uses XS-size full traffic formed by 1300 vehicles (internal and directional trips). Multi-maps use random05 distribution (normal distributed random) with 8 TWM maps.

Figure 4 shows the histograms corresponding to the different \(\psi ^{n}\) mentioned. Each histogram compares no-TWM and 8 maps TWM application scenarios. We can see that even in a low adoption schema as \(\psi _{0.05}^{n}\), travel time starts to enhance. When \(\psi ^{n}\) increases over 50% enhancements in mean travel-time are really relevant (23% travel time) growing to 48% for a 100% adoption of TWM. Last histogram shows perfectly how congested trips (green graph) have been reduced or even disappeared (blue graph). Mean route lengths have not changed significantly.

Fig. 4.
figure 4

GRID16 routing XS traffic with \(\psi _{0.05}^{n}\), \(\psi _{0.2}^{n}\), \(\psi _{0.5}^{n}\), \(\psi _{1}^{n}\) (Color figure online)

Full size image

3.4 TWM Routing Applied to Congested GRID16 Network

Now we check the impact of TWM distribution on traffic performance using a congested full traffic scenario (M size, 2800 vehicles). In order to approach a more realistic scenario we use 2 lane paths for the whole network. We use the same random05 maps (uniformly distributed random) with 8 maps distribution. We study just adherence factor \(\psi _{0.5}^{n}=50\%\) and \(\psi _{1}^{n}=100\%\) values, as they show how much multi-maps can enhance congestion.

As we can see from Fig. 5 histogram, applying multimaps to the near-congested network with \(\psi _{0.5}^{n}\) enhances mean travel-time 19,65% and median over 13%. \(\psi _{1}^{n}\) raises up to 42% and 28% respectively. As shown, when \(\psi ^{n}\) increases, the whole network gets enhanced. Drivers that were having good traffic performance are not affected by the multi-maps, but congested drivers acquire better routers to get to their destination. Specific congestions are cleared and overall travel-time increases. And, moreover, no mean router length is affected. Global metrics for gas emissions and noise are dramatically reduced.

Fig. 5.
figure 5

Grid16-2lanes. Congested network with \(\psi _{0.5}^{n}\)and \(\psi _{1}^{n}\).

Full size image

4 Conclusions and Future Works

Studies in reduced scenarios and with a random map generation, oriented to traffic balancing, have obtained satisfactory results leading to traffic indicators enhancements between 20% and 50%. Experiments conducted with ideal canonical traffic network show that multimap approach improves highly global traffic travel-time, starting at low adoption scenarios, and providing best performance in high-adoption and highly congested situations.

The benefits of the multimap approach include the following: (1) the possibility of automating early and real-time decision making; (2) generation of an integral model for the application of management and control policies; (3) can be offered as a service (SaaS model); (4) it is conceived as a evolutionary planning model, based in traffic feed back and learning cycles; (5) is non-intrusive and compatible with existing traffic management frameworks and traffic agents; (6) reuses existing data (Smart-Cities, OpenData) adding value over them; (7) is compatible with other existing algorithms and techniques; (8) drivers’ agents autonomy and privacy is preserved as the multimap model takes into account individual freedom of route choice; (9) it allows for the articulation of contingency plans and the integration of traffic prognosis models.

MuTraff stands out from an innovative perspective in the following: (a) it offers an integrated planning and re-planning model, extensible and open; (b) it enables traffic categorization for application to very different groups and situations; (c) it is replenished and self-learning.

Future work will cover: (a) adding user-perspective for evaluation of TWM impact that will condition the adherence factor; (b) simulation on real cities scenarios; (c) generation of hyper-paths based on TWM; (d) design of a platform architecture for MuTraff real deployment and (e) adding new simulation engines: microscopic and mesoscopic for fast TWM generation responding to real-time incidents.