On the multi-period combined maintenance and routing optimisation problem

Figures & data

Table 1. Summary and classification of the literature review.

	Maintenance characteristics							Technician characteristics
Article	Multi-period Planning	Multi-machines	CM	PM	Random time to failure	Machines geographically distributed	Without Degradation	Scheduling (visits patterns)	Routing	Travel Times	Time Windows	Workload	Combined Maintenance and Technicians
Martinod et al. 2018	X	x	x	x	X		x
Faddoul, Raphael, and Chateauneuf 2018	X	x	x	x
Eltoukhy et al. 2018		x		x			x	x				x	x
Eltoukhy et al. 2019	X	x		x			x					x
Khatab et al. 2018		x	x	x
Wakiru et al. 2021		x	x	x	X
Gopalakrishnan, Subramaniyan, and Skoogh 2020		x	x	x		x	x
Briš et al. 2017		x	x	x	x
Foong et al. 2008	X	x	x
Zhou & Shi 2019		x		x	x
Samal and Pratihar 2015		x			x		x
Nguyen et al. 2019	X	x	x	x	x	x	x	x	x	x			x
Irawan et al. 2017	X	x	x	x				x	x	x			x
Hajej, Rezg, and Gharbi 2020	X	x	x	x
Hajej, Rezg, and Gharbi 2018				x	x		x
Hajej and Rezg 2020		x		x	x		x
Koochaki et al. 2012	X			x	x					x			x
Jbili et al. 2018	X	x	x	x	x
Ome et al. 2018	x	x	x	x	x
Adjoul et al. 2021		x	x
Ahmed, Zeghal Mansour, and Haouari 2018	x	x	x	x				x	x	x			x
Our approach	x	x	x	x	x	x	x	x	x	x	x	x	x

Figure 1. Proposed Multi-Period Combined Maintenance and Routing (MPCMR) model.

Algorithm description composed by two inputs, two outputs, and their connection between the Maintenance Model (MM) and Routing Model (RM).

Figure 2. Sample maintenance cycles with preventive and corrective maintenance operations (E. López-Santana et al. 2016).

Three cumulative functions for three different cases of maintenance.

Figure 3. Total maintenance policy cost, PM, and CM cost.

Three different graphs of the total costs, preventive maintenance, and corrective maintenance.

Figure 4. Approach to the total expected cost per unit time function with |T| = 12 periods and η = 2.

Time horizon composed by 12 time periods with a frequency of two preventive maintenance operations.

Figure 5. Column generation approach to solve the RM.

Squares describing the column generation approach with two subproblems Route generator and Visit-patterns generator and the Master Problem.

Table

Algorithm 1. Benchmark procedure to generate the pattern visits sets $R_i$.
1:	$R_i=\left\{\mathrm{\varnothing }\right\}$
2:	First step // Generate set $R_i$ using the optimal solution ${\text{β}}_{it}^{\ast }$ solving MIP model (40) – (43)
3:	for all $i\in V_c$
4:	$R_i={\text{β}}_{it}^{\ast }$
5:	end for
6:	End first step
7:	Second step // Generate set $R_i$ according to periodic visits in the planning horizon
8:	for all $i\in V_c$
9:	$t_1$ = $U\left(0,\left|\mathcal{T}\right|-{\eta }_i\right)$
10:	${\omega }_i={\displaystyle \frac{\left|\mathcal{T}\right|-t_0}{{\eta }_i}}$
11:	for all $k\in \left\{2,\dots ,{\eta }_i\right\}$
12:	$t_k=t_{k-1}+{\omega }_i$
13:	end for
14:	$R_{\left|V_c\right|+i}=\left\{t_1,..,t_k\right\}$
15:	end for
16:	End second step

Figure 6. Number of times that each customer is considered in a route and the optimal maintenance frequency.

Bar and dot graph contrasting the frequency and number of times in a route.

Figure 7. Expected waiting time before CM.

bar graph of the expected waiting times.

Figure 8. Timer period where each customer is visited (left: 5 time periods, right: 10 time periods).

Two dot graphs contrasting the period when a customer is visited with two different time periods.

Figure 9. Example of a replication of event simulation of one customer with 5 times periods and a frequency of 2 maintenance operations.

Table

Algorithm 2. Simulation procedure to evaluate the performance of a solution
1:	Input: the visit pattern set ${\text{β}}_{it}$, frequency of maintenance operations ${\eta }_i$, the maintenance execution date $s_k$ for $k=1,..,{\eta }_i$, for each customer $i\in V_c$
2:	First step // Generate for each customer a vector $f_{ik}$ of k-th random times to failure and generate the times which failures will occur according to the probability distribution functions presented in section 7.1
3:	for all $i\in V_c$, $k\in \left\{1,\dots ,{\eta }_i\right\}$
4:	${\mathit{f}}_{\mathit{i}\mathit{k}}=f_i\left(t\right)$ //random time according to pdf $f_i$ of customer $i$
5:	end for
6:	for all $i\in V_c$
7:	$k=1$
8:	for all $t\in \mathcal{T},$
9:	if ${\text{β}}_{it}=1\mathbf{\text{then}}$
10:	$P_{ik}=s_k$ // Calculate the period time during which each visit will occur
11:	$k=k+1$
12:	end if
13:	end for
14:	end for
15:	End first step
16:	Second step // Compare the pattern visit $P_{ik}$ with $T{F}_{ik}$
17:	for all $i\in V_c$
18:	$T{R}_{i1}=0$
19:	$T{F}_{i1}=f_{i1}$
20:	for all $k\in \left\{1,\dots ,{\eta }_i\right\}$
21:	if $P_{ik}\le T{F}_{ik}$ then
22:	$A{T}_{ik}=T{F}_{ik}-P_{ik}$ //calculate the anticipation time
23:	$T{F}_{i,k+1}=P_{ik}+{T_{PM}}_i+f_{i,k+1}$ //calculate the new time of failure
24:	$AVGCost\left(i\right)+={\displaystyle \frac{C_{PM}}{P_{ik}+T_{P{M}_i}-T{R}_{ik}}}$ //add preventive maintenance cost
25:	$T{R}_{i,k+1}=P_{ik}+{T_{PM}}_i$
26:	Else
27:	$W{T}_{ik}=P_{ik}-T{F}_{ij}$ //calculate the waiting time
28:	$T{F}_{i,k+1}=P_{ik}+{T_{CM}}_i+f_{i,k+1}$ //calculate the new time of failure
29:	$AVGCost\left(i\right)+={\displaystyle \frac{C_{CM}+w{C}_w}{P_{ik}+T_{C{M}_i}-T{R}_{ik}}}$ //add corrective maintenance and waiting time costs
30:	$T{R}_{i,k+1}=P_{ik}+{T_{CM}}_i$
31:	end if
32:	end for
33:	end for
34:	End second step

Table 2. Summary of results from event simulation model for each customer $i$.

I	Frequency	Average (PM)	Average (CM)	% PM	% CM	Average anticipation time	Average waiting time	Average of maintenance cost from simulation	MP-CMR cost	Gap (%)
1	3	3	0	100.0%	0.0%	26.3	0	45.87	63.04	−27.24%
2	3	2.8	0.2	93.3%	6.7%	89.8	0.6	50.66	63.16	−19.79%
3	2	2	0	100.0%	0.0%	29.6	0	16.14	17.76	−9.12%
4	2	1.9	0.1	95.0%	5.0%	137.7	3.9	20.55	22.88	−10.20%
5	2	1.9	0.1	95.0%	5.0%	24	0.1	20.34	19.72	3.14%
6	3	2.9	0.1	96.7%	3.3%	24.5	0.1	56.92	76.20	−25.30%
7	3	2.5	0.5	83.3%	16.7%	118	11	59.14	61.76	−4.25%
8	1	0.9	0.1	90.0%	10.0%	13	0.6	8.30	7.84	5.85%
9	1	1	0	100.0%	0.0%	31	0	5.44	5.96	−8.78%
10	2	2	0	100.0%	0.0%	31.1	0	13.41	17.40	−22.92%
11	1	0.9	0.1	90.0%	10.0%	67.7	1.7	10.30	8.96	14.97%
12	4	3.7	0.3	92.5%	7.5%	118.6	3.7	101.23	125.88	−19.58%
13	5	4.6	0.4	92.0%	8.0%	165.4	1.8	107.28	116.64	−8.03%
14	1	1	0	100.0%	0.0%	24.1	0	5.82	8.76	−33.58%
15	2	1.7	0.3	85.0%	15.0%	143.1	7.9	28.94	28.08	3.07%
16	1	0.9	0.1	90.0%	10.0%	12.2	0.5	10.05	13.36	−24.79%
17	2	1.6	0.4	80.0%	20.0%	106.8	7.9	35.12	34.64	1.38%
18	4	3.4	0.6	85.0%	15.0%	129.6	3.8	105.97	121.80	−13.00%
19	1	1	0	100.0%	0.0%	24.9	0	6.43	8.48	−24.18%
20	1	1	0	100.0%	0.0%	23.7	0	6.63	6.92	−4.13%

Table 3. Results with 5, 10, and 20 time periods.

5 time periods
# of customers	Objective Function	Routing	Maintenance	%Routing	%Maintenance	CPU Time (s)	Paths	Patterns	Iterations
20	1857.64	1019	839	54.85%	45.15%	5.61	219	244	45
10 Time Periods
# of customers	Objective Function	Routing	Maintenance	%Routing	%Maintenance	CPU Time (s)	Paths	Patterns	Iterations
20	1819.44	1033	786	56.78%	43.22%	11.08	420	712	51
30	2879.76	1367	1512.76	47.47%	52.53%	41.29	600	1137	76
40	3410.56	1681	1729.56	49.29%	50.71%	158.451	754	1560	110
50	3779.8	1880	1899.8	49.74%	50.26%	122.725	922	1870	122
60	4596.84	2074	2522.84	45.12%	54.88%	185.632	1200	2342	140
20 Time Periods
# of customers	Objective Function	Routing	Maintenance	%Routing	%Maintenance	CPU Time (s)	Paths	Patterns	Iterations
20	1813.28	1023	790	56.42%	43.58%	187.83	1123	1598	145
30	2854.84	1376	1478.84	48.20%	51.80%	410.71	1505	2596	189
40	3392.4	1692	1700.4	49.88%	50.12%	212.859	1761	3444	191
50	3750.16	1889	1861.16	50.37%	49.63%	277.732	2170	4324	208
60	4525.52	2092	2433.52	46.23%	53.77%	400.67	2654	5649	202
70	5170.16	2463	2707.16	47.64%	52.36%	1037.487	3111	7011	401

Table 4. Results of Multi-Period Combined Maintenance and Routing model (MP-CMR) and benchmark procedure.

		Objective Function			Routing			Maintenance			CPU Time (s)			Paths			Iterations
Time periods	# of customers	MP-CMR	Benchmark	%Improve	MP-CMR	Benchmark	%Improve	MP-CMR	Benchmark	%Improve	MP-CMR	Benchmark	%Improve	MP-CMR	Benchmark	%Improve	MP-CMR	Benchmark	%Improve
5	20	1857.64	1948.4	−5%	1019	1118	−9%	838.64	830.40	1%	5.61	2.42	132%	219	263	−17%	45	59	−24%
10	20	1819.44	2004.96	−9%	1033	1207	−14%	786.44	797.96	−1%	11.08	5.31	109%	420	579	−27%	51	77	−34%
	30	2879.76	3107.64	−7%	1367	1586	−14%	1512.76	1521.64	−1%	41.29	15.19	172%	600	906	−34%	76	116	−34%
	40	3410.56	3794.88	−10%	1681	2103	−20%	1729.56	1691.88	2%	158.451	39.798	298%	754	1303	−42%	110	157	−30%
	50	3779.8	4175.24	−9%	1880	2283	−18%	1899.8	1892.24	0%	122.725	106.103	16%	922	1846	−50%	122	260	−53%
	60	4596.84	5149.72	−11%	2074	2675	−22%	2522.84	2474.72	2%	185.632	240.945	−23%	1200	2799	−57%	140	369	−62%
20	20	1813.28	2108.2	−14%	1023	1330	−23%	790.28	778.20	2%	187.83	11.55	1526%	1123	1191	−6%	145	75	93%
	30	2854.84	3289.36	−13%	1376	1826	−25%	1478.84	1463.36	1%	410.71	75.94	441%	1505	1896	−21%	189	146	29%
	40	3392.4	4017.16	−16%	1692	2352	−28%	1700.4	1665.16	2%	212.859	76.731	177%	1761	2478	−29%	191	163	17%
	50	3750.16	4698.36	−20%	1889	2809	−33%	1861.16	1889.36	−1%	277.732	186.118	49%	2170	3949	−45%	208	252	−17%
	60	4525.52	5534.72	−18%	2092	3119	−33%	2433.52	2415.72	1%	400.67	548.209	−27%	2654	6505	−59%	202	401	−50%
	70	5170.16	7966.32	−35%	2463	4970	−50%	2707.16	2996.32	−10%	1037.487	698.873	48%	3111	6979	−55%	401	386	4%

Figure 10. The average of waiting time for T = 5, 10, and 20 periods with (a) 20 customers, (b) 30 customers, and (c) 40 customers.

Three-line graphs and one dot graph presenting the cumulative waiting times and the frequency of visits respectively for 20, 30, and 40 customers.

Table 5. Travel time (hours) between pumping stations and maintenance parameters for each plant $i$.

	$j$
$i$	0	1	2	3	4	5	6	7	8	9	10	${C_{PM}}_i$	${C_{CM}}_i$	${C_w}_i$	${T_{PM}}_i$	${T_{CM}}_i$	$f_i\left(t\right)$^1
0	0	0	0	0	3.5	3.5	5	7.5	8.5	9.5	10.5	–	–	–	–	–	–
1		0	1.5	3	3.5	3.5	5	7.5	8.5	9.5	7.5	183	638	15	9	23	$N\left(45,4.091\right)$
2			0	1.5	2	2	3.5	6	7	8	6	121	515	14	5	15	$N\left(54,4.5\right)$
3				0	0.5	1.5	3	5.5	5.5	6.5	10.5	193	425	19	6	17	$W\left(66,3.5\right)$
4					0	1	2.5	5	5	6	10	156	561	14	8	24	$W\left(100,3.5\right)$
5						0	1.5	4	5	6	10	138	567	13	8	17	$W\left(63,3.5\right)$
6							0	2.5	3.5	4.5	8.5	194	498	17	10	15	$N\left(44,4.4\right)$
7								0	1	2	6	163	462	15	9	29	$W\left(84,3.5\right)$
8									0	1	4	100	639	12	9	23	$N\left(78,7.091\right)$
9										0	4	193	580	13	6	23	$N\left(96,8.728\right)$
10											0	105	549	18	10	21	$N\left(75,6.819\right)$

^a By $N\left(\mu ,\sigma \right)$ we denote the normal probability density function with mean $\mu$ and standard deviation $\sigma$; and by $W\left(\lambda ,k\right)$ we denote the Weibull probability density function with scale parameter $\lambda$ and shape parameter $k$.

Table 6. Results of Multi-Period Combined Maintenance and Routing model (MP-CMR) and benchmark model on case study with $\mathcal{T}=7$ and $\mathcal{T}=14$.

	7 periods			14 periods
Performance measure	MP-CMR	Benchmark	%Improve	MP-CMR	Benchmark	%Improve
Objective function	253.06	404.70	−37%	573.58	767.46	−25%
Routing	37.50	71.50	−48%	74.50	129.50	−42%
Maintenance	215.56	333.20	−35%	499.08	637.96	−22%
CPU time (s)	1.86	1.17	59%	5.59	1.82	207%
Frequency	14	14	0%	34	34	0%
Paths	155	121	28%	440	210	110%
Patterns	150	20	650%	342	20	1610%
Iterations	32	42	−24%	45	32	41%

Table 7. Average of maintenance cost of multi-Period Combined Maintenance and Routing model (MP-CMR) and benchmark model on case study with $\mathcal{T}=7$ and $\mathcal{T}=14$ for each plant $i$.

		7 periods				14 Periods
Plant i		MP-CMR	Benchmark	%Improve		MP-CMR	Benchmark	%Improve
1	2	18.18	18.46	−2%	4	16.96	20.31	−16%
2	2	19.82	27.72	−28%	5	19.88	23.82	−17%
3	1	8.84	22.28	−60%	3	8.92	12.81	−30%
4	1	11.20	11.20	0%	3	11.65	18.84	−38%
5	1	10.92	22.92	−52%	3	10.37	18.13	−43%
6	2	21.02	40.64	−48%	5	20.70	22.94	−10%
7	2	20.86	27.06	−23%	4	20.81	23.26	−11%
8	1	8.12	8.12	0%	2	7.68	7.56	2%
9	1	7.24	12.44	−42%	2	6.88	17.04	−60%
10	1	9.48	28.48	−67%	3	7.72	10.44	−26%
Total	14	135.68	219.32	−38%	34	131.57	175.16	−25%

Martinod, R. M., O. Bistorin, L. F. Castañeda, and N. Rezg. 2018. “Maintenance Policy Optimisation for Multi-Component Systems Considering Degradation of Components and Imperfect Maintenance Actions.” Computers & Industrial Engineering 124: 100–112. doi:10.1016/j.cie.2018.07.019

 Web of Science ®Google Scholar

Faddoul, R., W. Raphael, and A. Chateauneuf. 2018. “Maintenance Optimization of Series Systems Subject to Reliability Constraints.” Reliability Engineering and System Safety 180: 179–188. doi:10.1016/j.ress.2018.07.016

 Web of Science ®Google Scholar

Eltoukhy, A. E. E., Z. X. Wang, F. T. S. Chan, and S. H. Chung. 2018. “Joint Optimization Using a Leader–Follower Stackelberg Game for Coordinated Configuration of Stochastic Operational Aircraft Maintenance Routing and Maintenance Staffing.” Computers & Industrial Engineering 125: 46–68. doi:10.1016/j.cie.2018.08.012

 Web of Science ®Google Scholar

Eltoukhy, A. E. E., Z. X. Wang, F. T. S. Chan, and X. Fu. 2019. “Data Analytics in Managing Aircraft Routing and Maintenance Staffing with Price Competition by a Stackelberg-Nash Game Model.” Transportation Research Part E: Logistics and Transportation Review 122: 143–168. doi:10.1016/j.tre.2018.12.002.

 Web of Science ®Google Scholar

Khatab, A., C. Diallo, U. Venkatadri, Z. Liu, and E.-H. Aghezzaf. 2018. “Optimization of the Joint Selective Maintenance and Repairperson Assignment Problem Under Imperfect Maintenance.” Computers & Industrial Engineering 125: 413–422. doi:10.1016/j.cie.2018.09.012.

 Web of Science ®Google Scholar

Wakiru, J. M., L. Pintelon, P. Muchiri, and P. Chemweno. 2021. “Integrated Maintenance Policies for Performance Improvement of a Multi-Unit Repairable, One Product Manufacturing System.” Production Planning and Control 32 (5): 347–367. doi:10.1080/09537287.2020.1736684.

 Web of Science ®Google Scholar

Gopalakrishnan, M., M. Subramaniyan, and A. Skoogh. 2020. “Data-driven Machine Criticality Assessment-Maintenance Decision Support for Increased Productivity.” Production Planning & Control The Management of Operations, 1–19. doi:10.1080/09537287.2020.1817601.

 Web of Science ®Google Scholar

Briš, R., P. Byczanski, R. Goňo, and S. Rusek. 2017. “Discrete Maintenance Optimization of Complex Multi-Component Systems.” Reliability Engineering & System Safety 168: 80–89. doi:10.1016/j.ress.2017.04.008.

 Web of Science ®Google Scholar

Foong, W. K., A. R. Simpson, H. R. Maier, and S. Stolp. 2008. “Ant Colony Optimization for Power Plant Maintenance Scheduling Optimization—A Five-Station Hydropower System.” Annals of Operations Research 159 (1): 433–450. doi:10.1007/s10479-007-0277-y.

 Web of Science ®Google Scholar

Zhou, X., & Shi, K. (2019). Capacity Failure Rate Based Opportunistic Maintenance Modeling for Series-Parallel Multi-Station Manufacturing Systems. Reliability Engineering & System Safety, 181, 46–53. doi:10.1016/j.ress.2018.09.007

 Web of Science ®Google Scholar

Samal, N. K., and D. K. Pratihar. 2015. “Joint Optimization of Preventive Maintenance and Spare Parts Inventory Using Genetic Algorithms and Particle Swarm Optimization Algorithm.” International Journal of System Assurance Engineering and Management 6 (3): 248–258. doi:10.1007/s13198-015-0349-3.

 Google Scholar

Nguyen, H. S. H., P. Do, H.-C. Vu, and B. Iung. 2019. “Dynamic Maintenance Grouping and Routing for Geographically Dispersed Production Systems.” Reliability Engineering & System Safety 185: 392–404. doi:10.1016/j.ress.2018.12.031.

 Web of Science ®Google Scholar

Irawan, C. A., D. Ouelhadj, D. Jones, M. Stålhane, and I. B. Sperstad. 2017. “Optimisation of Maintenance Routing and Scheduling for Offshore Wind Farms.” European Journal of Operational Research 256 (1): 76–89. doi:10.1016/J.EJOR.2016.05.059.

 Web of Science ®Google Scholar

Hajej, Z., N. Rezg, and A. Gharbi. 2020. “Maintenance on Leasing Sales Strategies for Manufacturing/Remanufacturing System with Increasing Failure Rate and Carbon Emission.” International Journal of Production Research 58 (21): 6616–6637. doi:10.1080/00207543.2019.1683254.

 Web of Science ®Google Scholar

Hajej, Z., N. Rezg, and A. Gharbi. 2018. “Quality Issue in Forecasting Problem of Production and Maintenance Policy for Production Unit.” International Journal of Production Research 56 (18): 6147–6163. doi:10.1080/00207543.2018.1478150.

 Web of Science ®Google Scholar

Hajej, Z., and N. Rezg. 2020. “An Optimal Integrated lot Sizing and Maintenance Strategy for Multi-Machines System with Energy Consumption.” International Journal of Production Research 58 (14): 4450–4470. doi:10.1080/00207543.2019.1654630.

 Web of Science ®Google Scholar

Koochaki, J., J. A. C. Bokhorst, H. Wortmann, and W. Klingenberg. 2012. The Influence of Condition-Based Maintenance On Workforce Planning and Maintenance Scheduling The Influence of Condition-Based Maintenance on Workforce Planning and Maintenance Scheduling. doi:10.1080/00207543.2012.737944.

 Google Scholar

Jbili, S., A. Chelbi, M. Radhoui, and M. Kessentini. 2018. “Integrated Strategy of Vehicle Routing and Maintenance.” Reliability Engineering & System Safety 170: 202–214. doi:10.1016/j.ress.2017.09.030.

 Web of Science ®Google Scholar

Ome, J., C. Zhang, Y. Gao, L. Yang, U. Kumar, and Z. Gao. 2018. ARTICLE IN PRESS Integrated Optimization of Train Scheduling and Maintenance Planning on High-Speed Railway Corridors.”. doi:10.1016/j.omega.2018.08.005.

 Google Scholar

Adjoul, O., K. Benfriha, C. El Zant, and A. Aoussat. 2021. “Algorithmic Strategy for Simultaneous Optimization of Design and Maintenance of Multi-Component Industrial Systems.” Reliability Engineering and System Safety 208: 107364. doi:10.1016/j.ress.2020.107364.

 Web of Science ®Google Scholar

Ahmed, M. Ben, F. Zeghal Mansour, and M. Haouari. 2018. “Robust Integrated Maintenance Aircraft Routing and Crew Pairing.”. doi:10.1016/j.jairtraman.2018.07.007.

 Google Scholar

López-Santana, E., R. Akhavan-Tabatabaei, L. Dieulle, N. Labadie, and A. L. Medaglia. 2016. “On the Combined Maintenance and Routing Optimization Problem.” Reliability Engineering & System Safety 145: 199–214. doi:10.1016/j.ress.2015.09.016.

 Web of Science ®Google Scholar

Data availability statement

Raw data were generated at ARCOSES Research Group. Derived data supporting the findings of this study are available from the corresponding author ELS on request.