Linear Programming Model for Scheduling Road Maintenance

Brad Mytton & David Meaclem

Back to the main project page...

Algebraic Formulation

Two algebraic formulations are discussed. The first, is for the Christchurch City Council (CCC) roading network, and uses roughness (IRI) as the sole indicator of condition. The second incorporates the roads structure as well as roughness to indicate condition, yet data and solving capacity are not currently available.

The formulation shown is for the structure-inclusive model.

Indices:

f,g : the structural number of a road.
i,j : the IRI value of a road.
m,n : the type of maintenance undertaken. m,n = 0 when there is no maintenance performed.
t : the year, from 1 to T.
v : the average daily volume of traffic on a road (over all lanes).
z : the composition of vehicles on a road (% cars, heavy vehicles and so on).

Parameters:

az,v,i,f : the initial area of road in m2 with vehicle composition z, traffic volume v, an IRI of i, and a structural number of f.
b : the annual budget for road maintenance.
cm,t : the discounted cost of maintenance type m per m2.
cmz,m,t : the discounted cost per vehicle per metre per day when maintenance m is performed on a road with vehicle composition z.
dz,v : the annual percentage increase in structural number when no maintenance is performed on a road with vehicle composition z and traffic volume v.
disc : the discount rate.
h : the percentage of road area used in the target constraint sets.
pf,z,v : the annual percentage increase in IRI when no maintenance is undertaken on road sections with vehicle composition z, traffic volume v and structural number f.
qz,v,h : the target IRI of roads with vehicle composition z and traffic volume v. At most h% of the total area of this road type can have an IRI greater than this target.
rim,i : the IRI reset if maintenance m is performed on roads with current IRI i.
rsm,f : the structural number rest if maintenance m is performed on roads with a current structural number of f.
sz,v,h : the target structural number of road sections with vehicle composition z and traffic volume v. At most h% of the total area of this road type can have a structural number less than this value.
uz,v,i,t : the discounted user cost per metre of driving on roads with vehicle composition z, traffic volume v and an IRI of i. wz,v: the average width in metres of road sections with vehicle composition z and traffic volume v.
t : the interest rate.

Decision Variables:

Az,v,m,i,f,t : the total area in m2 of roads with vehicle composition z, traffic volume v, an IRI of i, structural number of f that have maintenance m undertaken on them in year t.
Ut : the unused budget in year t.
P : the perpetuities for user cost, cost during maintenance and maintenance cost.

Model:

Minimise

(1)

Subject to

for all z, v, j , g, t ¹ T. (2)

for all t. (3)

for all z, v, i. (4)

for all z, v, f.(5)

for all z, v, i. (6)

(7)

Objective Function (1)

The objective of this model is to minimise the cost of roads to the New Zealand public. The costs of roads to the New Zealand public comprise both road user costs and maintenance costs, as the public fund maintenance through taxation paid to Central Government. The objective function in this formulation reflects this objective and contains four separate terms. The first term from the objective function computes the total discounted cost of road maintenance over the planning horizon. The second term calculates the discounted road user costs incurred by motorists when driving along road sections. The third term computes the discounted increase in road user costs that occur when maintenance is being performed. The final term in the objective function is the perpetuities of user costs, costs during maintenance and maintenance costs calculated in constraint seven. The inclusion of these perpetuities is discussed in further detail in Section 2.9.7.

With this objective in mind, the solution to this formulation may indicate to an appropriate level of annual maintenance funding. The level of funding may presently be too low, or alternatively too high. Whichever case holds, a likely outcome is the improvement of road quality at the present budget level due to the formulation optimising road maintenance.

Maintenance State Change Constraint set (2)

This set of constraints works by tracking the structural number and IRI value of road sections with similar characteristics over the duration of the planning horizon. The IRI of a road section can change in two ways. Firstly, if no maintenance is performed during a year, then the IRI on a road section increases by the parameter p. Secondly, if a maintenance is performed on a road section, the IRI gets reduced to the IRI reset value of that specific maintenance type. The structural number can also change in two ways. Firstly, if no maintenance is carried out, then the structural number of a road section decreases by the parameter d. Secondly, when maintenance is performed, the structural number gets reset to the structural number reset associated with that maintenance type.

Budget constraint set (3)

The budget constraints ensure that the funds spent on maintenance during a year cannot exceed the funding available. As funds that are not required for use in a year can be placed in an account at the start of that year, interest is earned and the inflated amount will accrue to the next year when it can be used. Thus, the amount of funding available for road maintenance in an individual year is the annual budget plus any funds unused in previous years. These are equality constraints to ensure that when the funding available in a year exceeds the actual amount spent on maintenance, the remainder becomes unused funds which can then be utilised in following years.

Setting of Initial Area constraint set (4)

This constraint set ensures that the area of all road sections of the same road type, IRI value and structural number at the start of the planning horizon equates to the summation of the equivalent ‘Area of Road’ decision variables in the first year regardless of their maintenance type.

IRI Target constraint set (5)

For each road type with an IRI greater than a set limit in the final year of the planning horizon these constraints force the area of road, to be less than some fraction of the initial area of that road type. The target level for each road type’s IRI is taken as the 80th percentile of initial roughness values; that is, the IRI value lower than which 80% of the initial area of roads in a road type are. These values are different for all road types, ranging from just 2.8 for the high volume, high user cost Tertiary roads, to 6.4 for low volume Secondary roads. The target fraction that has been used in the base run is 20%. Thus, the constraint ensures that at the end of the planning horizon less than 20% of the area of a given road type can have an IRI equal to or exceeding the initial 80th percentile IRI value. This set of constraints have been included to prevent the dramatic reduction in road quality towards the end of the planning horizon that can be evident in solutions generated by Chong & Thompson with dTIMS.

Structural Number Target constraint set (6)

This set of constraints acts in the same manner as the target constraints for IRI. They ensure that road sections within a road type with structural numbers equal to or less than the target have a combined area that is less than a certain percentage of the total area. Again, this is by no means a complete method. The problems that may have occurred with the IRI targets could again provide setbacks.

Due to the lack of structural data and the solver capacity (without decomposition) a full results set could not be attained.

Back to the main project page...   Back to Management Science Honours Project page...

Page updated: 1 November 2000.