Linear Programming for the Scheduling of Road Maintenance for Transfund New Zealand

MANAGEMENT SCIENCE HONOURS PROJECT 2000

Brad Mytton & David Meaclem

Winner of THE PDL PRIZE IN MANAGEMENT SCIENCE / MANUFACTURING AND OPERATIONS MANAGEMENT in 2000.

This prize was established in 2000 by PDL Holdings Limited for the best project at 400-level in Management Science or Production and Operations Management.

Transfund New Zealand is the national body responsible for the allocation of road maintenance funds to the Local and City Councils’ of New Zealand. Transfund are presently trialling a new heuristic-based software package for scheduling road maintenance. A research project undertaken by students from the 1999 Management Science Honours class of the University of Canterbury concluded that the heuristic used in the software package was quite simplistic and limited by the number of possible maintenance schedules a solution was selected from. As a result, it was proposed that the scheduling of road maintenance throughout New Zealand be done using optimisation, namely linear programming.

Initially the linear program (LP) has been modelled for Christchurch City with a 15-year planning horizon. This linear program is formulated in such a way that the model is the same size, whether the area solved for is small or large. Therefore it is hoped that, in time, all road maintenance in New Zealand can be optimised at once with this formulation.

Solutions to the LP solved for the Christchurch roading network are limited, as the structure of the roads is excluded. As a result, the solution strategies derived do not represent the problem adequately enough to draw accurate conclusions about optimal treatment strategies. However, considerable insight has been gained into how this problem could be modelled, and the results produced.

A proposed formulation with the structure included has been solved on a fictional data set, as the structural number data (an index measuring a road’s strength) is not currently available. The inclusion of structure, however, limits the number of road types and years the model can be solved for because of a variable limit of the solver. With current means, the largest solvable model is for one road type over eight years. Further, a decomposition based on column generation is suggested as a good way to increase the solving capacity.

We believe this formulation can give superior results for scheduling road maintenance, once the appropriate data, and solver capacity is available.

Proposed formulation...  Back to Management Science Honours Project page...

Page updated: 1 November 2000.