Lagrangian relaxation-based decomposition approaches for the capacitated arc routing problem in the state-space-time network

References

• Amini, A., R. Tavakkoli-Moghaddam, and S. Ebrahimnejad. 2019. “A bi-objective transportation-location Arc Routing Problem.” Transportation Letters 12 (9): 623–637. doi:10.1080/19427867.2019.1679405.
   Web of Science ®Google Scholar
• Ansari Ardeh, M., Y. Mei, and M. Zhang. 2022. “Genetic Programming with Knowledge Transfer and Guided Search for Uncertain Capacitated Arc Routing Problem.” IEEE Transactions on Evolutionary Computation 26 (4): 765–779. doi:10.1109/TEVC.2021.3129278.
   Web of Science ®Google Scholar
• Baldacci, R., and V. Maniezzo. 2006. “Exact Methods Based on node-routing Formulations for Undirected arc-routing Problems.” Networks 47 (1): 52–60. doi:10.1002/net.20091.
   Web of Science ®Google Scholar
• Bard, J. F., and A. I. Jarrah. 2009. “Large-scale Constrained Clustering for Rationalizing Pickup and Delivery Operations.” Transportation Research Part B: Methodological 43 (5): 542–561. doi:10.1016/j.trb.2008.10.003.
   Web of Science ®Google Scholar
• Bartolini, E., J. F. Cordeau, and G. Laporte. 2013. “Improved Lower Bounds and Exact Algorithm for the Capacitated Arc Routing Problem.” Mathematical Programming 137 (1–2): 409–452. doi:10.1007/s10107-011-0497-4.
   Web of Science ®Google Scholar
• Belenguer, J. M., and E. Benavent. 2003. “A Cutting Plane Algorithm for the Capacitated Arc Routing Problem.” Computers & Operations Research 30 (5): 705–728. doi:10.1016/S0305-0548(02)00046-1.
   Web of Science ®Google Scholar
• Bianchessi, N., Á. Corberán, I. Plana, M. Reula, and J. M. Sanchis. 2022a. “The min-max close-enough Arc Routing Problem.” European Journal of Operational Research 300 (3): 837–851. doi:10.1016/j.ejor.2021.10.047.
   Web of Science ®Google Scholar
• Bianchessi, N., Á. Corberán, I. Plana, M. Reula, and J. M. Sanchis. 2022b. “The Profitable Close-Enough Arc Routing Problem.” Computers & Operations Research 140: 105653. doi:10.1016/j.cor.2021.105653.
   Web of Science ®Google Scholar
• Boland, N., J. Christiansen, B. Dandurand, A. Eberhard, J. Linderoth, J. Luedtke, and F. Oliveira. 2018. “Combining Progressive Hedging with a Frank–Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming.” SIAM Journal on Optimization 28 (2): 1312–1336. doi:10.1137/16M1076290.
   Web of Science ®Google Scholar
• Boyd, S., N. Parikh, E. Chu, B. Peleato, and J. Eckstein. 2011. “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers.” Foundations and Trends in Machine Learning 3 (1): 1–122. doi:10.1561/2200000016.
   Google Scholar
• Brandão, J., and R. Eglese. 2008. “A Deterministic Tabu Search Algorithm for the Capacitated Arc Routing Problem.” Computers & Operations Research 35 (4): 1112–1126. doi:10.1016/j.cor.2006.07.007.
   Web of Science ®Google Scholar
• Chu, F., N. Labadi, and C. Prins. 2005. “Heuristics for the Periodic Capacitated Arc Routing Problem.” Journal of Intelligent Manufacturing 16 (2): 243–251. doi:10.1007/s10845-004-5892-8.
   Web of Science ®Google Scholar
• Corberán, Á., R. Eglese, G. Hasle, I. Plana, and J. M. Sanchis. 2020. “Arc Routing Problems: A Review of the Past, Present, and Future.” Networks 76 (4): 431–450. doi:10.1002/net.21993.
   PubMedGoogle Scholar
• Corberán, Á., and G. Laporte. 2015. “Arc Routing.” Problems methods, and applications
   PubMedGoogle Scholar
• Eglese, R. W. 1994. “Routeing Winter Gritting Vehicles.” Discrete Applied Mathematics 48 (3): 231–244. doi:10.1016/0166-218X(92)00003-5.
   Web of Science ®Google Scholar
• Fisher, M. L. 1981. “The Lagrangian Relaxation Method for Solving Integer Programming Problems.” Management Science 27 (1): 1–18. doi:10.1287/mnsc.27.1.1.
   Web of Science ®Google Scholar
• Gendreau, M., G. Ghiani, and E. Guerriero. 2015. “Time-dependent Routing Problems: A Review.” Computers & Operations Research 64: 189–197. doi:10.1016/j.cor.2015.06.001.
   Web of Science ®Google Scholar
• Golden, B. L., and R. T. Wong. 1981. “Capacitated Arc Routing Problems.” Networks 11 (3): 305–315. doi:10.1002/net.3230110308.
   Web of Science ®Google Scholar
• Hertz, A., G. Laporte, and M. Mittaz. 2000. “A Tabu Search Heuristic for the Capacitated Arc Routing Problem.” Operational Research 48 (1): 129–135. doi:10.1287/opre.48.1.129.12455.
   Web of Science ®Google Scholar
• Kendy Arakaki, R., and F. Luiz Usberti. 2019. “An efficiency-based path-scanning Heuristic for the Capacitated Arc Routing Problem.” Computers & Operations Research 103: 288–295. doi:10.1016/j.cor.2018.11.018.
   Web of Science ®Google Scholar
• Khorramizadeh, M., and M. S. Shiri. 2022. “Integer Programming Formulation and Polyhedral Results for Windy Collaborative Arc Routing Problem.” Computers & Operations Research 142: 105727. doi:10.1016/j.cor.2022.105727.
   Web of Science ®Google Scholar
• Lai, Q., Z. Zhang, M. Yu, and J. Wang. 2022. “Split-Delivery Capacitated Arc-Routing Problem With Time Windows.” IEEE Transactions on Intelligent Transportation Systems 23 (3): 2882–2887. doi:10.1109/TITS.2020.3029055.
   Web of Science ®Google Scholar
• Li, R., X. Zhao, X. Zuo, J. Yuan, and X. Yao. 2021. “Memetic Algorithm with non-smooth Penalty for Capacitated Arc Routing Problem.” Knowledge-Based Systems 220.
   Web of Science ®Google Scholar
• Lu, G., X. Zhou, M. Mahmoudi, T. Shi, and Q. Peng. 2019. “Optimizing Resource Recharging location-routing Plans: A resource-space-time Network Modeling Framework for Railway Locomotive Refueling Applications.” Comput Ind Eng 127: 1241–1258. doi:10.1016/j.cie.2018.03.015.
   Web of Science ®Google Scholar
• Mahmoudi, M., and X. S. Zhou. 2016. “Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows: A Dynamic Programming Approach Based on state-space-time Network Representations.” Transport Res B-Meth 89: 19–42. doi:10.1016/j.trb.2016.03.009.
   Web of Science ®Google Scholar
• Monroy, I. M., C. A. Amaya, and A. Langevin. 2013. “The Periodic Capacitated Arc Routing Problem with Irregular Services.” Discrete Applied Mathematics 161 (4–5): 691–701. doi:10.1016/j.dam.2011.05.014.
   Web of Science ®Google Scholar
• Mourão, M. C., and L. S. Pinto. 2017. “An Updated Annotated Bibliography on Arc Routing Problems.” Networks 70.
   Web of Science ®Google Scholar
• Muyldermans, L., and G. Pang. 2010. “A Guided Local Search Procedure for the multi-compartment Capacitated Arc Routing Problem.” Computers & Operations Research 37 (9): 1662–1673. doi:10.1016/j.cor.2009.12.014.
   Web of Science ®Google Scholar
• Pecin, D., and E. Uchoa. 2019. “Comparative Analysis of Capacitated Arc Routing Formulations for Designing a New Branch-Cut-and-Price Algorithm.” Transportation Science 53 (6): 1673–1694. doi:10.1287/trsc.2019.0900.
   Web of Science ®Google Scholar
• Polacek, M., K. F. Doerner, R. F. Hartl, and V. Maniezzo. 2008. “A Variable Neighborhood Search for the Capacitated Arc Routing Problem with Intermediate Facilities.” Journal of Heuristics 14 (5): 405–423. doi:10.1007/s10732-007-9050-2.
   Web of Science ®Google Scholar
• Santos, L., J. Coutinho-Rodrigues, and J. R. Current. 2010. “An Improved Ant Colony Optimization Based Algorithm for the Capacitated Arc Routing Problem.” Transportation Research Part B: Methodological 44 (2): 246–266. doi:10.1016/j.trb.2009.07.004.
   Web of Science ®Google Scholar
• Shang, R., Y. Wang, J. Wang, L. Jiao, S. Wang, and L. Qi. 2014. “A multi-population Cooperative Coevolutionary Algorithm for multi-objective Capacitated Arc Routing Problem.” Information Sciences 277: 609–642. doi:10.1016/j.ins.2014.03.008.
   Web of Science ®Google Scholar
• Song, M., and L. Cheng. 2022. “An Augmented Lagrangian Relaxation Method for the mean-standard Deviation Based Vehicle Routing Problem.” Knowledge-Based Systems 247: 108736. doi:10.1016/j.knosys.2022.108736.
   Web of Science ®Google Scholar
• Stern, H. I., and M. Dror. 1979. “Routing Electric Meter Readers.” Computers & Operations Research 6 (4): 209–223. doi:10.1016/0305-0548(79)90005-4.
   Web of Science ®Google Scholar
• Tagmouti, M., M. Gendreau, and J.-Y. Potvin. 2007. “Arc Routing Problems with time-dependent Service Costs.” European Journal of Operational Research 181 (1): 30–39. doi:10.1016/j.ejor.2006.06.028.
   Web of Science ®Google Scholar
• Tagmouti, M., M. Gendreau, and J.-Y. Potvin. 2010. “A Variable Neighborhood Descent Heuristic for Arc Routing Problems with time-dependent Service Costs.” Comput Ind Eng 59 (4): 954–963. doi:10.1016/j.cie.2010.09.006.
   Web of Science ®Google Scholar
• Tagmouti, M., M. Gendreau, and J.-Y. Potvin. 2011. “A Dynamic Capacitated Arc Routing Problem with time-dependent Service Costs.” Transportation Research Part C: Emerging Technologies 19 (1): 20–28. doi:10.1016/j.trc.2010.02.003.
   Web of Science ®Google Scholar
• Vidal, T., R. Martinelli, T. A. Pham, and M. H. Hà. 2021. Arc Routing with Time-Dependent Travel Times and Paths 55 (3): 706–724.
   Google Scholar
• Yao, Y., X. Zhu, H. Dong, S. Wu, H. Wu, L. Carol Tong, and X. Zhou. 2019. “ADMM-based Problem Decomposition Scheme for Vehicle Routing Problem with Time Windows.” Transport Res B-Meth 129: 156–174. doi:10.1016/j.trb.2019.09.009.
   Web of Science ®Google Scholar
• Yu, M., X. Jin, Z. Zhang, H. Qin, and Q. Lai. 2019. “The split-delivery Mixed Capacitated arc-routing Problem: Applications and a forest-based Tabu Search Approach.” Transportation Research Part E: Logistics and Transportation Review 132: 141–162. doi:10.1016/j.tre.2019.09.017.
   Web of Science ®Google Scholar
• Zhang, Y., Y. Mei, B. Zhang, and K. Jiang. 2021. “Divide-and-conquer Large Scale Capacitated Arc Routing Problems with Route Cutting off Decomposition.” Information Sciences 553: 208–224. doi:10.1016/j.ins.2020.11.011.
   Web of Science ®Google Scholar