Uncertainty is one of the major factors that transportation system analysts and planners have to deal with when making transportation planning decisions. Finding the set of optimal sensor locations under uncertainty is a network design problem. This paper presents a nonlinear two-stage stochastic model. The first stage provides a sensor location plan to maximize the origin-destination (OD) flow coverage and link information gains, subject to a budgetary limitation, before considering any random events, while the recourse function associated with the second stage calculates the expected cost of vehicular flow changes, after random events occur. This novel two-stage stochastic bi-objective model simultaneously maximizes a weighted combination of link information gains and OD flow coverage to locate network passive point sensors. An iterative heuristic solution algorithm, hybrid Greedy Randomized Adaptive Search Procedure (HGRASP), is developed to find the near-optimal locations for this problem. The proposed methodology is tested on the Coordinated Highways Action Response Team network (Washington DC-Baltimore, Maryland corridor), in a mesoscopic traffic simulator. The results confirm the expectations that, under stochastic conditions, the sensor location plans obtained under the assumption of stochastic conditions result in better performance than plans developed for deterministic (normal) conditions. Also as expected, a greater number of optimally deployed sensors reduces demand uncertainty for both normal and incident conditions. © 2013 Elsevier Ltd.