Heterogeneous sensor location model for path reconstruction

Highlights

• A new traffic sensor location problem is developed and solved by strategically placing both passive and active sensors in a transportation network for path reconstruction.

• A scalar product operator is introduced to calculate path flows within algebraic framework.

• An extension matrix is generated and used to determine if a replacement scheme is able to reconstruct all path flows.

• Maximum clique theory is used to determine the upper bound of feasible replacement scheme.

• A polynomial-time algorithm is proposed to solve this problem.

Abstract

A new traffic sensor location problem is developed and solved by strategically placing both passive and active sensors in a transportation network for path reconstruction. Passive sensors simply count vehicles, while active sensors can recognize vehicle plates but are more expensive. We developed a two-stage heterogeneous sensor location model to determine the most cost-effective strategies for sensor deployment. The first stage of the model adopts the path reconstruction model defined by Castillo et al. (2008b) to determine the optimal locations of active sensors in the network. In the second stage, an algebraic framework is developed to strategically replace active sensors so that the total installation cost can be reduced while maintaining path flow observation quality. Within the algebraic framework, a scalar product operator is introduced to calculate path flows. An extension matrix is generated and used to determine if a replacement scheme is able to reconstruct all path flows. A graph model is then constructed to determine feasible replacement schemes. The problem of finding the optimal replacement scheme is addressed by utilizing the theory of maximum clique to obtain the upper bound of the number of replaced sensors and then revising this upper bound to generate the optimal replacement scheme. A polynomial-time algorithm is proposed to solve the maximum clique problem, and the optimal replacement scheme can be obtained accordingly. Three numerical experiments show that our proposed two-stage method can reduce the total costs of transportation surveillance systems without affecting the system monitor quality. The locations of the active sensors play a more critical role than the locations of the passive sensors in the number of reconstructed paths.

Introduction

To effectively mitigate transportation congestion, effective transportation surveillance systems have to be in place to facilitate transportation stakeholders to develop control and guidance tools. There is a range of different traffic sensors or detectors for monitoring the transportation network. The most popular and cheapest monitoring devices, perhaps, are loop detectors, which can provide data on speed, traffic flow and occupancy. In addition, the automatic vehicle identification (AVI) technology, though more expensive, can be adopted. It is able to read vehicle plates, and thus provides travel time and flow volume information for a specific path. In general, these traffic monitoring devices are used for extracting critical information regarding Origin-Destination demand, link flows, path flows and travel time. In particular, traffic sensors are used for OD demand observation, OD demand estimation, path reconstruction, link flow inference and travel time estimation.

Gentili and Mirchandani (2012) summarized the basic sensor location models and outlined future challenges. Recently, Castillo et al. (2015) performed a state-of-the-art review of mathematical programming frameworks for flow observability, estimation and prediction problems in transportation networks from different aspects including data, variables, constraints, objective functions and examples. In what follows, we explain the state-of-the-art literature review.

• Traffic sensors have long been used for estimating OD demand through optimally positioned traffic sensors. Yang and Zhou (1998) proposed four basic sensor location rules for OD estimation, the essence of which was to cover as much traffic flow as possible on different OD pairs. All path flow between each OD pair is required to be intercepted (Yang et al., 2006). Using these coverage rules, a mobile traffic sensor was introduced to monitor the transportation network. A vehicle routing model was proposed to model the routing behavior of the mobile sensor (Zhu et al., 2014). Furthermore, the effectiveness of the OD estimation was discussed. The OD estimation error can always be bounded for the sensor location model (Bianco et al., 2001). Hu and Liou (2014) utilized both passive and active sensors to estimate the OD demand. The existing detection and information content of the prior OD matrix was considered (Ehlert et al., 2006). The actual values of the input data parameters were considered for OD demand estimation (Yang and Fan, 2015). In addition to the OD observation or estimation-related sensor location studies, OD flow uncertainty is inevitable and was considered in estimating the OD demand matrix (Fei et al., 2007). There exists a tradeoff between the OD coverage and uncertainty reduction (Fei and Mahmassani, 2011). The recognition of uncertainty also triggered the development of new sensor location model to minimize the OD variation (Zhou and List, 2010, Simonelli et al., 2012, Fei et al., 2013). Sensor failure was also considered for the purpose of both travel time and OD trip estimation (Li and Ouyang, 2011). In addition to aforementioned mathematical programming models, algebraic methods have also been adopted for the sensor location problems. For example, Castillo and Conejo (2008) proposed an algebraic method to calculate all OD-pair and link flows in terms of observed links.

• The applications of sensor location models on link flow inference mainly focus on partial or full link flow observation. For full link flow observation problems, Hu et al. (2009) proposed a link flow inference method that uses a link-path incidence matrix. The node-link incidence matrix was adopted to determine the optimal traffic sensor locations without path enumeration. The nature of using node-link matrix is flow conservation law at the nodes (Ng, 2012, Ng, 2013). Due to the computational complexity of algebraic methods, spanning tree method was developed to optimally place traffic sensors without path information (He, 2013). This method was previously used in topological observability analysis in other applications, such as power systems (Mori and Tsuzuki, 1991), water networks (Rahal, 1995, Gupta and Prasad, 2000, Kumar et al., 2008), logistic chain networks (Syarif et.al, 2002) and communication networks (Sang-Moon et.al, 2005). Castillo et al. (2013) focused on the upper bound of the number of passive sensors to determine all link flows with the partial link-path matrix consisting of only the set of linearly independent path vectors. More recently, a new concept of non-planar, hole-generated networks was introduced in the link-flow observability problem (Castillo et al., 2014). Other contributions to this problem came from Liu et al. (2014) who incorporated the flow correlation between links and Viti et al. (2014) who offered a new metric to assess partial observability. In most of the above studies, loop detectors were used to infer link flow volume and linear algebra-related methods were adopted.

• Travel time estimation is another important application of traffic sensors. In particular, AVI sensors or other similar sensor technologies, such as Bluetooth, are popular because they can record the lapsed time of a vehicle passing two consecutive AVI sensors. As a result, AVIs can be used to observe and estimate the travel time for the entire traffic network via strategic network placement. This challenge has been a focused research endeavor. For example, Viti et al. (2008) presented an optimization model to place sensors for reliable travel time estimation and prediction at complex road networks by minimizing the estimation error in link states. The link flow and travel time correlations between links were considered. A bi-objective optimization was used to simultaneously maximize the total vehicle-miles and minimize the variance of predicted travel times (Mirchandani et al., 2009). Xing et al., (2013) developed an information-theoretic framework to minimize travel time uncertainty. More recently, a stochastic programming model was developed to address uncertainty of traffic conditions by using both traditional point sensors and point-to-point sensors (Park and Haghani, 2015).

• Compared to applications for OD demand observation, OD estimation, and link inference, there is limited research effort focusing on path reconstruction. An early study by Gentili and Mirchandani (2005) presented a bi-objective optimization model to minimize the number of AVI sensors to infer all path flows while maximizing the number of specified paths. However, this study was based on the assumption that path information could be obtained whenever vehicles pass through AVI sensors, which is unrealistic. Recent studies relaxed this assumption and reconstructed paths based on known path flow (Castillo et al., 2008b, Mínguez et al., 2010). Furthermore, the method was extended to consider the effects of path-differentiated congestion pricing (Zangui et al. 2015). Cerrone et al., (2015) incorporated the effect of Vehicle-ID sensor order into a new sensor location model. In summary, most path reconstruction-oriented sensor location problems rely on the use of AVI sensors, which could be costly for large-scale network applications. To the best of our knowledge, only one study considered the heterogeneous sensor location problem for path reconstruction (Castillo et al., 2012) in which genetic algorithm was used to obtain the near-optimal solutions.

Path reconstruction using traffic sensors is crucial from both the perspectives of theory and practice. Theoretically, both OD demand and link flows can be readily obtained from path flows. In practice, transportation agencies can use path reconstruction to estimate path flows, which have been traditionally difficult to obtain. For example, administrators of a toll freeway network may use path information to understand the behaviors of traveler and manage the fairly. AVI sensors have been widely considered in most path reconstruction studies, as they can read license plates and count vehicles. However, an AVI sensor (e.g., a video image processor) has a much higher price tag ($5000 to $26,000) compared to that of a loop detector ($500 to $800) (Mimbela and Klein, 2000). This noticeable cost difference motivates us to develop a new method using both passive sensors (e.g., loop detectors) and active sensors (e.g., AVI sensors) to achieve the same quality of path reconstruction at a significantly reduced cost.

In this study, we develop a two-stage model to locate heterogeneous sensors for path reconstruction. The first-stage is based on the path reconstruction model (see model in Section 4 by Castillo et al, 2008), by which the minimum number of AVI sensors with optimal locations are determined. The path reconstruction model is referred to as the OBSV model throughout the rest of our paper (Zangui et al. 2015). In the second stage, we develop a new algebraic method to strategically replace some of AVI sensors with cheaper, passive sensors (e.g., loop detectors) without sacrificing the path reconstruction quality. We justify the proposed two-stage method through extensive numerical experiments based on three transportation networks. The results show that transportation monitor system cost can be significantly reduced while maintaining path reconstruction quality. The results also indicate that the active sensor locations are more important than that of passive sensor locations.

The major contributions of this study are as follows. First, heterogeneous sensor types are considered simultaneously for path reconstruction. Second, a new two-stage model is developed, which extends the traditional method only based on mathematical programming method to a combined method of both mathematical programming and the use of the algebraic method. Third, the scalar product operator is introduced in the algebraic framework to infer path flows. The extension matrix is designed to determine if a replacement scheme is feasible. Clique graph theory is employed to find optimal sensor replacement schemes. A polynomial-time exact algorithm is proposed and successfully justified in a set of numerical experiments. Other minor contributions are that matrix rank determination method and clique graph theory are slightly revised to fit our two-stage model.

The remainder of the paper is organized as follows. Section 2 presents the two-stage model and the exact algorithm. Section 3 provides numerical experiments to illustrate the use of the model for obtaining optimal sets of heterogeneous sensors. The study is concluded in Section 4 with outlined future research directions.