Article Contents
Article Contents

# Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center

• * Corresponding author
• A railway network is an indispensable part of the public transportation system in many major cities around the world. In order to provide a safe and reliable service, a fleet of passenger trains must undergo regular maintenance. These maintenance operations are lengthy procedures, which are planned for one year or a longer period. The planning specifies the dates of trains' arrival at the maintenance center and should take into account the uncertain duration of maintenance operations, the periods of validity of the previous maintenance, the desired number of trains in service, and the capacity of the maintenance center. The paper presents a nonlinear programming formulation of the considered problem and several optimization procedures which were compared by computational experiments using real world data. The results of these experiments indicate that the presented approach is capable to be used in real world planning process.

Mathematics Subject Classification: 90B36, 90C59.

 Citation:

• Figure 1.  Heat maps displaying the probability of having more than 5 train-sets residing in the maintenance center for each day across the planning horizon of one year for cases (A) $\alpha = 1$, $\beta = 1000$; and (B) $\alpha = 1$, $\beta = 1$

Table 1.  Parameters for the train types.

 Train type $k$ $|F^k|$ $\tau_k$ $C_{kt}$ non-PH PH 1 25 4 3 1 2 5 5 2 1 3 5 5 1 1

Table 2.  Parameters of probability distribution for cycle time by train types.

 Train type Minimum Most likely Maximum Distribution 1 20 25 40 beta-PERT 2 27 30 46 beta-PERT 3 29 30 52 beta-PERT

Table 3.  Assignment of $\alpha$ and $\beta$ for all the cases.

 Case $\alpha$ $\beta$ Case $\alpha$ $\beta$ 1 1 1000 6 1 100 2 1 300 7 1 50 3 1 200 8 1 10 4 1 180 9 1 1 5 1 150

Table 4.  Comparison of the performance of MIPM and MILP

 Case LB MIPM MILP Time Obj. %Rel Time Obj. %Rel 1 156, 744 2, 078 206, 060 31.46 7 201, 203 28.36 2 62, 612 235 77, 764 24.20 7 80, 353 28.33 3 48, 629 68 59, 178 21.69 8 59, 103 21.54 4 45, 768 100 55, 368 20.98 8 56, 322 23.06 5 40, 190 54 48, 447 20.54 11 49, 369 22.84 6 30, 789 46 36, 245 17.72 8 36, 572 18.78 7 20, 940 41 23, 624 12.82 8 23, 337 11.45 8 10, 594 39 10, 753 1.50 8 10, 818 2.11 9 6, 706 38 6, 725 0.28 8 6, 748 0.63 Average 46, 997 300 58, 240 16.80 8 58, 203 17.46

Table 5.  Improvements in solution quality of MIPM and MILP by the local search LS1.

 Case MIPM-LS1 MILP-LS1 LS Time Obj. %Rel LS Time Obj. %Rel 1 46.32 189, 551 20.93 19.59 192, 637 22.90 2 44.29 72, 584 15.93 32.72 75, 368 20.37 3 36.11 56, 483 16.15 46.72 55, 102 13.31 4 28.95 53, 125 16.07 60.71 51, 999 13.61 5 67.76 42, 884 6.70 46.84 44, 547 10.84 6 22.06 32, 971 7.09 13.01 35, 356 14.83 7 7.44 22, 948 9.59 26.11 22, 905 9.38 8 10.56 10, 752 1.49 15.11 10, 793 1.88 9 6.89 6, 724 0.27 6.85 6, 732 0.39 Average 30.04 54, 225 10.47 29.74 55, 049 11.95

Table 6.  Improvements in solution quality of MIPM and MILP by the sequential local search SLS.

 Case MIPM-SLS MILP-SLS LS Time Obj. %Rel LS Time Obj. %Rel 1 879 189, 551 20.93 2, 366 190, 584 21.59 2 871 72, 584 15.93 3, 593 72, 868 16.38 3 884 56, 483 16.15 931 54, 766 12.62 4 802 53, 125 16.07 3, 245 51, 208 11.89 5 862 42, 884 6.70 3, 589 44, 173 9.91 6 838 32, 971 7.09 3, 592 34, 911 13.39 7 3, 196 22, 631 8.08 899 22, 905 9.38 8 699 10, 752 1.49 687 10, 793 1.88 9 708 6, 724 0.27 749 6, 732 0.39 Average 1, 082 54, 189 10.30 2, 183 54, 327 10.82

Table 7.  Performance of hybrid ILS with LS1 and ${\text{LS1}}^{'}$.

 Case In. Obj. Time Hybrid ILS with LS1 Hybrid ILS with ${\text{LS1}}^{'}$ Obj. %Rel Obj. %Rel 1 206, 060 2, 685 189, 487 20.89 180, 530 15.17 2 77, 764 864 71, 715 14.54 67, 092 7.16 3 59, 178 581 55, 624 14.38 51, 344 5.58 4 55, 368 932 50, 780 10.95 47, 803 4.45 5 48, 447 805 42, 416 5.54 41, 666 3.67 6 36, 245 472 32, 828 6.62 32, 371 5.14 7 23, 624 817 22, 494 7.42 22, 948 9.59 8 10, 753 483 10, 752 1.49 10, 752 1.49 9 6, 725 355 6, 724 0.27 6, 724 0.27 Average 58, 240 888 53, 647 9.12 51, 248 5.84

Table 8.  Performance of hybrid ILS with SLS and ${\text{SLS}}^{'}$.

 Case In. Obj. Time hybrid ILS with SLS hybrid ILS with ${\text{SLS}}^{'}$ Obj. %Rel Obj. %Rel 1 206, 060 3, 600 187, 992 19.94 179, 847 14.74 2 77, 764 2, 482 70, 845 13.15 66, 967 6.96 3 59, 178 1, 640 55, 100 13.31 51, 324 5.54 4 55, 368 2, 281 51, 459 12.43 47, 785 4.41 5 48, 447 2, 496 42, 193 4.98 41, 432 3.09 6 36, 245 1, 634 32, 968 7.08 32, 371 5.14 7 23, 624 1, 413 22, 613 7.99 22, 948 9.59 8 10, 753 1, 191 10, 752 1.49 10, 752 1.49 9 6, 725 1, 078 6, 724 0.27 6, 724 0.27 Average 58, 240 1, 979 53, 405 8.96 51, 128 5.69

Table 9.  Performance of multi-start ILS with LS1 and ${\text{LS1}}^{'}$.

 Case multi-start ILS with LS1 multi-start ILS with ${\text{LS1}}^{'}$ Time In. Obj. Obj. %Rel Time In. Obj. Obj. %Rel 1 2, 904 731, 900 200, 646 28.01 3, 600 701, 192 221, 792 41.50 2 3, 206 246, 939 76, 713 22.52 3, 600 228, 459 82, 564 31.87 3 3, 525 205, 225 56, 717 16.63 3, 600 161, 630 62, 662 28.86 4 3, 101 157, 225 52, 039 13.70 3, 600 141, 340 57, 548 25.74 5 2, 946 155, 164 46, 623 16.01 3, 600 115, 812 48, 889 21.65 6 2, 996 110, 872 35, 309 14.68 3, 600 97, 424 39, 585 28.57 7 2, 736 80, 850 23, 722 13.29 3, 600 60, 620 29, 355 40.19 8 2, 548 50, 200 11, 109 4.86 3, 600 29, 562 14, 635 38.15 9 2, 386 40, 485 6, 917 3.14 3, 600 30, 494 11, 311 68.67 Average 2, 928 197, 651 56, 644 14.76 3, 600 174, 059 63, 149 36.13

Table 10.  Performance of multi-start ILS with SLS and ${\text{SLS}}^{'}$.

 Case multi-start ILS with SLS multi-start ILS with ${\text{SLS}}^{'}$ Time In. Obj. Obj. %Rel Time In. Obj. Obj. %Rel 1 3, 600 704, 669 207, 738 32.53 3, 600 792, 732 229, 339 46.31 2 3, 600 234, 564 76, 228 21.75 3, 600 242, 8870 80, 410 28.43 3 3, 600 176, 729 55, 596 14.33 3, 600 149, 560 61, 766 27.01 4 3, 600 165, 457 52, 054 13.73 3, 600 139, 882 56, 795 24.09 5 3, 600 141, 360 45, 025 12.03 3, 600 112, 386 50, 796 26.39 6 3, 600 112, 397 35, 946 16.75 3, 600 109, 447 43, 065 39.87 7 3, 600 78, 051 23, 870 13.99 3, 600 59, 009 29, 110 39.02 8 3, 600 57, 798 11, 192 5.64 3, 600 30, 803 15, 081 42.35 9 3, 600 35, 437 6, 903 2.93 3, 600 28, 582 9, 512 41.85 Average 3, 600 189, 607 57, 173 14.85 3, 600 185, 030 63, 986 35.04

Table 11.  Summary of the effects of the different neighborhoods.

 Tables $\mathcal{N}$ $\mathcal{N}'$ EQUAL Winner 7 1 6 2 MIPM + ILS + $\mathcal{N}^{'}_1$ 8 1 6 2 MIPM + ILS + $\mathcal{N}^{'}_1$+ $\mathcal{N}^{'}_2$ 9 9 0 0 multi-start ILS + $\mathcal{N}_1$ 10 9 0 0 multi-start ILS + $\mathcal{N}_1$ + $\mathcal{N}_2$
•  [1] S. Ahmed, Two-stage stochastic integer programming: A brief introduction, in Wiley Encyclopedia of Operations Research and Management Science (eds. J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh and J.C. Smith), John Wiley & Sons, (2011). doi: 10.1002/9780470400531.eorms0092. [2] G. Bayraksan and D. P. Morton, Assessing solution quality in stochastic programs via sampling, in Informs 2009 Tutorials in Operations Research, (2009), 102-122. doi: 10.1287/educ.1090.0065. [3] P. Billingsley, Probability and Measure, 3$^rd$ edition, John Wiley & Sons, New York, 1995. [4] W. Biscarri, S. D. Zhao and R. J. Brunner, A simple and fast method for computing the Poisson binomial distribution function, Computational Statistics & Data Analysis, 122 (2018), 92-100.  doi: 10.1016/j.csda.2018.01.007. [5] K. Doganay and M. Bohlin, Maintenance plan optimization for a train fleet, in Computers in Railways XII, (eds. B. Ning and C.A. Brebbia), WIT Press, (2010), 349-358. doi: 10.2495/CR100331. [6] B. Fortz, M. Labbé, F. Louveaux and M. Poss, Stochastic binary problems with simple penalties for capacity constraints violations, Mathematical Programming, 138 (2013), 199-221.  doi: 10.1007/s10107-012-0520-4. [7] G. L. Giacco, D. Carillo, A. D'Ariano, D. Pacciarelli and A. G. Marín, Short-term rail rolling stock rostering and maintenance scheduling, Transportation Research Procedia, 3 (2014), 651-659.  doi: 10.1016/j.trpro.2014.10.044. [8] T. Homem-de Mello and G. Bayraksan, Monte Carlo sampling-based methods for stochastic optimization, Surveys in Operations Research and Management Science, 19 (2014), 56-85.  doi: 10.1016/j.sorms.2014.05.001. [9] Y. C. Lai, D. C. Fang and K. L. Huang, Optimizing rolling stock assignment and maintenance plan for passenger railway operations, Computers & Industrial Engineering, 85 (2015), 284-295.  doi: 10.1016/j.cie.2015.03.016. [10] B. Lin, J. Wu, R. Lin, J. Wang, H. Wang and X. Zhang, Optimization of high-level preventive maintenance scheduling for high-speed trains, Reliability Engineering & System Safety, 183 (2019), 261-275.  doi: 10.1016/j.ress.2018.11.028. [11] H. R. Lourenço, O. C. Martin, and T. Stützle, Iterated local search: framework and applications, in Handbook of Metaheuristics (eds. M. Gendreau and J. Potvin), 2$^nd$ edition, Springer, Boston, (2010), 363-397. [12] D. G. Malcolm, J. H. Rooseboom, C. E. Clark and W. Fazar, Application of a technique for research and development program evaluation, Operations Research, 7 (1959), 646-669.  doi: 10.1287/opre.7.5.646. [13] J. G. Pérez, M. Martín, C. García and M. Granero, Project management under uncertainty beyond beta: The generalized bicubic distribution, Operations Research Perspectives, 3 (2016), 67-76.  doi: 10.1016/j.orp.2016.09.001. [14] S. Mitchell, M. O'Sullivan and I. Dunning, PuLP: a Linear Programming Toolkit for Python, 2011. Available from: http://www.optimization-online.org/DB\_FILE/2011/09/3178.pdf. [15] C. Sriskandarajah, A. K. S. Jardine and C. K. Chan, Maintenance scheduling of rolling stock using a genetic algorithm, Journal of the Operational Research Society, 49 (1998), 1130-1145. [16] Sydney Trains, Sydney Trains Annual Report 2017-18, 2018. Available from: https://www.transport.nsw.gov.au/news-and-events/reports-and-publications/sydney-trains-annual-reports. [17] M. Waskom and the seaborn development team, mwaskom/seaborn, 2020. Available from: https://doi.org/10.5281/zenodo.592845.

Figures(1)

Tables(11)