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

Hanyu Gu; Hue Chi Lam; Yakov Zinder

doi:10.3934/jimo.2020177

Article Contents

2022, Volume 18, Issue 2: 747-772. Doi: 10.3934/jimo.2020177

This issue Previous Article Perturbation of Image and conjugate duality for vector optimization Next Article Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems

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

School of Mathematical and Physical Sciences, University of Technology Sydney, 15 Broadway, Ultimo, NSW 2007, Australia

^* Corresponding author
^* Corresponding author

Received: December 31, 2019

Revised: August 31, 2020

Early access: December 2020

Published: March 2022

Abstract Full Text(HTML) Figure(1) / Table(11) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 90B36, 90C59.

Citation:

Full Text(HTML)

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 $

Download: Full-size image PowerPoint slide

Table 1. Parameters for the train types.

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Table 4. Comparison of the performance of MIPM and MILP

Case	LB	MIPM			MILP
Case	LB	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

| Show Table

DownLoad: CSV

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

Case	MIPM-LS1			MILP-LS1
Case	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

| Show Table

DownLoad: CSV

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

Case	MIPM-SLS			MILP-SLS
Case	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

| Show Table

DownLoad: CSV

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

Case	In. Obj.	Time	Hybrid ILS with LS1		Hybrid ILS with $ {\text{LS1}}^{'} $
Case	In. Obj.	Time	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

| Show Table

DownLoad: CSV

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

Case	In. Obj.	Time	hybrid ILS with SLS		hybrid ILS with $ {\text{SLS}}^{'} $
Case	In. Obj.	Time	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

| Show Table

DownLoad: CSV

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

Case	multi-start ILS with LS1				multi-start ILS with $ {\text{LS1}}^{'} $
Case	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

| Show Table

DownLoad: CSV

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

Case	multi-start ILS with SLS				multi-start ILS with $ {\text{SLS}}^{'} $
Case	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

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.