A stochastic program approach for path reconstruction oriented sensor location model

Path flow identification is of particular interest for a number of traffic applications, such as OD demand estimation, link flow inference, and toll freeway revenue management. Optimal positioning of active sensors can help to identify path flows. Due to the stochastic nature of transportation systems, we propose a scenario based two stage stochastic programming framework which considers the uncertainty of the link-path matrix. The first stage model aims to minimize the total traffic sensor installation cost and the expected penalty for uncovered and undifferentiated paths. The second stage model attempts to minimize uncovered and undifferentiated paths for a given sensor location pattern and a specific scenario. In addition, a mean risk measure is also incorporated into the two stage stochastic programming framework, and consequently a mean risk two stage stochastic programming model is proposed. Both models have the same structure, where the first stage and second stage decision variables are binary. The second stage decision variable can be relaxed to a continuous variable without changing the nature of the model. To solve the two stochastic programming models, a branch and bound based integer L-shaped algorithm is presented. Finite steps convergence is guaranteed for the algorithm. To handle the problem with a large number of scenarios, a sampling technique is introduced, and the confidence bound is analyzed with respect to the scenario size. Extensive numerical experiments are conducted to verify the effectiveness of the proposed models and algorithm. The most important numerical results are as follows: (i) the stochastic programming framework is capable of capturing the reality more efficiently and accurately, (ii) the path differentiation factor is more critical than the path coverage factor in determining the sensor placement pattern, and (iii) in the partial parameter setting case, the mean risk based stochastic programming model results in a significantly different sensor placement pattern compared to the normal stochastic programming model. The study contributes to practical sensor placement design. (C) 2017 Elsevier Ltd. All rights reserved.