SCHEDULING PAVEMENT MAINTENANCE WITH DETERMINISTIC DETERIORATION AND BUDGET CONSTRAINTS Nejat Kafabakal Bilkert University 06533 Ankara, Turkey James C. Bean The University of Michigan Ann Arbor, Michigan 48109 Jack R. Lohmann Georgia Institute of Technology Atlanta, Georgia 30332 Technical Report 94-18 July 1994

Scheduling Pavement Maintenance with Deterministic Deterioration and Budget Constraints NEJAT KARABAKAL Bilkent University, 06533 Ankara, Turkey JAMES C. BEAN University of Michigan, Ann Arbor, Michigan 48109 JACK R. LOHMANN Georgia Institute of Technology, Atlanta, Georgia 30332 August 1994 Abstract The problem of scheduling pavement maintenance over time to minimize cost under budget constraints is formulated as an integer program. We assume that the rate of pavement deterioration is deterministic and known with certainty once the pavement condition and the choice of maintenance alternative are specified. We develop a dual heuristic based on a Lagrangian relaxation methodology. First, we solve individual street problems optimally ignoring the budget constraints. Then, we minimize the budget violations through a systematic rescheduling of maintenance activities across the streets. The computational tests show that the approach is effective for solving large problem instances in practice.

The problem of scheduling road pavement maintenance is of serious concern in practice because of the rate at which pavement deteriorates to unacceptable levels. The pavement condition can be improved by selecting a maintenance alternative ranging from simple routine maintenance such as pothole patching and chip sealing, or preventive maintenance such as crack sealing, to structural restoration such as reconstruction and rehabilitation. The selection of a maintenance alternative is not a straightforward task because of the differences in cost and effectiveness. The least expensive alternative may not be the best because it allows the pavement to deteriorate faster in subsequent periods. Hence, while the cost of a maintenance alternative depends mainly on the pavement's condition, the overall cost of maintaining a street pavement over time is a function of both timing and type of maintenance alternatives. The problem has been approached in a variety of ways by researchers. In particular, Markov decision models have been considered appropriate for modeling the process of cumulative deterioration (CARNAHAN[2]; RITCHIE et al.[12]; GOLABI, KULKARNI, AND WAY[7]). A major drawback of such models is that they do not readily accommodate budget constraints. Rather, they attempt to determine the sequence of maintenance alternatives which would result in minimum expected cost for each segment subject to some performance constraints. Resulting aggregate expenditures may fluctuate widely over time. In many real cases, it is important to determine maintenance alternatives given budget limitations. Most government agencies work to an annual budget process which imposes budgets on pavement maintenance programs. Unfortunately, introducing budget constraints removes the advantage of solving each street segment's maintenance problem independently. The economic interdependence of segments caused by sharing rationed capital requires simultaneous consideration of all maintenance decisions in each time period, thus creating a difficult combinatorial problem. KARABAKAL, LOHMANN, AND BEAN[10] studied a similar problem for equipment replacement with budget constraints and developed an exact approach. Later, KARABAKAL, BEAN, AND LOHMANN[9] extended this approach to an effective dual heuristic for solving large replacement problems. We use a Lagrangian relaxation methodology in which individual replacement problems are solved by a dynamic program (DP) that uses equipment's 1

age as the only state variable. The corresponding DP formulation for solving the pavement maintenance problem is more complex than that for equipment replacement since the states not only include age but also pavement condition. In this paper, assuming deterministic pavement deterioration, we study the problem of scheduling maintenance activities over time for a portfolio of street segments so as to minimize cost subject to periodic budget constraints. The remainder of the paper is organized as follows. In Section 1 we formally state the problem and give an integer programming (IP) formulation. Section 2 discusses our solution method for the problem. We use Lagrangian relaxation to develop a heuristic for solving large, realistically-sized problems. We describe a multiplier adjustment algorithm for solving the Lagrangian dual. Computational results are presented in Section 3. Finally, we present concluding remarks in Section 4. 1 Problem Statement and Formulation Pavement deterioration is commonly measured in terms of a standardized pavement condition index (PCI) which is an indication of the cumulative damage caused by various types of cracking, raveling, deformation, disintegration, and so on. The index was developed at the U.S. Army Construction Engineering Research Laboratory as part of the PAVER project, a computerized pavement management system (SHAHIN AND KOHN[13]). The PCI is given by an integer ranging from 0 to 100, where 100 represents perfect condition. Since the PCI covers such a wide range and its determination can be subject to an error of as much as ~5, it is usually more convenient to work with condition intervals. For example, SPITTLER et al.[14] used seven intervals in a highway evaluation project: failed (0-10), very poor (10-25), poor (25-40), fair (40-55), good (55-70), very good (70-85), and perfect (85-100). A maintenance alternative is any treatment performed on a deteriorating pavement segment after original construction, such as reconstruction, overlay, and routine maintenance. Routine maintenance is performed all the time in varying degrees depending on the pavement condition, hence, it is usually handled indirectly as a factor affecting the timing decisions of other major maintenance alternatives. 2

We first describe a single street segment's pavement maintenance problem in isolation. By introducing the budget constraints, we then formulate an IP to solve the problem for a portfolio of segments. Throughout the paper, we assume that all maintenance alternatives and cash transactions occur at the end of discrete time periods and that the end of period zero refers to the current time. Moreover, the following notation are used: s = index of street segments, S = set of street segments, a = index of maintenance alternatives, A = set of maintenance alternatives, j, f = indices of pavement conditions, Ca = set of acceptable pavement conditions at which maintenance alternative a can be applied (i.e., perfect pavement condition is excluded), C = UaEACa i, k = indices of time periods, js = current, observed condition of street segment s, H = planning horizon, T = set of time periods = {O,..., H}. 1.1 Single Street Segment Consider a street segment s with current pavement condition js. The decision maker may either let it deteriorate further by applying only routine maintenance or choose to install one of the major maintenance alternatives to improve the pavement condition. We assume that both deterioration and improvement rates are deterministic and known with certainty once the pavement condition and the choice of maintenance alternative are specified. For the purposes of illustration, consider a simplified example. Assume we have two major maintenance alternatives, reconstruction and overlay, or A = {R, 0}, and four possible pavement condition intervals, where 4 denotes the perfect condition and 1 denotes, for both maintenance alternatives, the minimum acceptable condition below which pavements should never be allowed to deteriorate, i.e., CR = Co = {1,2,3}. Deterioration rates in pavement condition depending on the choice of maintenance alternatives are shown in Fig3

Pavement Condition R: Reconstruction Perfect -4 0: Overlay Lowest acceptible - 1 t t+1 t+2 t+3 t+4 Time Figure 1: Pavement deterioration rates for the example street segment. ure 1. We assume that both reconstruction and overlay restore the pavement to the perfect condition regardless of its current condition; however, we permit the reconstruction alternative only when the pavement is at condition 1. For the overlay, the poorer the current condition, the higher the maintenance cost would be. Moreover, the rate of deterioration after each maintenance alternative is different. Reconstructing the pavement keeps it in perfect condition for the next period and then the pavement deteriorates by one condition level per period. If the overlay option is selected, the pavement starts deteriorating next period by one condition level per period. Furthermore, the deterioration rates define the maximum lives of the maintenance alternatives. In our example, the restoration of reconstruction can be kept for at most four periods and that of overlay for at most three periods, after which another maintenance alternative must be installed. The general problem has a network characterization which is exploited for the remainder of the paper. Consider a directed graph where nodes correspond to pairs (time period, pavement condition) and arcs correspond to maintenance decisions. A maintenance decision consists of the type of maintenance alternative and its life. Associated with each arc is a length parameter, discounted cost of the maintenance decision. An arc from node (i,j) to (k, ) is selected only if its maintenance alternative is installed in period i when the pavement condition is j, leading to condition e in period k and performing only routine 4

0 0 Figure 2: Shortest path formulation of the example street segment's maintenance scheduling problem. maintenance between i and k. To solve the problem for a segment s, we seek a shortest path from node (0, j) to any node in {(H, e)}eEc. An example graph is shown in Figure 2 for the street segment with deterioration characteristics given in Figure 1 and with H = 3, Js = 1. 1.2 Portfolio of Street Segments with Budget Constraints Let the decision variable x[s, a, (i, j), (k, ~) = 1 if, for segment s, maintenance alternative a is chosen in period i at condition j leading to condition f in period k and allowing only routine maintenance between i and k, where k > i. The notation a = 0 refers to the choice of continuing with routine maintenance and is available only in period zero. We define two maintenance cost parameters. First, let c[s, a, (i,j), (k,~)] be the discounted value of all costs corresponding to the decision x[sa, (i,j), (k,)] = 1. To keep notation simple, we suppose c[s,a, (i,j), (k, )] = oc whenever there is no arc from (i,j) to (k,~ ) in the directed graph of street segment s. Second, let P[s, a, (i,j)] be the cost of maintenance alternative a in period i when the condition of pavement s is j. If such a maintenance is scheduled, P[s, a, (i,j)] represents the amount of money to be spent from 5

the i-th period's budget, BR. We assume that routine maintenance costs are not included in expenditure determination; in particular, P[s, 0, (0,js)] = 0 for all s. Details in estimating cost parameters follow the model formulation. The problem of scheduling maintenance alternatives for a set of street segments so as to minimize the total discounted costs over H periods can be formulated as follows: minimize 3 y 3 c[s, a, (i,j), (k, )] x[s, a, (i,j), (k, )] sES aEA (i,j)ETxCa (k,~)ETxC k>i subject to the following constraints: 1. Network flows: For each s C S: C 3 Z[s, a, (0, j), (k,)] = 1 (1) aEA (k,e)ETxC k>0 3 3 zx[sa, (i,j),(k, )] = 3 > x[s,a, (k,), (i,j)] (2) aEA (k,e)eTxC aEA (k,I)eTxCa k>i k<i for all (i,j), i 0, i Z H E E E x[sa,(k,),(H,j)] > 1 (3) aEA (k,f)ETxCa jEC k<H 2. Budgets: For i=,..., H - 1: E S P[sa,(i,jJ)] S x[s,a,(i,j),(k,)] < B, (4) sES aEA jECa (k,e)ETxC k>i 3. Integrality: For all s e S; a C A; (i,j), (k,e) E T x C, k > i: Z[s,a, (i,j), (k, )] e {0, 1} (5) This formulation has approximately ISI x JAI x |CI x L x H variables, where L is the maximum life of a maintenance alternative. A problem with 100 segments, 5 maintenance alternatives, 10 pavement conditions, maximum lives of 10 periods, and horizon of 20 6

periods leads to one million binary variables. Integer programs of this size cannot be solved by current technology. In Section 2, we present a dual heuristic to obtain high quality solutions. 1.3 Estimating Maintenance Cost Parameters Define /a(t,p) be the real (inflation-free) cost, dollars per unit pavement area, of maintenance alternative a when the pavement is at condition p and t periods after a base period, possibly the original construction time of the pavement. For some maintenance alternatives, either t or p can be suppressed if the dependence on time or pavement condition, respectively, is deemed negligible. Let a = annual opportunity cost of capital, y = annual inflation rate, y = 1+, i.e., discount factor, qa = best pavement condition attained immediately after maintenance alternative a is performed, and rs = area of street segment s. Then c[sa,(ij),(kt)] = (/3a(iOj) + /30(t,p)yt) y rs, and 1<t<k-i; qa_>p>e P[s, a, (i,j)] = /a(i,j) r assuming that future budgets are also estimated in real terms. For the alternative of continuing with routine maintenance in period zero, above equations are specialized into the following. c[s, O,(0O,j),(k,)] = /o(t,p)ytrs, and 1<t<k; js>p>e P[sO,(Oj)] = 0. For example, SPITTLER et al.[14] provides the following cost estimations, all in dollars per square yard, based on guidelines in AASHTO 1987 DESIGN GUIDE[1] and REICHELT et al.[ll] 7

1. Cost of reconstruction (a = 1): p1l(t) = 16.42 + 0.124t. 2. Cost of overlay (a = 2): /32(t,p) = 8.5 + 0.02t + 0.1(100 - p). 3. Cost of routine maintenance (a = 0): /o(p) = 15.016 (0.948)P. 2 The Solution Method Let Ai > 0 be the multiplier for budget constraint i. Dualizing budget constraints using A, we get L(A) = min S EI 5 E c[s, a, (ij), (k, )] x[sa, (ij), (k, )]-5E Bi Ai (6) a (i,j) (k,) i where CA[s, a, (i,j), (k, e)] = c[s, a, (i, j), (k, )] + P[s, a, (i, j)] and G = {x x is feasible to (1)-(3) and (5)}. Any solution, x, obtained in evaluating L(A) for a A > 0 is referred to as a Lagrangian solution. The Lagrangian dual is formulated as max L(A). (7) A>O Relaxing the budget constraints removes the interdependency of maintenance decisions across street segments. Hence, the problem is decomposed into independent shortest path problems on acyclic graphs. We use a DP to solve each shortest path problem efficiently. Consider a segment, s, and its directed graph. To facilitate the presentation, append a dummy node, (H+1, *), to 8

the graph. Also add dummy arcs from each node in {(H,j)} ec to (H+1, *) with zero cost parameters. Let (i,) = { (k, ) I there exists an arc from (i,j) to (k, e) for segment s }, Ps(ij) = {(k,) I there exists an arc from (k,~) to (i,j) for segment s}, s = {(i,j) I Ps(i,j) $ q$}. Define fA[s, (i, j)] as the length of the shortest path from node (O, j) to node (i,j). Initialize fA [s, (0, j)] = 0 and solve the following forward recursive equations: fx[s, (ij)] = min {c[s, a, (k, ), (i,j)+ f[s, (k,)]} for all (ij) e T. aEA {(k,e)EP,(i,j) | i>k} (8) Although the total number of nodes in the network, H ICI + 2, can be high, many of them are not touched by any arc and the cardinality of A/, is much smaller. Therefore, the use of reaching rather than recursive fixing in solving (8) decreases computation significantly (see DENARDO[4] for a discussion of reaching and recursive fixing). For a single segment, the value of a minimum cost maintenance policy for s over H periods is given by fA (s), where fA (s) = f[s, (H+1, *)] = min fA[s, (H,j)]. jEC The Lagrangian value is then computed from L(A) = E fE(s) - E B s i For future reference, let us define bA[s, (i,j)] as the length of the shortest path from the dummy node (H+1,*) to node (i,j). Initialize bA[s,(H+1,*)] = 0, bx[s,(H,j)] = 0 for allj C, and bx[s, (0,j)] = fA(s). We can use the following backward recursion to compute the values for the remaining nodes. bx[s,(i,j)] = min {cx[s,a, (i, j), (k, )] + b[s, (k,)]} for all(i,j) e A/', (9) aEA {(ke)E'S(ij) I k>i} i {, HH + 1. 9

Next, we present a multiplier adjustment method (MAM) for solving (7). 2.1 A Multiplier Adjustment Method MAMs are heuristic algorithms for solving Lagrangian duals exploiting the special structure of a particular problem. Previous successful applications include the generalized assignment problem (FISHER, JAIKUMAR, AND VAN WASSENHOVE,[6] KARABAKAL, BEAN, AND LOHMANN[8]), set partitioning (CHAN AND YANO[3]), and equipment replacement (KARABAKAL, BEAN, AND LOHMANN[9]). A MAM usually guarantees monotonic bound improvement; however, it does not guarantee bounds better than those obtained by more common subgradient algorithms. See FISHER[5] for details and further application examples. The following development considers a directed graph representing the decisions for street segment s and assumes that the shortest path length fA*(s) is associated with the Lagrangian solution x. Definition 1 Given a Lagrangian solution x, expenditure in period i is defined as E(x) = E E E P[s, a, (i,j)] x[s, a, (i,j), (kJi)] s a 3 (ke) for i = 0,...,H-1. When Ei(x) > Bi, the central idea in our MAM is to increase Ai until one of the maintenance alternatives scheduled in period i is canceled. The exact amount of this increase is determined using Theorem 1 which, in turn, uses the following sensitivity results. Lemma 1 If x[s,a, (i,j), (k, )] = 0 in an optimal solution to (6), the minimum 6 such that cA [s, a, (i,j), (f, )] - 6 would cause x[s, a, (i,j), (k, )] = 1 in an alternative optimum is given by Ox[s, a, (i,j), (k, e)], where x[s,a, (i, j), (k, )] = f[s, (i,j)] + c[s, a, (i,j), (k, )] + bA[s, (k, )] - f(s). Proof. Let fA(s) be the length of the shortest path from node (0,j) to (H + 1, *) constrained to include the arc from (i,j) to (kC, ) using maintenance alternative a. Then fx(s) = f[, (i, j)] + [s, a, (i,j), (k, ~)] + bx[s, (k,)]. 10

In order to set x[s, a, (ij), (k,)] = 1 in an alternative optimum, f(s) should be at least as small as ftA(s). To enforce this selection we have to reduce c\[s, a, (i,j), (k, ~)] by at least f (s) - ft(s), where fA(s) - fA(s) = f[s, (i, j)] + c[s,, (i,j), (k, )] + bA[s, (k, )] - f(s) = OA[s,a,(i,j), (k, )]. (10) Lemma 2 If x[s, a,(ij), (k, )] = 1 in an optimal solution to (6) and if j and a are the only pavement condition and maintenance alternative, respectively, available in period i, the minimum 6 such that cA[s, a, (i,j), (k, )] + 6 would leave out scheduling a maintenance alternative in period i in an optimum is given by 6*: = fA~(S I~i)- f*(s) where f,*(s | i) is the length of the shortest path from node (0, j) to (H+1, *) constrained to leave out scheduling a maintenance alternative in period i. Proof. Omitted. ~ In Lemma 2, fA*(s i ~i) is computed by skipping all nodes {(i,j)}jec in (8). Theorem 1 If segment s has a maintenance alternative scheduled in period i* > 0 so that x[s,a, (i*,j), (kt)] = 1 for some a, j, and (k,E), then the minimum A such that A. + A would cause x[s, a, (i*,j), (k, )] = 0 in an optimum is given by A(s) = min{Al(), A2(s)}, (11) where A(S)= mi O9A[s,a', (i*, j), (k'')] Ailvs) ~ (k',e') P[s, a, (i*, j)] - P[s, a', (i*, j')] {a',j' | P[s,a',(i*,j')]<P[s,a,(i*,j)]} and A2(s)- f>(s (i*)-/ () P[s, a, (i*,j)] Proof. See Appendix. 11

Corollary 1 If i* = 0 so that x[s,a, (O,j ), (k, )] = 1 for some a and (k, e), then A (s) = (s), if a >o (12) +00, if a = 0 Proof. By problem definition, period 0 cannot be skipped. Thus, A2(s) = +oo. If a = 0, Ai(s) is also +00 because continuing with routine maintenance does not require any money from the current budget, Bo. * The multiplier A- can be interpreted as the penalty of violating the budget constraint of period i. If the total expenditure in period i exceeds the budget, its penalty Ai should be increased to discourage installing some maintenance alternatives. The following MAM is a systematic way of adjusting the penalties of violated constraints. The Multiplier Adjustment Algorithm Step 0: Initialize Ai = 0 for all i (i.e., ignore all budget constraints). Use DP recursions (8) and (9) for solving IS] independent shortest path problems and obtaining x~, fAho and bAo. Set the iteration counter k +- 0. Step 1: Let I = {i I Ei(xk) > Bi}. If I = X, stop; current xk is feasible. Step 2: Select the period i* e I for which the discounted value of the budget deficit is the largest, i.e., Ei (xk) - Bi i = argmax (ieI (1 + )i Step 3: Let S(i*) = s xk[s,a,(i*,j),(k,)] = 1 for some a, j, and (k,f)}. Compute A(s) for each s E S(i*) from either (11) or (12), depending on whether i* = 0 or not. Let s* = argmin A(s) and A* = A(s*). sES(i*) If A* = 0, update I - I \ {i*}. If I = X, stop; no further improvement is possible. Otherwise, go to step 2. If A* > 0, update multipliers: 1k+l. \k + (A*)+; Ak+l - A for i + i 12

where (A*)+ is infinitesimally greater than A* to ensure that street segment s* would not have the same maintenance alternative in period i' in the next iteration. Solve IS(i*)l independent shortest path problems with new multipliers to obtain xk+l, fk+1, and bk+l. Set k - k + 1, go to step 1. The MAM is a dual ascent procedure and its monotonicity is established by the following theorem. Theorem 2 Let i* be a period in which the budget constraint is violated at the k-th iteration of the MAM. That is, E-,(xk) > Bi.. Increasing 4A by A* > 0 found in step 3 increases L(Ak) by A* [Ei*(x) - B*] > 0. Proof. In the k-th iteration L(Ak) = Af;k()- E B A. Increasing by * incs i Increasing A, by A* increases the shortest path of each segment s C S(i*) by A* P[s, a, (i*,j)], where a is the maintenance alternative for s installed in period i* at pavement condition j by xk. Hence, L(A k+) = Z fAk(s)+A* + P[s,a,(i*,j)] - BA -A* Bi. ~s sES(i*) i L(Ak) + A*( P[s, a, (i,j)]- Bi. ses(i{) L (Ak) + A* [E.*(xk) -B*]. The MAM increases the Lagrangian value by attempting to decrease budget violations in certain periods. Therefore, the monotonic improvement of the Lagrangian value should lower the budget violations. Computational tests verify this effect. Definition 2 Given a Lagrangian solution, x, the discounted value of budget deficits is defined as D(x) = (max{0, Ei(x)- i}):o (1 c )'13 13

Unfortunately, there is no guarantee that D(x) is reduced monotonically. We performed the following computational experiments to evaluate the overall reduction in D(x) by the MAM. 3 Computational Experiments The MAM was coded in C and run with random test problems. To generate problem instances, we assumed seven PCI ranges: 1 (PCI 0-40), 2 (PCI 41-50), 3 (PCI 51-60), 4 (PCI 61-70), 5 (PCI 71-80), 6 (PCI 81-90), and 7 (PCI 91-100) and used upper range values in cost calculations. Current pavement conditions and segment areas were sampled from uniform distributions: U(1, 7) and U(1000, 7000), respectively. We supposed two types of major maintenance alternatives, reconstruction and overlay and used the functional forms of Section 1.3 to generate their cost parameters. Budgets are set proportional to the total street area in each period: Bi = - x ESs rs for all i, where s is varied between 5 and 9 to generate tight and loose budget scenarios. We also set H = 20 for all problems. We conducted two computational experiments to determine the effectiveness of the MAM, first with varying problem size for a given budget level, and second with varying budget levels for a given problem size. All problems were solved on a Sun Sparc Station 2+. In the first experiment, we set ( = 7 and focused on the algorithmic performance in terms of the objective value error, budget deviation, and solution time. Let K = number of MAM iterations to solve a problem instance, and x' = Lagrangian solution with the smallest present value of budget deficits, or D(x') = mink=l,...K{D(xk)}, where k is the iteration counter of the MAM. Note that x' may have plus or minus objective value error. To determine the average magnitude of these errors, we solved problems ranging from 5 segments to 200 segments. The results are summarized in Table 1. Solution times increase almost linearly with problem size and remain reasonable even for 200 segment problems. The absolute objective value error is insignificant regardless of the problem size. Moreover, the budget deficit statistics, average and maximum D(x'), verify our conjecture that the MAM is more effective in 14

reducing budget violations as the problem size increases. Naturally, large problems offer more freedom across assets for the MAM to fix budget violations. In the second experiment, we set |SI = 30 and focused on the performance with respect to budget tightness. We solved problems with varying from 9 (loosest) to 5 (tightest). The results are shown in Table 2. As budgets are made tighter, both deficits and solution times increase and problems become more difficult to solve. This can be attributed to the small number of alternative feasible paths that the MAM tries to find in reducing expenditures. Naturally, the MAM is more likely to locate feasible solutions with increasing budgets. Average absolute error, again, appears insignificant for all budget levels. 4 Conclusions We describe an effective heuristic for solving realistically-sized pavement maintenance scheduling problems under budget constraints. The heuristic is a MAM that solves a Lagrangian dual formulation. Its basic idea is to reduce the budget violations of the unconstrained solution progressively so that a feasible or acceptable solution is obtained. Computational experiments show that the final budget violation of the MAM solutions average well below 1%. Deficits increase as the problem size is decreased and budgets are made tighter. Average absolute error of the objective function value remains insensitive to both budget level and problem size. Based on these results, the MAM appears to be a viable tool in solving large problems in practice. Acknowledgments This research was supported in part by National Science Foundation grant DDM-9202849 to The University of Michigan. Previous version of this paper was presented at the 1993 ORSA/TIMS meeting in Phoenix. 15

Table 1: Performance of the MAM solutions with increasing problem size. Each line shows statistics for 10 problems. Average Average Maximum Average absolute error a D(x') D(x') CPU time \SI (%O) (%) (%) (secs) 5 0.08 1.82 5.32 6.92 10 0.06 0.79 4.42 11.19 20 0.06 0.58 2.90 28.60 30 0.08 0.23 0.48 33.80 50 0.03 0.05 0.36 65.91 100 0.04 0.09 0.45 165.90 200 0.02 0.03 0.25 244.30 a IV(xc')-L(K)I L(\'K) Table 2: Performance of the MAM with decreasing budget levels. Each line shows statistics for 10 problems. Average Average Maximum Feasible Average absolute error a D(x') D(x') solutions CPU time (%) (%) (%) (%) (sees) 9 0.07 0.00 0.00 100 18.74 8 0.05 0.02 0.17 90 20.62 7 0.08 0.23 0.47 50 33.80 6 0.07 0.75 1.29 0 56.34 5 0.05 3.20 5.90 0 48.49 a IV(r')-L(AK') L(AK) 16

alternative a (0,o j) *** (i*,j )... (ki )... (H+1,*) alternative a' Figure 3: Two possible ways of creating an alternative optimum by increasing Al. in order to set x[s, a, (i*,j), (k, )] = 0. Appendix: Proof of Theorem 1 Theorem 1 If segment s has a maintenance alternative scheduled in period i* > 0 so that x[sa, (ij), (k, = 1 for some a, j, and (k, ), then the minimum A such that A. + A would cause x[s, a, (i,j),(k, )] = 0 in an optimum is given by A(s) = min{Al(s), A2(s)}, (13) where A/(S) =min OAx[s,', (i*, j'), (k', (')] A (s) = min (k',e') P[s, a, (i*, )] - P[s,', (i*, j')] {a',j' I P[s,a',(i*,j )]<P[s,a,(i*,j)]} and ~A2(s)-= f(s [ i*) -f,() P[s, a, (i*,j)] Proof. The current shortest path, (Ojs)-(i*,j)-(k,e)-(H+1,*) in Figure 3, has length ft(s). For each A increase of A.*, the value of cA[s,a,(i*,j),(k,e)] is increased by A P[s, a, (*, j)]; as is fA*(s). When the increase in fA*(s) reaches a certain threshold, another path emerges as an alternative to the current shortest path. The new path will either 1) pass through one of the nodes in {(i*, j)}jec, or 2) skip all the nodes in {(i*,j')}jec. 17

1. If the value of CA[s, a, (i*,j), (k, )] is increased sufficiently, a new path from (0,js) to (H+ 1,*) passing through one of the nodes in {(i*,j')}jec, but installing another (cheaper) maintenance alternative a' to any node (k',e'), becomes as short as the current one. Without loss of generality, assume that the new path also passes through node (i*,j) in period i*. In Figure 3, this new path is (0, j)(i*,j)-(k',')-(H+l, *). As in Lemma 1, let fA(s) be the length of the shortest path constrained to include the arc from (i*,j) to (k',') using maintenance alternative a'. To enforce the lengths of these two paths, (O,js)-(i*,j)-(k, )(H+1, *) and (O, j)-(i*, j)-(k', C')-(H+1, *), to be equal, AX. should be increased by at least A > 0, satisfying f(s) + A P[s, a,, (*,j)] = fA(S) + A P[s, a', (ij)] (14) fx(s)- fA(s) = { P[s,a, (i*,j)]- P[, a', (i*,j)] } (15) provided P[s, a', (i*,j)] < P[s, a, (i*, )]. (16) If P[s, a', (i*,j)] > P[s, a, (Z*,j)], an alternative shortest path passing through period i* and installing a' does not exist. An illustration of equation (14) is given in Figure 4. The relation (16) between the slopes must hold for the intersection of the two lines, hence for the existence of A. From (10), f\A(s) - f*(s) = 0A[s, a', (*,j), (k',')]. Since there can be many arcs passing through period i* and installing maintenance alternative a' $ a, Al(s) is the minimum A over appropriate pavement conditions, maintenance alternatives, and their lives satisfying (15). Note that if there is no maintenance alternative a' satisfying (16), Ai(s) is set to +oo. 2. If the value of cA[s, a, (i*,j), (k,k )] is increased sufficiently, a new path from (O, js) to (H+1, *) not passing through period iZ becomes as short as the current one. This is the path (0, js)-(H+1, *) in Figure 3. From Lemma 2, A.* should be increased by at least A = A2(s), satisfying f(s) + A P[s, a, (i*, j)] = f(s | vi*). 18

Path Length f,(s)+ A'P[s,a, (i*,j) fA ) 4 IAf~(S~) I~ I<fA A(s) + A' P[s, a', (Z* *,j)] fA(s) A A' Figure 4: When Ai. is increased by A, there will be two alternative shortest paths. The value of A[s, a, (i*,j), (k, )] is reduced until either case occurs. Hence, (11). U References [1] AASHTO, "AASHTO Guide for Design of Pavement Structures-1987," Transportation Research Board, National Research Council, Washington D. C. (1987). [2] CARNAHAN, J. V., "Analytical Framework for Optimizing Pavement Maintenance," Journal of Transportation Engineering, 114, 307-322 (1988). [3] CHAN, T. J. AND YANO, C. A., "A Multiplier Adjustment Approach for the Set Partitioning Problem," Operations Research, 40, S40-S47 (1992). [4] DENARDO, E. V., Dynamic Programming: Models and Applications, Prentice Hall Inc., N.J., 1982. [5] FISHER, M. L., "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, 27, 1-18 (1981). [6] FISHER, M. L., R. JAIKUMAR, AND L. N. VAN WASSENHOVE, "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, 32, 1095-1103 (1986). 19

[7] GOLABI, K., KULKARNI R. B., AND WAY G. B., "A Statewide Pavement Management System," Interfaces, 12, 5-21 (1982). [8] KARABAKAL, N., J. C. BEAN AND J. R. LOHMANN, "A Steepest Descent Multiplier Adjustment Method for the Generalized Assignment Problem," Technical Report 9211, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor (1992). [9] KARABAKAL, N., J. C. BEAN AND J. R. LOHMANN, "Solving Large Replacement Problems With Budget Constraints," Working Paper 94-01-A, Faculty of Business Administration, Bilkent University, Turkey (1994). [10] KARABAKAL, N., J. R. LOHMANN, AND J. C. BEAN, "Parallel Replacement Under Capital Rationing Constraints," Management Science, 40, 305-319 (1994). [11] REICHELT, E. F. JR, SHARAF E. A., SINHA K. C., KUMARES C., AND SHAHIN M.Y., "The Relationship of Pavement Maintenance Costs to Pavement Condition Index," USA-CERL IR M-87/02, U.S. Army Corps of Engineers, Construction Engineering Research Laboratory, (1987). [12] RITCHIE, S., YEH C., MAHONEY J., AND JACKSON N., "Surface Condition Expert System for Pavement Rehabilitation Planning," Journal of Transportation Engineering, 113, 155-167 (1987). [13] SHAHIN, M. Y. AND KOHN S. D., "Overview of PAVER Pavement Management System," Transportation Research Record 846, Transportation Research Board, National Research Council, Washington D. C. (1982). [14] SPITTLER, J. R., KIM C. D., EHSAN N. AND CARR R. I., "Urban Bus Transit Impact on Flexible Pavement Condition and Lifecycle Cost-Preliminary Background," Center for Construction Engineering and Management, Department of Civil Engineering, The University of Michigan (1989). 20