A STUDY OF ENVIRONMENT CONSCIOUS TRAVELGUIDANCE WITH PARETO IMPROVEMENT
Yasuhiro Hayashi*, Akira Naitoh
Toyota Motor Corporation
1-4-18 Koraku, Bunkyo-ku, Tokyo 112-8701 Japan
Tel.: +81-3-5800-7372, Fax.: +81-3-3817-9045
Email: yhayashi@mail.toyota.co.jp, akira_naitoh@mail.toyota.co.jp
Meilan Jiang, Takashi Tokuyama
Toyota Technical Development Corporation
2-28-23 Izumi, Higashi-ku, Nagoya 461-0001 Japan
Tel.: +81-52-728-5115, Fax.: +81-52-728-5302
Email: meiran.jiyan@mail.toyota-td.jp, takashi.tokuyama@mail.toyota-td.jp
Morihisa Iijima, Ryota Horiguchi
i-Transport Lab. Co. Ltd.
3-7 Kanda-Surugadai, Chiyoda-ku, Tokyo 101-0062 Japan
Tel.: +81-3-5283-8527, Fax.: +81-3-5283-8528
E-mail: iijima@i-transportlab.jp, horiguchi@i-transportlab.jp
Masao Kuwahara
Institute of Industrial Science, University of Tokyo
4-6-1 Komaba, Meguro-ku, Tokyo 153-8505 Japan
Tel.: +81-3-5452-6418, Fax.: +81-3-5452-6420
Email: kuwahara@iis.u-tokyo.ac.jp

ABSTRACTThis paper examines the effects of traffic flow and environmental improvements through theprovision of Pareto-improved route guidance in situations where an adequate amount oftraffic information is provided by means of floating car data. Pareto-improved route guidanceis defined as guidance information that modifies routes or departure times in such a mannerthat it is capable of improving route costs for a given driver without worsening the route costs
for other drivers.

INTRODUCTION
Current traffic information services, of which VICS is an example, are designed to provide
optimal route information for motorists. In other words, such information services areintended to create a dynamic user optimum (DUO) state that is achieved when drivers selectthe shortest possible route to their destinations at a given current time and when this process isrepeated on a real time basis. However, the desired condition is not achieved because suchinformation is provided only on some roads at present. Information services based on flow
information are expected to achieve better conditions, given the fact that they provide
high-precision information covering a larger number of roads than has been possible in thepast. In terms of social cost, however, the condition that is optimal for users is generally1different from the dynamic system optimum (DSO) state. It is known that in order to achieve
DSO, some motorists must be required to pay a penalty in terms of a disadvantage.
Implementation of car navigation services solely intended to optimize social costs might not
be acceptable to users.
Object ofThis StudyLow

4. Dynamic System Optimum (DSO)
A condition that minimizes social costs byminimizing the system travel time at the expense ofsome drivers.
High

3. Pareto Optimum

2.

Individual Utility

Social CostHigh

A condition in which no one is worse off that also
reduces social costs.
Dynamic User Optimum (DUO)
A condition in which each driver individually chooses
a route based on the current traffic information.

1. Present StateA condition in which traffic information is provided
to some drivers on a limited number of roads.

LowFig. 1 Location of Pareto Optimum
In this study, we first compare the condition (the present state) that is achieved through theprovision of incomplete information with the condition (DUO) wherein complete information
can be provided by floating car data whose effectiveness is validated. In the next step, wediscuss whether the state wherein no one personally suffers a disadvantage when comparedwith the DUO state and wherein social costs can also be reduced can be achieved though theprovision of traffic information and route guidance information. Such a state is referred to as
the Pareto optimum state, and it is assumed that the state lies between the DSO and DUO, asillustrated in Fig. 1. The Pareto optimum state is defined as a condition wherein no one canimprove on the route costs unless someone else’s route cost is worsened. The text that follows
verifies the existence of such a Pareto optimum state and its effects on improving traffic flow
and the environment.
Re-creation by simulation
Present state (the present state
reproduced through the provision oflimited traffic informat ion)

EXAMINATION OF PARETO
OPTIMALTo evaluate the states assumed in Fig. 1, thefollowing procedures are employed to recreate
the conditions.
First, recreate by simulation the traffic conditions
that can be achieved in the situation where theprovision of traffic information is limited tosome roads as the present state. Then, determinea DUO state using complete traffic information
2Co mplete traffic
informat ion provided
DUO state
Searched
heuristically
Pareto optimu mStateDSO stateFig. 2 Re-Creation Procedureby running simulations on the assumption that traffic information can be employed on all
roads (that is, for the situation where sufficient traffic information is provided by means offloating car data) in comparison with the aforementioned present state. Evaluate the merits ofgenerating/providing traffic information by utilizing floating car data and by comparing thetwo states that are also determined through the simulations.
In the next step, based on the DUO state exploiting complete traffic information, heuristicallysearch for the Pareto optimum and DSO states. By evaluating the results of the search,
examine the possibility of implementing the Pareto optimum state and its environmental
improvement effects.

OUTLINE OF SIMULATION
The present state and the DUO state are determined by simulation. The area subject tosimulation is an approximately 16 km x 10 km area lying on the west side of Tokyo, as shownin Fig. 2.
Since the use of traffic information requires equipmentthat includes on-board units, not all vehicles arecandidates. It is also assumed that not all drivers
receiving traffic information use it and select routes
based on it. Based upon this assumption, in thesimulation, the proportion of traffic information used asroute guidance is set as a parameter in this study.
20 km

Re-creation of the present state by simulation: In thepresent state, traffic information is not provided on all
roads covered by the simulation area. Taking the stateof provision of traffic information into consideration,
this case study assumes that traffic information isprovided at 19.4% of road links. Based on thepercentage of vehicles on the road that are equippedwith car navigation systems, we assume that thepercentage of drivers who use traffic information as
route guidance is 50%. The present state is re-created as
10 km
a DUO based on an incomplete information state. In thesimulations, motorists who use traffic information andFig. 3 Target Simulation Area
those who do not use it are assumed to select different
travel routes. The extent to which the present state isrecreated by the results of simulations is verified by comparing the link speeds and thevolume of traffic determined by field surveys. This condition is referred to as the recreatedpresent state. In addition, the condition in which the proportion of drivers using traffic
information as route guidance has increased from the recreated present state to 75% isdenoted as present state 75, and the new condition is reproduced in the simulations.
DUO simulation: This state assumes that traffic information is provided on all roads and to allvehicles. Therefore, this state is reproduced as the DUO based on complete information, ascompared with the present state. In reality, however, since it is inconceivable that traffic3information can be provided immediately to all vehicles, the three conditions of 50%, 75%,and 100%, representing the percentages of drivers using traffic information as route guidance,
are reproduced by simulation. These conditions are referred to as DUO50, DUO75, andDUO100, respectively.
Pareto optimum and DSO: The two states, Pareto optimum and DSO, are calculated
heuristically from the DUO75 determined by simulation (1). The Pareto optimum isdetermined according to the rules by which routes are changed if individual costs and the costto the system as a whole do not degrade.

EVALUATION METHOD
Environmental improvement effects are relatively evaluated based on the simulation result ofeach state by comparing the total travel distance, the total travel time, and the total CO2emissions. The total CO2 emissions are calculated from simulation results, using the method
described in Reference (2).

SIMULATION RESULTThe results summarized in Table 1 were obtained by running simulations based on theconditions described above.
Table 1 Comparison of Simulation Results
Present Present DUO
statestate 7550Total travel distance(1000 vehicles x kilometers)
Total travel time(1000 vehicles x hours)
Distance traveled per vehicle (km)(total distance traveled/total number of vehicles)
Average travel speed (km/h)(total travel distance/total travel time)Amount of CO2 emitted (ton/day)Total travel time reduction effect
Percentage reduction from present
state (%)
Amount of CO2 reduction
Percentage reduction from present
state (%)

DUO
75

DUO
100

6858.36843.96815.36829.57037.5

339.7

322.4

297.0

292.8

340.5

3.9

3.9

3.9

3.9

4.020.2

21.2

22.9

23.3

20.7

1,562

1,519

1,456

1,448

1,586

5.1%

12.6%

13.8%

-0.2%

2.8%

6.8%

7.3%

-1.6%

It was verified that in all cases with the exception of DUO100, both total travel time and total
CO2 emissions can be reduced from the present state. In DUO100, the total travel distanceand the total travel time increased from the present state, thus representing an inefficient state.
It appears that this result is attributable to the occurrence of a hunting condition, which iswell-known in traffic engineering, as the users of traffic information increase and approach4

100%, thus causing the traffic flow, contrary to the intended effect. A comparison of presentstate 75 and DUO50 indicates that in both total travel time and CO2 emissions, DUO50
delivers a greater reduction effect, suggesting that an increase in the number of roads onwhich floating car data-based traffic information is provided produced a notable effect inreducing both of these quantities.

CONCEPT UNDERLYING PARETO OPTIMUM/DSO STATE SEARCH
The Pareto optimum state refers to a condition that is determined through Pareto
improvements that involve minimizing the total cost under the condition that no one driver’sindividual cost is made worse than the present state; under the Pareto optimum state, it isexpected that a cost socially smaller than the dynamic user optimum (DUO) state is produced,
which is achieved when users select the shortest possible path to their destination under thecondition that complete traffic information is provided under certain conditions. In this paper,
we examined whether the Pareto optimum state can be determined under realistic traffic
conditions, and to what extent improvements in social costs can be expected under thoseconditions, by means of simulation technique. However, because it is difficult to analyticallydetermine the Pareto optimum state on a complex, large-scale network using the dynamicsimulations conducted in this study, we adopted the technique of determining the Pareto
optimum state by approximation by means of a heuristic numerical search method (3).
Based on the DUO state (in this simulation, DUO75, which produces the smallest total travel
time and CO2 emissions) that is achieved by simulation, if different alternative routes areassigned to a vehicle departing at a given time, we determine the Pareto optimum state byapproximation by establishing a heuristic rule such that a change in route is allowed only
when the vehicle’s individual travel time is reduced (individual travel time check), whenchanging to that route leads to a reduction in social cost (total travel time check), and when
the travel time required by all other vehicles is not degraded (Pareto improvement check).

VERIFICATION OF THE PARETO OPTIMUM SEARCH
Based on the above concepts, the plausibility of the results of a search for the Pareto optimum
state was verified by limiting the scope of the search as follows.
Time window subject to analysis: 7:00 to 10:00(Restricted to 3 hours including the morning peak rush hours)
O-D pair of vehicles subject to a route change: limited to one pair
The calculation of total travel time also takes the travel volume generated by other O-D
pairs into consideration.
Number of candidate routes: 65 routes. Target O-D traffic volume: 211 vehicles (of which
111 vehicles use traffic information)
When a verification was made as to whether the search was performed correctly when asearch for the Pareto optimum state was conducted using the above conditions, it was foundthat the total travel time diminished without any vehicles experiencing an increase in travel
time, as intended, and the existence of a Pareto optimum state was confirmed.

5STRATEGIES FOR REDUCING COMPUTATION TIME
Because it involves the verification of travel time on all vehicles in the simulation for eachchange of routes, the Pareto optimum search procedure requires a massive amount ofcomputational processing. Since the required computational volume makes practicalevaluations difficult, in the examinations that follow we decided to perform evaluations bytreating the state searched for by removing the Pareto improvement check as the Pareto
optimum state. Further, because in this search program the computational time required in thesearch process increases in proportion to the number of vehicles subject to route changes, if
all vehicles are addressed when the Pareto improvement check is removed, a computationaltime on a scale of several days is required. For improved work efficiency, we removed thefollowing vehicles that contribute relatively little to an improvement in traffic flow frombeing subjected to a route change: O-D pairs with a traffic volume less than a fixed number;and with respect to the routes and alternate routes determined by simulation, O-D pairs thathave a total link extension/total path extension on paths less than a fixed number (pairs withextensive duplication). Further, in this search program, the time window to be processed islimited to 7:00 to 9:00 in the morning in which traffic congestion is likely to occur, and thevehicles subject to a route change are limited to those departing no earlier than 8:00 but nolater than 9:00. In this manner, it was ensured that the computation is complete within apractical time frame.

EVALUATION OF ENVIRONMENTAL IMPROVEMENT EFFECTS IN
PARETO OPTIMUM/DSO STATESThe two states, Pareto optimum and DSO states, determined according to the method
described above were evaluated by comparing them with DUO75 used as a reference in termsof total travel time and CO2 emissions. The results are summarized in Table 3.
Table 2 Evaluation of Environmental Improvement Effects in Pareto Optimum/DUO States

DUO75
Total travel timeAmount of CO2 emitted (kg)
Total travel time reduction effect
Percentage reduction from DUO75 (%)
Amount of CO2 reduction
Percentage reduction from present state (%)

Pareto optimumstate
46,288234,432

DSO state

－

2.22%

2.51%

－

0.98%

1.05%

47,339236,764

46,149234,282

The above results provide verification that the Pareto optimum state achieves anenvironmental improvement when compared with DUO75, and produces results that compare
favorably with DSO. Table 3 and Fig. 4 below show the impact of the Pareto optimum state
on individual vehicles by comparing changes in their travel time.

6

Table 3 Changes in Travel Time for Individual Vehicles Under Pareto Optimum/DUO States
Pareto optimum state
DSO state
RoutesNo route
TotalRoutes
No routechanged changechangedchange3,492 250,433
253,935
4,810 249,125

Number of vehicles (units)
Number of vehicles with no change intravel time (units)

Total
253,935281

204,474

204,775680

200,039

200,719

218

4875

5093

1,358

6,348

7,706

6.24%

1.95%

2.01%

28.23%

2.55%

3.03%

0.92

0.51

0.52

2.06

0.52

0.63

2,993

41,09044,0832,772

42,73845,51085.71%

16.41%

17.36%

57.63%

17.16%

17.92%

1.67

1.20

1.23

1.77

1.43

1.45

Vehicles experiencing deteriorationin travel time
Number of vehicles (units)
Percentage (%)(vehicles with deteriorated travel
time/total number of vehicles)
Travel time deterioration per vehicle(min)

Vehicles experiencing improved
travel time
Number of vehicles (units)
Percentage (%)(vehicles with deteriorated travel
time/total number of vehicles)
Travel time deterioration per vehicle(min)

Pareto optimu m state
Vehicles with no route change

1200
Number of vehicles

20000015000010000050000
0Vehicles with a change in route

1000
800
600
400200Change in travel time (sec)120180240300-300
-240
-180
-120-60

12018024030
0060

-300
-240
-180
-120-600060

Number of Vehicles

250000

DSO state

Change in travel time (sec)Fig. 4 Histograms of Changes in Travel Time by Individual Vehicles Under Pareto
Optimum/DSO States

The histogram in Fig. 4 clearly shows that the Pareto optimum state determined in this study,
when compared with the DSO state, contains an extremely small number of vehicles
experiencing a deterioration in travel time. It should also be noted that the DSO state contains
a large number of vehicles experiencing a deterioration in travel time, with a large proportionof route-changed vehicles experiencing a deterioration in travel time. This is due to the factthat DSO involves individual vehicles selecting routes that involve a deterioration in travel
time in the interest of achieving overall improvements.

7CONCLUSION
The following conclusions were obtained as a result of the present study. A Pareto optimum
state exists for a given motorist wherein the total travel time is improved in a manner that
does not degrade travel time, not only for the motorist himself but also for other motorists,
through the reassignment of routes by simulation and by heuristic means. Through routechanges that approximate a Pareto improvement that improves the total travel time without
degrading one’s own travel time, the total travel time can be improved over DUO without
worsening individual vehicle travel times compared with DSO.
The evaluations conducted in this study provide verification of the possibility of achieving aPareto optimum state that improves on total travel time without causing a deterioration in
individual travel time, by means of a Pareto-improving route change. However, because astrict Pareto optimum state could not be determined in this study within reasonable
computational amounts, we were unable to evaluate the extent of the environmental
improvement effects. Also, the Pareto optimum state is determined by means of heuristic
numerical searches based on simulation results. No attempt has been made to study themethod for determining a Pareto-improving path in real time when drivers select routes inorder to achieve the Pareto optimum state in real life.

REFERENCES(1) T. Yoshii, S. Ajisawa and M. Kuwahara: Impacts on traffic congestion by switching routes
and shifting departure time of trips・5th World Congress on Intelligent Transport Systems
Proceedings, 1998.10.
(2) N. Oshiro, M. Matsushita, Y. Namikawa and H. Ohnishi: Estimation of the fuelconsumption rate and the coefficient of carbon dioxide emission of automobiles, Civil
Engineering Report, Vol.43, No.11, pp.50-55, 2001.
(3) M. Kuwahara, T. Yoshii and K. Kumagai: An analysis on dynamic system optimalassignment and ramp control on a simple network, Journal of Infrastructure Planning andManagement, Vol.667, No.50, pp.59-71, 2001.1

8