# Self-Organised Routing for Road Networks

Holger Prothmann, Sven Tomforde, Johannes Lyda, Jürgen Branke, Jörg Hähner, Christian Müller-Schloer, Hartmut Schmeck

► To cite this version:

Holger Prothmann, Sven Tomforde, Johannes Lyda, Jürgen Branke, Jörg Hähner, et al. Self-Organised Routing for Road Networks. 6th International Workshop on Self-Organizing Systems (IW-SOS), Mar 2012, Delft, Netherlands. pp.48-59, 10.1007/978-3-642-28583-7_5. hal-01527528

HAL Id: hal-01527528

https://inria.hal.science/hal-01527528

Submitted on 24 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Self-organised Routing for Road Networks

Holger Prothmann¹, Sven Tomforde², Johannes Lyda², Jürgen Branke³, Jörg
Hähner², Christian Müller-Schloer², and Hartmut Schmeck¹

¹ Karlsruhe Institute of Technology (KIT), Institute AIFB, 76128 Karlsruhe,
Germany, [holger.prothmann|hartmut.schmeck]@kit.edu

² Leibniz Universität Hannover, Institute of Systems Engineering, Appelstr. 4,
30167 Hannover, Germany, [tomforde|lyda|haehner|cms]@sra.uni-hannover.de

³ University of Warwick, Warwick Business School, Coventry, CV4 7AL, UK,
juergen.branke@wbs.ac.uk

**Abstract.** Increasing mobility and the resulting rising traffic demands cause serious problems in urban regions world-wide. Approaches to alleviate the negative effects of traffic include an improved control of traffic lights and the introduction of dynamic route guidance systems that take current conditions into account. One solution for the former aspect is Organic Traffic Control (OTC) which provides a self-organised and self-adaptive system founded on the principles of Organic Computing. Based on OTC, this paper introduces a novel concept to dynamic route guidance in urban road networks. Inspired by the well-known protocols Distance Vector Routing and Link State Routing from the Internet domain, the major goal of the route guidance mechanism is to increase the network's robustness with respect to congested or blocked roads. The efficiency of the developed approach is demonstrated in a simulation-based evaluation that considers disturbed and undisturbed traffic conditions.

**Keywords:** dynamic route guidance, traffic signal control, observer/controller architecture;

# 1 Introduction

Today's urban traffic is characterised by serious congestion problems due to an
increasing demand for mobility. In consequence, the environmental impact of
motorised traffic is becoming a major concern in public debates and scientific
research [9]. Strategies to satisfy the rising demands are manifold and include
a more efficient usage of the existing infrastructure. Promising starting points
are a traffic-responsive control of traffic lights, their self-organised coordination,
and mechanisms for *dynamic route guidance* (DRG).

Considering the dynamic nature of traffic, the distributed location of inter-sections in urban road networks, and the autonomous behaviour of drivers, the traffic domain possesses several characteristics that make it an interesting test case for Organic Computing techniques [8]. Earlier work applied the generic observer/controller architecture proposed for Organic Computing to achieve adaptive traffic signal control [7]. The resulting *Organic Traffic Control* (OTC) system
is capable of optimising an intersection’s signalisation according to the observed traffic flows. The system has been equipped with self-organising coordination mechanisms that allow to establish progressive signal systems (or “green waves”) in the network. The resulting signal coordination has been shown to significantly reduce the network-wide number of stops and, in consequence, the fuel consumption and pollution emissions of motorised vehicles.

The existing OTC system tackles traffic in a passive manner by searching for the best signalisation in response to the network's traffic flows. In order to improve the robustness of traffic networks with respect to incidents (like blockages due to accidents or road works), this paper broadens OTC's scope by introducing a self-organising DRG mechanism that actively guides vehicles through the network. The DRG mechanism extends the existing infrastructure with ideas inspired by well-known routing protocols from the data communication domain. Considering the current traffic demand, the routing protocols are modified to determine the best paths through the road network. The recommended routes are then provided to drivers at each intersection of the network. The major goal of the DRG mechanism is to minimise travel times by preventing congestions. Furthermore, a better distribution of traffic streams helps to use the capacity of the road network efficiently.

The remainder of the paper is structured as follows: Section 2 reviews the state of the art in congestion management by discussing various possibilities to dynamically guide drivers through a traffic network. Section 3 revisits the OTC framework that serves as a basis for the proposed self-organising DRG mechanism. The mechanism and its underlying routing protocols are in the focus of Sect. 4. Section 5 discusses the results of a simulation study that evaluates the potential benefits of DRG. Finally, Sect. 6 concludes the paper by giving a summary and an outlook.

## 2 State of the art

In today's road networks, GPS-based navigation systems installed in many vehicles guide drivers to their destinations. The systems rely on an internal map of the network which is used by a variant of Dijkstra's algorithm to compute a shortest or fastest route. The route calculation can be based purely on data stored in the map or it can incorporate up-to-date information that is transmitted via the radio's *Traffic Message Channel* (TMC) or a mobile Internet connection. TMC provides digitally coded traffic and travel information via public radio, but covers highways and major roads, only. Data provided via an Internet connection includes urban areas, but its topicality and quality depend largely on the manufacturer-specific penetration rate of a system since the provided data is based on travel times experienced by other drivers.

Other approaches to vehicle routing address the topicality problem with the help of *floating car data*. In [12], Wedde et al. modified their Internet routing protocol *BeeHive* to be suitable for road traffic. In the resulting *BeeJamA* protocol, vehicles are routed from intersection to intersection on a next-hop-basis.
The routing is performed by regionally responsible navigation servers that store routing tables for their area and routes to other areas. The routing tables are updated based on information provided by vehicles that are assumed to continuously transmit their position, speed, and destination to the responsible navigation server. Like *BeeJamA*, the DRG mechanism proposed here relies on routing protocols originally developed for the Internet. However, the difference is in the acquisition of data on the current network state. While *BeeJamA* is based on car-to-infrastructure communication, the DRG mechanism proposed here relies on flow and signalisation data that is available at the network's signalised intersections such that no specially equipped vehicles are required.

The integration of route guidance mechanisms into urban traffic control systems has also been investigated in the European COSMOS project [1]. COSMOS developed incident management and rerouting strategies for various adaptive network control systems including MOTION. Rerouting in the MOTION system has been implemented with the help of a macroscopic traffic flow simulator that simulates routing alternatives on-line and recommends optimal routes through the network. Like the mechanism proposed in this paper, routing is based on traffic data available in the control system. However, routing in MOTION relies on centralised simulation and optimisation, while the DRG mechanism proposed here works completely decentralised.

## 3 Organic Traffic Control

The proposed self-organising DRG mechanism extends the existing OTC system for traffic light control [7]. The OTC system locally optimises an intersection's signalisation at run-time, while neighbouring intersections self-organise to form progressive signal systems in response to the network's traffic flows.

The local optimisation of signal plans at an intersection is based on the observer/controller architecture that has been proposed for Organic Computing [2]. An observer/controller extends a fixed-time or traffic-actuated signal controller – the *System under Observation and Control* (SuOC) – and optimises its signal timings at run-time. The observer monitors the traffic flows of the intersection's turnings and estimates the current vehicular delay for the signalised intersection. The delay is estimated from current flows and signal timings with the help of Webster's approximation formula [11]. Webster's formula is applied for each turning, before the obtained turning delays are combined in a flow-weighted sum to obtain the average vehicular delay for the intersection. Traffic flows and delays are provided to the controller, where they serve as input for a two-levelled learning mechanism. The controller's first level learns to select signal plans on-line in response to the current traffic demand, while the second level performs a model-based off-line optimisation of signal plans. Optimised plans are incorporated in the selection process on the first level.

As several intersections can be located in close vicinity within an urban road network, their coordination is another important aspect. By coordinating the signalisation of neighbouring intersections, progressive signal systems can be
established to avoid unnecessary stops. With the help of local communication
links, neighbouring intersections exchange data on the measured traffic flows and
on their current signalisation. Thereby, traffic streams that largely benefit from
coordination can be identified. Within the identified streams, the local signal
plans are adapted to obtain a progressive signal system.

The combination of adaptive intersections with a self-organising coordination
mechanism provides important technical preconditions for a DRG framework.
Turning delays that are derived by an intersection's observer/controller can be
reused to estimate travel times of alternative routes under the current traffic
demand and signalisation. With the help of the communication infrastructure,
turning costs can be distributed in the network. Therefore, the only components
missing for a DRG system are a routing protocol that derives and distributes
route recommendations and devices (like *Variable Message Signs* (VMS)) that
provide the recommended routes to the drivers.

## 4 Self-organised Route Guidance

To provide the OTC system with a routing functionality, each observer/controller
is extended by a *routing component* (RC). The RCs determine the best routes
to prominent destinations in the network. The recommended routes are updated
in response to the network's current traffic conditions and are derived with the
help of a routing protocol. The decentralised protocol manages the distribution
of travel time data in the network and maintains routing tables that contain
the currently recommended routes. Drivers are routed on a next-hop-basis from
intersection to intersection. The recommended next turn for a prominent desti-
nation is announced by VMSs installed at the intersections (or alternatively by
means of car-to-infrastructure communication).

The remainder of this section presents two protocols for vehicle routing that
are based on the well-known *Distance Vector Routing* (DVR) and *Link State
Routing* (LSR) algorithms used in the Internet (see e. g. [10]). The protocols
rely on delay estimations provided by the observer/controller components of
the network's signalised intersections and reuse their communication network to
exchange routing data (see Sect. 3). To handle incidents in the network (like road
blockages caused by accidents), an incident detection mechanism is assumed to
be available as additional data source. To this end, Klejnowski [6] presented a
distributed incident detection technique for urban settings. Before introducing
the details and modifications of the DVR and LSR protocols in the remainder
of this section, essential differences between routing in communication and road
networks are highlighted in the following.

### 4.1 Differences between Road Traffic Routing and Internet Routing

Although there is a strong relation between road traffic routing and Internet
routing, several differences can be observed. In comparison to communication
networks, road networks are typically limited in their size (in terms of contained
routers or intersections). In addition, the road network of a city is operated by one authority, while communication networks are loosely coupled sub-networks maintained by varying providers. In both cases, the routing decisions are derived by exchanging messages. In data communication, the same channel is used for payload and routing messages, while in traffic routing two separate networks exist which operate at significantly different speeds. Hence, payload (i. e. vehicles) and routing messages do not compete for bandwidth in road networks. However, traffic routing cannot make use of direct channel characteristics, but has to derive travel time estimations from detectors in the road network.

Besides the general structure of the network, nodes themselves are largely different. An intersection in traffic control corresponds to a router in data communication. Typically, a router contains one routing table for all destinations, since no restrictions regarding the relationship between incoming and outgoing links exist. In contrast, intersections can have separate queues for their turnings such that not only the destination of a vehicle, but also the used intersection approach need to be considered. This defines the need of separate routing tables for all approaches of an intersection. In addition, the transmission time within the router can be mostly neglected in data communication, but the occurring delays at intersections are the key characteristic to quantify the link cost (i. e. the travel time).

Furthermore, obvious differences are related to the dissimilarity of data packets and vehicles. Data packets can be dropped in case of overload situations, their ordering can be reorganised according to prioritisations, and some may also be stored for comparably long durations. These options are not available for road networks.

## 4.2 Distance Vector Routing for Road Networks

The first DRG mechanism adapts the Internet's DVR protocol [10] for the usage in urban road networks. The adapted protocol is responsible for maintaining routing tables for each of the intersection's approaches. It updates them based on routing messages received from neighbouring intersections and communicates changes to its own neighbours.

The mechanism works as follows: Initially, each intersection checks whether it is located in the vicinity of a predefined prominent destination (like the main station, a stadium, or the city hall). If a prominent destination is identified, the RC creates routing table entries for those approaches that can reach the destination via one of the intersection's turnings. The table entries contain the destination, the recommended turning, and the current travel time as cost. The travel time consists of two parts: the distance-induced travel time and the average delay caused by red traffic lights. The former part is approximately static and can be estimated from the length and the speed limits of the connecting road segments (which are assumed to be available at the intersection). The latter value is obtained from the intersection's observer/controller (see Sect. 3). The sum of both values is stored as total travel time for the routing entry.
Once a routing table entry has been created or updated, it is sent as routing message (or *distance vector*) to the corresponding upstream intersection where all routing tables are iteratively updated. To obtain the cost for the received route, the time that is required to reach the sender (i. e. the local turning delay plus the travel time for the connecting road segment) is added to the travel time received with the message. Then, the routing table is checked: If the message's destination is unknown, a new table entry is created from the message. Otherwise, the existing routing entry is checked. If its recommended turning leads to the sender, its travel time is updated. If, on the other hand, the known route recommends a different turning, the travel times of the known and the novel route are compared and the novel route replaces the known one if it is faster. As a result, the routing tables store estimated travel times to each destination.

In literature, the standard DVR protocol from the Internet domain is affected by the *count-to-infinity* problem (see e. g. [10]). The problem occurs in the context of updating the distance vectors. It can be neglected for the modified approach for traffic networks, since (1) data moves much faster than cars, (2) the DRG mechanism is periodically restarted, and (3) traffic situations typically do not change abruptly.

## 4.3 Link State Routing for Road Networks

A modified LSR protocol serves as DVR alternative. LSR broadcasts estimated travel times for the network's turning movements. Based on these broadcasts, the best routes can be derived.

In a first step, each RC generates a status description for its intersection. For this purpose, *link states* are determined for each path that directly connects a preceding to a succeeding intersection. Every such path includes one turning movement that belongs to the RC's intersection. Besides information about start and end intersection, the link state contains the expected total travel time for the path. Similar to the DVR approach, the total travel time consists of two parts, namely the distance-induced travel time and the delay occurring at the path's signalised turning movement. Again, the former part can be estimated by taking travelled distances and speed limits into account, while the latter part is calculated as the turning's estimated delay using Webster's formula. After determining the link states for all turnings, the RC sends this information to all other RCs in the network using broadcast messages.

After receiving all link state broadcasts, each RC is able to build a graph of the network by combining the link states in a second step. A link state message represents a subgraph describing one intersection and the approaching roads. By connecting these subgraphs according to the defined start and end intersections of each link, each RC obtains a weighted graph that models the road network with the current travel times.

The last step of the process derives minimum-cost routes and stores the route recommendations in the routing tables for each approaching road. Minimum-cost routes may be identified with the help of Dijkstra's algorithm that is applied to the graph generated in the previous step. As result of the calculation, the
currently best paths to all destinations are known and can be stored in the routing tables that are associated with the intersection approaches. Like for the DVR protocol, the table entries contain the destination, the recommended next turning, and the estimated travel time to the destination.

# 5 Evaluation

To evaluate the potential benefits of a DRG system, OTC-controlled intersections with and without their RCs have been compared in a simulation study.

## 5.1 Experimental setup

The evaluation has been conducted for a simulated network that is illustrated in Fig. 1. The network consists of three Manhattan-type sub-networks. It contains 27 signalised intersections (depicted as circles) and 28 prominent destinations (depicted as diamonds). Within each sub-network, the intersections are connected by one-laned road segments of 250 m length that provide two additional turning lanes starting 100 m before an intersection. Regions are connected by two-laned roads. Fig. 1. Network map (incl. incident location)

<figure><img src="image_2.png" /></figure>

Signalised intersections are operated by an observer/controller (see Sect. 3) and can provide route recommendations for the prominent destinations. Each destination also serves as origin for traffic entering the network. Two scenarios are investigated:

- In the regular scenario, eight vehicles per hour travel from every origin to every destination. In total, 6048 vehicles traverse the network in every hour. Since this demand does not cause significant jams at the network's intersections, the scenario allows to evaluate the impact of DRG under uncongested conditions. It is simulated for a period of three hours.

- In the incident scenario, the same amount of traffic traverses the network. However, one of the roads connecting two sub-networks is temporarily blocked due to an incident (see Fig. 1). The blockage affects both directions of the road, occurs after 15 minutes and lasts for 20 minutes within the two hour simulation period. The incident scenario allows to evaluate the benefit of DRG in the presence of disturbances.

As the literature reports a widely varying driver acceptance for VMS-based route recommendations [4, 5], acceptance rates of 0.125 (low), 0.375 (medium),
<table><caption>**Table 1.** Result summary for the regular scenario</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Ref.</th><th colspan="3">Distance Vector Routing</th><th colspan="3">Link State Routing</th></tr><tr><th>0.125</th><th>0.375</th><th>0.75</th><th>0.125</th><th>0.375</th><th>0.75</th></tr></thead><tbody><tr><td>Travel time [s]</td><td>378</td><td>342 (9.5%)</td><td>312 (17.5%)</td><td>305 (19.3%)</td><td>348 (7.9%)</td><td>315 (16.7%)</td><td>316 (16.3%)</td></tr><tr><td>Stops [#]</td><td>5.14</td><td>4.92 (4.3%)</td><td>4.66 (9.3%)</td><td>4.61 (10.3%)</td><td>5.00 (2.7%)</td><td>4.73 (8.0%)</td><td>4.75 (7.6%)</td></tr><tr><td>Fuel [l]</td><td>187.6</td><td>190.5 (-1.5%)</td><td>182.4 (2.8%)</td><td>178.9 (4.6%)</td><td>192.5 (-2.6%)</td><td>185.0 (1.4%)</td><td>184.9 (1.4%)</td></tr><tr><td>CO [kg]</td><td>811.3</td><td>784.4 (3.3%)</td><td>721.9 (11.0%)</td><td>707.2 (12.8%)</td><td>797.0 (1.8%)</td><td>731.4 (9.8%)</td><td>731.8 (9.8%)</td></tr><tr><td>HC [kg]</td><td>63.9</td><td>61.5 (3.8%)</td><td>56.2 (12.1%)</td><td>55.0 (13.9%)</td><td>62.4 (2.3%)</td><td>56.8 (11.1%)</td><td>56.8 (11.1%)</td></tr><tr><td>NO<sub>x</sub> [kg]</td><td>13.8</td><td>13.2 (4.3%)</td><td>12.0 (13.0%)</td><td>11.7 (15.2%)</td><td>13.4 (2.9%)</td><td>12.2 (11.6%)</td><td>12.1 (12.3%)</td></tr></tbody></table>

and 0.75 (high) have been investigated for both scenarios. The routing protocols have been executed every 150 s and are evaluated with respect to the mean travel time and the mean number of stops per vehicle. These measures indicate how efficiently the road network is utilised and reflect the drivers' comfort. Additionally, fuel consumption and pollution emissions of all vehicles have been investigated in total to estimate the environmental impact of DRG. The evaluation of pollution emissions focusses on Carbon Dioxide (CO₂), Carbon Monoxide (CO), Nitrogen Oxides (NOₓ), and un-burnt Hydrocarbons (HC) as these are the main pollutants emitted from petrol and diesel engines. CO, NOₓ, and HC are emitted especially during high load and idling periods of petrol and diesel engines (i. e. when vehicles are standing with running engines or when they have to accelerate after a stop). The emission of CO₂ is (for a given type of fuel) directly proportional to the fuel consumption.

All response variables have been evaluated with the help of the microscopic traffic simulator AIMSUN v. 5.1.11 [3]. Fuel consumption rates and pollution emissions have been derived with the help of AIMSUN's environmental models.

## 5.2 Experimental results

Simulation results for the regular scenario are summarised in Table 1. The table lists the mean travel time and the mean number of stops per vehicle and gives the total amount of consumed fuel and emitted pollutants for the entire network. To account for stochastic influences in the simulated environment, all table entries are average results taken from five simulation runs.

Table 1 provides data for a reference case without routing and for the proposed DRG mechanisms. In the reference case, simulated vehicles randomly select a route that minimises the distance to their destination. In the DRG case, recommended routes (with respect to current traffic conditions) are provided to the drivers. The different routing protocols and the assumed acceptance rates are listed in separate table columns. Percentage points in brackets specify the relative improvement compared to the reference case. From the results, conclusions can be drawn with respect to the suitability of the routing protocols, the influence of the driver acceptance, and the general advantage of DRG.

Results indicate a benefit of DRG for regular traffic conditions. Independently of the assumed acceptance rate, both routing protocols lead to reduced mean travel times and stops. In consequence, fuel consumption and pollution emissions are reduced in most cases. Only for low acceptance rates, DRG causes a slight increase of the total fuel consumption as the additional fuel used on the
faster, but longer recommended routes is not compensated by the relatively small reduction of jams that is achieved by rerouting. This negative effect does not occur for medium and high acceptance rates that exhibit a significantly better performance with respect to all response variables.

Figure 2 visualises mean travel times and stops obtained over the course of the simulation period. The figure shows that DVR and LSR lead to reductions especially during the first two hours. In this period, the observer/controller components at the intersections are still learning. Thus, the signalisation is not yet optimal such that queues can be observed in some road segments. This opens possibilities for DRG. Once all intersections are operated with a near-optimal signal plan, queues are relatively small everywhere in the network. In consequence, the benefit of routing is limited, but still observable.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Mean travel times and stops for the regular scenario</figcaption></figure>

In the regular scenario, queues can be reduced by an optimised signalisation alone. This changes for the incident scenario, where traffic jams are caused by blocked roads that disturb the regular traffic flows. Traffic lights can adapt their signalisation to changed flows, but they cannot eliminate growing jams caused by the incident. Here, DRG helps to guide drivers away from blocked roads.

Table 2 summarises the simulation results for the incident scenario. As in the regular case, the implementation of a DRG mechanism is beneficial with respect to the mean travel time and the mean number of stops experienced by
<table><caption>**Table 2.** Result summary for the incident scenario</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Ref.</th><th colspan="3">Distance Vector Routing</th><th colspan="3">Link State Routing</th></tr><tr><th>0.125</th><th>0.375</th><th>0.75</th><th>0.125</th><th>0.375</th><th>0.75</th></tr></thead><tbody><tr><td>Travel time [s]</td><td>457</td><td>422 (7.7%)</td><td>349 (23.6%)</td><td>333 (27.1%)</td><td>414 (9.4%)</td><td>354 (22.5%)</td><td>340 (25.6%)</td></tr><tr><td>Stops [#]</td><td>5.60</td><td>5.62 (-0.4%)</td><td>4.97 (11.3%)</td><td>4.83 (13.8%)</td><td>5.56 (0.7%)</td><td>5.05 (9.8%)</td><td>4.94 (11.8%)</td></tr><tr><td>Fuel [l]</td><td>204.8</td><td>213.7 (-4.3%)</td><td>194.3 (5.1%)</td><td>187.8 (8.3%)</td><td>212.4 (-3.7%)</td><td>197.4 (3.6%)</td><td>193.1 (5.7%)</td></tr><tr><td>CO [kg]</td><td>636.4</td><td>632.3 (0.6%)</td><td>528.9 (16.9%)</td><td>507.9 (20.2%)</td><td>622.5 (2.2%)</td><td>538.0 (15.5%)</td><td>521.0 (18.1%)</td></tr><tr><td>HC [kg]</td><td>51.3</td><td>50.4 (1.4%)</td><td>41.8 (18.5%)</td><td>39.9 (22.2%)</td><td>49.6 (3.3%)</td><td>42.4 (17.3%)</td><td>40.9 (20.3%)</td></tr><tr><td>NO<sub>x</sub> [kg]</td><td>10.9</td><td>10.8 (0.9%)</td><td>8.8 (19.3%)</td><td>8.4 (22.9%)</td><td>10.6 (2.8%)</td><td>9.0 (17.9%)</td><td>8.6 (18.9%)</td></tr></tbody></table>

individual drivers – the only exception being a marginally increased number of stops observed for DVR at a low acceptance rate. In consequence, the total amount of fuel consumed and pollutants emitted in the network is reduced in most cases. Only at a low acceptance rate, the total fuel usage is increased by rerouting. This can again be attributed to the length of recommended detours and the relatively small contribution to jam reduction in the low acceptance case. Independently of the routing protocol, the system performance improves with respect to all response variables as the acceptance rate increases. Overall, both protocols perform comparably well in the incident scenario.

Figure 3 depicts the mean travel time and the number of stops over the course of the simulation period. The peak that occurs after approximately 35 minutes and lasts for the rest of the first simulated hour indicates that the simulated incident affects both response variables. As the depicted data is gathered when the simulated vehicles have completed their trip, effects of the incidents show up in the figure with some delay after the incidents' occurrence. Furthermore, the disturbances last for some time after the incident has cleared.

When no route recommendations are provided, uninformed drivers try to use temporarily unavailable routes which causes the increase of travel times and stops. With the help of DRG, the incidents' negative effects can be alleviated independently of the applied routing protocol. Informed drivers that comply to the provided route recommendations avoid congested parts of the network. For medium or high acceptance rates, neither travel times nor stops reach the high peak values that can be observed for the reference scenario without DRG. Furthermore, both measures quickly reach their normal levels after an incident. This shows that DRG can improve the robustness of a road network with respect to disturbances like road work or accidents. Reasonably, this positive effect is more pronounced for higher acceptance rates.

# 6 Conclusion

The paper presented a self-organising approach for dynamic route guidance in urban road networks. An existing framework for traffic signal control has been extended with communicating routing components that derive route recommendations in response to the network's current traffic demand. The routing components are located at signalised intersections, where they estimate turning delays from the locally available traffic and signalisation data. Using a distributed vehicle routing mechanism that is inspired by the *Distance Vector Routing* and
<figure><img src="image_4.png" /><figcaption>Fig. 3. Mean travel times and stops for the incident scenario</figcaption></figure>

*Link State Routing* protocols known from the Internet, drivers are guided from intersection to intersection on a next-hop-basis.

A simulation study has investigated the benefits of the distributed route guidance system. Compared to drivers who randomly pick a shortest route to their destination, a traffic-responsive routing can significantly reduce travel times, stops, and – in consequence – also fuel consumption rates and pollution emissions even for moderate acceptance rates. Although vehicle routing is found beneficial even for regular traffic conditions, its benefits can be observed especially in the presence of blocked road segments. Here, a dynamic routing improves the robustness of the traffic network by guiding drivers around the disturbed areas. The beneficial effects of routing remain (to a limited extent) also for low acceptance rates.

Future work will refine the vehicle routing concept by including hierarchically structured routing tables. By partitioning a large network into regions and introducing intra- and inter-region routing tables, the requirements for the computation, communication, and storage of routing data can be reduced.

## Acknowledgment

We gratefully acknowledge the financial support by the German Research Foundation (DFG) within the priority programme 1183 "Organic Computing".
References

1. Bielefeldt, C., Condie, H.: COSMOS – Congestion Management Strategies and Methods in Urban Sites. Final report, The MVA Consultancy (1999)

2. Branke, J., Mnif, M., Müller-Schloer, C., Prothmann, H., Richter, U., Rochner, F., Schmeck, H.: Organic Computing – Addressing complexity by controlled self-organization. In: Margaria, T., Philippou, A., Steffen, B. (eds.) Proc. 2nd Int. Symp. on Leveraging Applications of Formal Methods, Verification and Validation (ISoLA 2006). pp. 200–206 (2006)

3. Casas, J., Ferrer, J.L., Garcia, D., Perarnau, J., Torday, A.: Traffic Simulation with Aimsun. In: Barceló, J. (ed.) Fundamentals of Traffic Simulation, pp. 173–232. Springer (2010)

4. Emmerink, R.H.M., Nijkamp, P., Rietveld, P., Van Ommeren, J.N.: Variable message signs and radio traffic information: An integrated empirical analysis of drivers’ route choice behaviour. Transportation Research Part A: Policy and Practice 30(2), 135–153 (1996)

5. Erke, A., Sagberg, F., Hagman, R.: Effects of route guidance variable message signs (VMS) on driver behaviour. Transportation Research Part F: Traffic Psychology and Behaviour 10(6), 447–457 (2007)

6. Klejnowski, L.: Design and implementation of an algorithm for the distributed detection of disturbances in traffic networks. Master’s thesis, Institut für Systems Engineering – System und Rechnerarchitektur, Leibniz Universität Hannover (2008)

7. Prothmann, H., Branke, J., Schmeck, H., Tomforde, S., Rochner, F., Hähner, J., Müller-Schloer, C.: Organic traffic light control for urban road networks. Int. Journal of Autonomous and Adaptive Communications Systems 2(3), 203–225 (2009)

8. Schmeck, H.: Organic Computing – A new vision for distributed embedded systems. In: Proc. 8th IEEE Int. Symp. on Object-Oriented Real-Time Distributed Computing (ISORC’05). pp. 201–203 (2005)

9. Schrank, D., Lomax, T.: The 2009 Urban Mobility Report. Tech. rep., Texas Transportation Institute (2009)

10. Tanenbaum, A.S.: Computer Networks. Pearson Education, 4th edn. (2002)

11. Webster, F.V.: Traffic Signal Settings. Road Research Technical Paper No. 39, UK Road Research Laboratory, Dept. of Scientific and Industrial Research (1958)

12. Wedde, H.F., Lehnhoff, S., et al.: Highly dynamic and adaptive traffic congestion avoidance in real-time inspired by honey bee behavior. In: Holleczek, P., Vogel-Heuser, B. (eds.) Mobilität und Echtzeit – Fachtagung der GI-Fachgruppe Echtzeitsysteme. pp. 21–31. Springer (2007)