25 Ｍ－ 09

Dynamic Distribute Route Recommendation System for
Multiple Destinations
ゴウタム・チャクラボルティ（ソフトウェア情報学部、教授）、
澤本 潤（ソフトウェア情報学部、教授）、
チャヤーノン サブアーパー（大学院後期課程）
Using vehicle for evacuation from areas affected by natural disaster is an important part ofa rescue plan. While fleeing to safety place or evacuation center during disaster, there is a highprobability to get trapped in traffic congestion. This is because people will access shortest routeto safety place and road from high-populated affected area to the nearest evacuation center will
be quickly clogged with cars. We proposed a system, which will recommend routes to vehicles
using current traffic state. The recommendation will be extended to every individual vehicle forsmooth transportation to evacuation shelter, especially when more than one shelter is available.
In case of disaster, access to evacuation center will be difficult due to heavy traffic or damage
to part of the road network by disaster. For reliable navigation, we need to evaluate routes tosupport multiple destinations and re-route in real-time, by evaluating routes with updated congestion status at regular intervals, as situation changes. We proposed a routing algorithm for
multiple destinations problem by introducing a virtual destination connecting real ones. We
also proposed proper distribution of traffic to prevent and postpone traffic congestion to decrease
delay to reach safety places.

１ Introduction

could happen, and in hilly areas where floodis prevalent. Due to thin population, lownormal traffic and mountainous landscape,the roads are narrow. At many places it isdifficult to take a U-turn, or maneuver two
cars. Moreover, some evacuation centers,that are easy to access, may already be notsuitable for shelter at all, because they areaffected by natural calamities, or already too
crowded to accept more people. Even updated
traffic information is available, it is difficult
for a person to judge the safety/quickest
route to shelter. A suitable navigation system
for such a situation is not available.
Prevention of traffic congestion on road
network is already supported in DTA. But
for multiple destinations problem or destination specified by its properly only (likeshelter, parking place), there is no support
to find optimum destination and its route
recommendation. We proposed an algorithm
where the optimum from multiple possible
destinations could be selected. For searchingsuch an optimal route, where link cost varies
dynamically and multiple destinations areequally acceptable, we propose a K-shortest
routing algorithm, which is updated at predefined intervals, and recommended to the

In disaster environment (e.g., Tsunami,
Flooding) it is necessary to evacuate to safety
place, using vehicle. It is important partof rescue plan especially for old, sick anddisable person. Vehicles need reliable navigation system to support evacuation. In theexisting navigation systems (e.g., Garmin [1],TomTom [2]), they compute routing to specific destination. With Internet technology
and web service for route computation (e.g.,
Google [3] and Microsoft [4]) and dynamic
traffic assignment (DTA) [7][11], the system
can compute routing, considering road traffic
congestion data, to find an optimum route foreach vehicle.
The navigation system would suggest
optimum routes to destination. A vehicle
then follows the directions to the specificdestination. The situation is different in caseof disaster, when it is necessary for people
to relocate to safe zone, to move to evacuation center. The destination is not specificand more than one destination is equallyacceptable. More often than not, the roads
leading to those shelters get clogged due
to high traffic. This is especially true forcoastal regions in Japan where tsunami
2

used. Some services, such as Google, provide
traffic information by forecasting congestion
and its duration by performing advanced statistical predictive analysis of traffic patterns
based on past conditions. For route guidance,
first the shortest path is calculated, and thencongested links in the path, if any, are identified. Rerouting is done to avoid the predicted congested portions.
The cost of a link, when the optimizing
metric is travel time, is a dynamic entity.
The cost varies at subsequent time instances.
We need to have the traffic information at
regular intervals, and use cost prediction
algorithms for routing. [8] demonstrated afast greedy time-dependent shortest path algorithm (SP-TAG) by using time-aggregatedgraph (TAG) data structure instead of atime-expanded graph.
[7] is designed to help explain the basic
concepts and definitions of dynamic traffic
assignment (DTA) models and addresses application, selection, planning, and executionof a DTA model. It also describes the general
DTA modeling procedure and modeling issues
that may be of concern to the model user.
DTA research can be classified into two categories: analytical methods and simulationbased models. In analytical model approach
DTA is modeled as a nonlinear programming
problem, or an optimal control problem, ora variational inequalities problem. They
provide theoretical insights. The computational intractability prevents their deployment in real systems [12].
However, existing researches on navigation aim to find fastest route to specific destination for a routine environment. Application of existing navigation system in disasterenvironment is a challenge. They are inadequate to save human lives by finding thesafest route and recommend proper destination in a critical time, to an individual user.

user. When K = 2, the best and second bestroutes are searched and randomly recommend with a probability destination depending on the respective costs of the two routes.
When real-time road traffic and corresponding delay is considered as link cost, routes
with heavy traffic are automatically avoided.
1-st route is the primary route recommended.
Others are alternate routes for distributing
the traffic to prevent traffic congestion on
shortest route.
The support virtual destination, multiple
destination are connected to a single virtual
destination with link cost equal to zero.
They are Virtual Edges. Nodes in the graphare start nodes, and shortest path to virtual
destination are selected. This path would
therefore include one real-destination and avirtual link of cost 0 to the virtual destination. It is trivial to shown that one and only
one real destination will be selected in the
shortest path. Algorithm to find routes toother real destination is discussed in Section
3. The proposed method for routing is basedon dynamic traffic assignment (DTA) [7].
Link cost, inversely proportional to thetraffic, will lead to select less congested routes
and will distribute the traffic uniformly.
The current paper proposed road network
routing algorithm based on Yen’s k-shortest
path algorithm. Link cost is the travel time.
Thus, shortest path means the shortest travel
time to destination. The rest of this paper
is organized as follows. Section 2 discusses
related works. Section 3 describes existingroad traffic routing algorithm and how they
are applied to disaster environment. Section
4 presents the simulation environment, experimental results and their analysis. The
paper is finally concluded in section 5.

２ Related Works

Navigation services and devices were developed for fast searching and to recommend
routes more intelligently. Some services use
real-time traffic information as a componentof cost to calculate route. Real-time traffic
information such as INRIX [5] provides
traffic information, with pre-defined delay.
However, they do not cover the traffic data
information of the whole area. Traffic information is collected only at a few hot spots.
For delay calculation, prediction algorithm is

３ Route Recommendation for Disaster
Environment

Navigation system calculate route by inbuilt device itself, or get route from web
service system. But, native navigation system
can only recommend route for a specific destination. In many practical situations, thedriver can only characterize the intended
destination, but not specify. For example,
3

culating all such routes from source node,i.e., from the vehicle to all destinations will
involve time-consuming computation. To
reduce this computation, we introduced a
new destination node, named Virtual Destination. Virtual destination is a virtual node.
Virtual connections of cost (time of travel)
zero will connect every real destination to
the virtual node.
While we run k-shortest route algorithm,
from an area to the virtual destination, real
destinations will be included, as the paths
to virtual destination are only from real
destinations. The shortest path algorithm
will give the shortest route to the real destination. The next shortest path will be via
another real destination. It is possible tohave route, connecting two real destinations,and finally to the virtual destination using
virtual link. We modified Yen’s algorithm, sothat such routes are avoided. Thus, different
real destinations are included in different
k-shortest paths. In the simulation experiments, described in the next section, ouralgorithm finds k-shortest routes at regularintervals, and the first best route is selected
every time. The recommended routes maychange when a new route recommendation isreceived. Simulations results with K-shortest
routes, where K>3 are not included in thismanuscript.

while looking for a parking place in an
unknown town, the specification could be thedistance and cost, but not a specific parking
lot. To find proper destination and corresponding route recommendation, system canget road traffic information from a central
system or from vehicle ad-hoc network(VANET) [14]. VANET is a ad-hoc networking technology to support communication ina challenging environment. It is still an open
area of research for protocol and application
design due to their potentially large scaleand variety of possible situations.
VANET technology allow a vehicle tocommunicate with another vehicle or abase station using wireless communication of IEEE 1609 Wireless Access in Vehicular Environment (WAVE) [14], IEEE
802.11p. IEEE 1609 defines the operationsof WAVE in higher communication layer.
IEEE 802.11p [9] define amendments to
the IEEE 802.11 MAC and PHY to support
data exchange in high-speed mobile environments. The purpose of the WAVE system isto provide seamless, interoperable services
and connectivity to support pedestrian andvehicle with proper application and wirelesscommunication support.
In this work, we calculate best K-shortest
path to recommend route as well as the destination. The traffic is distributed over theroad network by recommending different
routes to different vehicle from top K shortest routes to avoid traffic congestion.

3.2 Shortest Path
Aim of the proposed routing algorithm is
to avoid long immobility on some parts of
the route. The system would suggest routeso as to be able to reach safely to evacuation
center in fastest possible time. Travel time
is considered as the cost metric of route optimization algorithm. We use Greenshield’s model to estimate the travel time, since
it is simple and extensively used in DTA
models. The model assumes that there is alinear relationship between the estimatedroad speed V i on a section of a road, andthe traffic density Ki (vehicles per meter)on that road segment. This is expressed in
Eq. 1, where Λ jam and Vf are the complete
traffic jam density and the free-flow speed
for the road segment i, respectively. Ti andLi are the estimated travel time and length
for the same segment. The free-flow speed
Vf is defined as the average speed at which

3.1 Virtual Destination
In case of emergency evacuation, vehicles
would try to reach the nearest evacuation
shelter. Roads from densely populated area
to the nearest shelter will be choked withtraffic. All vehicles will try to reach the same
shelter using the same shortest route. The
basic idea of the proposed route recommendation algorithm is to consider multiple destinations simultaneously, so as to distributethe traffic, and achieve an overall shorter
travel time to shelters. The optimization criterion is travel time.
Existing shortest path algorithms do notsupport multiple destinations. To support
multiple destinations routing, they need to
calculate shortest path to each destinationand present lowest cost as best route. Cal4

a motorist would travel if there were no congestion or other adverse conditions on theroad. To simplify our implementation, we
consider that the free-flow speed is the roadspeed limit. Basically, Λ i= Λ jam is the ratio
between the current number of vehicles andthe maximum possible number of vehicles,on the ith-segment of the road. The current
number of vehicles is obtained from thetraffic data collected by the available service,whereas the maximum number of vehicles
is proportional to length of the section of
the road, the exact value being road length/(average vehicle length + minimum gap
between vehicles)of the existing route get traffic congestion, or
are unusable.
(3)

４

Simulation Experiment and Performance Analysis

We simulated the proposed routing algorithm in disaster environment, where thewhole population from danger area needs toevacuate to safety shelter at the same time.
We used the software Simulation of Urban
Mobility (SUMO) 0.23 [10]. SUMO is an
open-source highly portable microscopic roadtraffic simulation package designed to handle
large road network.
For road network, we used part of the map
from tsunami disaster on March 11th, 2011in Miyako, Iwate [16]. The real road network
is shown in Fig. 1, where safe shelters aremarked in green and red zone Algorithm 1
Route selection strategy from the set of recommended routes is high risk area (actuallysubmerged in water during Tsunami). Other
parameters of simulation are mentioned inTable 1. We downloaded this road map fromOpenStreetMap [17][18] in OSM format, anduse Net-Convert tools in SUMO to convert
maps into a sumo usable format. We used
random trip tools in SUMO to introduce a
vehicle at a random point on road map, andstart moving from there.
Speed of all vehicles are limited to
15-20km/hr. This speed is adequate toevacuate from tsunami [19]. Other parameters in SUMO were set to default: vehicle
length=5m, the minimal gap=2.5m, and thedriver's imperfection=0.5.
For each scenario, we generate vehicles
joining the road network and allow vehicles
to travel to randomly selected destinations
from the beginning of simulation until thefirst 10 minutes. The vehicles move in haphazard directions towards diverse destinations, as happen on an ordinary day. After
10 minutes the Tsunami alarm starts. Vehicles receive the alarm and route recommendation to safety shelter. Vehicles will follow
route recommendation and drive to safe
shelter. In each scenario, we use the same
map data but different vehicle start locationand mobility. For each scenario we repeat(1)(2)
3.3 Road Traffic Distribution
If the algorithm calculates only the bestroute based on static information, the route
recommendation system will not be robust
to natural disaster. Traffic congestion will
happen because all vehicles starting at thesame area will get the same route in same
period of time. We can avoid congestion by
distributing vehicles over different routes.
In addition, one can distribute vehicles overdifferent destinations. We proposed a routing
algorithm based on K-shortest path algorithm proposed by Yen [15]. For K=3, thebest, second best and third best routes arecalculated. The proposed system will distribute vehicles in K routes. The probability thata particular route will get selected depends
on the calculated travel time for that route.
The probability is inversely proportional to
the travel time, i.e., the i th path will be selected with probability Pi
Each recommendation will announce K
routes, where Ci is the delay cost of the ithroute, and K is the number of routes recommended. Vehicle can receive a newly recommend route at some point on the road.
However frequent recommendations of newroutes will confuse the driver. To avoid thisproblem, vehicle will change route only when
new K-recommend route are not partiallyoverlapped with the previously recommendedroute. This situation will happen when parts
5

distributed method gives better results. Thus,
for lightly populated area, we do not need
distribution, but it is effective for highly
populated area.
We can conclude that distributing traffic
improves safety, instead of navigating all vehicles on the best route, when the number ofvehicles in network is increases. But there isno difference when the number of routes recommend is 2 or 3, in this particular setting,i.e., road network.

simulation 50 times, with same parameters
but vehicles joining the road randomly. The
average and variance of results are shownin Fig. 2 and Fig. 3. We group simulation
results by number of vehicles and analyze
it for number of vehicles arrived at destinations in 1 hour, and evacuation time needed.
All simulations used virtual destination
to solve multiple destinations problem. We
compare results using 1 ≤ K ≤ 3, where K=1
is when only 1st.-best route is recommended,
K=2 or K=3 are when 1st.-best and 2nd.best routes, or 1st.-best, 2nd.-best and 3rd.best routes are recommended. In those cases
traffic is distributed. We assume that roadtraffic density at different links are available
by deployment of traffic surveillance infrastructure on road (e.g., loop detectors andvideo cameras). The system will transmit therecommended route via GPRS/3G/4G LTE or
VANET communication.

Fig. 2. Number of vehicles arrived at
destination in 1 hour
4.2 Evacuation Time
Evacuation time is the time required fromstarting of alarm until all vehicles are insafety shelter.  Fig. 3 shows the result of theevacuation time required. From the plot, we
can see that evacuation time increases with
the number of vehicles on the road network.
Using K=2 and K=3 we could achieve a
shorter evacuation time compared to K=1,
when number of vehicles is high.
We can conclude that distributing traffic
improves evacuation time, when the numberof vehicles in network is increase. But there
is no difference between cases when thenumber of routes recommended is 2 or 3, in
this particular setting, i.e., road network.
This result strongly depends on the road
network of a particular town. For a town

Fig.1：Map data used for experiment
Table 1：Parameters Used For The Simulation
Parameters
Value
Road speed limit (km/hr)
15Road traffic update frequency
5(min)Number of vehicle
1000-2000
Number of safety area
3
4.1 Number of arrivals
The success of the navigation algorithm isreflected in the number of vehicles that could
reach safe shelter in a disaster environment.
Fig. 2 shows the number vehicles arrived at
one of the three safety shelters at the endof the simulation. The result clearly showsa better performance using the distributed
method, when K>1, i.e., more than 1 route insearched and recommended probabilistically.
However, in case of low traffic-density, theresults are the same. Result using 2-routeand 3-route recommendation is the best forhigh density. As the traffic volume increases,

Fig. 3. Evacuation Time used ,i.e., travel timeto evacuation shelter
6［９］D. Jiang and L. Delgrossi. Ieee 802.11p:
Towards an international standard
for wireless access in vehicular environments. In Vehicular Technology
Conference, 2008. VTC Spring 2008.
IEEE, pages 2036–2040, May 2008.
［10］D. Krajzewicz, J. Erdmann, M. Behrisch, and L. Bieker. Recent development and applications of SUMO- Simulation of Urban MObility. International
Journal On Advances in Systems andMeasurements, 5(3&4):128–138, December 2012.
［11］S. Maerivoet. Modelling traffic on motorways: State-of-the-art, numerical
data analysis, and dynamic traffic assignment. PhD thesis, Electrical engineering department, katholieke Universiteit Leuven, Belgium, 2006.
［12］S. Peeta and A. K. Ziliaskopoulos.
Foundations of dynamic traffic assignment: The past, the present and thefuture. Networks and Spatial Economics, 1:233–265, September 2001.
［13］C . S o m m e r , R . G e r m a n , a n d F .
Dressler. Bidirectionally Coupled
Network and Road Traffic Simulation for Improved IVC Analysis. IEEE
Transactions on Mobile Computing,10(1):3–15, January 2011.
［14］R. Uzcategui and G. Acosta-Marum.
Wave: A tutorial. Communications
Magazine, IEEE, 47(5):126–133, May
2009.
［15］J. Y. Yen. Finding the k shortest loopless paths in a network. Management
Science, 17(11):712–716, 1971.
［16］http://www.city.miyako.iwate.jp/
kikikanri/miyako_hazardmap.html/.
[Online Available;].
［17］ M. Haklay and P. Weber, Openstreetmap: User-generated street maps, Pervasive Computing, IEEE, vol. 7, pp.
12{18, Oct 2008.
［18］h t t p : / / w w w . o p e n s t r e e t m a p . o r g / .
[Online Available;].
［19］H. I. Jun LEE a, Kiichiro HATOYAMAb, For mulation of tsunami evacuation
strategy to designate routes for the carmode - lessons from the three cities intohoku area, japan, Proceedings of theEastern Asia Society for Transportation Studies, vol. 9, 2013.

prone to tsunami or similar natural disaster,
we can find the minimum value of K (above
which the congestion does not improve) fromits road network and number of cars.

５ Conclusion and Future WorkIn this paper, we proposed a road navigation algorithm. The proposed algorithm canfind K shortest routes to a number of target
destinations. We introduce the idea of virtual
destination for efficient search. By searching
multiple routes, we could distribute vehicles
over different routes to prevent traffic congestion. To evaluate our proposed algorithm,
we simulated evacuation situation in caseof tsunami. We used real map data from
Miyako, Japan. This map includes information of tsunami on March 11th, 2011. With
realistic simulation, we could conclude thatthe proposed algorithm was successful to leadmore vehicles to safe destinations. We also
varied that distributing traffic could increase
number of vehicles arrived at safe destination, and reduce evacuation time.

６ References［１］http://www.garmin.com/. [Online
Available;].
［２］http://www.tomtom.com/. [Online
Available;].
［３］http://www.google.com/mobile/. [Online
Available;].
［４］https://www.microsoft.com/streets/.
[Online Available;].
［５］http://www.inrix.com/. [Online Available;].
［６］h t t p : / / h t t p : / / w w w . o m n e t p p . o r g / .
[Online Available;].
［７］Y. C. Chiu, J. Bottom, M. Mahut, A.
Paz, R. Balakrishna, T. Waller, and
J. Hicks. Dynamic traffic assignment:
A primer. Transportation Research ECircular, (E-C153), Washington, DC,
USA, 2011.
［８］B. George, S. Kim, and S. Shekhar.
Spatio-temporal network databases
and routing algorithms: A summary of
results. In D. Papadias, D. Zhang, andG. Kollios, editors, Advances in Spatial
and Temporal Databases, volume 4605
of Lecture Notes in Computer Science,
pages 460–477. Springer Berlin
Heidelberg, 2007.
7