Abstract
The rapid population growth and the high rate of migration to urban areas impose a heavy load on the urban infrastructure. Particularly, sewerage systems are the target of disruptions, causing potential public health hazards. Although sewer systems are designed to handle some sediment and solid transport, particles can form deposits that increase the flood risk. To mitigate this risk, sewer systems require adequate maintenance scheduling, as well as ad-hoc repairs due to unforeseen disruptions. To address this challenge, we tackle the problem of planning and scheduling maintenance operations based on a deterioration pattern for a set of geographically spread sites, subject to unforeseen failures and restricted crews. We solve the problem as a two-stage maintenance-routing procedure. First, a maintenance model driven by the probability distribution of the time between failures determines the optimal time to perform maintenance operations for each site. Then, we design and apply an LP-based split procedure to route a set of crews to perform the planned maintenance operations at a near-minimum expected cost per unit time. Afterward, we adjust this routing solution dynamically to accommodate unplanned repair operations arising as a result of unforeseen failures. We validated our proposed method on a large-scale case study for sediment-related sewer blockages in Bogotá (Colombia). Our methodology reduces the cost per unit time in roughly 18% with respect to the policy used by the city’s water utility company.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abraham, D. M., Wirahadikusumah, R., Short, T., & Shahbahrami, S. (1998). Optimization modeling for sewer network management. Journal of Construction Engineering and Management, 124(5), 402–410.
Afshar-Nadjafi, B., & Afshar-Nadjafi, A. (2017). A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of King Saud University-Engineering Sciences, 29(1), 29–34.
Alrabghi, A., & Tiwari, A. (2015). State of the art in simulation-based optimisation for maintenance systems. Computers & Industrial Engineering, 82, 167–182.
Angel, S., Parent, J., Civco, D. L., & Blei, A. M. (2016). Atlas of urban expansion, volume 1: Areas and densities. Cambridge, MA: Lincoln Institute of Land Policy.
Baldacci, R., Mingozzi, A., & Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, 59(5), 1269–1283.
Beasley, J. E. (1983). Route first-cluster second methods for vehicle routing. Omega, 11(4), 403–408.
Bertazzi, L., & Speranza, M. G. (2012). Inventory routing problems: An introduction. EURO Journal on Transportation and Logistics, 1(4), 307–326.
Bettinelli, A., Ceselli, A., & Righini, G. (2011). A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 19(5), 723–740.
Blakeley, F., Argüello, B., Cao, B., Hall, W., & Knolmajer, J. (2003). Optimizing periodic maintenance operations for schindler elevator corporation. Interfaces, 33(1), 67–79.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300–313.
Bräysy, O., & Gendreau, M. (2005). Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation science, 39(1), 104–118.
Campbell, A., Clarke, L., Kleywegt, A., & Savelsbergh, M. (1998). The inventory routing problem. In Fleet management and logistics (pp. 95–113). Springer.
Chen, X., Thomas, B. W., & Hewitt, M. (2016). The technician routing problem with experience-based service times. Omega, 61, 49–61.
Chen, X., Thomas, B. W., & Hewitt, M. (2017a). Multi-period technician scheduling with experience-based service times and stochastic customers. Computers & Operations Research, 82, 1–14.
Chen, Y., Cowling, P., Polack, F., Remde, S., & Mourdjis, P. (2017b). Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system. European Journal of Operational Research, 257(2), 494–510.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91.
Dekker, R. (1996). Applications of maintenance optimization models: A review and analysis. Reliability Engineering & System Safety, 51(3), 229–240.
Desaulniers, G. (2010). Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Operations Research, 58(1), 179–192.
Edgar, T. F., Himmelblau, D. M., Lasdon, L. S., et al. (2001). Optimization of chemical processes (Vol. 2). New York: McGraw-Hill.
Empresa de Acueducto y Alcantarillado de Bogotá (2015) Delimitación por zonas de servicio. http://www.acueducto.com.co/wps/html/resources/2014/delimitacionporzonas.doc.
Fletcher, T. D., Andrieu, H., & Hamel, P. (2013). Understanding, management and modelling of urban hydrology and its consequences for receiving waters: A state of the art. Advances in Water Resources, 51, 261–279.
Fontecha, J. E., Akhavan-Tabatabaei, R., Duque, D., Medaglia, A. L., Torres, M. N., & Rodríguez, J. P. (2016). On the preventive management of sediment-related sewer blockages: A combined maintenance and routing optimization approach. Water Science and Technology, 74(2), 302–308.
Fukasawa, R., Longo, H., Lysgaard, J., de Aragão, M. P., Reis, M., Uchoa, E., et al. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106(3), 491–511.
Gendreau, M., Potvin, J.-Y., Bräumlaysy, O., Hasle, G., & Løkketangen, A. (2008). Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography. In The vehicle routing problem: latest advances and new challenges (pp. 143–169). Springer.
Goodson, J. C., Ohlmann, J. W., & Thomas, B. W. (2013). Rollout policies for dynamic solutions to the multivehicle routing problem with stochastic demand and duration limits. Operations Research, 61(1), 138–154.
Goodson, J. C., Thomas, B. W., & Ohlmann, J. W. (2017). A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs. European Journal of Operational Research, 258(1), 216–229.
Gurobi Optimization, LLC (2019). Gurobi Optimizer Reference Manual. http://www.gurobi.com.
Jardine, A. K., & Tsang, A. H. (2013). Maintenance, replacement, and reliability: Theory and applications. Boca Raton: CRC Press.
Kek, A. G., Cheu, R. L., & Meng, Q. (2008). Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots. Mathematical and Computer Modelling, 47(1–2), 140–152.
Korving, H., Clemens, F. H., & van Noortwijk, J. M. (2006). Statistical modeling of the serviceability of sewage pumps. Journal of Hydraulic Engineering, 132(10), 1076–1085.
Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4(03), 66.
Lai, K., Leung, K., Tao, B., & Wang, S. (2001). A sequential method for preventive maintenance and replacement of a repairable single-unit system. Journal of the Operational Research Society, 52(11), 1276–1283.
L’Ecuyer, P. (2016). Ssj: Stochastic simulation in java, software library.
L’Ecuyer, P., Meliani, L., & Vaucher, J. (2002). Ssj: Ssj: A framework for stochastic simulation in java. In Proceedings of the 34th conference on Winter simulation: Exploring new frontiers, Winter Simulation Conference (pp. 234–242).
López-Santana, E., Akhavan-Tabatabaei, R., Dieulle, L., Labadie, N., & Medaglia, A. L. (2016). On the combined maintenance and routing optimization problem. Reliability Engineering & System Safety, 145, 199–214.
Mendoza, J. E., & Villegas, J. G. (2013). A multi-space sampling heuristic for the vehicle routing problem with stochastic demands. Optimization Letters, 7(7), 1503–1516.
Pessoa, A., De Aragão, M. P., & Uchoa, E. (2008). Robust branch-cut-and-price algorithms for vehicle routing problems. In The vehicle routing problem: Latest advances and new challenges (pp. 297–325). Springer.
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013a). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1–11.
Pillac, V., Guéret, C., & Medaglia, A. L. (2013b). A parallel matheuristic for the technician routing and scheduling problem. Optimization Letters, 7(7), 1525–1535.
Pillac, V., Guéret, C., & Medaglia, A. L. (2018). A fast reoptimization approach for the dynamic technician routing and scheduling problem (pp. 347–367). New York: Springer.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985–2002.
Prins, C., Lacomme, P., & Prodhon, C. (2014). Order-first split-second methods for vehicle routing problems: A review. Transportation Research Part C: Emerging Technologies, 40, 179–200.
Rodríguez, J. P., McIntyre, N., Díaz-Granados, M., & Maksimović, Č. (2012). A database and model to support proactive management of sediment-related sewer blockages. Water Research, 46(15), 4571–4586.
Rodríguez, M. (2008). Informe de evaluación de alternativas de tratamiento y manejo de lodo de alcantarillado sanitario y pluvial. EAAB-UniAndes: Tech. rep.
Ross, S. M. (2014). Introduction to probability models. Cambridge: Academic Press.
Santry Jr, I. W. (1972). Sewer maintenance costs. Journal (Water Pollution Control Federation), 44(7), 1425–1432.
Shirmohammadi, A. H., Love, C., & Zhang, Z. G. (2003). An optimal maintenance policy for skipping imminent preventive maintenance for systems experiencing random failures. Journal of the Operational Research Society, 54(1), 40–47.
Soriano-Pulido, E., Valencia-Arboleda, C., & Rodríguez-Sánchez, J. P. (2019). Study of the spatiotemporal correlation between sediment-related blockage events in the sewer system in Bogotá (Colombia). Water Science & Technology, 79(9), 1727–1738. https://doi.org/10.2166/wst.2019.172.
Torres, M. N., Rodríguez, J. P., & Leitao, J. P. (2017). Geostatistical analysis to identify characteristics involved in sewer pipes and urban tree interactions. Urban Forestry & Urban Greening, 25, 36–42.
UN General Assembly (2015). Transforming our world: The 2030 agenda for sustainable development. New York: United Nations (1).
United Nations. (2016). Global sustainable development report 2016. Department of Economic and Social Affairs.
Vammen, K. (2015). Desafios del agua urbana en las americas: Perspectivas de las academias de ciencias. Agricultura, sociedad y desarrollo, 12(3), 475–478.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 231(1), 1–21.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3), 658–673.
Wang, C. H., Yeh, R. H., & Wu, P. (2006). Optimal production time and number of maintenance actions for an imperfect production system under equal-interval maintenance policy. Journal of the Operational Research Society, 57(3), 262–270.
Wang, H. (2002). A survey of maintenance policies of deteriorating systems. European Journal of Operational Research, 139(3), 469–489.
Worldatlas. (2018). The 150 largest cities in the World. https://www.worldatlas.com/citypops.htm.
Yang, M. D., & Su, T. C. (2007). An optimization model of sewage rehabilitation. Journal of the Chinese Institute of Engineers, 30(4), 651–659.
Zhang, S., Ohlmann, J. W., & Thomas, B. W. (2014). A priori orienteering with time windows and stochastic wait times at customers. European Journal of Operational Research, 239(1), 70–79.
Zhang, S., Ohlmann, J. W., & Thomas, B. W. (2018). Dynamic orienteering on a network of queues. Transportation Science, 52(3), 691–706.
Acknowledgements
We would like to thank EAAB for providing us with data. We thank Professor Jorge Mendoza at HEC Montréal (Canada), for his support with the Multi-space Sampling Heuristic (MSH) which was extensively used in this project. Also, we would like to thank Gurobi for providing us with an academic license of their linear optimizer. Last, but not least, we thank the comments of the anonymous referees that significantly improved our paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendices
Notation tables
Original CMR overview
The Maintenance Model (MM) establishes the expected cost per unit time \(\mathcal {C}(\delta )\) of conducting a maintenance operation at time \(\delta \) for a single site. For those systems in which the maintenance operation generates a renewal, it is common practice to calculate the expected cost per unit time as the ratio between the expected cost per cycle and the expected cycle duration (López-Santana et al. 2016; Jardine and Tsang 2013; Ross 2014). The function \(\mathcal {C}(\delta )\) is a nonlinear continuous function that considers both a preventing cycle, i.e., when the site has not failed before \(\delta \); and a corrective cycle, i.e., when the site fails before \(\delta \). Additionally, the random variable T represents the time between failures, and f(t) and F(t) are the density and cumulative distribution functions, respectively. The probability of a corrective cycle is given by \(F(\delta )\), while the probability of a preventive cycle is \(1-F(\delta )\). Equation (18) shows the expected cost per unit time as a function of \(\delta \) for a given site as follows:
The numerator is the expected cycle cost, where w is the waiting time, that is, the time interval between the failure event and \(\delta \). The denominator is the expected cycle time which comprises the cycle time of a PM and the cycle time of a CM. The cycle time of a PM is the time to the next maintenance operation \(\delta \) plus the corresponding duration of maintenance operation \(T_{\text {PM}}\). The cycle time of a CM includes: \(M(\delta )\), the conditional expected time to failure given that the site fails before \(\delta \); w, the expected waiting time; and \(T_{\text {CM}}\), the duration of the maintenance operation. Equations (19) and (20) formally describe \(M(\delta )\) and w as follows:
Although Eq. (20) implies that \(M(\delta )+w=\delta \), Eq. (18) is written in terms of w for the sake of the connection between the maintenance model and the routing model.
As a side note, because f(t) and F(t) are continuous, and \(T_{\text {CM}}\) and \(T_{\text {PM}}\) are deterministic and nonnegative, Eq. (18) represents a nonlinear continuous function defined in \(\delta >0\). Moreover, the \(\displaystyle {\lim _{\delta \rightarrow 0^{+}} \mathcal {C}(\delta )\approx \frac{C_{\text {PM}}}{T_{\text {PM}}}}\) and the \(\displaystyle {\lim _{\delta \rightarrow \infty } \mathcal {C}(\delta ) \approx C_{\text {w}}}\). Finally, based on the fact that the maintenance operation will be performed in any moment between 0 and \(\tau \), and \(\mathcal {C}(\delta )\) is continuous, it is possible to determine that this function has a minimum value in some point \(\delta ^*\) such that \(0<\delta ^*< \tau \). The intuition behind this fact is that while the expected preventive maintenance cost per unit time decreases, the expected corrective maintenance cost per unit time increases, as \(\delta \) increases (López-Santana et al. 2016). Additionally, an inflection point can be found at a point \(\xi \) such that \(\delta ^*<\xi < \infty \). Figure 10 is an example of the performance of \(\mathcal {C}(\delta )\) with \(T\sim Exp(\lambda =0.033)\), \(C_{\text {PM}}=10\), \(C_{\text {CM}}=25\), \(C_{\text {w}}=20\), \(T_{\text {PM}}=0.5\), and \(T_{\text {CM}}=1\).
Example of \(\mathcal {C}(\delta )\)
Equation (18) is computed for each site \(i\in \mathcal {V}_s\) in order to obtain the optimal time \(\delta _i^{*}\) for a maintenance operation. After obtaining \(\delta _i^{*}\), the expected cycle length \(L_i(\delta _i^{*})\) and the number of operations \(\eta _i\) to schedule along the time horizon \(\tau \) are calculated in Eqs. (21) and (22), as follows:
Note that Eq. (21) is essentially the same as the denominator of Eq. (18), but every term is indexed by \(i\in \mathcal {V}_s\). The number of maintenance operations \(\eta _i\) establishes the size of sets \( v _i=\{o_1^i,o_2^i,\ldots ,o_{\eta _i}^i \}\)\(\forall i\in \mathcal {V}_s\), thus, the construction of graph \(\mathcal {G}^{'}=(\mathcal {V}_M,\mathcal {A}_M)\) naturally follows.
The Routing Model (RM) is a Mixed Integer Program (MIP) over the directed time-space graph \(\mathcal {G}^{'}\). López-Santana et al. (2016) use a similar formulation to the one proposed by Kek et al. (2008), except for the objective function which is addressed by a piecewise approximation of the function \(\mathcal {C}(\delta )\). The main decision variables of the model relate to the sequence of each route and the time at which a maintenance operation starts. With the latter group of decision variables, the expected waiting time is computed for each maintenance operation. The expected waiting time of a site is considered as the average among the corresponding maintenance operations.
A key point in López-Santana et al. (2016) is the connection between the MM and the RM. The output of the MM allows the creation of the graph \(\mathcal {G}^{'}\) and establishes the objective function in the RM. In the other direction, the output of the RM allows the computation of the expected waiting time for each site \(\hat{w}_i\), which then becomes a known parameter of Eq. (18) for the MM. The parameter \(\hat{w}_i\) replaces w, and then a new \(\delta _i^{*}\) is computed for each site. The process is repeated until and ad-hoc stopping criterion is met, namely, if either after several consecutive iterations, e.g., 10, there is no improvement of the objective function or the procedure reaches a maximum number of iterations, e.g., 100. For further implementation details and proofs, the reader is referred to López-Santana et al. (2016).
Algorithms
1.1 Performance evaluation
We evaluated the performance of the CMR policy given by our methodology. To do so, we simulated the failure process over the considered sites and computed the policy’s cost per unit time.
For each site \(i\in \mathcal {V}_s\), let \(g_i\) be the time of the next failure; \(F_i^{-1}\), the inverse of the cumulative distribution function; \(e_i\), the time of the last visit; \(L_i(\delta _i^*)\), the optimal expected cycle length; \(n_i\), the number of current visits; \( v _i\), the set of maintenance operations; and \(s_j^i\), the starting time of the j-th maintenance operation.
For each time slot \(\pi \in \mathcal {T}\), let \(\tau _\pi ^l\) and \(\tau _\pi ^u\) the lower and upper bounds of the time slot, respectively; and \(\zeta _\pi \) the set of routes to be carried out. Then, for each route \(k\in \zeta _\pi \) let \(\mathcal {V}(k)\) be the set of sites to be visited, with \(s_i\) the time site \(i\in \mathcal {V}(k)\) is visited; and \(\lambda _k\) the last scheduled maintenance operation. Additionally, \(\mathcal {V}^{'}=\cup _{k\in \zeta } \mathcal {V}(k)\) represents the set of all sites to be visited.
Finally, let \(\mathcal {K}\) be the set of replications of the simulation, \(\mathcal {C}^q\), \(r^q\), and q the total cost per unit time of the policy, the number of failures, and the q-th replication, respectively. To measure the performance of the CMR solution, we calculate the mean (\(\mathcal {C}_{\bar{x}}\)), standard deviation (\(\mathcal {C}_{s}\)), and confidence interval ([\(\mathcal {C}_l,\mathcal {C}_u\)]) of the total cost per unit time (\(\mathcal {C}\)) of the policy, as well as the mean (\(r_{\bar{x}}\)) of the number of failures.
1.2 EAAB’s current planning strategy
We define for each site \(i\in \mathcal {V}_s\), \(F_i\) as the cumulative distribution function, \(e_i\) as the time of the last visit, \(g_i\) as the time of next visit, \(L_i(\delta _i^*)\) as the optimal expected cycle length, \(n_i\) as the number of current visits, \(r_i\) as the reliability, and \(q_i\) as a copy of \(r_i\). Also, Let \(p_{kj}\) be the set of sites assigned to route k along week j; \(c_{kj}\), the cost of route k in week j; a, the number of weeks in the planning horizon, i.e., \(a=8\); b, the number of available crews, i.e., \(b=5\); d, the average number of maintenance operations assigned by route, i.e., \(d=94\); \(u_j\), the upper bound of week j; and l, the number of available week days, i.e., \(l=7\).
Rights and permissions
About this article
Cite this article
Fontecha, J.E., Guaje, O.O., Duque, D. et al. Combined maintenance and routing optimization for large-scale sewage cleaning. Ann Oper Res 286, 441–474 (2020). https://doi.org/10.1007/s10479-019-03342-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-019-03342-8