مقاله انگلیسی رایگان در مورد مشکل تعمیر راه آهن تصادفی مسیریابی تاکتیکی

مقاله سال ۲۰۱۶

 مجله امگا – Omega

Development of an efficient plan for preventive maintenance is crucial in many fields [28,30,19]. The plethora of activities for which preventive maintenance must be scheduled includes railway transportation. To ensure a good daily service in terms of punctuality and safety, railway infrastructure managers have to plan and perform maintenance operations for whole railway networks. Most of these operations involve preventive maintenance at a tactical level within a medium time horizon, usually of 1 year. The aim of preventive maintenance activities is to control track failure probability to guarantee a stable and safe service and minimize maintenance costs. ACEM-Rail [26] is a European project to improve the optimization and automation of railway infrastructure maintenance. One of the objectives of the ACEM-Rail project is to develop new algorithms for efficient planning of railway infrastructure maintenance tasks based on stochastic data drawn from predictions. Several studies have addressed railway maintenance planning. Cheung et al. [9] studied the railway track possession assignment problem (RTPAP) using constraint satisfaction. The problem involves assigning railway tracks to scheduled maintenance tasks according to the satisfaction of a set of constraints. The aim of the RTPAP is to produce a plan that maximizes the assignment of jobs with the highest priority. To effectively achieve this goal, an engineering work track possession assignment system based on the CHIP constraint programming language [27] substituted manpower used to find a manual solution for the RTPAP. The performance of the system was ten times more efficient than the manual method, and its solutions are free of human errors. Budai et al. [6,7] proposed a preventive maintenance scheduling problem in which routine activities and projects were scheduled within a given time horizon by minimizing possession costs. The authors provided an integer programming model for the problem and proved that it is NP-hard. Moreover, they provided three fast but simple heuristics. To reduce the gap yielded by these heuristics, Budai et al. [8] tackled the same problem using genetic and memetic algorithms. van Zante-de Fokkert et al. [29] studied a problem in which the whole network was divided into basic working zones named single-track grids. The authors proposed a method yielding a maintenance schedule in two phases. Moreover, they provided a mixed integer programming model with a lexicographic objective function that first minimizes the number of nights (i.e., the length of the plan) and then the sum of the maximum workloads scheduled.

Although these methods efficiently address railway maintenance planning at a tactical level, they deal with a known set of maintenance tasks to be scheduled within a given time horizon. However, within the predictive setting of the ACEM-Rail project, future track conditions are not known in advance and the development of the deterioration process can be only predicted. Therefore, maintenance tasks are affected by uncertainty resulting from unknown deterioration processes. The resulting problem involving creation and solution of an efficient adaptive maintenance plan to minimize overall costs when maintenance tasks are not known a priori but subject to uncertainty is the Stochastic Tactical Railway Maintenance Problem (STRMP). We call the deterministic STRMP subproblem that the infrastructure manager has to solve in each month of the rolling horizon Deterministic Tactical Railway Maintenance Problem (DTRMP). Very little has been proposed so far in the literature to address the STRMP. Heinicke et al. [16] outlined a preliminary methodology in which capacity and risk constraints are treated as soft constraints. Nevertheless, their results were limited to three instances. The aim of our study is to complete the work started by Heinicke et al. [16] and provide a formal definition of the problem, improved heuristics to address the problem, and extensive computational results. We extend the preliminary work of Heinicke et al. [16] with a number of contributions. We provide a formal definition of the problem setting for both the STRMP and the DTRMP. Moreover we formulate an integer linear programming model for the DTRMP and treat capacity and risk constraints as hard constraints. The STRMP and the DTRMP show a number of analogies with the bin packing problem (BPP) [18], in particular with one of the latest variants, namely the stochastic generalized BPP (SGBPP) [22], and its deterministic variant, the generalized BPP (GBPP) [2]. Using a linear model and exploiting the analogies with these BPPs, we present three efficient heuristics that can address the DTRMP. The first heuristic, named ADAPTED FIRST FIT DECREASING (AFFD), is an adaptation of the FIRST FIT DECREASING (FFD) heuristic [18], which is widely used for BPPs. The second heuristic is a GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE (GRASP), which uses the AFFD heuristic in each iteration of the algorithm. The last heuristic is a GENETIC ALGORITHM (GA) that uses the GRASP in the initialization phase and the AFFD heuristic in each iteration of the algorithm. We also present extensive computational results for 40 instances, each consisting of 36 plans, for a 3-year overall rolling horizon.

The remainder of the paper is organized as follows. In Section 2 we define the STRMP. Section 3 describes the DTRMP and the three heuristics developed to address it. In Section 4 we present computational results. Section 5 concludes. 2. The Stochastic Tactical Railway Maintenance Problem The STRMP involves scheduling of predictive and preventive maintenance activities within a given time horizon (planning horizon) over a long-term rolling horizon. The goal is to bring the degradation process under control by performing appropriate maintenance activities at minimum cost. A set of maintenance activities, called warnings, is assigned to resolve a set of glitches on the track. Each warning can be assigned to a temporal portion of the planning horizon, called a time slot. In general, one glitch can be resolved by more than one warning. The final assignment of warnings to time slots is called a plan. Each warning is characterized by a cost, an amount of resources for resolving the warning, and a risk. Depending on the maintenance carried out, warnings can be at different degradation levels. The degradation process for warnings is modeled using a set of degradation levels and a Markov chain that defines the transition between the degradation levels. Therefore, the cost, the resource requirement, and the warning risk depend on the degradation level for a given warning. Because of the different probabilities for the degradation levels in the time slots, the above values also depend on the time slot in which a warning is allocated. Each time slot is characterized by the resource amount available to resolve assigned warnings