Trans. of the Society of Instrument
and Control Engineers

計測自動制御学会産業論文集
Vol.10, No.13, 113/122（2011）

Vol.10, No.13, 113/122 (2011)

Estimation of Missing Traﬃc Volume by Genetic Algorithm Basedon Traﬃc Flow Balance
Manoj Kanta Mainali∗ , Shingo Mabu∗ and Kotaro Hirasawa∗Traﬃc information collected as a part of ITS has wide range of applications. However, the collected data
might be incomplete due to the missing values caused by detector failures, communication problems or hardware/software related problems etc. To fully explore the potential of collected data, it is essential to ﬁll thegaps caused by the missing values. In this paper, a method is proposed to estimate the missing traﬃc volume
based on the traﬃc ﬂow balance, i.e., the total incoming traﬃc volume is equal to the total outgoing traﬃcvolume at intersections. The missing traﬃc volume is basically estimated using the traﬃc volume information of
the neighboring road sections. But, since the traﬃc volumes of the neighboring road sections might be missing
as well, genetic algorithm is applied to estimate multiple missing traﬃc volumes simultaneously. The proposed
method is evaluated using the traﬃc volume information generated by a large scale traﬃc simulator SOUND/4U.
Key Words: Intelligent transportation systems, missing data, traﬃc volume estimation, genetic algorithm

1.

researchers have applied data mining techniques to mine

Introduction

time related association rules from traﬃc databases andIn order to alleviate the traﬃc congestion problem andused its results for traﬃc prediction 12)∼15) .

facilitate the mobility in metropolises, a large amount of

From the above, it is concluded that the collected traﬃc

traﬃc information are collected as a part of intelligent

data, whether they are real-time data or archived data,transportation system (ITS) such as Vehicle Information

are essential for many potential applications in ITS. How-1)

in Japan. Suchever, the collected data might be incomplete due to theinformation are collected via several kinds of traﬃc mon-missing values caused by detector failures, communica-

itoring devices such as loop detectors set on the roads.

tion problems or any other hardware/software related

These collected traﬃc data have wide range of applica-

problems. The presence of missing data in the databasetions. The real time traﬃc information is provided towould degrade the quality as well as reliability of the data

travelers to support their decision making process on theand might impede the eﬀectiveness of ITS applications.

and Communication System (VICS)

1)

optimal route choice . As shown by the work of Kim et.
2)

Therefore, it is essential to ﬁll the gaps caused by missing

al. , the real time information can contribute to reduce

data in order to fully explore the applicability of the data

the operation cost and maximize resource utilization. In

and realize the ITS applications.

addition to these applications, the collected data could

While many diﬀerent kinds of traﬃc data such as traf-

be applied to maximize the utilization of the infrastruc-ﬁc volume, speed, occupancy etc. are collected, the focus

ture for smooth ﬂow of the traﬃc. One such applicationof this research is on the missing traﬃc volume data. Itof real time traﬃc data is the adaptive traﬃc signal con-is supposed that the detectors collecting traﬃc informa-

trol

3)∼6)

. On the other hand, global routing strategies
7)∼9)tion are set up at road sections and the collected values

that utilize therepresent the traﬃc volume for that road sections. The

traﬃc volume information to mitigate the traﬃc conges-

aim of this research is to ﬁll the missing traﬃc volume

tion. Since these applications make use of real-time traﬃcdata for road sections with their estimated values. Our

information, the archived traﬃc information become also

approach is based on the simple concept of the traﬃc ﬂow

valuable resources for their applications to be realized.

balance, i.e., the total incoming traﬃc volume is equal to

The archived data could be used for several kinds of pur-the total outgoing traﬃc volume at intersections. Moreposes such as network planning, congestion management,

concretely, the feature of the proposed method is to esti-

have been proposed by Yu et. al.

environmental analysis etc.
∗10), 11). In addition, several

Graduate School of Information, Production and Systems,
Waseda University, Kitakyushu, Fukuoka 808-0135, Japan(Received March 14, 2011)mate the missing data using the traﬃc volume information of the neighboring road sections. But, the problem
is not so simple, because traﬃc volumes from many roadsections might be missing simultaneously, in other words,

c 2011 SICE
TRIA 013/11/1013⃝

T. SICE Vol.10 No.13 August 2011

the traﬃc volume estimation should be done considering

have also been proposed by some researchers 21)∼23) . Ni

the whole road networks, not intersection by intersection.

et. al. 24) has proposed a multiple imputation scheme

In order to consider the multiple missing traﬃc volumes,

to impute the missing values. Basically, this approach

Genetic Algorithm (GA) is applied for the overall estima-

runs the expectation maximization/data augmentation

tion of the missing traﬃc volumes in the road networks.

approach multiple times and combines the results to re-

The rest of the paper is organized as follows. Section 2

place the missing data.

presents the related works and our contribution. Section

Diﬀerent techniques to estimate the missing data have

3 gives the deﬁnitions of notations used throughout thediﬀerent data requirements and their performance de-paper. In section 4, the proposed method to estimate thepends on the input data. Some researchers suggest using

missing traﬃc volumes is described. Section 5 presents

several estimation techniques based on some strategies in-

the performance evaluation of the proposed method. Fi-

stead of considering only one technique to estimate thenally, section 6 concludes the paper with the discussion

missing values under all conditions 19), 22) .

on future works.

2.

Most of the previous studies focus on estimating themissing data for highways. In this paper, we do not fo-

Related works and our contribution

cus on the highways, but consider estimating the miss-

Literature survey in the related ﬁeld shows that sev-

ing traﬃc volumes for common road networks. There-eral heuristic and statistical estimation techniques havefore, a new method is proposed in this paper to estimate

16)∼18).

the missing values based on the traﬃc ﬂow balance, i.e.,

Heuristic methods includes techniques such as historicalthe total incoming volume is equal to the total outgoingaverage, average of surrounding time periods, average ofvolume at intersections. The proposed approach makes

surrounding detectors etc. Historical average simply takes

use of the traﬃc volume information from the neighbor-the average of the past data of the same time of the day

ing road sections to estimate the missing traﬃc volume.

and the same day of the week as an estimate of the miss-However, there is no guarantee that the traﬃc volumes

ing values. This approach assumes that the traﬃc ﬂowsof the neighboring road sections are always available. To

through the same location are similar from day to day.

overcome this problem, the proposed method estimates a

However, the traﬃc ﬂow through the same location maylarge number of missing traﬃc volumes in the road net-vary signiﬁcantly from day to day and this approach can-works simultaneously using GA.

been applied to estimate the missing traﬃc data

The unique features of the proposed method are,• Estimate the missing values using only the traﬃc

not consider such variations. In the average techniqueof the surrounding time periods, the average of the data

volumes of the neighboring road sections

before and after the missing data in the same location is• Estimate multiple missing values simultaneously

used to ﬁll the missing values. But, the application of thisusing GA

method is limited to the cases where there is no consecutive missing data. While the above approaches considers• Since multiple missing traﬃc volumes are esti-

only the data from the same location, the average of themated at a time, the proposed approach can easily

surrounding detectors takes the relationship between thehandle the situations where the traﬃc volumes ofdata from the adjacent detectors into account by replacing the missing value with the average of the adjacent

the neighboring road sections are missing as well
However, unlike the previous approaches applicable todetectors. This method assumes that the data from theestimate other missing data such as speed, occupancy etc.,

adjacent detectors are available, and cannot be applied

the proposed method is limited to the estimation of thewhen the data in the adjacent detectors are missing too.

traﬃc volumes.

Statistical approaches are complex processes compared3.

to the heuristic approaches and include techniques such as
regression, expectation maximization, data augmentation

Notations and Deﬁnitions

In this section we give the deﬁnitions of the notations

etc 16) . Depending on the statistical process and deﬁni-

used throughout the paper.

tion, they have diﬀerent requirements for input data. Several works have applied and evaluated these methods toestimate the missing values in the transportation domain
under diﬀerent circumstances

16)∼20).

I: set of suﬃxes of intersections

S: set of suﬃxes of road sectionsi∈I

Other techniques such as Artiﬁcial Neural Networks
114: intersection i

計測自動制御学会産業論文集sij

第 10 巻第 13 号 2011 年 8 月

∑

vij ≤

: road section from intersection i ∈ I to intersection j ∈ I

vki

(3)

k∈B(i)−{j}∀i ∈ I, ∀j ∈ A(i)A(i) : set of suﬃxes of intersections from intersection i ∈ I

Eq. (2) implies that the incoming volume to intersec-

B(i) : set of suﬃxes of intersections to intersec-

tion i from intersection j should be less than or equal totion i ∈ I

the sum of the outgoing volume from intersection i except

vij: traﬃc volume of road section sij ∈ Sv̂ij: estimated traﬃc volume of road section

for intersection j. Similarly, Eq. (3) implies that the outgoing volume from intersection i to intersection j shouldsij ∈ S

be less than or equal to the sum of incoming volume tointersection i except for intersection j. While in practi-

4.

Traﬃc volume estimation

cal cases these two inequality equations might be easily
satisﬁed because the summation of the right hand of theTraﬃc volume gives the measurement of the number of

equations include the traﬃc volumes coming from othercars that pass through a certain point in a given periodintersections except intersection j or traﬃc volumes goingof time. The traﬃc volume of the road section may beto other intersections except intersection j.

diﬀerent depending on where it is measured. Under the

For the traﬃc volume balance, the total incoming vol-assumption of the static traﬃc, for any intersection i weume and total outgoing volume is only the information

can consider the following equality and inequality equa-

required. Therefore, the balance equation can be applied

tions in order to estimate the traﬃc volumes of the roadto any structure such as T-junction of intersections. Ad-

networks (see Fig. 1),

ditionally, the restrictions such as one-way traﬃc exist in
∑

∑

vji =

j∈B(i)

road networks. However, the proposed method can be apvij(1)

plied to such situations by just restricting the direction,j∈A(i)

which has no inﬂuence on the traﬃc ﬂow balance at inter-∀i ∈ I

sections. In real road sections with multiple lanes, detectors are set for each lane 16) and the set of these detectors
is called ‘station’ 16) . This paper does not consider thek

traﬃc volume for each lane, but only considers the traﬃcvolume for the road section, in other words, the traﬃcvv

volume from the station, which is obtained by summingki

ik

up the traﬃc volumes of the detectors of each lane.

j

vji
v

It is clear from Eq. (1) that the proposed method makes

v

il

i

vli

ij

the estimation using the traﬃc volume information of thelneighboring road sections. However, the traﬃc volume
in many road sections might be missing and there is novmi v

guarantee that the traﬃc volumes of the neighboring roadimsections are always available. Therefore, to overcome thisproblem, GA is used to estimate multiple missing traﬃcmvolumes at a time. The details of the GA procedure to

Fig. 1: Traﬃc volumes at intersection iestimate the missing traﬃc volumes are described below.
In the description, we intentionally skip the description
on the general ﬂow of GA as readers could refer to any

Eq. (1) deﬁnes the basic traﬃc ﬂow balance, i.e., theliterature in the evolutionary computation for the basic

total incoming traﬃc volume is equal to the total outgoingalgorithm of GA 25), 26) .

traﬃc volume at intersections. In addition, the following
two inequality equations can also be considered,
∑
vji ≤
vik

4. 1

Chromosome encoding

GA is a population based heuristic search method inwhich solutions to the problems are encoded as the chro-(2)k∈A(i)−{j}mosome of individuals. Usually, binary encoding is the∀i ∈ I, ∀j ∈ B(i)most commonly used for the chromosome encoding. How115

T. SICE Vol.10 No.13 August 2011

ever, other encoding is also possible, and in this paper,

the traﬃc enters to the start intersection i and leaves fromwe use the real number encoding. Suppose the number ofthe end intersection j. The maximum traﬃc volume thatmissing traﬃc volumes to estimate is n. Then, an arraypasses through road section sij is the total incoming traf-of size n is used as the chromosome of individuals, whereﬁc volume (S) at intersection i or the total outgoing traﬃceach gene represents an estimate of the missing traﬃcvolume (E) at intersection j. Thus, we deﬁne the upper

volume for a particular road section.

bound by taking the maximum of S and E.

4. 2

Initialization

An initial population of individuals is generated randomly. When using a binary encoding, the values foriS

the genes are randomly initialized with 0 or 1. However,

sij

j

E

in this paper, a real value is used for encoding. Therefore, the lower bound and the upper bound are deﬁned

Fig. 2: Example of initializing traﬃc volume

to randomly initialize the population. The lower boundfor road section sij

is considered to be 0 and the upper bound is decided using the traﬃc volumes of the neighboring road sections.
4. 3

Let’s assume that the gene represents the estimate of traf-

Fitness evaluation

ﬁc volume v̂ij for road section sij , then the upper boundThe ﬁtness function gives how the individual is ﬁtted

max{S, E} and initialized v̂ij are calculated as follows,

for a given problem and is used to guide the evolution
process. The ﬁtness function of individuals is deﬁned asS=∑

follow in this paper considering Eq. (1), Eq. (2) and Eq.
vki ,

(3).

k∈B(i)

E=

∑

vjk ,

k∈A(j)

F = F1 + F2 + F3 + F4
2

∑
∑
∑

vji −
vij  ,
F1 =v̂ij =random(0, max{S, E})
In the above upper bound calculation, if the traﬃc vol-i∈Ij∈B(i)j∈A(i)∑ (v − k∈A(i)−{j} vik )2 ,∑ ∑  ji∑
F2 =if vji > k∈A(i)−{j} viki∈I j∈B(i) 0, otherwise∑2
 (vij −k∈B(i)−{j} vki ) ,

∑ ∑ 
∑
F3 =
if vij > k∈B(i)−{j} vki
i∈I j∈A(i)  0, otherwise

ume of the road section is missing, then the value represented by the individual is used for that road section if
it is already initialized, otherwise, a value of 0 is used.
However, when many values are missing, the initialization range is diﬀerent. Let us consider an extreme casein which the traﬃc volumes of all the neighboring roadsections of road section sij are missing. If the estimate of
the neighboring road sections are not initialized yet, thenF4 =the upper bound for sij becomes 0, and the same for the∑sijlower bound. As the previous example shows, when there
are many missing values, the above upper bound could1v̂ij −
|B(i)− {j}|∈X

1
v̂ij −
|A(j) − {i}|limit the initial values, which could also limit the searchability of GA. Because of this, only some of the individu-∑k∈B(i)−{j}∑2vki  +2
vjk k∈A(j)−{i}X : Set of road sections whose traﬃc volumes are

als are initialized using the above upper bound (INIT I)

missing in both directions

and the rest of the individuals are initialized using thefollowing upper bound (INIT II),

Here, F1 , F2 and F3 evaluates the satisfaction of theEqs. (1)(2)(3), respectively. In addition to these evaluations, one more evaluation F4 is added, which is onlyv̂ij = random(0, max{S, E} + θ)deﬁned for the special sections, where the traﬃc vol-

θ : parameterumes of both directions in the sections are unknown. The

An illustrative example of the above procedure is shown

fourth evaluation deﬁnes that the estimated traﬃc volume

below. Let us assume that we are initializing the traﬃcshould be equal to the average of the incoming volumes

volume of road section sij in Fig. 2. In road section sij ,except from the opposite direction at the start intersection
116計測自動制御学会産業論文集

第 10 巻第 13 号 2011 年 8 月

and also should be equal to the average of the outgoing

converge to the unique global optimal solution, but thevolumes except to the opposite direction at the end inter-obtained results in diﬀerent trials are almost similar. Any-

section. For example, let us consider Fig. 3 in which theway, if there are many solutions which have the same ﬁt-

traﬃc volume vij and vji for road sections sij and sji areness value, then one of them is adopted as the optimal

missing, respectively. These two road sections are oppo-

solution.

site to each other, i.e., the outgoing and incoming road

4. 4

sections for intersection i, vice-versa for intersection j. In

At each generation, genetic operators - selection,

the traﬃc ﬂow balance equation, these two values could

crossover and mutation - are applied to the current pop-

easily oﬀset each other as they are opposite in the direc-

ulation to generate a new population.

Genetic operations

tion. For example, lets consider the traﬃc ﬂow balance

4. 4. 1

at intersection i for which vji is incoming volume and vij

In the selection operation, individuals are selected prob-

Selectionis outgoing volume. In the traﬃc ﬂow balance condition

abilistically based on their ﬁtness values. While there areof Eq. (1), if the incoming traﬃc volume vji is subtracted

many diﬀerent types of selection operations, we use eliteby the outgoing volume vij as shown in Fig. 3, then any

selection, in which the elite individual is copied to thevalues of vji and vij could easily satisfy the balance con-next generation, and tournament selection is also used.

dition, although Eq. (2) and Eq. (3) deﬁnes the upper

4. 4. 2bound. And, the above is also applied when considering

Crossover exchanges the gene information of two par-the traﬃc ﬂow balance for intersection j. In order to de-ents to create two oﬀspring. The procedure of crossover

termine the estimate of the traﬃc volumes uniquely underoperation is shown in Algorithm 1.

such a condition, the evaluation criteria F4 is added in the

Algorithm 1 Crossover operation

above ﬁtness function.

v ij

sij

Select two parents pg and ph , g ̸= h using tournament selection
Generate a random number x in (0,1)
if x < pc , where pc is crossover probability thenfor all i = 1 to n, where n is the length of chromosomedoGenerate a random number y in (0,1)
if y < 0.5 thenExchange gene at ith position of two parents
end ifend forelse
Copy parents pg and ph to the next generation
end if

v ij

j

i
v ji

sji

Crossoverv ji

Fig. 3: Example of both directions traﬃc volume missing

In the ﬁtness evaluation, F1 is the main evaluation factor and other evaluations are added as constraints. F2and F3 are added only if the described conditions are not

4. 4. 3satisﬁed. Similarly, F4 is considered when the traﬃc vol-Mutation

Mutation operator modiﬁes the individual by randomly

ume of both directions in road sections is missing. Wechanging the gene information based on mutation proba-

didn’t consider any weight because F2, F3 and F4 arebility of Pm . Two types of mutation operations are used.

only added as constraints and if the constraints are sat-

The ﬁrst one (MUT I) randomly changes the gene infor-

isﬁed, then these terms do not contribute to the ﬁtness

mation as shown in Algorithm 2.

calculation, i.e., their values are 0. Our preliminary testof using weight parameters of F2, F3 and F4 didn’t show

Algorithm 2 Mutation operation

any signiﬁcant diﬀerence in the result, so we didn’t con-

for all i = 1 to n do
Generate a random number x in (0,1)
if x < pm thenCalculate the following for road section sij that corresponds to ith gene∑S = k∈B(i) vki∑
E = k∈A(j) vjk
y = random(0, max{S, E})
Replace the value of ith gene with y
end ifend forsider any weight parameters.
Here, it should be noted that during the ﬁtness evaluation, the estimate of missing values from the individuals
is used for the missing traﬃc volumes. Also, the ﬁtness iscalculated using only the intersections that are associatedwith the road sections with missing traﬃc volumes.
GA is a heuristic search method which evolves to ﬁnd
optimal solutions. There is no guarantee that it always
117

T. SICE Vol.10 No.13 August 2011

2'7UDIILFVYHKLFOHVPLQXWH

In the second type of mutation (MUT II), a part of thecurrent value is added or subtracted with equal probability. The procedure is similar to the MUT I, except thestep of changing the value of ith gene is replaced with thefollowing,v̂ij = v̂ij ± α × v̂ij
Fig. 5: Example of OD traﬃcs for the OD pairs

α : parameter
When the GA procedure is ﬁnished, the values repre-

Table 1: GA parameter settings

sented by the elite individual are regarded as the estimate

Parameter
Value
Population size
301
INIT I size
150
INIT II size151
θ10
Elite selection
1
Tournament size
4
Crossover rate
0.7
MUT I rate
0.001
MUT II rate
0.001
α
0.5
Maximum generation 2000

of the missing traﬃc volumes for road sections.

5.
5. 1

Simulations

Study data and settings

The performance of the proposed method is evaluatedusing the traﬃc volume data generated by traﬃc simulator SOUND/4U 27) . Simulations run using 7941 majorroad sections around Kurosaki of Kitakyushu city (Fig. 4)
by setting 20 OD and 100 OD pairs. The simulations run
for 2 hrs and the traﬃc volume information for the roadsections is collected every minute. The cars are gener-

method is used to estimate the traﬃc volumes collected

ated randomly for the OD pairs and OD traﬃc volume isfor 1 minute, 5 minutes, 10 minutes and 20 minutes. Thechanged like the real traﬃcs. An example of OD traﬃcs

traﬃc volume data with 1 minute is the one generated byis shown in Fig. 5.

the simulator. The traﬃc volume data for the remaining
time periods is generated by aggregating the traﬃc volume data with 1 minute for the respective time period.
In other words, we can regard the traﬃc volume collected
for a small time period as a low traﬃc volume and thatfor a large time period as a high traﬃc volume.
Simulations were carried out using GA under the parameter settings as shown in Table 1. We considered a
population size of 301, out of which 150 individuals are
initialized based on INIT I initialization and the rest of
the individuals are initialized using INIT II. In the selection, elite selection and tournament selection of size 4 areapplied. All evaluations are done by the average over ten
runs of GA.
5. 2

Fig. 4: Kitakyushu road network used in simulations

Evaluation indicesTo evaluate the performance of the proposed method
we use the following indices,
The traﬃc volume information was obtained at a ran-

1. Mean Percentage Error (MPE) : This index gives

domly chosen time because only the static traﬃc volume

the evaluation of the average estimation error in terms of

estimation is studied in this paper, where we only selected

percentage.

the 2074 road sections with non-zero traﬃc volume. The
MP E =

traﬃc volume missing roads were selected randomly withthe rates of 1, 2, 3, 5, 10 and 20% from these road sections.

1 ∑ |vij − v̂ij |
× 100
n
vij

n : number of estimated traﬃc volumes

For the selected road sections, the traﬃc volume estimation is done using the proposed method. The proposed

2. Mean Absolute Error (MAE) : This index gives the118計測自動制御学会産業論文集

第 10 巻第 13 号 2011 年 8 月

evaluation of the average estimation error in terms of the

In addition, we also evaluated the time required to esti-

magnitude, which is described in a unit of traﬃc volumes.

mate the missing traﬃc volumes by the proposed method.

M AE =

1∑|vij − v̂ij |n

We measured the time required to estimate the missing
traﬃc volumes with 20 minutes for the unknown rates of
1% and 20%. It approximately took about 20 (s) for 1%

3. Root Mean Square Error (RMSE) : This index also

unknown rate and 180 (s) for 20% unknown rate whengives the evaluation of the average estimation error inusing a machine with Intel Core i5 2.53 GHz processor.

terms of magnitude, but in this case more weight is given

It is obvious that the higher unknown rate requires highto large errors because the square of the error is consid-

computational time because the problem size becomes big

ered. Therefore, this index can give the evaluation of theas the number of unknown traﬃc volumes is high.

variance in the estimation errors.
√
1∑
RM SE =
(vij − v̂ij )2
n
5. 3

5. 4

Discussion

The simulation results show that the proposed method
can estimate the missing traﬃc volume data very closely

Simulation results

to the actual values on average. The motivation behind

The evaluation of the proposed method to estimate theestimating the missing traﬃc volume data is to supple-

missing traﬃc volumes for diﬀerent time periods is shown

ment the ITS applications. Our perspective is that thein Fig. 6–9. In the traﬃc volume with 1 minute (Fig. 6),

results obtained can be used in ITS applications from thethe average of the percentage error of all the estimations

performance of the proposed method. However, the preci-

were approximately within the range of 15% to 30% forsion required for the practical use depends on the type of

diﬀerent unknown rates. This means that, while the per-the applications and also on the policy the system adopts.

centage error for each estimation may diﬀer, on average,

In regard to the application of the estimated data to ITS,

the proposed method estimates the missing traﬃc vol-further research could be done to study the performanceumes within 15 ∼ 30% of actual values. The average of theof the ITS applications quantitatively when using the es-

percentage error of all the estimations in the traﬃc vol-timated traﬃc volume data for missing data. However,ume with 5 minutes (Fig. 7) were approximately between

such study is out of the scope of this paper and we leave

4% to 6%. Similarly, in the traﬃc volume with 10 minutes

it open for future work.

and traﬃc volume with 20 minutes (Fig. 8 & Fig. 9), the6.

average of the percentage error of all the estimations wasConclusions

approximately between 1.5% ∼ 3.5% and 0.5% ∼ 2%, re-This paper has proposed a missing traﬃc volume es-

spectively. We can see from these results that as the time

timation technique based on the traﬃc volume balance.

period increases, the estimation error gradually decreases.

It should be noted that Genetic Algorithm was applied

It is because the traﬃc volumes in the longer time period

to estimate the multiple missing traﬃc volumes consider-tend to be ﬁltered and become less noisy than the short

ing the overall estimation of the missing data in the roadtime period. In addition, results show that the MAE val-

networks. The proposed method was evaluated using theues are very small in all the cases, which indicates that

traﬃc volume information collected by a large scale roadthe estimated traﬃc volumes are very close to the actual

simulator SOUND/4U for diﬀerent time periods with var-traﬃc volumes on average. The RMSE evaluations show

ious unknown rates. It was clariﬁed from the simulationthat the RMSE values are small and close to the MAE,

results that the proposed method can estimate the miss-which implies that the variance in the errors of estimateding traﬃc volume information very closely to the actual

traﬃc volumes is small. The results of the above eval-values. As a part of future work, further improvements ofuation indices show that the proposed method gives thethe proposed method could be studied for dynamic situ-

estimates of the missing traﬃc volumes very closely to theations.

actual values on average. An example of the comparison

Referencesof the actual and estimated traﬃc volumes is shown in1) K. Tamura and M. Hirayama: Toward Realization of VICS
- Vehicle Information and Communications System, In
Proc. of the IEEE Vehicle Navigation and Information
Systems Conference, 72/77, Oct. (1993)
2) S. Kim, M. E. Lewis and C. C. White, III: Optimal Vehicle Routing With Real-Time Traﬃc Information, IEEE
Transactions on Intelligent Transportation Systems, 6-2,

Fig. 10, which shows the comparison of the traﬃc volumes of missing sections in the case of 1 minute and 20
minutes of 1% unknown rate. From Fig. 10 it is clear thatthe estimated traﬃc volumes are close to the actual traﬃcvolumes.
119

T. SICE Vol.10 No.13 August 2011(a) MPE(b) MAE(c) RMSE

Fig. 6: Results in the traﬃc volumes with 1 minute(a) MPE(b) MAE(c) RMSE

Fig. 7: Results in the traﬃc volumes with 5 minutes(a) MPE(b) MAE(c) RMSE

Fig. 8: Results in the traﬃc volumes with 10 minutes(a) MPE(b) MAE(c) RMSE

Fig. 9: Results in the traﬃc volumes with 20 minutes

178/188, June (2005)
3) S. Chiu: Adaptive Traﬃc Signal Control Using Fuzzy
Logic, In Proc. of the Intelligent Vehicles Symposium,
98/107, July (1992)
4) P. Mirchandani and L. Head: A Real-time Traﬃc Signal
Control System : Architecture, Algorithms, and Analysis,
Transportation Research Part C : Emerging Technologies,
9-6, 415/432, Dec. (2001)
5) J. Lee, B. Abdulhai, A. Shalaby and E.-H. Chung: Real-Time Optimization for Adaptive Traﬃc Signal Control Using Genetic Algorithms, Journal of Intelligent Transportation Systems, 9-3, 111/122, July (2005)
6) C. Cai, C. K. Wong and B. G. Heydecker: Adaptive Trafﬁc Signal Control Using Approximate Dynamic Programming, Transportation Research Part C : Emerging Technologies, 17-5, 456/474, Oct. (2009)7) S. Yu, S. Mabu, F. Ye, H. Wang, K. Shimada and K.
Hirasawa: Q Value-Based Dynamic Programming with120

計測自動制御学会産業論文集

第 10 巻第 13 号 2011 年 8 月

Man and Cybernetics, 2249/2255, Oct. (2010)15) X. Li, S. Mabu, H. Zhou, K. Shimada and K. Hirasawa:
Genetic Network Programming with Estimation of Distribution Algorithms for Class Association Rule Mining
in Traﬃc Prediction, Journal of Advanced Computational
Intelligence and Intelligent Informatics, 14-5, 497/509(2010)
16) B. L. Smith, W. T. Scherer and J. H. Conklin: Exploring Imputation Techniques for Missing Data in Transportation Management Systems, Transportation Research
Record : Journal of the Transportation Research Board,
1836, 132/142 (2003)
17) J. H. Conklin and W. T. Scherer: Data Imputation Strategies for Transportation Management Systems, A Research
Project Report for the Virginia Department of Transportation (VDOT), Report No. UVACTS-13-0-80 (2003)
18) L. N. Ngyuyen and W. T. Scherer: Imputation Techniques to Account for Missing Data in Support of Intelligent Transportation Systems Applications, A Research
Project Report for the Virginia Department of Transportation (VDOT), Report No. UVACTS-13-0-78 (2003)
19) D. Maier, K. Tufte and R. J. Fernandez-Moctezuma: Improving Travel Information Products Via Robust Estimation Techniques, Technical Report No. OTREC-RR-09-02,
Oregon Transportation Research and Education Consortium, March (2009)20) L. Qu, Y. Zhang and J. Hu: PPCA-Based Mising Data
Imputation for Traﬃc Flow Volume: A Systematical Approach, IEEE Transactions on Intelligent Transportation
Systems, 10-3, 512/522, Sept. (2009)21) M. Zhong, S. Sharma and P. Lingras: Genetically Designed Models for Accurate Imputations of Missing Traﬃc
Counts, Transportation Research Record : Journal of theTransportation Research Board, 1879, 71/79 (2004)22) M. Chen, J. Xia and R. Liu: Developing a Strategy for Imputing Missing Traﬃc Volume Data, Journal of the Transportation Research Forum, 45-3, 57/75 (2006)23) R. J. Fernandez-Moctezuma, K. A. Tufte, D. Maier and
R. L. Bertini: Toward Management and Imputation of
Unavailable Data in Online Advanced Traveler Information Systems, In Proc. of IEEE Intelligent Transportation
Systems Conference, 24/29, Oct. (2007)24) D. Ni, J. D. Leonard II, A. Guin and C. Feng: Multiple Imputation Scheme for Overcoming the Missing Values andVariability Issues in ITS Data, Journal of Transportation
Engineering, 131-12, 931/938, Dec. (2005)
25) J. H. Holland: Adaptation in Natural and Artiﬁcial Systems, University of Michigan Press, Ann Harbor (1975)
26) D. E. Goldberg: Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley (1989)
27) SOUND/4U, i-Transport Lab. Co. Ltd., http://www.itransportlab.jp/products/sound/index.html.

(a) Result of the traﬃc volumes with 1 minute(b) Result of the traﬃc volumes with 20 minutes

Fig. 10: Comparison of actual and estimated traﬃc volumes under 1% unknown rate

Boltzmann Distribution for Global Optimal Traﬃc Routing Strategy, Journal of Advanced Computational Intelligence and Intelligent Informatics, 13-5, 581/591 (2009)8) S. Yu, S. Mabu, M. K. Mainali, S. Eto, K. Shimada
and K. Hirasawa: Multi-Routes Algorithm using Temperature Control of Boltzmann Distribution in Q valuebased Dynamic Programming, In Proc. of the IEEE International Conference on Systems, Man, and Cybernetics,
3989/3994, Oct. (2009)9) S. Yu, S. Mabu, M. K. Mainali, K. Shimada and K. Hirasawa: Various Temperature Parameter Control Methods
in Q value-based Dynamic Programming with Boltzmann
Distribution, In Proc. of IEEE International Conference
on Systems, Man and Cybernetics, 2677/2683, Oct. (2010)
10) A. Stathopoulos and T. Tsekeris: Methodology for Processing Archived ITS data for reliability analysis in urban
networks, In Proc. of IEE Intelligent Transportation Systems, 153-1, 105/112, March (2006)
11) Y. Chen, J. Hu, Y. Zhang and X. Li: Traﬃc Data Analysis
Using Kernel PCA and Self-Organizing Map, In Proc. ofIntelligent Vehicles Symposium, 472/477, June (2006)12) H. Zhou, W. Wei, K. Shimada, S. Mabu and K. Hirasawa:Time Related Association Rules Mining with Attributes
Accumulation Mechanism and its Application to Traﬃc
Prediction, Journal of Advanced Computational Intelligence and Intelligent Informatics, 12-4, 393/403 (2008)13) H. Zhou, S. Mabu, K. Shimada and K. Hirasawa:
Backward Time Related Association Rule Mining with
Database Rearrangement in Traﬃc Volume Prediction, In
Proc. of the IEEE International Conference on Systems,
Man and Cybernetics, 1047/1052, Oct. (2009)14) H. Zhou, S. Mabu, K. Shimada and K. Hirasawa: Time Related Association Rule Mining with Accuracy Validation inTraﬃc Volume Prediction with Large Scale Simulator, In
Proc. of the IEEE International Conference on Systems,

Manoj KANTA MAINALIHe received his M.E. degree from the Graduate School of Information, Production and Systems, Waseda University, Japan, in 2009. Since2009 he is a Ph.D. candidate at the Graduate School of Information, Production and Systems, Waseda University.

121

T. SICE Vol.10 No.13 August 2011

Shingo MABU (Member)He received the B.E. and M.E. degrees inElectrical Engineering from Kyushu University,
Japan in 2001 and 2003, respectively and Ph.D.
degree from Waseda University, Japan in 2006.
Since April 2007, he has been an Assistant Professor in the Graduate School of Information,
Production and Systems of Waseda University.
Dr. Mabu is a member of the Society of Instrument and Control Engineers and IEEE.

Kotaro HIRASAWA (Member)He received the B.E. and M.E. degrees from
Kyushu University, Japan in 1964 and 1966, respectively. From 1966 to 1992, he was with Hitachi Ltd., where he served as a Vice Presidentof Hitachi Research Laboratory. From December 1992 to August 2002, he was a Professor
in the Graduate School of Information Scienceand Electrical Engineering of Kyushu University. Since September 2002, he has been a Professor in the Graduate School of Information,
Production and Systems of Waseda University.
Dr. Hirasawa is a member of the Society of
Instrument and Control Engineers and IEEE.

122