Estimating an individual's environmental exposure is a complicated problem that depends on the amount of time of the individual's exposure, the uncertain location of the individual, and the uncertainty in the levels of environmental factors based on available localized measurements. This problem is critical in the applications of environmental science and public health. In this paper we study the fundamental issues related to spatio-temporal uncertainty of human trajectories and environmental measurements and define a model of exposure uncertainty. We adopt a geometric data structure called the Voronoi diagram to interpolate environmental data, and utilize it in our proposed method to efficiently solve this problem. We evaluate the performance of the proposed method through experiments on both synthetic and real road networks. The experimental results show that our solution based on probabilistic routing aggregation is an efficient and extensible method for environmental exposure time estimation.