=Paper=
{{Paper
|id=Vol-1098/care2013_Mizuno
|storemode=property
|title=Proposal of Information Provision to Probe Vehicles Based on Distribution of Link Travel Time that Tends to Have Two Peaks
|pdfUrl=https://ceur-ws.org/Vol-1098/care2013_Mizuno.pdf
|volume=Vol-1098
|dblpUrl=https://dblp.org/rec/conf/ausai/MizunoKI13
}}
==Proposal of Information Provision to Probe Vehicles Based on Distribution of Link Travel Time that Tends to Have Two Peaks==
https://ceur-ws.org/Vol-1098/care2013_Mizuno.pdf
Joint Proceedings - AIH 2013 / CARE 2013
Proposal of information provision to probe
vehicles based on distribution of link travel time
that tends to have two peaks
Keita Mizuno, Ryo Kanamori, and Takayuki Ito
Nagoya Institute of Technology,
Gokiso, Showa, Nagoya 466-8555, JAPAN
mizuno.keita@itolab.nitech.ac.jp,
kanamori.ryo@nitech.ac.jp,
ito.takayuki@nitech.ac.jp
http://www.itolab.nitech.ac.jp/itl2/page_en/
Abstract. In most cities, traffic congestion is a primary problem that
must be tackled. Traffic control/operation systems based on information
gathered from probe vehicles have attracted a lot of attention. In this pa-
per, we examine provision of travel information to eliminate traffic jams.
Although it is conventional to provide the mean of historical accumu-
lated data, we introduce the 25th percentile and 75th percentile values
because a distribution of link travel time tends to have two peaks. As
a result, the proposed method reduced travel time of vehicles compared
with the conventional method.
Keywords: Traffic management, Probe car, Intelligent Transport Sys-
tem
1 Introduction
Automobile traffic jams have become a major problem in many cities of the
world. In Japan, an increase in vehicle emissions and time loss due to traffic
congestion have also become significant problems. As a solution to these prob-
lems, information collected from probe vehicles is attracting attention. In this
research, we assume an environment in which information of the travel time of
a vehicle in the past can be obtained, vehicles can communicate mutually, and
vehicles can share traffic conditions to reduce the travel time of all vehicles.
Thus, we propose a method of providing information to a probe vehicle for re-
ducing travel time of regular vehicles, and show the effectiveness of the proposed
method by simulation experiments.
In this research, we focus on how a distribution of link travel time tends to
have two peaks for historical accumulated data of travel time of the vehicle. In
addition to the mean of historical accumulated data of the link travel time, us-
ing the 25th percentile value and 75th percentile value of historical accumulated
data, we perform path finding and give information to the probe vehicle. Fur-
thermore, to demonstrate that the proposed method of this research is effective,
Page 53
Joint Proceedings - AIH 2013 / CARE 2013
2 Keita Mizuno, Ryo Kanamori, and Takayuki Ito
we implement traffic flow simulation based on the cell transmission model[1][2],
and we perform vehicle movement simulation of the conventional method and
proposed method. We use travel time of the vehicle, which has also been used
in conventional research, for the effect analysis of information provided to the
probe vehicle. In addition, we examine the difference between the time taken to
move in the simulation and travel time to the destination that is expected from
the historical accumulated data of the vehicle.
The remainder of this paper is organized as follows. Background and purpose
of this research are presented in chapter 2, and the distribution of link travel time
having two peaks is discussed in chapter 3. We describe the proposed information
provision method in chapter 4, the vehicle simulation in chapter 5, and the
effectiveness of the proposed method, along with future work in chapter 6.
2 Background and purpose
In this chapter, we describe the background and purpose of this research. Per-
sonal vehicles have become an essential means of transportation for many people.
However, there are many problems we must solve; for example, decline in eco-
nomic efficiency due to traffic congestion, global environmental degradation such
as global warming and air pollution, and many traffic accidents. Transportation
and traffic account for about 20% of carbon dioxide emissions in Japan, and of
that, vehicles account for about 90%[3]. Figure 1 is a diagram showing the rela-
tionship between carbon dioxide emissions and the running speed of a vehicle.
Because we can see that the carbon dioxide emissions from the vehicle decrease
when running speed of the vehicle increases, we must decrease carbon dioxide
emissions by eliminating traffic congestion, and increasing the running speed of
the vehicle. Also, there are approximately 5 billion hours per year in time lost to
congestion in Japan, and the economic loss is 11 trillion yen. Problems caused by
traffic congestion have clearly become serious in Japan, as in many other parts
of the world, and it is necessary to resolve these issues.
In addition to the promotion of next-generation vehicles such as electric cars
as a way to solve these problems, traffic operation and management measures
by Intelligent Transport Systems (ITS), such as providing path information and
road pricing, have attracted attention. The number of vehicles with vehicle per-
ception and navigation systems (probe vehicles) is increasing, and technology
of information collection and provision has also advanced in route search infor-
mation. Further, from the historical accumulated data collected from the probe
vehicle, it is observed that a distribution of link travel time tends to have two
peaks.
About providing information to the probe vehicle, Kanamori et al.[4] sim-
ulated providing information to a probe vehicle using not only the historical
accumulated data collected from the probe vehicle but also predicting the traffic
situation. Morikawa et al.[5] simulated providing information to a probe vehi-
cle using the number of right and left turns in the path to the destination, in
addition to the historical accumulated data collected from the probe vehicle.
Page 54
Joint Proceedings - AIH 2013 / CARE 2013
Proposal of information provision to probe vehicles 3
Fig. 1. Relationship between carbon dioxide emissions and running speed of vehicle
In researches of Kanamori et al. and Morikawa et al., they simulated providing
information that uses the mean of historical accumulated data collected from
probe vehicles, and searches for a route to a destination.
The purpose of this research is to propose a method to use historical accu-
mulated data focusing on the distribution of link travel time, which tends to
have two peaks, and reducing travel link time of vehicles in the simulation.
3 Distribution of link travel time
In this section, we discuss how a distribution of link travel time tends to have
two peaks. Link travel time of the vehicle described in this research is the time
to travel from one intersection to another.
Figure 2 shows example of distribution of link travel time. It is observed that
a distribution of link travel time tends to have two peaks when the vehicles pass
through the intersection, and simulations that reproduce a distribution of link
travel time have been researched[6].
The cause of the link travel time of the vehicle having two peaks is, for
example, a traffic signal. When the vehicle passes through an intersection, a
considerable difference occurs because the vehicle stops at the signal or doesn’t
stop. In previous research, they didn’t consider that a distribution of link travel
time tends to have two peaks; instead, they used the mean value of the link
travel time collected from the probe vehicle.
4 Information provision to probe vehicles
In this chapter, we provide a detailed description of the method of information
provision to the probe vehicle in this research. As usage of the historical accu-
Page 55
Joint Proceedings - AIH 2013 / CARE 2013
4 Keita Mizuno, Ryo Kanamori, and Takayuki Ito
Fig. 2. Distribution of link travel time
mulated data of link travel time for searching the route to the destination, in
addition to a conventional method to provide the mean of historical accumulated
data of the travel time, we introduce provisions of the 25th percentile value and
75th percentile value of historical accumulated data of the travel time in this
research.
Probe vehicle assumed in this paper is sending information of link travel
time and receiving information of path to destination with least travel time.
Information of path to destination with least travel time is predicted by link
travel time collected from probe vehicle.
In this experiment, we use the data of the 25th percentile and 75th percentile
values of the historical accumulated data of link travel time. To decide which
value we will use in this research, we conduct a preliminary experiment. First,
we used only the 25th percentile value of the historical accumulated data in
the information-providing simulation. Second, we used only the 75th percentile
value of the historical accumulated data in the information-providing simulation.
We compared the mean of historical accumulated data of the link travel time
with 25th percentile and 75th percentile values regarding the travel time of the
vehicle. In this research, assuming the differences of factors such as the number
of intersections passed through depending on the travel distance of the vehicle,
Page 56
Joint Proceedings - AIH 2013 / CARE 2013
Proposal of information provision to probe vehicles 5
we compare the mean value, 25th percentile and 75th percentile values by travel
distance of each vehicle.
We set the travel distance of vehicles using the 25th percentile or 75th per-
centile values in the simulation, and conduct information provision simulation
using the 25th percentile and 75th percentile values for searching the route to
the destination.
5 Simulation for evaluation
5.1 Settings of simulation
We use the data of Kichijoji and Mitaka that are provided in the traffic simu-
lation clearing house as a road network used for the evaluation experiment in
this research. The traffic simulation clearing house[7] is an institution providing
various data for validation. The network is composed of 57 nodes and 137 links.
Vehicles in the simulation number about 17,000 units, and approximately 50%
are probe vehicles in this experiment. Further, in order to accumulate link travel
time for the vehicles to be used for route search, the simulation was repeated
about 30 times. Figure 3 is a network diagram from Kichijoji and Mitaka that
is used for the simulation in this research.
Fig. 3. Network of Kichijoji and Mitaka
Page 57
Joint Proceedings - AIH 2013 / CARE 2013
6 Keita Mizuno, Ryo Kanamori, and Takayuki Ito
Table 1 shows survey contents collected by Kichijoji and Mitaka. Investiga-
tion time is set to a high-traffic period.
Since the investigation data contain the times each vehicle entered and exited
the network, we can obtain the travel time to the destination of each vehicle.
Table 1. Details of survey of Kichijoji and Mitaka
investigation time AM 7:00 AM 10:00
target area Mitaka and Musashino, Tokyo
observation points 70
target vehicle four wheel vehicles
survey contents passage time
vehicle number
car model(bus, taxi, and other)
5.2 Traffic flow simulation
In this research, we implemented a traffic flow simulation based on the cell trans-
mission model, in which the repeatability of travel time is high and we can control
the route choice of the vehicle in the simulation. The cell transmission model is
a model that divides the network links into cells and controls the movement of
vehicles by the density of vehicles in a cell.
yi (t) = min{ ni−1 (t), Qi (t), Ni (t) − ni (t)} (1)
– yi (t): number of vehicles moving to the cell of index i at time t
– Qi (t): maximum number of vehicles that can flow into the cell of index i
at time t
– Ni (t): maximum number of vehicles in the cell of index i at time t
– ni (t): number of vehicles in the cell of index i at time t
Equation (1) represents the number of vehicles to move between cells on the
cell transmission model. The number of vehicles that can move to the next cell
is determined by the smallest number of the following: number of vehicles in the
present cell, the amount of empty space in the next cell, or maximum number
of vehicles that can flow into the next cell. Equation (2) represents traffic flow
rate.
q = k ∗v (2)
– q: traffic flow rate in the cell.
– k: vehicle density in the cell.
Page 58
Joint Proceedings - AIH 2013 / CARE 2013
Proposal of information provision to probe vehicles 7
– v: vehicle speed in the cell.
Traffic flow rate can be calculated from the vehicle speed and vehicle density
in the cell. There are many equations that can calculate the vehicle speed from
the density. In this research, we use the formula of Green Shields[8] to calculate
the traffic flow rate.
The traffic flow simulation implemented in this research uses a data set of
network and departure time, departure point, destination point, and whether
the vehicle is a probe vehicle. To verify the reproducibility of the traffic flow
simulation, we compare ours with the traffic flow simulation based on the cellular
automata model[9][10] regarding a coefficient of simple linear regression and root
mean square of the travel time of the vehicle. The cellular automata model is a
discrete model and is easy to implement. In the experiments, root mean square
being close to 0 and a coefficient of simple linear regression being close to 1
represents that the reproducibility of vehicle travel time is high.
Table 2. Comparison of cellular automata model and cell transmission model for
reproducibility of travel time
model root mean square coefficient of simple linear regression
cell transmission 2.029 0.835
cellular automata 3.502 0.339
Table 2 shows the results of a comparison of the coefficient of simple linear
regression and the root mean square regarding the simulation based on the cel-
lular automata model and the cell transmission model. Table 2 shows that the
reproducibility of the travel time in the simulation based on the cell transmis-
sion model is greater than that of the cellular automata model from the values
of both the coefficient of simple linear regression and the root mean square.
Traffic flow simulation that reproduces a distribution of link travel time tend-
ing to have two peaks is required for information provision and shows the effec-
tiveness of proposed method.
Figure 4 shows that the passage number and travel times of the vehicles on
one link in the network when we simulated movement of the vehicles using the
Kichijoji and Mitaka data set on traffic flow simulation. As Figure 4 shows, it
was confirmed that it is possible to reproduce a distribution of link travel time
tending to have two peaks in the traffic flow simulation implemented in this
research.
5.3 Experimental result
Difference of the travel time for each distance of vehicles We show
the comparison results regarding the travel time of vehicles between using the
Page 59
Joint Proceedings - AIH 2013 / CARE 2013
8 Keita Mizuno, Ryo Kanamori, and Takayuki Ito
Fig. 4. Traffic volumes and travel time of the vehicles at a certain link in the simulation
Fig. 5. Difference in travel time of vehicles between using the mean value and 75th
percentile value for route search by travel distance of vehicles
mean value, 25th percentile value and 75th percentile value of the historical
accumulated data of the link travel time.
Figures 5 and 6 show difference of travel time between using the mean, 25th
percentile value, and 75th percentile value for route search by travel distance
of vehicle. The value of the graph subtracts the travel time when using 75th
percentile and 25th percentile values from the travel time in case of using the
mean value. As the value of the graph is large, it represents that the travel time
Page 60
Joint Proceedings - AIH 2013 / CARE 2013
Proposal of information provision to probe vehicles 9
Fig. 6. Difference in travel time of vehicles between using the mean value and 25th
percentile value for route search by travel distance of vehicles
of vehicles using the mean value is more than the travel time of vehicles using
the 25th percentile value and 75th percentile value. In Figure 5, the travel time
of vehicles using the 75th percentile value is less than that using the mean value
regarding vehicles that travel distances of 1,000 meters or more. On the other
hand, in Figure 6, the travel time of vehicles using the 25th percentile value is
less than that using the mean value regarding vehicles that travel distances of
1,000 meters or less.
Proposed method and evaluation In this research, we proposed that vehicles
whose travel distance is 1,000 meters or less perform a route search using the
25th percentile value of historical accumulated data, and vehicles whose travel
distance is 1,000 meters or more perform a route search using the 75th percentile
value of historical accumulated data. The effect analysis is the total travel time
of all vehicles in the simulation.
Figure 7 shows the result of the simulation experiment in each case. Values
in the graph of Figure 7 show the total travel time of all vehicles in each case.
We describe setting of each case. There is no probe vehicle in case 1; that is,
vehicles do not change their routes in repetition. The probe vehicles search for
the route using mean value in case 2, 25th percentile value in case 3, and 75th
percentile value in case 4 as link cost. We use the proposed method in case 5.
As shown in the graph of Figure 7, using both 25th percentile value and
75th percentile value of historical accumulated data reduced the travel time of
all vehicles most.
Page 61
Joint Proceedings - AIH 2013 / CARE 2013
10 Keita Mizuno, Ryo Kanamori, and Takayuki Ito
Fig. 7. Total travel time of all vehicles in each information provision
6 Conclusion and future work
In this research, we presented background information about the problems caused
by the increasing number of vehicles on the road, such as economic losses and
environmental degradation. Also, the number of probe vehicles has increased in
recent years, and the distribution of link travel time tends to have two peaks.
Next, we proposed information provision based on a distribution of link travel
time tending to have two peaks. In the experimental simulation, as the infor-
mation provision to the probe vehicle, we proposed using both the 25th per-
centile and 75th percentile values as a function of travel distance of a vehicle.
We demonstrated that the proposed method reduced the travel time of all vehi-
cles compared with the conventional method.
In future work, we will simulate a large network. In this experiment, since we
used a small network data set, it is necessary to test a larger network to confirm
that the proposed method is effective.
The information method proposed in this research used travel distance of
the vehicles; it is also necessary to use such factors as the departure time of the
vehicles in future research.
References
1. Carlos F. Daganzo: The cell transmission model: A dynamic representation of high-
way traffic consistent with the hydrodynamic theory, Transportation Research B,
28(4):269-287(1994)
2. Carlos F. Daganzo: The cell transmission model, part II: Network traffic, Trans-
portation Research Part B: Methodological, Volume 29, Issue 2, Pages 79-93, (1995)
Page 62
Joint Proceedings - AIH 2013 / CARE 2013
Proposal of information provision to probe vehicles 11
3. Ministry of Land, Infrastructure, Transport and Tourism: amount of carbon dioxide
emissions:
http://www.mlit.go.jp/sogoseisaku/environment/sosei environment tk 000007.html,
Ministry of Land, Infrastructure, Transport and Tourism
4. Ryo Kanamori: Jun Takahashi, Takayuki Ito: A proposal of Route Information Pro-
vision with Anticipatory Stigmergy for Traffic Management, IPSJ SIG Technical
Report. ICS, 2012-ICS-169(1), 1-6, (2012)
5. Takayuki Morikawa: Toshiyuki Yamamoto, Tomio Miwa, Lixiao Wang: Development
and Performance Evaluation of Dynamic Route Guidance System ”PRONAVI” ,
Traffic Engineering, Vol.42, No.3, pp.65-75(2007)
6. Mohsen Ramezani, Nikolas Geroliminis: On the estimation of arterial route travel
time distribution with Markov chains, Elsevier, vol. 46, pages 1576-1590(2012)
7. Traffic Simulation Clearing House: http://www.jste.or.jp/sim/index.html
8. B.D.Greenshields: A Study in Highway Capacity, H. R. B., Proceedings, Vol.14,
p.468(1935)
9. A. Schadschneider, M. Schreckenberg: Cellular automaton models and traffic flow,
J. Phys. A26, L679 (1993)
10. Shinichi Tadaki, Makoto Kikuchi: Stability of congestion phase in a two-
dimensional cellular automata traffic model, Bussei Kenkyu 61(5), 453-457(1994)
11. Hirokazu Akahane, Takashi Ooguchi, Hiroyuki Oneyama: Genealogy of the devel-
opment of traffic simulation model, Traffic Engineering 37(5), 47-55(2002)
Page 63