Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

THE OPTIMAL ARRANGEMENT OF INFRARED BEACONS ON A
ROAD NETWORK TO COLLECT VEHICLE TRAJECTORIES PATTERN ANALYSIS USING SCHEMA THEORY
Ryota HORIGUCHI
Doctoral Researcher
Institute of Industrial Science,
University of Tokyo
4-6-1-Cw504 Komaba, Meguro, Tokyo
153-8505 Japan
Fax: +81-3-54526420
E-mail: poepoe@nishi.iis.u-tokyo.ac.jp

Masao KUWAHARA
Professor
Institute of Industrial Science,
University of Tokyo
4-6-1-Cw504 Komaba, Meguro, Tokyo
153-8505 Japan
Fax: +81-3-54526420
E-mail: kuwahara@nishi.iis.u-tokyo.ac.jp

Hirokazu AKAHANE
Professor
Department of Civil Engineering,
Chiba Institute of Technology
2-17-1 Tsudanuma, Narashino, Chiba
275 Japan
Fax: +81-474-780474
E-mail: akahane(at)ce.it-chiba.ac.jp

Abstract: This research purposes to estimate the optimal arrangement of less infrared beacons
to identify the trajectories of traveling vehicles on a road network. The paper, at first,
describes the “schema”, which represents the essential pattern to be extracted under certain
beacon arrangement. Subsequently, the estimation of the optimal arrangement of beacons canbe described as a combination optimization problem to maximize the entropy of schema. To
demonstrate the estimation of the optimal arrangement, a case study in Hamamatsu area isattached at the end of this paper.
Key Words: infrared beacon, VICS, ITS, combination optimization

1. INTRODUCTION
An infrared beacon used in VICS (Vehicle Information Control System) in Japan has the role
as a media both to provide the traffic information (Down-Link) and to collect the identicalcommunication with equipped vehicles (Up-Link). It is now strongly expected to derive thevaluable information like traveling vehicle trajectories from the collected Up-Links, and toutilize it for transportation planning and management.
This research purposes to estimate the optimal arrangement of less infrared beacons to collect
the trajectories of all traveling vehicles on a road network. Here, a trajectory does not mean aprecise vehicle tracking on a road, but means a path accompanied with timestamps on eachlink along the path. Although, the 'optimal' arrangement can be discussed from various pointsof view, e.g. optimal to provide most up-to-date traffic information for drivers, vehicle
trajectories might be most useful information, which can be aggregated into any
pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

time-dependent OD matrix, or into travel time of any sections. Drivers’ route choice behavior
models, required for dynamic route guidance service, can be analyzed based on collectedtrajectories as well.
By simply chaining Up-Links of each identified vehicle, we may estimate the vehicle
trajectories. If beacons are very sparsely installed, the estimated trajectory has someuncertainty because there might be alternative paths connecting two adjacent Up-Links’
beacons. If beacons are fully installed onto each link, all of the trajectories of the equipped
vehicle will completely determined, but this leads overinvestment off course. There must be
an optimal arrangement of the beacons that ensures some certainty of estimated trajectories
and satisfies the limit of the number of beacons. When the network becomes complicated andcontaining various directions of traveling vehicles, however, it is getting harder to estimate
the optimal arrangement of beacons only with “chaining” Up-Links.
The paper, at first, introduces road-vehicle communication in VICS, then describes themethodology to evaluate the quality of the estimation using “schema”, which is the featurepattern to be extracted from available paths under certain beacon arrangement. The “schema”
can be applied to the future extended Up-Link, which contains the recent history of travelinglinks. Subsequently the estimation is described as a combination optimization problem using“schema”. This optimization problem is NP-complete, but may be solved using some efficient
searching methods. To demonstrate the estimation of the optimal arrangement, a case study inTokyo area will be included in this paper.

2. UP-LINK COMMUNICATION IN VICS
There are three types of media used in VICS; i.e. i) infrared beacons, ii) FM short range wave
beacons, and iii) FM broadcasting wave. Only infrared beacons support two-way
communication, Down-Link and Up-Link, between road and equipped vehicles. Down-Link
provides various traffic information, such as congestion, parking site availability, road
construction, etc., which are to be indicated on the monitor of in-vehicle navigation system.
On the other hand, Up-Link collects vehicle identical information containing the items inTable 1. An equipped vehicle receives a random identification number (ID) given by the first
beacon to pass through, and keep the ID during the trip. When an equipped vehicle passing
through a beacon, the vehicle returns Up-Link to the beacon, packing with the ID number,present timestamp, previous beacon and previous timestamp, etc. The Up-Links are gatheredand stored into the database in VICS center.
Table 1 : Items included in Up-Link
Data Item
Random vehicle ID
Current beacon ID
Current beacon passing timestamp
Previous beacon ID
Previous prefecture code
Previous beacon passing timestamp
Starting beacon ID
Starting prefecture code
Starting beacon passing timestamp
Vehicle type code

pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

The Up-Links of the same ID are paired between two adjacent beacons, and normally used toestimate travel time of the section by comparing two timestamps of the pair (Oda et al., 1996).
Another usage to estimate origin-destination (OD) traffic volume has been proposed(Mashiyama et al., 1998). The estimation method bases on the expansion of the sample OD
matrix obtained by chaining Up-Links of the same ID. They also proposed the method tointerpolate miscommunication of Up-Link, then attempted to estimate trajectory of eachvehicle. However, they put the assumption that drivers may take the shortest path when there
are alternative paths between the adjacent beacons. The estimated trajectories, therefore, arestill not complete.

3. VEHICLE TRAJECTORY IDENTIFICATION USING SCHEMA
Although the possibility of the usage of Up-Links has been figured out, the problem how
arrange the limited number of beacons still remains in order to obtain the valuable
information with sufficient quality. The criteria for the optimal arrangement of beacon will bestrongly required, because it is unrealistic that all links in a network implement beacons.
When the network becomes complicated and contains various directions of traveling vehicles,
however, it becomes difficult to estimate the optimal arrangement of beacons only byheuristic searching approach.
This chapter introduces the schema of path as an indicator of the degree of trajectory
identification. Schema is the common patterns found in the set of pattern vectors. For instance,
pattern vectors (1, 0, 0, 1) and (1, 1, 0, 0) are said to contain a schema (1, *, 0, *). The ‘*’ inthe schema denotes ‘can be either 0 or 1’. Hereafter, a simple network shown in Figure 1 isused for the explanation of evaluation method in this chapter. The network consists of eightlinks and contains one OD pair.

2

Origin4
Destination
6

1

7

3

8
5
Link ID number

Figure 1 : Simple network used for the explanation

Before to start the evaluation, we need to enumerate all plausible paths found in the subject
network. Some useful algorithms were proposed so far to enumerate plausible paths, e.g. theefficient path in Dial's assignment algorithm (Dial, 1970). In the sample network above, there
are four paths between the OD pair.
The enumerated paths are represented in two ways. Firstly, the k-th path between an OD pairdenoted as rs is expressed as an ordered list of link number Rrsk.
Rrsk = {arski | i = 1, 2, …, mrsk}.
wherearski : the i-th link number of the k-th path.
pp.219-228(1)

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

mrsk : the number of link along the k-th path.
In the sample network, the four paths are expressed as the following ordered lists, i.e.:
R1 = {1, 2, 4, 8},
R2 = {1, 3, 5, 8},
R3 = {1, 2, 7, 5, 8},
R4 = {1, 3, 6, 4, 8}.

(2)

The paths are also expressed as a pattern vector Qrsk of which elements take 0/1. The index of
the vector means the link number. If the i-th link belongs to the k-th path, the i-th element of
the vector takes 1.
Qrsk = { qrskj | qrskj =δj, j = 1, 2, …, N}(3)where δj= 1
(aj ∈ Rrsk), or= 0(aj ∉ Rrsk),
aj : the j-th link,
N : the number of links on the k-th path.

Subsequently, the path R1~R2 are also expressed like the pattern vectors below.
Q1 = (1, 1, 0, 1, 0, 0, 0, 1),
Q2 = (1, 0, 1, 0, 1, 0, 0, 1),
Q3 = (1, 1, 0, 0, 1, 0, 1, 1),
Q4 = (1, 0, 1, 1, 0, 1, 0, 1).

(4)

If any path does not contain link loop, there exits the one-by-one mapping between Rrsk andQrsk. Therefore, the one-by-one mapping frsk that translates the index j of path pattern vector Q
to the index i of the ordered list R can be defined as follows.
∀ qrskj∈ Qrsk ∩ qrskj =1,∃ frsk : j→i | arski ∈ Rrsk ∩ arski = j.

(5)

The arrangement of beacons can be also represented as the pattern vector Bp, i.e.:
Bp = {bpl | bpl=δl, l = 1, 2, …, N}
whereδl = 1= 0(6)(the l-th link has a beacon ), or(the l-th link does not have a beacon).

Now, the operator ‘#’ is introduced that extracts the schema Srskp of the path Qrsk under the
beacon arrangement Bp.
# : (Qrsk, Bp) →Srskp
where

(7)

Srskp = {srskpl | srskpl=ϕl, l = 1, 2, …, N}
ϕl = 1(qrskl=1 ∩ bpl =1),
= 0
(qrskl=0 ∩ bpl =1), or
pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

= *(bpl =0).

Here ‘srskpl =1’ implies that the path contains l-th link, and ‘srskpl =0’ vice-versa. Otherwise,‘srskpl =*’ means unknown because there is no beacon installed at l-th link.
Assume that a vehicle traveling along one of the enumerated paths. The Up-Links concerning
to the vehicle’s trajectory can be expressed as an ordered list of link numbers, then also can bemapped into a link pattern vector, which contains a certain schema. This implies that the
trajectory might be along one of the paths that embed the same schema within them.
Back to the sample network, assume the case that the two beacons are installed at Link-4 andLink-5. For this case, the pattern vector of beacon arrangement B1 is expressed as follows.
B1 = (0, 0, 0, 1, 1, 0, 0, 0)(8)

Using the operator ‘#’, the pattern vectors of the paths are transformed into the following
schema vectors S11~ S41.
Q1#B1 = S11 = (*, *, *, 1, 0, *, *, *),Q2#B1 = S21 = (*, *, *, 0, 1, *, *, *),Q3#B1 = S31 = (*, *, *, 0, 1, *, *, *) = S21,
Q4#B1 = S41 = (*, *, *, 1, 0, *, *, *) = S11.

(9)

The schema vectors above are actually classified into two types S11 and S21, so that the
Up-Links chain of all vehicle trajectories has one of S11 or S21. However, both S11 and S21 areassociated with two paths. It is impossible to determine which path is the correct one in thiscase.
For the next case that the two beacons are installed at Link-2 and Link-4, the beacon pattern
vector is described as follow.
B2 = (0, 1, 0, 1, 0, 0, 0, 0)(10)Similarly the following four schema vectors of the paths R1~R2 are obtained by applying theoperator ‘#’.
Q1#B2 = S12 = (*, 1, *, 1, *, *, *, *),Q2#B2 = S22 = (*, 0, *, 0, *, *, *, *),Q3#B2 = S32 = (*, 1, *, 0, *, *, *, *),Q4#B2 = S42 = (*, 0, *, 1, *, *, *, *).
(11)
In this case, each of the four paths has its own schema, consequently any trajectory on the
network can be identified to the path of which schema is the same as the Up-Links’ schema.

4. OPTIMIZATION OF BEACON ARRANGEMENT
Getting the number of the paths that involve the same schema less, the certainty that the
trajectory that gives the same schema would take one of the paths becomes higher. Therefore,
pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

by introducing the entropy of schemata, we may define the following optimization problem
looking for the efficient arrangement of beacons to identify as much as vehicle trajectories
with less beacons as possible.
Find Bp such as E(Hp, Cp)→maximum,
where

Here,

Hp = -ΣrsΣkxrskplog(xrskp),
xrskp = ||Srskp|| / Krs,
Cp = ||Bp|| / N.

(12)

Hp
: the entropy of schemata,Cp: the coverage ratio of the links with a beacon,rsK: the number of paths between rs,||Srskp|| : the number of paths belonging to Srskp,||Bp|| : the number of links with a beacon,N: the number of links.

The definition of entropy can be modified to incorporate realistic traffic conditions. For
instance, if we prefer to identify the trajectories used by as much drivers as possible with lessbeacons, we may introduce the weighted entropy as follows.
H'p = -ΣrsQrsΣkxrskplog(xrskp)
where

Qrs

(13)

: traffic demand concerning with rs.

The entropy of schemata obviously becomes large when the number of the paths belonging toeach schema is less. The arrangement giving the maximum entropy, therefore, implies thateach schema has only one path, but such arrangement is not generally unique on the subject
network. We have to decide the concrete definition of the evaluation function E both tomaximize the entropy of schema and to minimize the number of beacons, depending on our
purpose. For instance, if we want to completely identify the paths of all trajectories, E will bedefined as follows; i.e.
E1 = Hp + δ(1 - Cp)
where

δ = 1
= 0

(14)
(when the all trajectories are identified), or(otherwise)

It is clear that this optimization problem is NP-complete and has local minima, some effective
searching algorithms to avoid the local minima need to be applied, such as genetic algorithms(Goldberg, 1989), TABU search method (Malek, 1990), etc.

5. SCHEMA FOR EXTENDED UP-LINK COMMUNICATION
It is now under consideration that the format of Up-Link is extended to include the nearest
passing links and travel times. With this extended Up-Links, VICS may collect more
information about the links having no beacon. We can expect to be able to identify vehicle
trajectories with much less number of beacons than the present Up-Link format.

pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

For the case of the extended Up-Link containing the history of n nearest links, the operator '#'in eq.(7) is modified to '#n' extracting schema Srskp from link pattern vector Qrsk and beacon
pattern vector Bp; i.e.
# n : (Qrsk, Bp) →Srskp
where

(15)

Srskp = {srskpl | srskpl=ϕl, l = 1, 2, …, N}
ϕl = 1 (∪(qrsky=1 ∩ bpy =1 | (x=i-n,…, i), frsk(l) = i, frsk(y) = x)),= 0 (qrskl=0 ∩ bpl =1), or= * (otherwise).

Here, 'ϕl = 1' means that the travel information of the l-th link would be included in the
Up-Link uploaded within n further links.
Again back to the sample network and assume if Up-Link contains the history of 1 nearest
link. When two beacons are installed at Link-4 and Link-5 (same as the pattern B1 in eq.(8)),
the schema of each path R1~R2 is extracted as follows.
Q1#1B1 = S11 = (*, 1, *, 1, 0, *, *, *),Q2#1B1 = S21 = (*, *, 1, 0, 1, *, *, *),Q3#1B1 = S31 = (*, *, *, 0, 1, *, 1, *),Q4#1B1 = S41 = (*, *, *, 1, 0, 1, *, *).

(16)

In this case, four individual schemas can be extracted from four paths, and consequently all
trajectories on the network can be identified.

6. COMPUTATIONAL EXPERIMENTS
In order to demonstrate the optimization of the beacon arrangement, the network at the centerof Hamamatsu-city in Figure 2 is used for the computational experiments. The network
spreads about 1.5 km from east to west, and contains 78 links. The 15 circles in the figure
represent the centroids to be trip ends, so that there are 240 OD pairs in the network.
Furthermore, 729 efficient paths can be enumerated.

Signal intersection

Link

Centroid

Figure 2 : The network at the center of Hamamatsu-city

Now, two types of evaluation functions E1 and E2 are assumed as follows; i.e.

pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

E1 = Hp + δ(1 - Cp),
where δ = 1 (when the all trajectories are identified), or= 0 (otherwise).

(17)

E2 = Hp * (1 - Cp).

(18)

The eq.(17) implies to identify all trajectories with less beacons, and eq.(18) does compromise
the identification and the number of beacons.
Then the next four case studies are examined. The result of the optimization for each case isindicated in Table 2. The optimization strategy here is somehow simple to repeat 1,000 times
random Hill-Climbing then to employ the best for each case, as it is not the purpose of thisresearch to determine the most useful strategy.
i) Optimize E1 for the present Up-Link (n=0),ii) Optimize E1 for the extended Up-Link with nearest 3 links (n=3),iii) Optimize E1 for the extended Up-Link with nearest 5 links (n=5),iv) Optimize E2 for the extended Up-Link with nearest 5 links (n=5).
Casei) E1, n=0ii) E1, n=3iii) E1, n=5iv) E2, n=5

Table 2 : The result of optimization search# of paths identified# of link installed beacon
729 (100%)50 (64%)729 (100%)
37 (47%)729 (100%)
33 (42%)501 (69%)
18 (23%)In the cases i) ~ iii), the optimal arrangement can identify 100% of trajectories. The numberof beacons is getting smaller when the number of nearest links included extended Up-Link
becomes large. However, the decrease in the number of beacon (50 -> 33) seems to bemoderate comparing to the increase in the number of links in extended Up-Link (0 -> 5).
The compromising case of iv) identifies 69% of paths with only 23% coverage of beacon
links. For this case, all paths are no weighted so that the path used by much trajectories andthe path used by less trajectories are equally treated. If we consider the weight for each pathdepending on the OD traffic volume of the path, the percentage of identified trajectories will
be get higher.
Figure 3 illustrates the optimal arrangement of beacons for each case. The arrows in the figure
indicate beacons. The forward direction of the link is to see the beacon on the left-hand side.
There may be a tendency that the nearest links accessing to the destination centroid always
have beacons, no matter how extend Up-Link. The beacons on such accessing links may not
be simultaneously used to identify other paths, so that the moderate decrease in the number ofrequired beacons described above would be pointed out.

pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4
#Beacon = 50

#Beacon = 37
BeaconBeaconE 1 , n=0

E 1 , n=3

#Beacon = 33

#Beacon = 18, # Identified Path = 501
BeaconBeaconE 1 , n=5

E 2 , n=5

Figure 3 : The optimal arrangement of beacons

7. CONCLUSION
In this paper, the schema of the trajectory obtained under certain beacon arrangement on aroad network was introduced as the index of path identification. Using the schema, it becomes
possible to search the optimal arrangement of beacons to identify vehicle trajectories, suchthat it is difficult to obtain by heuristic method to chain Up-Link. The method also extended
to future Up-Link format currently in consideration. Furthermore, the case studies using thereal network at Hamamatsu-city were examined to demonstrate the applicability of themethod, and the optimal arrangements of beacons were obtained.
For the practical use of the method presented here, there might be some discussion to beaddressed. The first one coming is how to enumerate the plausible paths in advance. Dial's
efficient paths are enumerated in this paper, but there is no guarantee that they are enough to
pp.219-228

Journal of the Eastern Asia Society for Transportation Studies, Hanoi’01, Vol.4, No.4

cover the all paths drivers really use. What is the practical evaluation function for each case isalso to be discussed. For example, the OD traffic volume estimated by traffic-census etc.
should be incorporated into the evaluation function.

REFERENCES
Dial, R.B. (1970): A probabilistic multipath traffic assignment algorithm which obviates pathenumeration, Transportation Research 5, pp.83-111, 1971
Goldberg, D.E. (1989): Genetic algorithms, in search, optimization & machine learning,
Addison Wesly Publishing Company Inc.
Malek, M., Guruswamy, M. et al. (1990): A hybrid algorithm technique, Technical Report ofTexas Univ. at Austin, TR-89-06, 1990
Mashiyama. Y, Kuwahara. M, Yoshii. T., Niikura S. and Oda T. (1998): Estimating Traffic
Demand using Uplink Information from Infrared Vehicle Detectors, Proceedings of 5thWorld Congress on Intelligent Transport Systems (CD-ROM), Seoul, Oct., 1998
Oda.T, Takeuchi.K, Yoshio Y.and Niikura S. (1996): Evaluation of Measured Travel Time
Utilizing Two-way Communication in UTMS, Proceeding of 3rd World Congress on ITS(CD-ROM), Orlando, Oct., 1996

pp.219-228