This project extends Mytton and Meaclem's research on 'Linear Programming for the Scheduling of Road Maintenance'. The research focused on the maintenance of New Zealand's locally controlled roads, which is primarily funded by Transfund New Zealand.
Transfund New Zealand is overseeing New Zealand local authorities implement a pavement management system, dTIMS. This system uses a heuristic to determine a good maintenance schedule for a group of roads, over a user defined planning horizon. In contrast to dTIMS, the model developed in the course of this project uses linear programming (LP) to determine an optimal pavement maintenance schedule. This model is called SDC_OPMS.
SDC_OPMS is based on Mytton and Meaclem's prototype PMS. They proposed aggregating roads of the same road type (primary, secondary, tertiary, and feeder), traffic volume category, and road condition category, into individual variables that were to have maintenance m, carried out in year t. Of these defining attributes, traffic volume and road condition indicators are naturally ratio data and therefore must be categorised. The categorisation of data inherently removes a degree of accuracy in the model. The number of categories for each data type is therefore a trade-off of the level of detail and the model size.
Due to the solvers capacity, the model size and hence the level of detail had to be restricted. The lack in detail is the fundamental weakness of Mytton and Meaclem's prototype. This has motivated the modifications that have been made to the prototype: advanced linear programming techniques have been applied to increase its efficiency and solving capacity; and the effectiveness of the level of detail has been enhanced using statistical techniques.
Mytton and Meaclem's formulation had an inherent network structure, a simplified section of which is illustrated in figure 1.
The formulation requires that the area of roads entering state A in time t (node X), as a result of the appropriate maintenance treatments on roads in condition A, B, C, and D in time (t-1) equal the area of roads that go from node X, to state A, B, C, and D in time (t+1).
This structure has been explicitly coded using AMPL's node and arc notations, to clarify the structure to model users and the solver. The solver can then apply a network LP algorithm, reducing solving time.
Extensions have been made to the network structure to consider the budget and service level targets. These have been included in the model as side constraints.
Exploiting the benefits of a pure network structure, the model was decomposed into pure network sub-problems with relaxed side constraints. Although this does improve the efficiency of the model, the primary reason for decomposing the model was to increase the solving capacity of the model.
The model is decomposed by decomposition-based pricing, an explicit form of decomposition by column generation. This technique essentially breaks the model into a number of relaxed sub-problems. If a particular variable is in the solution of a sub-problem, then this variable becomes a contender to be in the solution of the master-problem. The technique iterates, continually adding more variables as possible contenders for the solution, until the optimal solution is found.
(Back to top)
As the level of detail considered in the model is restricted, analysis has been undertaken on key areas of the data, to ensure that the level available is used in the most effective way. The key areas were identified as the comprehensiveness of the road condition indicators, and the degree to which traffic volume categories represent reality.
A road's traffic volume is naturally ratio data. To effectively categorise this data hierarchical cluster analysis was performed. Hierarchical cluster analysis seeks to form categories so that the variance within all categories is minimised. This increases the categories’ representation of reality (Southland), and minimises the loss in detail that occurs when transforming the data from ratio data to categorical data.
Mytton and Meaclem's prototype is restricted to a one-dimensional road condition measure. The measure of road condition used is IRI, as it is the primary indicator of a road’s service level. However, to model the overall condition of a road section over a period of time adequately, at a minimum, the structural number should also be considered.
To provide a more complete view of a roads condition in SDC_OPMS, eight key road condition indicators were compressed into their underlying factors using principal components analysis (PCA). PCA was performed on a demo data set, finding two factors that predict 78% of the overall variation in the data set's eight road condition indicators.
Further output from PCA enabled the conversion between the eight road condition indicators and the two factors.
A fundamental component of a PMS, is modelling a road's change in state as a result of a maintenance option (including 'do nothing'). Most maintenance types reset a road's state to a constant condition. However, a small number of these resets are dependant on the initial state of the road.
The prediction of the change of state of a road to which no maintenance is applied is a complicated process, involving numerous parameters. In SDC_OPMS, each combination of factors and roughness levels were converted to individual variables. These variables were then deteriorated using dTIMS's road deterioration models. The deteriorated variables were then converted back into factors. The resulting state changes of each combination of factors and roughness were tabulated, and called from SDC_OPMS.
(Back to top)