- Title
- The network maintenance problem
- Creator
- Charkhgard, Parisa
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2020
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- In this thesis, we describe an optimisation problem motivated by the need to maintain infrastructure networks over time. We consider infrastructure networks in which a product is transported between distinct origin-destination pairs, and at the same time the infrastructure assets need to be maintained by resources moving in the network. In order to perform maintenance the assets have to be shut down from time to time which potentially reduces the system capacity in those time periods. The objective is to maximise the total throughput of product by aligning the maintenance activities appropriately. This problem combines flow maximisation with maintenance scheduling capturing some important aspects of the motivating practical problem: (1) the interaction between the utilisation of network assets such as nodes and arcs, and their maintenance demands; (2) the limited number of resources available to perform the maintenance; and (3) the time taken to move maintenance resources between different locations in the network. Depending on the application context, there are a number of natural ways to reflect these in a mathematical model, and this gives rise to a rich and challenging optimisation problem which we call the network maintenance problem. In this thesis, we formally introduce the problem, present a mixed integer linear programming formulation, and prove that even a simple variant of the problem with a single origin-destination pair and unrestricted resource movement is already NP-hard. Next, we study a number of variants of the problem in which the network has a special structure. More precisely, we focus almost completely on the case where the network is a path (with the exceptions of Sections 3.1 and 6.3. The problems that we study are of interest for the following reasons. Firstly, they generalise variants of well-studied problems in the literature such as the lot-sizing problem and the warehouse problem. Secondly, we believe that understanding these special cases will be useful in tackling more general variants of the network maintenance problem. In this thesis, we focus on designing efficient algorithms to solve these problem variants and identifying the ones whose optimal objective value can be computed in polynomial time. Furthermore, we study the polyhedral structure of some of these variants and present compact perfect extended formulations which can be solved in polynomial time.
- Subject
- infrastructure networks; optimisation problems; maintenance activities; system capacity
- Identifier
- http://hdl.handle.net/1959.13/1416256
- Identifier
- uon:37021
- Rights
- Copyright 2020 Parisa Charkhgard
- Language
- eng
- Full Text
- Hits: 546
- Visitors: 1100
- Downloads: 623
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Thesis | 2 MB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Abstract | 201 KB | Adobe Acrobat PDF | View Details Download |