A METHODOLOGY FOR DATA CLEANSING AND TRIP
END IDENTIFICATION OF PROBE VEHICLES
Majid Sarvi 1) , Edward Chung 1), Yasunori Murakami 1), Ryota Horiguchi2),
Masao Kuwahara 1)

1. INTRODUCTION
This study firstly proposes a methodology,
which estimates link travel time. In addition,
potential approaches to obtain probe vehicles
traffic demands from intelligent probe car (IPcar) is introduced. Then a general methodology
to cleanse the GPS data will be discussed indetail. Several intelligent vehicle- highwaysystem demonstration projects are currentlyassessing the feasibility of using probe vehicles
to collect real-time traffic data for advanced
traffic management and information systems.
However, only a few generalized algorithms
have been developed and tested. Travel time,or the time required to traverse a route between
any two points of interest, is a fundamental
measure in transportation. Travel time is a
simple concept understood and communicatedto a wide variety of audiences. Various kindsof travel time estimation and OD prediction arebeing implemented. Several data collection
techniques can be used to measure or collect
travel times. These techniques are designed tocollect travel times and average speeds ondesignated roadway segments or links. Because
these techniques differ from point-based speed
measurement, the resulting travel time andspeed data are much different than spot speeds.
An overview of the techniques relevant to thisstudy is provided in the following paragraphs.
The test vehicle technique (often referred to
as “floating car”) are the most common travel
time collection methods and consist of avehicle(s) that is specifically dispatched todrive with the traffic stream for the datacollection purpose.
_____________________________________
Key words: Probe vehicle, travel time/ OD estimation, data cleansing
1) University of Tokyo, IIS, Kuwahara Lab., 4-6-1 Komaba, Meguro
Ku, Tokyo 153-8505, Japan, Email: msarvi@nishi.iis.u-tokyo.ac.jp
Tel: 03-5452-6098, Fax: 03-5452-6420
2) i-Transport Lab. Co., Ltd., 2-12-404, Ageba-cho, Shinjuku-ku,
Tokyo, 162-0824, Japan, Email: horiguchi@i-transportlab.jp ,Tel/Fax: 03-5261-3077

The emerging and non-traditional technique
is currently being researched or developed, or
may be considered non-traditional whencompared to existing methods. Thesetechniques use a varie ty of methods, such as
inductance loops, weigh- in- motion stations, oraerial video to estimate or calculate travel
times.
The ITS probe vehicle technique utilizes
passive instrumented vehicles in the traffic
stream and remote sensing devices to collect
travel times. The ITS probe vehicles can bepersonal, public transit, or commercial vehicles.
ITS probe vehicles also typically report travel
time data to a transportation management
center (TMC) in real- time. Probe vehicles may
be equipped with several different types ofelectronic transponders or receivers. The
monitoring of cellular telephone activity is also
being tested for potential travel time collectionapplications. GPS receivers use a network of
24 satellites to determine vehicle position andare becoming common for route guidance and“mayday” security applications.
This research firstly addresses the outline oftravel time and OD estimation using IP car
equipped with GPS. Then the general
methodology used to cleanse the GPS data isdiscussed in detail.
2. OUTLINE OF TRAVEL TIME AND ODESITIMATION
Figure 1 shows the general layout of travel
time and OD estimation as well as evaluationof required number of probe cars. First, thedata obtained from 179 vehicles including 140
taxies and 39 buses running in Yokohama area
are used for the study. This data is collected
and accumulated over 15 days.
Due to communication and GPS errors there
are instances where data are not recording i.e.
contains gap. GPS error might happens where
an IP vehicle passes an underground street orin vicinity of elevated structures or due toengine being turned off. During data cleansing
process, an attempt has been undertaken todiscard those inaccurate data.

level of certainty for the entire link is achieved
i.e. a predetermined frequency of IP vehicles
will be observed.

IP car data

Data Cleansing

map matching

Travel pattern(OD matrix)

Link
characteristics

Estimate route
travel time

Movements
OD & Taxi ranks

Statistics
link & flow

Travel time model
development

Accuracy of travel
Time estimates

Level ofconfidence

3. DATA CLEANSING PROCESSThe outline of data cleansing process isillustrated in Figure 2-a. As mentioned earlier
the trajectory of each IP vehicle during one-day
trip is a continuous path, which should be
broken up into origin and destination. Inaddition, there are communications and GPSerrors, which required be recognized andcleansed for each IP car data (see Figure 2-b).
Continuous trajectory

cutting by gap(recognizing TE and data fault)

No. of IP car
required

PB event occurs
during Gap

Cut trajectoryat gap (TE)Figure 1. General layout of travel time and IP
vehicles OD estimation.

(1)

Due to the accuracy limit of GPS (about 30meters), a map matching process is needed toassign a specific route associated with thecollected data to the trajectory of each IPvehicle. However, for the OD estimation, map
matching is not necessary because OD is area
based. In addition to data cleansing thetrajectory of each IP vehicle during one-day
trip is a continuous line (path), which should be
broken up into origin and destination. This
process will be discussed later in detail. The
obtained OD matrix will demonstrate themovement patterns of IP vehicles within thenetwork. However, in future by equipping
more vehicles with GPS such as private cars
the network overall OD might be obtained. As
well the taxi ranks movement during morning
or evening peaks can also be gained which isvaluable to the taxi management center. The
study continues with estimation of travel timeand frequency of IP car over each link. In thisstep, based on travel time analysis, thecharacteristics of traffic pattern, conge stion andfree flow, could additionally be achieved. Oneof the most important questions has to beaddressed yet, is the number of IP vehicles
required in the network. Since there is arelationship between the number andmovement pattern of IP vehicles, andapplication of the data, the appropriate numberof IP vehicles need to be estimated. Thisapproach is designed to ensure that a specific(2) Gap duration is more Cut trajectory
than 15 min.
at gap(data fault/TE)(3)
Cut trajectory
Gap speed > 60 km/hr or
Gap speed < 75% of speed at at gap (data fault)
last ST record

(4)

(5)

(6)

cutting by SS (recognizing TE)
Cut trajectory
SS duration is moreat SS (TE)Than 100 sec
Duration of SS with PB
is more than 100 sec
Duration of SS with hazard
light is more than 130 sec

Cut trajectoryat SS (TE)Cut trajectoryat SS (TE)Figure 2-a. Outline of data cleansing process.

In Figure 2-a, PB is parking brake, SS isshortstop (when the vehicle speed < 3 km/hr),
TE is the trip end, and ST is short trip. Gap
speed means D/T where D (gap distance) is
straight distance between the two points
containing gap (communication error) and T is
gap duration.
Figure 2-b demonstrates the trajectory (pattern)of an IP vehicle. It consists of sequential ST
and SS events and likely a recording gap due tothe engine being turned off or any otherpreviously mentioned causes.
The procedure in Figure 2-a is as follows: (1)Figure 3 demonstrates the relationship between
gap duration with parking brake and its
frequency (relative ratio means number ofobserved value/total number of observedvalues). Based on this figure most of long gaps
happen with parking brake. In other words, along communication gap simultaneous with aparking brake is most likely that an engine hasbeing turned off. Therefore, we can consider
this event as a trip end and terminate a trip ofthe IP car at this point.

order to distinguish the destination of each trip
as it is explained in step 3 of Figure 2-a.
(3) Those points without parking brake, which
are located above the 60 km/hr line of Figure
4-b (average maximum speed of car in surfacestreet) practically are unfeasible and would beconsidered as an errors or data faults.
30000

Distance traveled by IP vehicle
Recording gap

Gap distance (m)

ST

25000

Without PB

20000

With PB60 km/hr line

15000

10000

ST5000

STST0SS

SS0SS

ST: short trip
SS: short stop

900 1200 1500 1800 2100 2400 2700 3000 3300 3600

Gap duration (sec)Figure 4-a. Gap duration and di stance relationship

Figure 2-b. ST, SS and recording gap definition
0.8
0.7

Bus with PB

0.6

Taxi with PB

0.5
0.4
0.3
0.2
0.1

Consequently, those points would be
eliminated from the database. The points below
the line however, are feasible and could
happened due to passage of an IP car throughunderground streets or in vicinity of elevatedstructures. For those points if the gap speed isless than 75% of the speed at the last recorded
short trip (S T), it is considered as trip end.
Otherwise, the two trajectories before and after
gap will be connected with a straight line to
produce a complete trajectory (see Figure 2-b).

930

870

810

750

690

630

570

510

450

390

330

270

210

150

90

030

5000

Duration of Gap(sec)(2) The relationship between gap duration andgap distance is shown in Figure 4-a. Based on
our data cleansing methodology all points withlonger than 15 minutes gap duration are
considered as trip end events (even if theymight satisfy the step 3 of Figure 2-a).
However, these points may or may not be
considered as destination of trips. In otherwords, when a gap or communication error
longer than 15 minutes happens, judging about
what happened during that period of time istentative. Therefore, is prudent to consider thispoint as a trip end event. On the other hand forthe gap shorter than 15 minutes ourmethodology requires more investigations inWithout PB

4000Figure 3. Duration of Gap with PB and its frequency

With PB

Gap distance (m)Relative Ratio

300 600time

60 km/hr line
30002000

1000

00300

600

900 1200 1500 1800 2100 2400 2700 3000 3300 3600

Gap duration (sec)Figure 4-b. Illustration of data faults(4) Having the communication and GPS error
cleansed, the next step would be separating thecontinuous trajectory based on shortstop (SS)events as illustrated in the second portion ofFigure 2-a. The relation between SS durationand SS frequency is demonstrated in Figure 5.

The cumulative percentage of SS without
parking brake longer than 100 sec is less than 5percent. Additionally, the average cycle time ofsignals are about 100 sec. Therefore, it is quiterational to consider a SS event longer than 100sec. as the destination of trip.

Bus without PB

0.20

Taxi without PB

0.15
0.10
0.05

0.30

0.35

0.25

Bus with PB

0.20

Taxi with PB

0.15
0.10
0.05

1150 45ove
r95
105
115
12513585

75

6555

45

3525

0.00
515

Relative Ratio

0.30

Duration of Short Stop(sec)Figure 6. SS duration with PB and its frequency(6) The last step used to decipher the TE eventin the methodology could be those SS withhazard lights. It is assumed that some drivers
might use hazard light when they are dropping
off or picking up passengers. The relation
between SS duration with hazard light and SS
frequency is demonstrated in Figure 7.
According to this Figure 7 all SS events withTaxi with HZ

0.15
0.10
0.05

Duration of Short Stop(sec)Figure 7. SS duration with HZ light and its frequency

4. CONCLUSIONSThis study proposed a general methodology, tocleans IP vehicle data and to determine trip
ends from a continuous trajectory of each IPvehicle. In addition a framework on anapplication of the cleansed data to determine
travel pattern (OD) of IP vehicles, travel time
statistics and ultimately travel time prediction
is presented. The application of IP vehicle data
is not limited to travel time prediction only.
Theses data can also be used in otherapplications such as travel behavior andvehicle emission.
ACKNOWLEDGMENT
The authors would like to thank NEC, NEC
soft and Japan association of electronic
technology for automobile traffic and drivingfor providing us with the IP vehicles data.
REFERENCES
1) Chul, G., Jaihak, O., Sigon, K.
(1998).”Determination of optimal number of probevehicle for real-time traffic flow information.” 5thITS world congress, Seoul, Korea, 1998.

2) Makimura, M., et al. (2002).”Performanceindicator measurement using car navigation
system.” 81st TRB annual meeting, WD, 2002.

290

270

250

230

210

190

170

150

13090

1100.00
70(5) Figure 6 shows the relationship between SS
duration with parking brake and its frequency.
SS with parking brake could happen due toembarking or disembarking of passengers.
According to this figure all SS event withparking brake longer than 100 sec could beconsidered as TE event.

0.20

50

Figure 5. SS duration without PB and its frequency

Bus with HZ30

Duration of Short stop(sec)

0.2510150ove
r

125
135
145

95
105
115

75
85

55
65

35
45

515
25

0.00

Relative Ratio

Relative Ratio

0.25

hazard light longer than 130 sec could beconsidered as TE event.
However, It is worth mentioning that utilizing
the proposed data cleansing methodology
might not produce the desired results. In otherwords, there could be TE events that need to beidentified (e.g. those SS with/without parking
brake shorter than 100 sec). If that is the case,more cleansing criterions should be taken into
consideration. Some potential criterions could
be cutting a continuous trajectory at loops, uturn or self-crosses.