Status
Proof-of-Concept is finished. The project is in hibernation due to the technical difficulties described in the Solution section. Other investigations are needed for further development. Follow-up work has been carried out during the UK Quantum Hackathon 2025, enabling better scaling of the solution.
FLAGSHIP PROGRAMME
Road maintenance scheduling
Summary
We developed road maintenance scheduling optimisation algorithms that reduce costs when roads are closed for regular maintenance and urgent works. They allocate work orders to different sections of a road, subject to a variety of constraints.
This is one of the quantum application discovery projects co-funded by the National Quantum Computing Centre under the SparQ programme, in collaboration with the Science and Technology Facilities Council.
The problem
The problem formulation is inspired by the real-world scheduling process for planning maintenance on the A19 highway in the UK. The planning considers different aspects simultaneously and involves fixed road closures for annual maintenance, accounting for external events, adjustments for urgent works, task dependency and team skill differences. Required resources are labour, equipment and the cost to close the road. Currently, the planning is done manually, which results in a waste of time and resources.
Solution
We simplified the problem and built scheduling optimisation algorithms in response to the demand for an automated process for more efficient road maintenance planning. Ultimately it intends to reduce the total cost, which includes labour cost and equipment transfer cost, and reduce the waiting time between jobs. Several different approaches and methods were explored, which include several classical algorithms, such as mixed integer linear programming and genetic algorithms, and quantum algorithms — in the form of unconstrained binary quadratic programming on gate-based quantum hardware.
All algorithms were tested using synthetically generated data based on real-world data. The performance of the three solvers was similar. However, because the constraints and the objective function introduce too many auxiliary variables, the algorithms presented some scalability issues that required reducing the dimensionality of the problems that could be executed on quantum gate-based hardware.