ارزش عدم قطعیت در برنامه ریزی مدیریت زیرساخت آسفالت : یک روش برنامه ریزی عدد صحیح

Currently there is a true dichotomy in the pavement maintenance and rehabilitation (M&R) literature. On the one hand, there are integer programming-based models that assume that parameters are deterministically known. On the other extreme, there are stochastic models, with the most popular class being based on the theory of Markov decision processes that are able to account for various sources of uncertainties observed in the real-world. In this paper, we present an integer programming-based alternative to account for these uncertainties. A critical feature of the proposed models is that they provide – a priori – probabilistic guarantees that the prescribed M&R decisions would result in pavement condition scores that are above their critical service levels, using minimal assumptions regarding the sources of uncertainty. By construction of the models, we can easily determine the additional budget requirements when additional sources of uncertainty are considered, starting from a fully deterministic model. We have coined this additional budget requirement the price of uncertainty to distinguish from previous related work where additional budget requirements were studied due to parameter uncertainties in stochastic models. A numerical case study presents valuable insights into the price of uncertainty and shows that it can be large.

An efficient maintenance and rehabilitation (M&R) policy for pavement infrastructure is critical for a safe and cost-effective transportation system. Researchers have developed numerous decision support systems to obtain optimal M&R policies. One popular class of models makes the assumption of determinism: Pavement deterioration and improvements in pavement conditions are known with complete certainty (e.g. Fwa et al., 1988, Fwa et al., 1996, Wang et al., 2003 and Ng et al., 2009). The resulting models are typically based on integer programming, with high computational requirements (although recent advances have reported increasingly larger problem instances that can be solved, e.g. see Dahl and Minken, 2008 and Yoo and Garcia-Diaz, 2008). Clearly, the assumption of determinism is questionable in practice since pavement behavior depends on factors that are not completely known, such as environmental conditions, traffic loading and the structural properties of the pavement. Consequently, deterministic models cannot guarantee, in any sense, that pavement sections be maintained above their critical service levels, although most mathematical programming-based models have constraints that aim to “ensure” that the resulting pavement conditions are above a minimum level. Moreover, integer programming-based M&R models yield open-loop (i.e. non-condition-based) policies that are generally – from a managerial perspective – less desirable than condition-based, feedback policies common in stochastic models. For this reason, integer programming-based models are typically used on a rolling-horizon basis. In order to incorporate stochasticity in the determination of optimal M&R policies, researchers have devised alternative models. The most popular class of models that explicitly accounts for the stochastic nature of the M&R problem is based on the theory of Markov Decision Processes (MDP). Unlike integer programming-based models, MDP models yield condition-based policies that are more attractive from a managerial perspective. Golabi et al. (1982) was the first to introduce the MDP approach to the pavement management problem. They determined a long-term M&R policy that was guaranteed to be optimal when the planning horizon is infinitely long. A short-term model was proposed to ensure that the steady-state condition is reached after a finite number of years. The same philosophy was adopted by Mbwana and Turnquist (1996). However, unlike Golabi et al. (1982), their model explicitly determined the optimal M&R action for each pavement section, whereas the output of the majority of MDP-based models only specifies the fraction of pavement sections in a particular state to which a certain M&R action is to be applied. The reason for this simplifying assumption is because of the well-known curse of dimensionality that makes the solution of large-scale MDP problems challenging, e.g. see Bertsekas (2001). Numerous other variations of the MDP-based pavement management problem have been proposed (e.g. Carnahan et al., 1987, Guignier and Madanat, 1999, Smilowitz and Madanat, 2000, Ferreira et al., 2002, Guillaumot et al., 2003 and Boyles et al., 2010). The specification of the transition probabilities in MDP models is typically a result of statistical estimation ( Madanat and Wan Ibrahim, 1995 and Mishalani and Madanat, 2002). However, when there is a lack of historical data, the use of statistical procedures might not be feasible ( Smilowitz and Madanat, 2000). Recently, Chu and Durango-Cohen, 2007 and Chu and Durango-Cohen, 2008 presented an alternative to Markov transition probabilities with the use of state-space specifications of time series models to estimate infrastructure performance. Using this new approach, Durango-Cohen and co-workers have developed another class of infrastructure M&R models using continuous state and decision variables, thereby overcoming the computational and statistical limitations of the MDP models ( Durango-Cohen and Tadepalli, 2006, Durango-Cohen, 2007, Durango-Cohen and Sarutipand, 2007 and Durango-Cohen and Sarutipand, 2009). Besides the use of determinism and stochasticity to classify the current infrastructure management literature, another possible criterion is whether one is examining a single facility versus an entire network. In terms of this alternative criterion, the current work focuses on the facility level budgeting problem (following Carnahan et al., 1987, Madanat, 1993a, Madanat, 1993b, Madanat and Ben-Akiva, 1994, Guillaumot et al., 2003 and Boyles et al., 2010). The network level budget requirements can simply be obtained by solving the proposed budgeting problem for each facility in the system, as we shall demonstrate in Section 4. The related problem of network level budget allocation will be examined in future work (e.g. see Golabi et al., 1982, Fwa et al., 1988, Fwa et al., 1996, Mbwana and Turnquist, 1996, Guignier and Madanat, 1999, Smilowitz and Madanat, 2000, Ferreira et al., 2002, Wang et al., 2003, Gao and Zhang, 2008 and Ng et al., 2009). From the above, it is clear that the predominant assumption in the current (stochastic) pavement management literature is that pavement conditions can be described by some discrete-time Markov chain, with known transition probabilities. To the best of our knowledge, we are only aware of one previous work that has addressed uncertainty in a non-MDP framework. Gao and Zhang (2008) developed a complex, linear, robust optimization model to determine optimal M&R decisions. Equations describing pavement deterioration and condition score improvements due to M&R actions were obtained based on linear regression. While they explicitly modeled the explanatory variables in the regression to be random, the regression coefficients were assumed to be deterministic, whereas sampling variation and measurement errors could easily lead to non-deterministic coefficients. A prominent feature of their model is that probabilistic guarantees can be given to the likelihood that pavement conditions get worse than their minimum acceptable levels, for each pavement section individually. We want to note that MDP models are also able to yield these probabilistic guarantees at the pavement section level (e.g., Mbwana and Turnquist, 1996), although most of these models impose probabilistic guarantees at the network level, i.e., they guarantee that a certain fraction of all pavement sections will be above their critical service levels. There are two major contributions in this paper. First, we present two non-MDP models based on integer programming to incorporate uncertainty in the pavement management problem. They are simpler and more intuitive than the model proposed by Gao and Zhang (2008). Furthermore, we do not confine ourselves to the use of linear regression-based performance models. Our models only require the specification of some nominal parameter values and a set of intervals in which the parameters are hypothesized to reside. In our first model, we consider uncertainty in the pavement improvement due to M&R activities, whereas in the second model we also examine uncertainty in pavement deterioration rates. Second, we study the price of uncertainty, i.e., we present useful insights into the impact of uncertainty on M&R decision making (as compared to the case when uncertainty is completely ignored). In particular, we present some insightful results on the differences in budget requirements between planning in a deterministic world versus planning in an environment where parameters are allowed to be random. Note that due to the dichotomy in the current pavement management literature (a model is either fully deterministic or fully stochastic), the impact of uncertainty on M&R planning is not easily determined because of the fundamentally different assumptions in the two modeling paradigms. The models proposed in the current paper make such a comparison straightforward as they are gradual generalizations of each other. In a number of related studies by Madanat, 1993a, Madanat, 1993b and Madanat and Ben-Akiva, 1994 and Kuhn and Madanat, 2005 and Kuhn and Madanat, 2006 similar concepts as the price of uncertainty have been introduced. For example, Madanat, 1993a and Madanat, 1993b and Madanat and Ben-Akiva (1994) introduced the concept of “the value of more precise information” to quantify the cost savings that can be realized when infrastructure inspections are more accurate. Kuhn and Madanat, 2005 and Kuhn and Madanat, 2006 examined the “cost of uncertainty”, referring to the difference in maintenance cost when uncertainty in the Markov transition probabilities is explicitly considered versus the case where they are not. In other words (as in Madanat, 1993a and Madanat, 1993b; Madanat and Ben-Akiva, 1994), they consider the differences in costs when parameters in a stochastic model are uncertain themselves, whereas in the current paper we start with a deterministic model and examine how the cost changes when uncertainty is gradually included in the model. Furthermore, the models developed in the above cited references are all based on MDPs, while our models are based on integer programming. In light of these observations, this work can be seen as an integer programming-based alternative to quantify the value of more precise information/cost of uncertainty, with the critical difference that we are starting with a fully deterministic model (whereas previous work starts with a stochastic MDP model). Though “cost of uncertainty” might be a more appropriate term (as price implies the purchase of uncertainty), in order to distinguish our work from previous MDP-based procedures, we have chosen to use “the price of uncertainty”. It is to be emphasized that it is not our goal to claim that integer programming models should be preferred over MDP-based models. We simply observe that current integer programming models are not capable of satisfactorily accounting for uncertainties (whereas this can easily be done using MDP models) and present an integer programming-based model that fills in this gap in the current M&R literature. The remainder of this paper is organized as follows. In Section 2 we present our first model in which the only source of uncertainty is given by the improvements due to M&R actions. Section 3 complements the model and presents our second model in which both M&R improvements as well as deterioration rates are assumed to be uncertain. A case study using pavement data from the Rockwall County in Texas gives a numerical demonstration of the proposed models (Section 4). Finally, Section 5 summarizes the major contributions and findings of the current paper and presents a discussion of interesting future research directions.

In this paper we presented two major contributions to the infrastructure management literature. The first is the introduction of two infrastructure M&R models that explicitly account for uncertainties observed in the real world (i.e., uncertainties in deterioration rates and the condition score improvements due to M&R), using a novel integer programming approach. That is, our models are not based on the theory of MDPs, unlike virtually all existing stochastic pavement management planning models. Another critical feature of the proposed models is that they provide probabilistic guarantees a priori (i.e., at the time of solving the models) that the prescribed M&R decisions would result in condition scores that are above their critical service levels. Furthermore, all the above is realized with minimal assumptions regarding the sources uncertainty. For example, our models do not require the specification of the entire probability distributions to characterize uncertainties, which might be burdensome for the decision maker or simply impossible due to a lack of data. Instead, our models only require the specification of some nominal and worst case values. (However, for other situations, e.g. when there is a reason to believe that positive deviations from the nominal value are more likely than negative deviations, the symmetry assumption might become a limitation of the proposed model.) Finally, we want to note that while we have given model formulations for a single facility, it is straightforward to determine the budget requirements in an entire network by applying the models to each individual facility in the network as we had demonstrated in Section 4. The second major contribution of the current paper is the introduction and quantification of the price of uncertainty, which we have defined as the additional monetary resources required when infrastructure M&R planning is performed accounting for uncertainty versus the case when uncertainty is completely ignored. Previous related work starts with a stochastic MDP model and examines the impact of parameter uncertainties, whereas we start with a fully deterministic model. By construction (we have demonstrated that the proposed models are gradual generalizations of each other), the formulated models lend themselves elegantly for this purpose. In a numerical case study using real world data from Rockwall County in Texas, we found that: • The price of uncertainty is a non-decreasing function of the level of uncertainty (and the confidence level imposed by the analyst). In particular, we demonstrated that there are instances in which the budget obtained from a deterministic model equals the budget resulting from a stochastic model, i.e., the price of uncertainty can be zero. Intuitively, this will be the case when the level of uncertainty is relatively low. • The price of uncertainty increases with the number of uncertainties considered. • M&R schedules resulting from deterministic models are typically different from those obtained from stochastic models (although the associated budget can be the same). • The price of uncertainty can be large. For the Rockwall County in Texas, it was found that the required budget resulting from a stochastic model can be three times as high as compared to the budget obtained from a deterministic model. • The computational time increases when going from model (P0) to (P1) to (P2). The proposed models are not without limitations. For example, since they are based on integer programming, they inherit the high computational requirements inherent in integer programming models. The developed models also yield open-loop M&R policies that are less desirable from a managerial perspective than the condition-based policies common to, for example, MDP-based models. (We want to emphasize that it is not our goal to advocate the use of a particular type of model in this paper. We simply observed that, unlike for example MDP-based models, current integer programming models are not capable of satisfactorily accounting for uncertainties and presented an integer programming-based model that fills in this gap in the current M&R literature.) Several critical future research directions exist. Because of one of the goals of the current paper (i.e., quantifying the price of uncertainty), we have not included any budget constraints in the proposed models. However, such a constraint is necessary when highway maintenance agencies have fixed budgets and optimal resource allocation schedules are needed. Hence in future work, we intend to examine the related (network level) budget allocation problem. Due to the much higher computational requirements, we anticipate that novel heuristic algorithms (such as genetic algorithms) will need to be devised to tackle the resulting nonlinear integer program. The price of uncertainty obtained in the current paper is dependent on the modeling framework used. We conjecture that other modeling assumptions (e.g., one could assume that in addition to the mean values of the M&R improvements, their variances are known as well) would lead to different prices of uncertainty. Hence it would be interesting to formulate other models to numerically examine the sensitivity of the results under different model assumptions. Another line of future work is the relaxation of the symmetry assumption since – as indicated above – this might not be always desired. And finally, while we have focused on pavement in this paper, we want to stress that the price of uncertainty is a much more general concept, and as such, it is applicable to a much wider range of transportation infrastructure (and beyond).