Arc Routing with Time-Dependent Travel Times and Paths

References

• Baldacci R , Mingozzi A , Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Bartolini E , Cordeau J-F , Laporte G (2013) Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Programming 137(1):409–452.Crossref, Google Scholar
• Bast H , Delling D , Goldberg A , Müller-Hannemann M , Pajor T , Sanders P , Wagner D , Werneck RF (2016) Route planning in transportation networks. Kliemann L , Sanders P , eds. Algorithm Engineering: Selected Results and Surveys (Springer, Berlin), 19–80.Crossref, Google Scholar
• Batz GV , Geisberger R , Sanders P , Vetter C (2013) Minimum time-dependent travel times with contraction hierarchies. J. Experiment. Algorithmics 18(1):1–43.Google Scholar
• Belenguer JM , Benavent E (1998) The capacitated arc routing problem: Valid inequalities and facets. Comput. Optim. Appl. 10(2):165–187.Crossref, Google Scholar
• Ben Ticha H (2017) Vehicle routing problems with road-network information. PhD thesis, Université Clermont Auvergne, Clermont-Ferrand, France.Google Scholar
• Ben Ticha H , Absi N , Feillet D , Quilliot A (2019) Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows. Comput. Oper. Res. 104(1):113–126.Crossref, Google Scholar
• Beullens P , Muyldermans L , Cattrysse D , Van Oudheusden D (2003) A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. 147(3):629–643.Crossref, Google Scholar
• Black D , Eglese R , Wøhlk S (2013) The time-dependent prize-collecting arc routing problem. Comput. Oper. Res. 40(2):526–535.Crossref, Google Scholar
• Brandão J , Eglese R (2008) A deterministic tabu search algorithm for the capacitated arc routing problem. Comput. Oper. Res. 35(4):1112–1126.Crossref, Google Scholar
• Cattaruzza D , Absi N , Feillet D , González-Feliu J (2017) Vehicle routing problems for city logistics. EURO J. Transportation Logist. 6(1):51–79.Crossref, Google Scholar
• Cookson G , Pishue B (2018) INRIX Global Traffic Scorecard. Technical report, INRIX, Kirkland, WA.Google Scholar
• Corberán Á , Laporte G (2015) Arc Routing: Problems, Methods, and Applications (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Eglese R , Maden W , Slater A (2006) A road timetable to aid vehicle routing and scheduling. Comput. Oper. Res. 33(12):3508–3519.Crossref, Google Scholar
• Foschini L , Hershberger J , Suri S (2014) On the complexity of time-dependent shortest paths. Algorithmica 68(4):1075–1097.Crossref, Google Scholar
• Gendreau M , Ghiani G , Guerriero E (2015) Time-dependent routing problems: A review. Comput. Oper. Res. 64:189–197.Crossref, Google Scholar
• Ghiani G , Guerriero E (2014) A note on the Ichoua, Gendreau, and Potvin (2003) travel time model. Transportation Sci. 48(3):458–462.Link, Google Scholar
• Gmira M , Gendreau M , Lodi A , Potvin J-Y (2021) Tabu search for the time-dependent vehicle routing problem with time windows on a road network. Eur. J. Oper. Res. 288(1):129–140.Crossref, Google Scholar
• Hershberger J (1989) Finding the upper envelope of n line segments in O(n log n) time. Inform. Processing Lett. 33(4):169–174.Crossref, Google Scholar
• Herszterg I , Poggi M , Vidal T (2019) Two-dimensional phase unwrapping via balanced spanning forests. INFORMS J. Comput. 31(3):527–543.Link, Google Scholar
• Huang Y , Zhao L , Van Woensel T , Gross J-P (2017) Time-dependent vehicle routing problem with path flexibility. Transportation Res. Part B: Methodological 95:169–195.Crossref, Google Scholar
• Ichoua S , Gendreau M , Potvin J-Y (2003) Vehicle dispatching with time-dependent travel times. Eur. J. Oper. Res. 144(2):379–396.Crossref, Google Scholar
• Irnich S (2008) Solution of real-world postman problems. Eur. J. Oper. Res. 190(1):52–67.Crossref, Google Scholar
• Jaballah R , Veenstra M , Coelho LC , Renaud J (2019) The time-dependent shortest path and vehicle routing problem. Technical Report CIRRELT-2019-12, CIRRELT, Université Laval, Québec.Google Scholar
• Laporte G , Ropke S , Vidal T (2014) Heuristics for the vehicle routing problem. Toth P , Vigo D , eds. Vehicle Routing: Problems, Methods, and Applications (Society for Industrial and Applied Mathematics, Philadelphia), 87–116.Crossref, Google Scholar
• Lera-Romero G , Miranda Bront JJ , Soulignac FJ (2020) Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows. Networks 76(1):24–53.Crossref, Google Scholar
• Li LYO , Eglese RW (1996) An interactive algorithm for vehicle routeing for winter-gritting. J. Oper. Res. Soc. 47(2):217–228.Google Scholar
• Maden W , Eglese R , Black D (2010) Vehicle routing and scheduling with time-varying data: A case study. J. Oper. Res. Soc. 61(3):515–522.Crossref, Google Scholar
• Martinelli R , Pecin D , Poggi M (2014) Efficient elementary and restricted non-elementary route pricing. Eur. J. Oper. Res. 239(1):102–111.Crossref, Google Scholar
• Martinelli R , Pecin D , Poggi M , Longo H (2011) A branch-cut-and-price algorithm for the capacitated arc routing problem. Pardalos PM , Rebennack S , eds. Experimental Algorithms , Lecture Notes in Computer Science, vol. 6630 (Springer, Berlin), 315–326.Crossref, Google Scholar
• Mecler J , Subramanian A , Vidal T (2020) A simple and effective hybrid genetic search for the job sequencing and tool switching problem. Comput. Oper. Res. 127:105–153.Google Scholar
• Orda A , Rom R (1990) Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3):607–625.Crossref, Google Scholar
• Pecin D , Uchoa E (2019) Comparative analysis of capacitated arc routing formulations for designing a new branch-cut-and-price algorithm. Transportation Sci. 53(6):1673–1694.Link, Google Scholar
• Pessoa A , Uchoa E , Poggi M , Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3–4):259–290.Crossref, Google Scholar
• Rincon-Garcia N , Waterson BJ , Cherrett TJ (2018) Requirements from vehicle routing software: Perspectives from literature, developers and the freight industry. Transportation Rev. 38(1):117–138.Crossref, Google Scholar
• Røpke S (2012) Branching decisions in branch-and-cut-and-price algorithms for vehicle routing problems. Presentation at the International Workshop on Column Generation, June 13, GERAD–HEC Montreal, Montreal.Google Scholar
• Sun J , Meng Y , Tan G (2015) An integer programming approach for the Chinese postman problem with time-dependent travel time. J. Combin. Optim. 29(3):565–588.Crossref, Google Scholar
• Toffolo TAM , Vidal T , Wauters T (2019) Heuristics for vehicle routing problems: Sequence or set optimization? Comput. Oper. Res. 105:118–131.Crossref, Google Scholar
• Vidal T (2017) Node, edge, arc routing and turn penalties: Multiple problems—One neighborhood extension. Oper. Res. 65(4):992–1010.Link, Google Scholar
• Vidal T , Laporte G , Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286(2):401–416.Crossref, Google Scholar
• Vidal T , Battarra M , Subramanian A , Erdogan G (2015a) Hybrid metaheuristics for the clustered vehicle routing problem. Comput. Oper. Res. 58(1):87–99.Crossref, Google Scholar
• Vidal T , Crainic TG , Gendreau M , Prins C (2013) Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. Eur. J. Oper. Res. 231(1):1–21.Crossref, Google Scholar
• Vidal T , Crainic TG , Gendreau M , Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234(3):658–673.Crossref, Google Scholar
• Vidal T , Crainic TG , Gendreau M , Prins C (2015b) Timing problems and algorithms: Time decisions for sequences of activities. Networks 65(2):102–128.Crossref, Google Scholar
• Vidal T , Maculan N , Ochi LS , Penna PHV (2016) Large neighborhoods with implicit customer selection for vehicle routing problems with profits. Transportation Sci. 50(2):720–734.Link, Google Scholar
• Visser TR , Spliet R (2020) Efficient move evaluations for time-dependent vehicle routing problems. Transportation Sci. 54(4):1091–1112.Link, Google Scholar
• Yu VF , Lin S-W (2015) Iterated greedy heuristic for the time-dependent prize-collecting arc routing problem. Comput. Indust. Engrg. 90:54–66.Crossref, Google Scholar