Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 13, 2026

Available Issues

April 10, 2013 - May 13, 2026

Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem

Published Online:29 Mar 2021https://doi.org/10.1287/trsc.2020.1036

References

  • Adulyasak Y , Cordeau JF , Jans R (2014) Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems. INFORMS J. Comput. 26(1):103–120.Google Scholar
  • Aráoz J , Fernández E , Franquesa C (2009) The clustered prize-collecting arc routing problem. Transportation Sci. 43(3):287–300.Google Scholar
  • Aráoz J , Fernández E , Franquesa C (2013) GRASP and path relinking for the clustered prize-collecting arc routing problem. J. Heuristics 19(2):343–371.Google Scholar
  • Aráoz J , Fernández E , Meza O (2009) Solving the prize-collecting rural postman problem. Eur. J. Oper. Res. 196(3):886–896.Google Scholar
  • Aráoz J , Fernández E , Zoltan C (2006) Privatized rural postman problems. Comput. Oper. Res. 33(12):3432–3449.Google Scholar
  • Archetti C , Speranza MG (2014) Arc routing problems with profits. Corberán Á, Laporte G, eds. Arc Routing (Society for Industrial and Applied Mathematics, Philadelphia), 281–299.Google Scholar
  • Ávila T , Corberán Á , Plana I , Sanchis JM (2016) A branch-and-cut algorithm for the profitable windy rural postman problem. Eur. J. Oper. Res. 249(3):1092–1101.Google Scholar
  • Barthélemy T , Rossi A , Sevaux M , Sörensen K (2010) Metaheuristic approach for the clustered VRP. Proc. EU/ME 2010: 10th Anniversary of the Metaheuristic Community, Lorient, France, https://hal.archives-ouvertes.fr/hal-00519811.Google Scholar
  • Bartolini E , Cordeau JF , Laporte G (2011) Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Programming 137(1–2):409–452.Google Scholar
  • Battarra M , Erdoǧan G , Vigo D (2014) Exact algorithms for the clustered vehicle routing problem. Oper. Res. 62(1):58–71.Google Scholar
  • Belenguer JM , Benavent E (1998) The capacitated arc routing problem: Valid inequalities and facets. Comput. Optim. Appl. 10(2):165–187.Google Scholar
  • Belenguer JM , Benavent E , Irnich S (2014) The capacitated arc routing problem: Exact algorithms. Corberán Á, Laporte G, eds. Arc Routing (Society for Industrial and Applied Mathematics, Philadelphia), 183–221.Google Scholar
  • Benavent E , Campos V , Corberan A , Mota E (1992) The capacitated arc routing problem: Lower bounds. Networks 22(7):669–690.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.Google Scholar
  • Bode C , Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182.Google Scholar
  • Bode C , Irnich S (2014) The shortest-path problem with resource constraints with (k, 2)-loop elimination and its application to the capacitated arc-routing problem. Eur. J. Oper. Res. 238(2):415–426.Google Scholar
  • Bode C , Irnich S (2015) In-depth analysis of pricing problem relaxations for the capacitated arc-routing problem. Transportation Sci. 49(2):369–383.Google Scholar
  • Butsch A , Kalcsics J , Laporte G (2014) Districting for arc routing. INFORMS J. Comput. 26(4):809–824.Google Scholar
  • Corberán Á , Laporte G , eds. (2014) Arc Routing (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar
  • Corberán A , Prins C (2010) Recent results on arc routing problems: An annotated bibliography. Networks 56(1):50–69.Google Scholar
  • Corberán Á , Fernández E , Franquesa C , Sanchis JM (2011a) The windy clustered prize-collecting arc-routing problem. Transportation Sci. 45(3):317–334.Google Scholar
  • Corberán Á , Plana I , Rodríguez-Chía AM , Sanchis JM (2011b) A branch-and-cut algorithm for the maximum benefit chinese postman problem. Math. Programming 141(1-2):21–48.Google Scholar
  • Cormen TH , Leiserson CE , Rivest RL , Stein C (2009) Introduction to Algorithms (MIT Electrical Engineering and Computer Science) , 3rd ed. (MIT Press, Cambridge, MA). Google Scholar
  • Costa L , Contardo C , Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Google Scholar
  • Defryn C , Sörensen K (2017) A fast two-level variable neighborhood search for the clustered vehicle routing problem. Comput. Oper. Res. 83:78–94.Google Scholar
  • Dror M , ed. (2000) Arc Routing: Theory, Solutions and Applications (Springer US, New York).Google Scholar
  • Eiselt HA , Gendreau M , Laporte G (1995a) Arc routing problems, Part I: The Chinese postman problem. Oper. Res. 43(2):231–242.Google Scholar
  • Eiselt HA , Gendreau M , Laporte G (1995b) Arc routing problems, Part II: The rural postman problem. Oper. Res. 43(3):399–414.Google Scholar
  • Expósito Izquierdo C , Rossi A , Sevaux M (2013) Modeling and solving the clustered capacitated vehicle routing problem. Fink A, Geiger MJ, eds., Proc. 14th EU/ME Workshop, Hamburg, Germany, 110–115.Google Scholar
  • Expósito-Izquierdo C , Rossi A , Sevaux M (2016) A two-level solution approach to solve the clustered capacitated vehicle routing problem. Comput. Industrial Engrg. 91:274–289.Google Scholar
  • Feillet D , Dejax P , Gendreau M (2005) Traveling salesman problems with profits. Transportation Sci. 39(2):188–205.Google Scholar
  • Franquesa C (2008) The clustered prize-collecting arc routing problem. PhD dissertation, Technical University of Catalonia, Barcelona, Spain.Google Scholar
  • Ghiani G , Laporte G (2014) The undirected rural postman problem. Corberán Á, Laporte G, eds. Arc Routing (Society for Industrial and Applied Mathematics, Philadelphia), 85–99.Google Scholar
  • Golden BL , Wong RT (1981) Capacitated arc routing problems. Networks 11(3):305–315.Google Scholar
  • Golden B , Dearmon J , Baker E (1983) Computational experiments with algorithms for a class of routing problems. Comput. Oper. Res. 10(1):47–59.Google Scholar
  • Gomory R , Hu T (1961) Multi-terminal network flows. J. Soc. Industrial Appl. Math. 9(4):551–570.Google Scholar
  • Hansen P , Mladenović N (2001) Variable neighborhood search: Principles and applications. Eur. J. Oper. Res. 130(3):449–467.Google Scholar
  • Hintsch T (2021) Large multiple neighborhood search for the soft-clustered vehicle-routing problem. Comput. Oper. 129: 105132.Google Scholar
  • Hintsch T , Irnich S (2018) Large multiple neighborhood search for the clustered vehicle-routing problem. Eur. J. Oper. Res. 270(1):118–131.Google Scholar
  • Hintsch T , Irnich S (2019) Exact solution of the soft-clustered vehicle-routing problem. Eur. J. Oper. Res. 280:164–178.Google Scholar
  • Irnich S , Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 33–65.Crossref, Google Scholar
  • Irnich S , Toth P , Vigo D( 2014) The family of vehicle routing problems. Vigo D, Toth P, eds. Vehicle Routing (Society for Industrial and Applied Mathematics, Philadelphia), 1–33.Google Scholar
  • Jepsen M , Petersen B , Spoorendonk S , Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Google Scholar
  • Kiuchi M , Shinano Y , Hirabayashi R , Saruwatari Y (1995) [An exact algorithm for the capacitated arc routing problem using parallel branch and bound method.] Spring National Conf. of the Operational Research Society of Japan, 28–29.Google Scholar
  • Letchford AN , Reinelt G , Theis DO (2004) A faster exact separation algorithm for blossom inequalities. Bienstock D, Nemhauser G, eds, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 3064 (Springer, Berlin), 196–205.Google Scholar
  • Letchford AN , Reinelt G , Theis DO (2008) Odd minimum cut sets and b-matchings revisited. SIAM J. Discrete Math. 22(4):1480–1487.Google Scholar
  • Li LYO , Eglese RW (1996) An interactive algorithm for vehicle routing for winter-gritting. J. Oper. Res. Soc. 47(2):217–228.Google Scholar
  • Lübbecke ME , Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Google Scholar
  • Mourão MC , Pinto LS (2017) An updated annotated bibliography on arc routing problems. Networks 70(3):144–194.Google Scholar
  • Pecin D , Pessoa A , Poggi M , Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Google Scholar
  • Pop PC , Fuksz L , Marc AH , Sabo C (2018) A novel two-level optimization approach for clustered vehicle routing problem. Comput. Indust. Engrg. 115(Supplement C):304–318.Google Scholar
  • Sevaux M , Sörensen K (2008) Hamiltonian paths in large clustered routing problems. Proc. EU/MEeting 2008 Workshop on Metaheuristics for Logistics and Vehicle Routing, vol. 8, 411–417.Google Scholar
  • Vidal T , Battarra M , Subramanian A , Erdoǧan G (2015) Hybrid metaheuristics for the clustered vehicle routing problem. Comput. Oper. Res. 58:87–99.Google Scholar
  • Ward J Jr (1963) Hierarchical grouping to optimize an objective function. J. Amer. Statist. Assoc. 58(301):236–244.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree