White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Optimisation for Large-scale Maintenance, Scheduling and Vehicle Routing Problems

Chen, Yujie (2017) Optimisation for Large-scale Maintenance, Scheduling and Vehicle Routing Problems. EngD thesis, University of York.

This is the latest version of this item.

Thesis2.pdf - Examined Thesis (PDF)
Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (5Mb) | Preview


Solving real-world combinatorial problems is involved in many industry fields to minimise operational cost or to maximise profit, or both. Along with continuous growth in computing power, many asset management decision-making processes that were originally solved by hand now tend to be based on big data analysis. Larger scale problem can be solved and more detailed operation instructions can be delivered. In this thesis, we investigate models and algorithms to solve large scale Geographically Distributed asset Maintenance Problems (GDMP). Our study of the problem was motivated by our business partner, Gaist solutions Ltd., to optimise scheduling of maintenance actions for a drainage system in an urban area. The models and solution methods proposed in the thesis can be applied to many similar issues arising in other industry fields. The thesis contains three parts. We firstly built a risk driven model considering vehicle routing problems and the asset degradation information. A hyperheuristic method embedded with customised low-level heuristics is employed to solve our real-world drainage maintenance problem in Blackpool. Computational results show that our hyperheuristic approach can, within reasonable CPU time, produce much higher quality solutions than the scheduling strategy currently implemented by Blackpool council. We then attempt to develop more efficient solution approaches to tackle our GDMP. We study various hyperheuristics and propose efficient local search strategies in part II. We present computational results on standard periodic vehicle routing problem instances and our GDMP instances. Based on manifold experimental evidences, we summarise the principles of designing heuristic based solution approaches to solve combinatorial problems. Last bu not least, we investigate a related decision making problem from highway maintenance, that is again of interest to Gaist solutions Ltd. We aim to make a strategical decision to choose a cost effective method of delivering the road inspection at a national scale. We build the analysis based on the Chinese Postman Problem and theoretically proof the modelling feasibility in real-world road inspection situations. We also propose a novel graph reduction process to allow effective computation over very large data sets.

Item Type: Thesis (EngD)
Academic Units: The University of York > Computer Science (York)
Identification Number/EthosID: uk.bl.ethos.703384
Depositing User: Miss Yujie Chen
Date Deposited: 14 Feb 2017 11:16
Last Modified: 24 Jul 2018 15:21
URI: http://etheses.whiterose.ac.uk/id/eprint/16107

Available Versions of this Item

  • Optimisation for Large-scale Maintenance, Scheduling and Vehicle Routing Problems. (deposited 14 Feb 2017 11:16) [Currently Displayed]

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)