A mathematical programming model to select maintenance strategies in railway networks

Highlights

• A nonlinear integer program is given to select maintenance strategies for railways.

• A tailored heuristic enables fast solution to be found with standard solvers.

• A tailored relaxation method enables the quality of the solution to be quantified.

• Metrics of topology, availability, service, costs are combined in a holistic approach.

• Effects of tracks redundancy, centrality, train frequency, availability are studied.

Abstract

This paper presents a nonlinear integer programming model to support the selection of maintenance strategies to implement on different segments of a railway network. Strategies are selected which collectively minimise the impact of sections’ conditions on service, given network availability and budget constraints. Different metrics related to the network topology, sections’ availability, service frequency, performance requirements and maintenance costs, are combined into a quantitative approach with a holistic view. The main contribution is to provide a simple yet effective modelling approach and solution method which are suitable for large networks and make use of standard solvers. Both an ad hoc heuristic solution and relaxation methods are developed, the latter enabling the quality of the heuristic solution to be estimated. The availability of railway lines is computed by exploiting the analogy with series–parallel networks. By varying the model parameters, a scenario analysis is performed to give insight into the influence of the system parameters on the selection of strategies, thus enabling more informed decisions. For its simple structure, the model is versatile to address similar problems arising in the maintenance of other types of networks, such as road and bridges networks, when deciding on the strategic allocation of maintenance efforts.

Introduction

Infrastructure asset maintenance for transportation networks is a complex decision making process involving the allocation of limited maintenance resources to achieve a trade-off between costs and service performance. Railway networks are an example of large scale transportation networks consisting of a variety of heterogeneous assets spatially distributed and interdependent. The network topology coupled with the operational use of the infrastructure are such that a failure of an individual section might affect the availability of an entire line.

Maintenance planning is addressed at strategic, tactical and operational level. Strategic maintenance planning involves first, at asset level (e.g. track, signalling and telecoms, bridges, earthworks, electrical power), the development of maintenance strategies which define fixed rules to maintain the assets. These rules include type of inspection and its frequency, the waiting time to maintenance, the thresholds on time, age, usage and/or conditions which trigger maintenance actions with different levels of urgency. Then, at network level, strategies must be chosen for different network segments. Maintenance strategies as defined above, form the basis for the planning of maintenance activities and intervention programs defined at tactical and operational planning levels, which govern the maintenance operations.

This paper introduces an optimisation model based on mathematical programming to support the selection of the maintenance strategies to implement on different regions of a railway network. The resulting combination of strategies enables to obtain the best value from the assets from a network perspective. Its intended use is subsequent to the development of the actual strategies, which are here given as input to the model. The model is performance-oriented, it assumes that decisions are aimed at minimising the expected number of trains per time unit affected by a speed restriction, while availability targets for different railway lines have to be met and budget constraints have to be respected. The main contribution of this paper is to present a simple yet effective modelling approach and solution method which are suitable for large networks and make use of standard solvers, thus making its use in practice more attractive. From a modelling perspective, the value of the proposed model is to provide a quantitative approach which combines different metrics related to the network topology, sections availability, service frequency, performance requirements and maintenance costs, in a holistic view with a clear and simple structure rather than a black box. As the approach is quantitative in nature, a wide study of the sensitivity of the solution with respect to the model parameters is performed. The value of this study is to give insight on the relative and combined contribution of different factors on the selection of strategies. These factors include track redundancy, centrality of sections, service frequency, budget and lines availability targets. The final contribution of this paper is to have developed both a heuristic solution approach and an ad hoc relaxation method, thus enabling the quality of the heuristic solution to be estimated. The model addresses a real problem in practice faced by infrastructure owners/managers related to the strategic maintenance planning of their networked infrastructures. Although the model is developed and demonstrated here for a railway network, its simple structure makes it versatile and suitable to address similar problems arising in the maintenance of other types of networks when deciding on the strategic allocation of maintenance efforts. Examples are road and bridges networks, where long-term maintenance strategies must be chosen for individual or groups of road segments or bridges respectively.

Literature proposes different optimisation models to support maintenance planning for different infrastructures and planning levels. A recent overview of the literature on asset management and maintenance of multi-unit systems is given in [1], [2], and previously in [3], [4]. The survey in [1] distinguishes between contributions dealing with multi-component and multi-asset systems, focusing more specifically on the latter. While authors usually refer to multi-component systems to describe a single asset (e.g. a machine or a bridge) and its constituent components, multi-asset systems are systems of multiple assets otherwise connected. The present paper focuses on this last category.

In the infrastructure sector, maintenance planning of systems of assets mainly focuses on the optimisation of sequential decisions. Typically these decisions concern the selection of one or more interventions out of a given set based on the current state of the assets. Example of interventions are rehabilitation, renovation, routine maintenance, or do nothing. Decisions are often constrained by limited budgets and capacity targets, while the objective is to optimise either maintenance costs and/or some measure of the system performance. The authors in [5] address the problem of planning maintenance for a system of heterogeneous assets undergoing stochastic deterioration over a finite time horizon. They develop a two-stage bottom-up approach. First, the optimal maintenance activities are determined for each asset among a set of feasible interventions. Then, a system-level optimisation selects the best combination of interventions given budget constraints. All assets in the system are independent except for the shared budget. A similar approach has been used in [6] with application to a hypothetical railway system. A number of assets are associated to each link in the network, each with a set of available maintenance activities. For each asset the best activity is obtained by solving a Markov decision problem via dynamic programming. At system-level the budget constraint includes the cost reduction achieved through opportunistic maintenance of adjacent assets. A threshold on the minimum capacity to be guaranteed between an origin and a destination node is also imposed. In [7], the authors develop a model with the objective of determining the optimal set of maintenance interventions for a system of bridge decks. Again, they suggest a two-step approach where they use the optimal cost of maintenance and replacement for each bridge resulting from a facility-level optimisation problem previously defined in [8]. Then, at system level, they select the optimal combination of maintenance and replacement activities which minimise the probability of system failure subject to budget constraints. A two-stage bottom-up optimisation approach is proposed in [9] for timely maintenance planning in heterogeneous systems. The specific maintenance action and time of execution are optimised per component based on a system perspective. The approach is demonstrated with application to a simple imaginary railway network. In a more recent contribution [10] the budget allocation and maintenance planning problem for multi-asset systems is addressed again as a finite-horizon Markov decision process for each individual asset. Then the system level optimisation is formulated as an integer programming problem which minimise the total expected maintenance cost of all assets under a budget constraint formulated for each decision period. The shared budget is the only interaction considered across the facilities. The problem is nonlinear, and a standard linearisation method based on auxiliary binary variables is adopted. Through Lagrangian relaxation of the budget constraint, the system-level optimisation can be decomposed into multiple Markov decision problems, one for each asset, and a lower bound to the primal problem is obtained. This decomposition approach is only possible because the shared budget is the only dependency among facilities. A linear optimisation model is presented in [11] to determine optimal intervention programs consisting of the interventions to be performed each year over a finite time horizon for a system of assets. The above mentioned contributions all focus on sequential decision making and formulate the problem as a Markov decision process, mostly solved via dynamic programming. The sequence of interventions to be executed for each asset per time interval (e.g. each year) during a finite time horizon is obtained. All models assume knowledge of the state of the asset following intervention.

In [12] and [13] the authors address a similar problem as the above cited contributions but with a different modelling approach. They aim at determining optimal intervention programs for railway networks with multiple assets, where interventions are selected among a given set under budget and structural constraints. They adopt a network flow model approach resulting in a mixed integer linear program which is solved via the simplex and branch and bound methods. Interventions are selected based on their cost, duration and reduction of failure risk. The approach is extended in [14] which focuses particularly on the estimation of intervention costs and the effects of intervention programs on service.

Other maintenance planning problems for multi-asset systems appearing in the literature deal with the prioritisation of assets interventions, the grouping of works and the scheduling of maintenance activities. In [15] a linear integer programming model is proposed for the scheduling of preventive small routine maintenance activities and major jobs on a single railway link. The dynamic grouping and scheduling of maintenance activities for multi-component systems is addressed in [16], [17]. Jobs are grouped together to minimise possession costs based on given maintenance frequency and which routine jobs can be combined. The optimal grouping of components is also addressed in [18] in the context of preventive maintenance of multi-component systems via a multi-level preventive decision-making model. A maintenance grouping approach for a series system with availability constraints is proposed in [19], where the maintenance planning is updated in a dynamic context. A multi-objective optimisation model is presented in [20] for scheduling renewal works of ballast, rails and sleepers while seeking a trade-off between life-cycle costs and the track availability. The problem is solved via a genetic algorithm. The optimisation of maintenance schedule for railway power supply system is addressed in [21], [22] where the authors develop a biobjective optimisation model which considers the trade-off between reliability and maintenance costs. A biobjective optimisation model is also presented in [23] to optimise planned maintenance and renewal activities for track geometry. The model determines whether a track section is tamped or renewed in a given trimester or not, and what level of speed restriction is imposed. The contributions reviewed above address maintenance planning problems at a tactical and/or operational level.

At a strategic level instead, a typical problem is to determine long-term maintenance policies defining the fixed rules for inspection and maintenance such as inspection frequency and condition (or alternatively age or usage) thresholds triggering interventions. In [24] a non-homogeneous Markov model solved via a numerical procedure is used to determine the probability of rail cracks, and it is combined with a Genetic Algorithm to find rail inspection intervals and waiting time for maintenance which minimise both costs and the probability of rail cracks. In [25] the authors consider a series–parallel systems of components of different types. They use a Markov model to describe the degradation and on-condition maintenance processes, and recour to Monte Carlo simulation to obtain the average system availability and the probability of being under maintenance at any given time t. A genetic algorithm is then used to find the maintenance thresholds per component type, which simultaneously optimise profit from system operation and system availability. In [26] a life-cycle cost model is proposed to investigate tamping and track renewal strategies to minimise ballast life-cycle costs. In particular, an iterative search algorithm is used to determine the best strategy among a set of alternatives including fixed intervals or fixed condition’s thresholds triggering a tamping intervention. A similar decision problem is addressed in [27] for multi-component systems, where the optimal frequency of scheduled visits and the preventive maintenance threshold for a component within a series system are sought. Here renewal theory is used to evaluate the long-term average maintenance costs, and an iterative procedure is used to find the near optimal values of visits’ frequency and maintenance thresholds that minimise the long-term average cost. The above contributions look at the development of maintenance strategies by optimising maintenance parameters such as inspection intervals and maintenance thresholds simultaneously for multiple components within a system. However they assume that the “structure” of a maintenance strategy is the same for all component types, and the only difference is in the values taken by the maintenance parameters.

This paper can be framed among those works aiming at the selection of long-term maintenance strategies for multi-asset systems with a networked structure. However, unlike the above contributions, it presents an approach that allows for fundamentally different maintenance strategies to be compared based on their costs and resulting availability and level of performance of the assets. Indeed in reality, the assets comprising an infrastructure system are quite diverse and complex, and this reflects into equally diverse and complex maintenance strategies. From here the choice to separate the problem of developing individual strategies, from the one of selecting the best strategies to be used in combination for a network of assets and allocate the maintenance budget accordingly. This paper focuses on the latter problem, thus contributing to the wider literature of portfolio decision analysis which aims at supporting decisions for the selection of projects and the allocation of resources [28]. Recent contributions to portfolio decision analysis in infrastructure maintenance are [29], [30]. In [29], a sequential portfolio selection approach on a multi-period horizon is presented to identify the optimal risk-based maintenance portfolios for gas networks. The maintenance portfolio consists of a set of pipe segments which will undergo complete replacement. The problem of allocating prognostic and health management capabilities in power transmission networks to maximise the network global reliability efficiency under budget constraints is addressed in [30].

In the present paper, given a portfolio of potential maintenance strategies and a network of assets, one wants to select the strategies that collectively enable a trade-off between maintenance costs, system availability and service impact. This corresponds to allocate maintenance efforts among different sections of the network. The problem is formulated here for a railway network and is modelled via mathematical programming. A nonlinear combinatorial optimisation problem is presented, where the nonlinearities are due to the availability constraints imposed on railway lines which account for the network topology. It further develops the work in [31] by refining an ad hoc linearisation approach to approximate the optimal solution from above, and by presenting a relaxation method to quantify the quality of the solution and therefore the performance of the proposed heuristic. The model takes into account economic, functional and operational dependencies between different sections of the network by considering a shared limited budget, and by making use of reliability network theory to model the contribution of individual track sections to the availability of railway lines along which service run. The model requires the knowledge of the effects of each strategy on the long-term behaviour of the assets. Input to the model can be given by state-based models as suggested in [31], which combine degradation and maintenance processes to predict the long-term assets response to maintenance strategies. Petri nets [32] can be used to this aim, as they can assess the probabilities of different states of interest, including section closures and speed restrictions, as well as the average work volumes (see e.g. [33], [34], [35], [36] for railway tracks and bridges). Alternative methods which model the assets as multi-state systems (e.g. [37], [38], [24]) can serve the same purpose, as well as historical data.

The rest of the paper is organised as follows. After providing the problem description and problem statement in Section 2, the model is presented in Section 3, where the approach to model the unavailability of railway lines based on the theory of reliability networks is described. Then Section 4 provides the solution approach, including both the method developed to find an approximate solution and a lower bound to estimate the quality of the approximate solution. Finally the proposed modelling and solution methods are tested through a wide scenario analysis on an illustrative example considering a real portion of the UK railway network.