Locating Vehicle Identification Sensors for Travel Time Information

Abstract

The problem of optimally locating sensors on a traffic network has been object of growing interest in the past few years. Sensor location decisions models differ from each other according to the type of sensors that are to be located and the objective that one would like to optimize. In this paper, we survey the main existing contributions in the literature related to the optimal location strategies of Automatic Vehicle Identification (AVI) readers on the links of a network to get travel time information.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Currently, transportation networks are significantly instrumented with various types of sensors, ranging from simple inductive loop detectors embedded in the pavement that produce a signal when a vehicle is over it, to image detectors which use cameras machine vision to detect activities over the pavement, to mechanical gauges to measure the strain on the pavement and associated infrastructure like bridges, to GPS-equipment in the vehicles that is be able to track vehicles in the network (commonly referred to as traffic probes when they are used to obtain a congestion measure of traffic such as travel times). Machine vision and laser-based readers are used to automatically collect tolls on a highway. Traffic sensors may also be used to detect incidents on a road by observing a sudden change in traffic flow patterns. All these uses are ultimately related to (a) managing traffic on a network by monitoring traffic and making traffic control decisions to decrease congestion , energy use, air pollution, etc. and (b) planning networks so that the demand using the road network is appropriately served. Thus, locating sensors optimally improves our traffic management and network planning decisions.

The problem of optimally locating sensors on a traffic network has been the object of growing interest in the past few years. Sensor location decision models differ from each other according to the type of sensors that are to be located and the objective function that one would like to optimize. Many different models have been proposed in the literature as well as corresponding solution approaches. The proposed existing models could be classified according to two main criteria: (i) the typology of sensors to be located on the network (e.g., counting sensors, image sensors, Automatic Vehicle Identification (AVI) readers), and, (ii) the objective function to be optimized, such as minimizing errors in estimating Origin- Destination (OD) trips, route flows, link flows, or travel times. Among the first models, Lam and Lo (1990) addressed the problems of locating sensors to estimate OD flows and studied how different deployments of sensors on the network could affect OD flow estimation. Since then, studies on locating sensors have grown rapidly due to the development of new methods and technologies. Indeed, traditionally, counting sensors have collected speed and flow volume data, but sensors based on technologies such as vehicle recognition and GPS can give much more information about the operation of the network. Hence new objective functions have been studied: route flow estimation and observability, link flow estimation and observability, travel time measurement and estimation, etc.

The authors have recently reviewed the literature related to sensor location for flow observability and estimation (Gentili and Michandani 2011, 2012). The focus of this chapter is on the optimal location of sensors to monitor travel time related information.

2 Travel Time Measurement and Estimation

Real-time measurement and estimation of travel times is a useful tool for traffic management and for providing information to travelers. For example, this knowledge is used for dynamically updating travel time predictions. Traditionally, collection of information for travel time estimation has been carried out by transportation agencies through an extensive use of counting sensors (i.e., loop inductance detectors) uniformly located on freeways and highways usually at distances of 0.5–1.0 miles. The origin of such a practice is based on past analysis that has shown uniform spacing among detectors is useful for Automatic Incident Detection algorithms (ADI) (the role of ADI algorithms based on loop detector data is addressed in Chap. 7 of this volume). However, it should be noted that given the massive use of GPS enabled smart phones, the data from the resulting probe vehicles’ travel times are increasingly being used for incident detection as well as travel time estimation. Nevertheless, for situations where this kind of information is not readily available, either because of low market share of smart phones or when data communication networks are not sufficiently advanced or when communication of vehicle data is expensive, the location of fixed permanent sensors is still an important and relevant approach to gather real time data for estimating travel times. The effect of counting sensor deployment on the quality of the measurements and estimation of travel times has been widely studied (see for example, Ban et al. 2009; Bartin et al. 2007; Chan and Lam 2002; Chaudhuri et al. 2011; Danczyk and Liu 2011; Edara et al. 2010; Fujito et al. 2007; Liu et al. 2006). Travel time measurement can also be obtained using technology such as Automatic Vehicle Identification (AVI) readers. Examples include sensors that use machine vision to read license plates, sensors that read unique blue tooth signals from each vehicle that passes in its vicinity, and sensors that read a radio electronic tag much like the RFID tags used to track parts in manufacturing facilities. The remainder of the chapter will review existing approaches to optimally locating AVI readers on networks to estimate travel times and related measures.

Fig. 13.1

A simple network example

3 Travel Time and Related Information on Networks

The use of AVI readers for estimating roadway travel times is a recent development. Their primary application has been for electronic toll collection. AVI reader systems rely on a combination of passive tags attached to vehicles and electronic readers installed on the roads (above lanes, or on roadsides). A vehicle is detected and identified every time it passes a reader. Upon detection of a vehicle, the system transmits the information to a data processing center where a measurement of the travel time between two consecutive readers can be computed. For example consider the network in Fig. 13.1. By locating two AVI readers, one on link (4, 7) and one on link (8, 9), all the vehicles that pass both locations are intercepted, and, by comparing the interception times, information on the travel time on the portion of the intercepted network can be determined. Obviously, one could be interested in determining travel times on links of the network, on particular routes in the network, or travel times between OD pairs in the network. Optimal location decisions depend on what travel times one wants to estimate.

Assume, for example, the network of Fig. 13.1 has the following OD pairs W = {(1, 3), (1, 9), (7, 11), (5, 13)}, each of them connected, in this simple example, by a single route (these are listed in Table 13.1). To get information about travel times between OD pair w = (1, 3) one needs to locate AVI reader at the upstream and downstream end-points of the route connecting w, that is one on link (1, 2) and the other on link (2, 3). Hence, to have information about travel times among all the OD pairs in the network, AVI readers should be located on links (1, 2), (2, 3), (7, 8), (8, 9), (10, 11), (5, 4) and (12, 13). This would provide knowledge of the travel times on the entire routes connecting all the OD pairs in the network. However, in case of multiple routes between OD pairs and also when there are budget limits to acquire sensors, such detailed knowledge is unlikely to be collected. In this case, one cannot get information about travel times on all entire routes but only on portions of some of them. For example, by locating readers on links (4, 7) and (8, 9), travel times on parts of routes two and four could be collected. Consider now the OD trips listed in Table 13.1. If the purpose of determining travel times is to disseminate such information among commuters, then the majority of users would not benefit from the reader located on links (4, 7) and (8, 9). It would be preferable to locate one of the readers on link (1, 2) and the other on (2, 3) to intercept as many commuters as possible for as long as possible.

Table 13.1 OD pairs, OD trips and OD routes related to the example network in Fig. 13.1

It is clear, then, that different factors should be considered when locating AVI readers. Some of them are:

• Number of AVI readers: this is a measure of the installation cost of the system .

• Number of readings: a reading is obtained when the same vehicle is intercepted at two different locations. This measure relates to the amount of travel time data that is obtained from the AVI system.

• Length between readings: a reading obtained by two readers that are far apart has more travel time information compared with readings obtained by two readers that are close to each other.

• Number of OD pairs covered: For an O-D pair to be covered, at least one reading should be obtained from one of the routes between the OD pair. This is useful for estimating OD flows, and estimating OD travel times when the network is in equilibrium (Sheffi 1984).

• Travel time reliability: If travel time along a link has little variance, then a real-time travel time reading on that link has little value; if variance is large, then real-time travel times are very useful. Hence, sensors can collect real-time information to estimate travel time reliability .

The models reviewed in the next section take into account some of these factors in developing the locational decision criteria and associated models. In particular, six different mathematical formulations are presented to optimally locate readers on the links of the network, which we refer to as AVI Location Problems or AVIL models.

4 Mathematical Models

We can represent a traffic network by a graph G $\,=\,$(V, A) where the set of nodes V represents intersections in the network and the set of links A, joining node pairs, represents roads. We denote by W the set of OD pairs of the network and by ${R}_{w}$ the set of routes connecting the OD pair w $\,\in \,$ W. The entire set of routes in the network is denoted by R and we have $R=\underset {w\in W}{\bigcup }{{{R}_{w}}}$. We denote by h $^{w}$ the average number of trips connecting the OD pair w for the period of study, and by ${f}_{r}$ the average flow volume on route r. Additional notation will be introduced as needed.

The first model (model AVIL $_{1}$), presented by Sherali et al. (2006), works under the assumption that there is a single route connecting each OD pair. This model associates different weights (benefit) to OD pairs and seeks to maximize the total benefit accrued by locating at most k readers, respecting a given budget constraint. An OD pair is considered to be covered if the readers are located on the route connecting the OD pair at the upstream and the downstream end-points of the route (particularly, at the beginning and ending links). In particular, let us consider the OD pair w $\,\in \,$ W and consider the shortest route ${r}_{\textit{ij}}$ connecting it, that starts with link i and ends with link j. Due to the simplifying assumption of having one route for each OD pair, we can use route ${r}_{\textit{ij}}$ to represent its corresponding OD pair. Route ${r}_{\textit{ij}}$ is defined to be covered if readers are located both on link i and on link j. When the route ${r}_{\textit{ij}}$ is covered, a benefit ${u}_{\textit{ij}}$ is obtained. Let ${c}_{j}$ be the cost of installing a reader on link j. Define ${z}_{j}$ to be a binary variable associated with link j $\,\in \,$ A that assumes a value of 1 if a reader is located on the link and 0 otherwise. The AVIL $_{1}$ model is the following:

$$ \begin{aligned} \textit{AVIL}_1:\; {\rm{ Max}}\mathop \sum \limits_{{r_{\textit{ij}}} \in R} {\rm{}}{u_{\textit{ij}}}{z_i}{z_j} \end{aligned} $$

(13.1)

$$ \begin{aligned} {\rm{s}}{\rm{.t}}{\rm{. }}\mathop \sum \limits_{j \in A} {\rm{}}{z_j} \le k \end{aligned} $$

(13.2)

$$ \begin{aligned} \mathop \sum \limits_{j \in A} {\rm{}}{c_j}{z_j} \le {C_{max}} \end{aligned} $$

(13.3)

$$ \begin{aligned} {{z}_{j}}\in \{0{,}1\}{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.4)

The objective function (13.1) maximizes the total benefit accrued by locating the readers. Constraint (13.2) limits the sensors to at most $k$ readers. Constraint (13.3) imposes the total budget to be at most${C}_{max}$. A possible definition of the benefit factor is also proposed by Sherali et al. (2006). They defined the benefit factor u _ij to describe the relevance of route ${r}_{\textit{ij}}$ (and hence, of its corresponding OD pair) in capturing information about the variability of travel times in the network. Such factors are computed according to the coefficient of variation associated with each link j, defined as follows:

$$ \begin{aligned} {{\textit{COV}}_{j}}=\frac{{{\sigma }_{j}}}{{{\upmu }_{j}}}, \end{aligned} $$

(13.5)

where $\upmu_{\!j}$ and $\upsigma_{j}$ are estimates of the mean and standard deviation of travel times on link $\textit{j}$, respectively. For each route ${r}_{\textit{ij}}$, the corresponding benefit factor ${u}_{\textit{ij}}$ is computed considering the coefficients of variation (13.5) associated with the links that belong to the route. In particular, the suggested benefit ${u}_{\textit{ij}}$ is computed as:

$$ \begin{aligned} {u_{ij}} = {{\textit{COV}}_{ij}} = \sqrt {\frac{{\mathop \sum \nolimits_{a \in {r_{ij}}} {\rm{}}\sigma_a^2}}{{\mathop \sum \nolimits_{a \in {r_{ij}}} {\rm{}}\upmu_a^2}}}. \end{aligned} $$

(13.6)

Sherali et al. (2006) linearized model AVIL ₁ and applied the Reformulation Linearization Technique (Adams and Sherali 1986, 1990) to solve it. They applied the model to data from Interstate-35 Freeway, San Antonio, Texas, USA.

The more realistic assumption of having multiple routes between each OD pair is considered in the other models AVIL $_{i}$, i $\,=\,$2, $\ldots$, 6. These models assume an OD pair to be covered if there are at least two readers located on each of the routes connecting the OD pair, without any restriction on where on the routes they are located. Model AVIL $_{2}$ to follow is basically a set covering formulation aimed at minimizing the total number of readers to be located on the network to ensure the coverage of all the OD pairs. Let ${z}_{j}$ be the number of sensors located on link j. Model AVIL $_{2}$ is as follows (Chen et al. 2004).

$$ \begin{aligned} {{\textit{AVIL}}_2}{\rm{:\; Min}} \mathop \sum \limits_{j \in A} {\rm{}}{z_j} \end{aligned} $$

(13.7)

$$ \begin{aligned} \text{s}\text{.t}\text{. }\sum_{j\in r}{{{z}_{j}}}\ge \text{2}\;{}\forall r\in {{R}_{w}}{}\;{}\forall {}{}w\in W \end{aligned} $$

(13.8)

$$ \begin{aligned} {{z}_{j}}\in \left\{0{,}1,2,\ldots\right\}{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.9)

The objective function (13.7) minimizes the total number of readers to be located on the network. Constraints (13.8) ensure that each OD pair is covered. Since the location variable ${z}_{j}$ associated with link j denotes the total number of readers that can be installed on the link, the total number of readers located on a link can be greater than 1. The maximum number of readers that can be installed on each link of the network can be determined by the spacing requirement between pairs of readers. Moreover, note the slightly different definition of coverage\index{Coverage!definition of} of an OD pair compared to the one used in model $\textit{AVIL}_{1}$: an OD pair w is considered to be covered when there are at least two readers installed on each route $\textit{r} \,\in\, {R}_{w}$ connecting the OD pair. Unlike model $\textit{AVIL}_{1}$ where for each route the only locations for readers that are considered are on the first and last link of the route, readers for model $\textit{AVIL}_{2}$ can be located anywhere on the route.

When the total number of readers is limited, a different objective function has been proposed. The following model, AVIL $_{3}$ (Chen 2004), is a variant of the well known maximal covering location problem (Church and ReVelle 1974 ) where, for a fixed number of available readers to be installed, the objective is to maximize the total number of covered OD pairs.

$$ \begin{aligned} {{\textit{AVIL}}_3}:\; {\rm{Max}} \mathop \sum \limits_{w \in W} {\rm{}}{y_w} \end{aligned} $$

(13.10)

$$ \begin{aligned} \text{s}\text{.t}\text{. }{{y}_{w}}\le max\left\{0,\sum_{j\in r}{{{z}_{j}}}-1 \right\}{}\;{}\forall {}\;{}r\in {{R}_{w}}{}\;{}\forall {}\;{}w\in W \end{aligned} $$

(13.11)

$$ \begin{aligned} \mathop \sum \limits_{j \in A} {\rm{}}{z_j} \le k \end{aligned} $$

(13.12)

$$ \begin{aligned} {{z}_{j}}\in \{0{,}1,2,\ldots \}{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.13)

$$ \begin{aligned} {{y}_{w}}\in \{0{,}1\}{}\forall {}w\in W \end{aligned} $$

(13.14)

Variables y _w , defined for each OD pair, assume value equal to 1 if the OD pair w is covered and 0 otherwise; and, therefore, objective (13.10) maximizes the total number of ODs covered. The coverage is ensured by the set of constraints (13.11) which force y _w to be equal to 0 unless there are at least two readers located on each route connecting w. The total number of installed readers is limited to k through constraint (13.12).

The main differences between model AVIL $_{2}$ and AVIL $_{3}$ with respect to the classical set covering problem and the maximal covering problem, respectively, are: (i) multiple location of readers on the same link is allowed, and (ii) the definition of OD pair coverage requires the installation of at least two devices on each covered route connecting the OD pair.

The following model AVIL $_{4}$ locates k readers on the links of a network to maximize the weighted sum of the total number of readings and of the total number of covered OD pairs (Teodorovic 2002):

$$ \begin{aligned} {{\textit{AVIL}}_4}{\rm{:\; Max}} \frac{{{h_1}}}{H}\sum\limits_{r \in R} {{f_r}\left( {\sum\limits_{j \in r} {{z_j}} - 1} \right)} + \frac{{{h_2}}}{{\left| W \right|}}\sum\limits_{w \in W} {{y_w}} {\rm{}} \end{aligned} $$

(13.15)

$$ \begin{aligned} \text{s}\text{.t}.\quad{{y}_{w}}\le \max{}\left\{0,\sum_{j\in r}{{{z}_{j}}}-1 \right\}{}\;{}\forall {}\;{}r\in {{R}_{w}},\; \forall {}\;{}w\in W \end{aligned} $$

(13.16)

$$ \begin{aligned} \mathop \sum \limits_{j \in A} {\rm{}}{z_j} \le k \end{aligned} $$

(13.17)

$$ \begin{aligned} {{z}_{j}}\in \{0{,}1,2,\ldots{}\}{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.18)

$$ \begin{aligned} {{y}_{w}}\in \{0{,}1\}{}\;{}\forall {}\;{}w\in W \end{aligned} $$

(13.19)

where (i) ${h}_{1}$, ${h}_{2}$, are the weights assigned to model the importance of the two components in the objective and (ii) H is the total number of trips in the network (i.e., $H = \mathop \sum \limits_{w \in W} {\rm{}}{h^w}$). The criterion (13.15) maximizes the weighted sum of two components in the objective: the first component is the ratio between the total number of readings obtained from the locations of the readers and the total trips in the network; and the second component of the objective function is the ratio between the total number of covered OD pairs and the total number of OD pairs in the network. When a weight ${u}_{w}$ is assigned to each OD pair w as a measure of importance, then the second component of the objective function could also be: $\frac{{{h_2}}}{{\sum\limits_{w \in W} {{u_w}} {\rm{}}}}\mathop \sum \limits_{w \in W} {\rm{}}{u_w}{y_w}$. The coverage of the OD pairs is considered by the set of constraints (13.16) which force ${y}_{w}$ to 0 unless there are at least two readers located on each route connecting w. Constraint (13.17) assumes that the total number of installed readers cannot be greater than k.

Distances among two located readers (that is, the length of a reading) is not considered in any of the above models. In AVIL $_{5}$ this measure is defined as the total vehicle-miles monitored. In AVIL $_{6}$ it is a general benefit factor. These two models are explained next.

Model AVIL $_{5}$ solves the problem of optimally locating k readers on the links of the network to maximize the number of vehicle-miles (or vehicle-travel times) monitored. For each link j $\,\in \,$ A and each route r $\,\in \,$ R the parameter $d_{j}^{r}$ denotes the distance from the origin of route r to a potential reader located on link j. The following sets of variables are defined for AVIL $_{5}$: the binary variable ${z}_{j}$ equals to 1 if a reader is located on link j and 0 otherwise; the binary variable ${y}_{\textit{rj}}$ equals to 1 if a reader on link j is the most downstream reader located on route r and 0 otherwise; the binary variable ${x}_{\textit{rj}}$ equals to 1 if a reader on link j is the most upstream reader located on route r and 0 otherwise. The mathematical formulation is the following (Mirchandani et al. 2009):

$$ \begin{aligned} {{\textit{AVIL}}_5}{\rm{:\; Max}} \mathop \sum \limits_{r \in R} {\rm{}}\mathop \sum \limits_{j \in r} {\rm{}}\left( {{y_{rj}} - {x_{rj}}} \right)d_j^r{f_r} \end{aligned} $$

(13.20)

$$ \begin{aligned} {\rm{s}}{\rm{.t}}.\;\mathop\sum \limits_{j \in A} {\rm{}}{z_j} \le k \end{aligned} $$

(13.21)

$$ \begin{aligned} {{y}_{rj}}\le {{z}_{j}}{}\;{}\forall {}\;{}r\in R{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.22)

$$ \begin{aligned} {{x}_{rj}}\le {{z}_{j}}{}\;{}\forall {}\;{}r\in R{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.23)

$$ \begin{aligned} \sum_{j\in r}{{{y}_{rj}}}\le 1{}\;{}\forall {}\;{}r\in R \end{aligned} $$

(13.24)

$$ \begin{aligned} \sum_{j\in r}{{{x}_{rj}}}\le 1{}\;{}\forall {}\;{}r\in R \end{aligned} $$

(13.25)

$$ \begin{aligned} \sum_{j\in r}{{{y}_{rj}}}-\sum_{j\in r}{{{x}_{rj}}}=0{}\;{}\forall {}\;{}r\in R \end{aligned} $$

(13.26)

$$ \begin{aligned} {{z}_{j}}\in \{0{,}1\}{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.27)

$$ \begin{aligned} {{y}_{rj}}\in \{0{,}1\}{}\;{}\forall {}\;{}r\in R{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.28)

$$ \begin{aligned} {{x}_{rj}}\in \{0{,}1\}{}\;{}\forall {}\;{}r\in R{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.29)

Objective function (13.20) maximizes the total vehicle-miles monitored. Note that this function takes into account both the length of each reading and the total number of readings. Constraint (13.21) requires locating no more than k readers on the network. Constraints (13.22) and (13.23) are logical constraints linking the variables and ensuring that there cannot be a most upstream (or a most downstream) reader on a route if no reader is located on it. Constraints (13.24) and (13.25) ensure that there is no more that one most upstream reader and no more than one most downstream reader on each route. Finally, constraint (13.26) states that if there is a most upstream reader on route r, there must also be a most downstream reader on the same route and vice versa. Similarly, if there is no most upstream reader on route r, then there cannot be a most downstream reader on the same route and vice versa. It is also true that if on a route there is only one reader installed, then it is both the most upstream and downstream reader on that route, and the vehicle miles monitored on that route is zero.

The objective function of AVIL $_{5}$ can be modified so that the model tries to locate AVI readers to obtain travel time statistics and improve predictability of estimated travel times. This model, referred to as $\it {AVIL}_{\text 5'}$, is illustrated in Sect. 5 where its application is discussed.

A generalized surveillance benefit (Li and Ouyang 2012) is maximized in model AVIL $_{6}$. Consider a route r, and, without loss of generality, let us assume every link of the route is a candidate location for a reader. If ${s}_{r}$ readers are located on the route, then we can divide the route into ${s}_{r}\,-\,$1 sections where each section has a reader on its upstream boundary link and its downstream boundary link. Without loss of generality, we also assume there are two virtual locations b and t for each route, located at the very beginning and at the very end of the route with two virtual readers located at positions 0 and ${s}_{r}\,+\,$1, respectively. Denote the portion of the route between link j and link h by ${r}_{\textit{jh}}$. We say that the portion ${r}_{\textit{jh}}$ is monitored if (i) a reader is located on link j and on link h, and (ii) there is no reader located in between (that is, the two readers on j and h are consecutive). If ${r}_{\textit{jh}}$ is a monitored portion, then the two links j and h are said to be paired on route r. More specifically, given a route r and ${s}_{r}$ readers located on it, the link of the route where the i-th reader is located is paired with the link where the (i $\,+\,$1)-st reader is located, and with the link where the (i–1)-st reader of the route is located. The virtual initial link b at position 0 is paired with link ${j}_{1}$ where the first real reader is located; the virtual last link t at position ${s}_{r}\,+\,$1 is paired with link ${j}_{{{s}_{r}}}$ where the last real reader, with position ${s}_{r}$, is located. Figure 13.2 depicts a route r with five links, that is j $\,=\,$1, 2, 3, 4, 5. Two virtual links b and t are added to the route, and two virtual readers are assumed to be located on them. Suppose ${s}_{r}\!=\,$3 readers are located on the route, on links one, three, and five. Then, the monitored portions of the route are: ${r}_{{b}{1}}$, ${r}_{13}$, ${r}_{35}$, and ${r}_{ 5 {t}}$. The virtual link b is paired with link one which is also paired with link three, which in turn is paired with link five, and so on.

Fig. 13.2

Monitored portions of a route and corresponding benefit factors

Finally, if the i-th reader of the route is located on link j and the (i $\,+\,$1)-st reader on the route is located on link h, then we denote by $\varepsilon _{jh}^{r}=\varepsilon _{{{j}_{i}}{{j}_{i+1}}}^{r}$ the benefit associated with the monitored section ${r}_{\textit{jh}}$ (see example in Fig. 13.2). The total benefit accrued with the given locations of the readers is then:

$$ \begin{aligned} \varepsilon = \mathop \sum \limits_{r \in R} {\rm{}}\mathop \sum \limits_{i = 0}^{{s_r}} {\rm{}}\varepsilon_{{j_i}{j_{i + 1}}}^r \end{aligned} $$

(13.30)

To introduce model $\textit{AVIL}_{6}$, which seeks to locate a limited number of readers to maximize (13.30), some additional notation is needed. Given a route r and a link $\textit{j} \,\in\, \textit{r}$, the set $F_{j+}^{r}$ is the set of links of the route after link j where a reader can be located, while the set $F_{j-}^{r}$ is the set of links of the route before link j where a reader can be located. The set $F_{jh}^{r}$ is the set of links of route r between link j and link h where a reader can be located. Hence, for example, if we consider the route in Fig.13.2, the set $F_{1+}^{r}=\left\{2{,}3,4{,}5,t \right\}$, the set $F_{1-}^{r}=\{b\}$ and the set $F_{25}^{r}=\{3{,}4\}$. Finally, let us define the binary variable $y_{jh}^{r}$ to be equal to 1 if the portion of route r between two readers located on link j and link h is monitored and 0 otherwise. The mathematical formulation for $\textit{AVIL}_{6}$ is as follows (Li and Ouyang 2012):

$$ \begin{aligned} {{\textit{AVIL}}_{\rm{6}}}:\;{\rm{Max}} \mathop \sum \limits_{r \in R} {\rm{}}\mathop \sum \limits_{j \in F_{t - }^r} {\rm{}}\mathop \sum \limits_{h \in F_{j + }^r} {\rm{}}y_{jh}^r\varepsilon_{jh}^r \end{aligned} $$

(13.31)

$$ \begin{aligned} {\rm{s}}{\rm{.t}}.\;\mathop \sum \limits_{j \in A} {\rm{}}{z_j} \le k \end{aligned} $$

(13.32)

$$ \begin{aligned} \mathop \sum \limits_{h \in F_{j + }^r} {\rm{}}y_{jh}^r = {z_j}{\rm{}}\quad\forall {\rm{}}\, j \ne t \in r{\rm{}}\quad \forall {\rm{}}\,r \in R \end{aligned} $$

(13.33)

$$ \begin{aligned} \mathop \sum \limits_{j \in F_{{h^ - }}^r} {\rm{}}y_{jh}^r = {z_h}{\rm{}}\quad \forall {\rm{}}\, h \ne b \in r{\rm{}} \quad\forall {\rm{}}\, r \in R \end{aligned} $$

(13.34)

$$ \begin{aligned} {{z}_{b}}={{z}_{t}}=1 \end{aligned} $$

(13.35)

$$ \begin{aligned} {{z}_{j}}\in \{0{,}1\}{}\;{}\forall {}\;{}j\in A \end{aligned} $$

(13.36)

$$ \begin{aligned} y_{jh}^{r}\in \{0{,}1\}{}\;{}\forall {}\;{}h,\;j\in r{}\;{}\forall {}\;{}r\in R \end{aligned} $$

(13.37)

Constraint (13.32) imposes that the total number of readers to be installed be less than or equal to k. Constraints (13.33) pair link j of route r where a reader is located (that is, when ${z}_{j}\!=\,$ 1), with only one link h in the route that follows j. Constraints (13.34) pair link h of route r where a reader is located (that is, when ${z}_{h}\!=\,$ 1), with only one link j in the route that precedes h. Finally, the objective function (13.31) maximizes the total benefit accrued by the location as defined by (13.30). For possible examples of how benefit factors $\varepsilon_{jh}^{r}$ can be defined, the reader can refer to Li and Ouyang (2012)).

Models AVIL $_{i}$, i $\,=\,$1, 2, $\ldots$, 6 were introduced and developed in the last few pages to indicate how these models have been evolving, introducing more and more constraints and objectives. The first model (model AVIL $_{1}$) assumes that there is a single route connecting each OD pair, which happens only in special sparse networks, for example in rural areas. Model AVIL $_{2}$ (which minimizes the total number of readers to be located on the network to ensure that all OD routes are observed) and model AVIL $_{3}$ (which maximizes the total number of OD routes observed with a limited numbers of available readers), should be applicable in the cases when the observation effort does not increase as the volume of traffic on the network changes, and hence applicability is limited. On the other hand, when the traffic manager or the transportation planner wants to monitor all the traffic on the network or to maximize the amount of traffic monitored, then model AVIL $_{4}$ is more appropriate.

Distances among two located readers is not considered in any of the Models AVIL $_{i}$, i $\,=\,$1, $\ldots$, 4. In AVIL $_{5}$ this measure is defined as the total vehicle-miles monitored. This is generalized in AVIL $_{6}$ where a general benefit factor is considered for an OD route monitored, which could be some function of travel distance, travel time, or some other measure of benefit to the planner or manager. The application described next focuses on the travel time reliability of the OD routes monitored, where here “reliability” essentially means how well the travel time can be predicted. If there is no variance in travel time, then it is highly predictable, whereas when the travel time has large variance its predictability is low. Installing sensors in the latter case will help the traffic manager predict travel times better as real-time measurements are made.

Fig. 13.3

Study area of Harris County, TX

5 Applications

In this section we discuss two applications of model AVIL $_{5}$ to a portion of the Harris County (Texas) network (see Fig. 13.3). One of the authors was working with the County on a traffic management research project, and as a by-product they were interested in if they could use toll tag readers to monitor traffic in a certain area. Consequently, we developed two different models for (i) the problem of optimally locating the toll tag readers (these are effectively AVI readers) on the arcs of the network to maximize the number of vehicle-miles (or vehicle-travel times) monitored (model AVIL $_{5}$ presented in the previous section) and (ii) the problem of optimally locating AVI readers on the arcs of the network to maximize the ability to predict travel times on the network. The motivation underlying the first problem is for traffic managers to have an idea of the traffic volume in the region at any given time. The motivation underlying the second problem is to monitor travel times and communicate to commuters some predictions of the mean travel times of their routes. In this case, the underlying model is assumed to be stochastic. That is, each arc (or route segment) will have a mean travel time that changes slowly over time during the day, while the actual travel time has a further fluctuation which is due to differences in driving characteristics of the commuters; this latter fluctuation may be treated as some sort of additive noise. In particular, let $\uptau _{j}$ denote the travel time on link j. $\uptau _{j}$ is therefore a random variable with mean $\upmu _{j}$ and variance $\sigma _{j}^{2}$. This variance $\sigma _{j}^{2}$ is assumed to be constant over time and known for all links in the network. It is also assumed that for any time period, the a priori distribution of $\upmu _{j}$ is known, which is Normal with mean $\upeta _{j}$ and variance $\upgamma _{j}$. Therefore, the variance of travel time on link j has two components, that is, $var({{\tau }_{j}})=\sigma _{j}^{2}+{{\upgamma }_{j}}$. For the short period of time when travel time data is collected, the expected travel time on link j is $\upeta _{j}$. Knowing the values of $\upeta _{j}$ and var ($\uptau _{j}$), a confidence interval for $\uptau _{j}$ can be obtained. If n observations of, the average value of the observed travel times (denoted ${\bar {\tau }}_{j}$) are collected, then according to the Central Limit Theorem ${\bar {\tau }}_{j}$ can be approximated by a normal distribution with mean $\upmu _{\!j}$ and variance $\tfrac {1}{n}\sigma _{j}^{2}$. With an observation of ${\bar {\tau }}_{j}$, the a priori distribution of $\upmu _{j}$ can be updated by using Bayesian statistical theory. The updating can be performed using the following formulas:

$$ \begin{aligned} {{\hat{\upeta }}_{j}}=\frac{\tfrac{1}{n}{{\upeta }_{j}}\sigma_{j}^{2}+{{{\bar{\tau }}}_{j}}{{\upgamma }_{j}}}{\tfrac{1}{n}\sigma_{j}^{2}+{{\upgamma }_{j}}} \end{aligned} $$

(13.38)

$$ \begin{aligned} {{\hat{\upgamma }}_{j}}=\frac{\tfrac{1}{n}{{\upgamma }_{j}}\sigma_{j}^{2}}{\tfrac{1}{n}\sigma_{j}^{2}+{{\upgamma }_{j}}} \end{aligned} $$

(13.39)

Therefore, the expected value of $\uptau _{j}$ is ${\hat {\upeta }}_{j}$ and $var({{\tau }_{j}})=\sigma _{j}^{2}+{{\hat {\upgamma }}_{j}}$. Note that the variance of $\upmu _{j}$ is reduced after the updating:

$$ \begin{aligned} {}\Delta{}{{\upgamma }_{j}}={{\upgamma }_{j}}-{{\hat{\upgamma }}_{j}}=\frac{\upgamma_{j}^{2}}{\tfrac{1}{n}\sigma_{j}^{2}+{{\upgamma }_{j}}} \end{aligned} $$

(13.40)

Equation (13.40) shows that the larger the sample size (n) of $\uptau_{j}$, the more the variance is reduced and, hence, the more reliable the travel time estimate. The above analysis can be extended to an entire route r (or a portion of it) under the assumption of independence among the travel times on different links of the same route. Consider the portion ${r}_{\textit{jh}}$ of route r between link j and link h and assume AVI readers are located both on link j and link h. The route travel time ${{\tau }_{{{r}_{jh}}}}$ on such a portion is then a random variable with mean ${\upmu_{{r_{jh}}}} = \mathop \sum \limits_{i \in {r_{jh}}} {\rm{}}{\upmu_i}$ and variance $var({\tau_{{r_{jh}}}}) = \mathop \sum \limits_{i \in {r_{jh}}} {\rm{}}\sigma_i^2 + \mathop \sum \limits_{i \in {r_{jh}}} {\rm{}}{\upgamma_i}$. The updating on the distribution of ${{\upmu }_{{{r}_{jh}}}}$ would lead to the computation of the reduction of variance:

$$ \begin{aligned} {}\Delta{}{{\upgamma }_{{{r}_{jh}}}}={{\upgamma }_{{{r}_{jh}}}}-{{\hat{\upgamma }}_{{{r}_{jh}}}} \end{aligned} $$

(13.41)

where ${{\upgamma }_{{{r}_{jh}}}}$ and ${{\hat{\upgamma }}_{{{r}_{jh}}}}$ are the a priori and the a posteriori variances of the ${{\upmu }_{{{r}_{jh}}}}$.

Model AVIL $_{5}$ can be applied to solve the problem of locating a given number k of AVI readers on the links of a network to maximize the reliability of travel time estimates. The resulting model formulation, AVIL $_{\rm 5'}$, is:

$$ \begin{aligned} {{\textit{AVIL}}_{5\prime }}{\rm{: \;Max}}\; {\textstyle{1 \over 2}}\mathop \sum \limits_{r \in R} {\rm{}}\mathop \sum \limits_{i \in r} {\rm{}}\mathop \sum \limits_{j \in r} {\rm{}}{y_{ri}} + {z_{rj}}{\rm{\Delta }}{\upgamma_{{r_{ij}}}} \end{aligned} $$

(13.42)

s.t. (13.21) – (13.29).

5.1 The Study Area

The study area is bounded by Barker Cypress Road, Interstate 10, US 290, and Sam Houston Tollway (represented by the shaded area in Fig. 13.3) in Texas, USA, with 470 total arcs and 230 total nodes. The total number of OD pairs is 930, which amounts to a total of 1700 routes, 12,075 miles, 90,020 vehicles and 459,234 vehicle-miles. There are already a number of AVI readers installed on the traffic network. Figure 13.4 shows the approximate location and direction of those devices. It can be seen that most existing vehicle identification devices are located on freeways and highways such as Interstate 10, US 290, and Sam Houston Tollway.

Fig. 13.4

Existing AVI Readers in the study area of Harris County, TX

5.2 Results

Figures 13.6, 13.7, and 13.8 give the optimal locations for 5, 10 and 15 additional AVI readers, respectively, obtained when solving AVIL $_{5}$ to maximize the total vehicle-miles monitored (that is, the objective function (13.20)) by using CPLEX 7.0. Performance results for installing different numbers of additional AVI readers are given in Table 13.2 where: (a) the first column reports the total number of additional AVI readers installed; (b) the second and third columns report the vehicle-miles monitored and the percentage with respect to the total, respectively; (c) the fourth and fifth columns report the total monitored flow and the percentage with respect to the total, respectively; (d) and the two last columns show the route length monitored and the percentage with respect to the total, respectively.

Table 13.2 Performance of AVI reader location strategies in the study area of Harris County, when maximizing total vehicle-miles

We can observe (refer to Table 13.2) that the performance of the existing readers is such that only 39.6 % of the total vehicle mileage, 55.9 % of the total flow and 18.5 % of the total route length is monitored. By locating additional AVI readers, these percentages, obviously, increase. However, we can notice that the marginal increase in the total vehicle-miles monitored decreases with additional readers installed. Indeed, the first five additional readers produce an increase of 23.8 % points; by adding five additional readers the increase is 12.6 % points and, with 5 more additional readers, the increase is equal to 6.9 % points.

Figure 13.5 shows the total benefit of the new sensors installed, from 5 to 15 sensors. Note the decreasing slope of the %total vehicle mileage function.

Fig. 13.5

Total benefit of the new sensors installed, from 5 to 15 sensors

Fig. 13.6

Optimal location of 5 additional AVI readers in the study area of Harris County, when maximizing total vehicle-miles

Fig. 13.7

Optimal location of 10 additional AVI readers in the study area of Harris County, when maximizing total vehicle-miles

Fig. 13.8

Optimal location of 15 additional AVI readers in the study area of Harris County, when maximizing total vehicle-miles

Figures 13.9, 13.10, and 13.11 give the optimal locations for 5, 10 and 15 additional AVI readers, respectively, obtained when solving AVIL $_{\rm 5'}$ to maximize the reliability of travel time estimates (that is, the objective function (13.42)), again using CPLEX 7.0. We assumed that the travel time variance is proportional to travel time on that link. That is, longer travel times have larger variances. The total variance of the mean route travel times in the study area is 12,579. The traffic monitoring results of installing different numbers of AVI readers are summarized in Table 13.3 where the first column reports the total number of additional AVI readers installed, the second column reports the total reduction in variance, and the last column reports the percentage of the reduction with respect to the total variance. With the existing AVI readers located, the total variance reduction is 3361, which is 26.72 % of the total variance. By installing additional AVI readers, the reduction of the variance increases to 7578.79 with 5 additional readers, to 8997.69 with ten additional readers and to 9908.40 with 15 additional readers. Note again that the marginal decrease in the total variance decreases with additional readers installed. Indeed, the first five additional readers produce a decrement of 33.53 % points; by adding 5 additional readers the decrement is 11.28 % points and, with 5 more additional readers, the decrement is equal to 7.24 % points.

Fig. 13.9

Optimal location of 5 additional AVI readers in the study area of Harris County, when maximizing travel time reliability

Fig. 13.10

Optimal location of 10 additional AVI readers in the study area of Harris County, when maximizing travel time reliability

Fig. 13.11

Optimal location of 15 additional AVI readers in the study area of Harris County, when maximizing travel time reliability

Table 13.3 Travel time reliability results of AVI reader location strategies in the study area of Harris County

6 Conclusions

Although much has been written about sensor location problems, this chapter is the first comprehensive summary of the use of vehicle identification sensors to monitor OD route coverage, travel times and related information on traffic networks. In particular, application of such models was demonstrated for (a) maximizing the vehicles-miles monitored and (b) maximizing the predictability of travel time estimates where the resulting variance reduction is especially useful for routes that are well traveled and a priori travel time variances are high.

Further uses of such sensors and attendant models by planners and traffic managers for the applications discussed, as well as future applications that one has yet to discover, attest to the value of this research and these models.