Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 13, 2026

Available Issues

April 10, 2013 - May 13, 2026

An Adaptive Iterated Local Search for the Mixed Capacitated General Routing Problem

Published Online:25 Apr 2016https://doi.org/10.1287/trsc.2015.0660

References

  • Bach L, Hasle G, Wøhlk S (2013) A lower bound for the node, edge, and arc routing problem. Comput. Oper. Res. 40(4):943–952.Crossref, Google Scholar
  • Bach L, Lysgaard J, Wøhlk S (2014) A branch-and-cut-and-price algorithm for the mixed capacitated general routing problem. Bach L, ed. Routing and Scheduling Problems—Optimization Using Exact and Heuristic Methods. Doctoral dissertation, School of Business and Social Sciences, Aarhus University, Aarhus, Denmark, 37–75.Google Scholar
  • Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math. Programming 120(2):347–380.Crossref, Google Scholar
  • Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
  • Bartolini E, Cordeau J-F, Laporte G (2011) Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Programming 137(1–2):1–44.Google Scholar
  • Benavent E, Campos V, Corberán A, Mota M (1992) The capacitated arc routing problem. Lower bounds. Networks 22(7):669–690.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
  • Bodin L, Maniezzo V, Mingozzi A (2003) Street routing and scheduling problems. Hall RW, ed. Handbook of Transportation Science, Internat. Series Oper. Res. Management Sci., Vol. 56 (Springer Science+Business Media, New York), 413–449.Crossref, Google Scholar
  • Bosco A, Laganà D, Musmanno R, Vocaturo F (2013) Modeling and solving the mixed capacitated general routing problem. Optim. Lett. 7(7):1451–1469.Crossref, Google Scholar
  • Bosco A, Laganà D, Musmanno R, Vocaturo F (2014) A matheuristic algorithm for the mixed capacitated general routing problem. Networks 64(4):262–281.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
  • Christofides N, Eilon S (1969) An algorithm for the vehicle-dispatching problem. Oper. Res. Quart. 20(3):309–318.Crossref, Google Scholar
  • Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. Christofides N, Mingozzi A, Toth P, Sandi C, eds. Combinatorial Optimization (Wiley, Chichester, UK), 315–338.Google Scholar
  • Corberán A, Laporte D (2014) Arc Routing: Problems, Methods, and Applications, SIAM Monographs Discrete Math. Appl. (SIAM, Philadelphia).Google Scholar
  • Corberán A, Prins C (2010) Recent results on arc routing problems: An annotated bibliography. Networks 56(1):50–69.Crossref, Google Scholar
  • Corberán A, Letchford AN, Sanchis JM (2001) A cutting plane algorithm for the general routing problem. Math. Programming Ser. A 90:291–316.Crossref, Google Scholar
  • Corberán A, Mejia G, Sanchis JM (2005) New results on the mixed general routing problem. Oper. Res. 53(2):363–376.Link, Google Scholar
  • Corberán A, Mota E, Sanchis JM (2006) A comparison of two different formulations for arc routing problems on mixed graphs. Comput. Oper. Res. 33(12):3384–3402.Crossref, Google Scholar
  • Corberán A, Plana I, Sanchis JM (2007) A branch and cut algorithm for the windy general routing problem and special cases. Networks 49(4):245–257.Crossref, Google Scholar
  • Dell’Amico M, Díaz Díaz JC, Iori M (2012) The bin packing problem with precedence constraints. Oper. Res. 60(6):1491–1504.Link, Google Scholar
  • Golden B, Raghavan S, Wasil E, eds. (2008) The Vehicle Routing Problem: Latest Advances and New Challenges, Oper. Res./Comput. Sci. Interfaces Series, Vol. 43 (Springer-Verlag, Berlin Heidelberg).Crossref, Google Scholar
  • Golden BL, Wong RI (1981) Capacitated arc routing problems. Networks 11(3):305–315.Crossref, Google Scholar
  • Golden BL, DeArmon JS, Baker EK (1983) Computational experiments with algorithms for a class of routing problems. Comput. Oper. Res. 10(1):47–59.Crossref, Google Scholar
  • Golden BL, Wasil EA, Kelly JP, Chao IM (1998) Metaheuristics in vehicle routing. Crainic T, Laporte G, eds. Fleet Management and Logistics (Kluwer, Boston), 33–56.Crossref, Google Scholar
  • Gröer C, Golden B, Wasil E (2011) A parallel algorithm for the vehicle routing problem. INFORMS J. Comput. 23(2):315–330.Link, Google Scholar
  • Gutiérrez JCA, Soler D, Hérvas A (2002) The capacitated general routing problem on mixed graphs. Revista Investigacion Operacional 23(1):15–26.Google Scholar
  • Gutin G, Punnen AP, eds. (2006) The Traveling Salesman and Its Variations, Vol. 12 (Springer Science+Business Media, New York).Google Scholar
  • Hasle G (2014) Arc routing applications in newspaper delivery. Corberán A, Laporte D, eds. Arc Routing: Problems, Methods, and Applications, SIAM Monographs Discrete Math. Appl. (SIAM, Philadelphia), 371–395.Google Scholar
  • Hasle G, Kloster O, Smedsrud M, Gaze K (2012) Experiments on the node, edge, and arc routing problem. Technical Report A23265, SINTEF, Oslo, Norway.Google Scholar
  • Irnich S, Laganà D, Schlebusch C, Vocaturo F (2015) Two-phase branch-and-cut for the mixed capacitated general routing problem. Eur. J. Oper. Res. 243(1):17–29.Crossref, Google Scholar
  • Kokubugata H, Moriyama A, Kawashima H (2007) A practical solution using simulated annealing for general routing problems with nodes, edges, and arcs. Stützle T, Birattari M, Hoos HH, eds. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, Lecture Notes Comput. Sci., Vol. 4638 (Springer-Verlag, Berlin Heidelberg), 136–149.Crossref, Google Scholar
  • Lacomme P, Prins C, Ramdane-Chérif W (2004a) Competitive memetic algorithms for arc routing problems. Ann. Oper. Res. 131(1):159–185.Crossref, Google Scholar
  • Lacomme P, Prins C, Tanguy A (2004b) First competitive ant colony scheme for the carp. Dorigo M, Birattari M, Blum C, Gambardella LM, Mondada F, Stützle T, eds. Ant Colony Optimization and Swarm Intelligence, Lecture Notes Comput. Sci., Vol. 3172 (Springer-Verlag, Berlin Heidelberg), 426–427.Crossref, 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 (SIAM, Philadelphia), 87–116.Crossref, Google Scholar
  • Li F, Golden B, Wasil E (2005) Very large-scale vehicle routing: New test problems, algorithms, and results. Comput. Oper. Res. 32(5):1165–1179.Crossref, Google Scholar
  • Li LYO, Eglese RW (1996) An interactive algorithm for vehicle routing for winter-gritting. J. Oper. Res. Soc. 47:217–228.Crossref, Google Scholar
  • Lourenço HR, Martin OC, Stützle T (2010) Iterated local search: Framework and applications. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics, Internat. Series Oper. Res. Management Sci., 2nd ed., Vol. 146 (Springer-Verlag, Berlin Heidelberg), 363–398.Crossref, Google Scholar
  • Mandal SK, Pacciarelli D, Løkketangen A, Hasle G (2015) A memetic NSGA-II for the bi-objective mixed capacitated general routing problem. J. Heuristics 21(3):359–390.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 MP, Rebennack S, eds. Experimental Algorithms, Lecture Notes Comput. Sci., Vol. 6630 (Springer-Verlag, Berlin Heidelberg), 315–326.Crossref, Google Scholar
  • Mester D, Bräysy O (2007) Active-guided evolution strategies for large-scale vehicle routing problems. Comput. Oper. Res. 34(10):2964–2975.Crossref, Google Scholar
  • Nagata Y, Bräysy O (2009) Edge assembly based memetic algorithm for the capacitated vehicle routing problem. Networks 54(4):205–215.Crossref, Google Scholar
  • Orloff CS (1974) A fundamental problem in vehicle routing. Networks 4(1):35–64.Crossref, Google Scholar
  • Pandi R, Muralidharan B (1995) A capacitated general routing problem on mixed networks. Comput. Oper. Res. 22(5):465–478.Crossref, Google Scholar
  • Pisinger D, Røpke S (2007) A general heuristic for vehicle routing problems. Comput. Oper. Res. 34(8):2403–2435.Crossref, Google Scholar
  • Polacek M, Doerner KF, Hartl RF, Maniezzo V (2008) A variable neighborhood search for the capacitated arc routing problem with intermediate facilities. J. Heuristics 14(5):405–423.Crossref, Google Scholar
  • Prins C (2009) A GRASP × evolutionary local search hybrid for the vehicle routing problem. Pereira FB, Tavares J, eds. Bio-Inspired Algorithms for the Vehicle Routing Problem, Studies Comput. Intelligence, Vol. 161 (Springer-Verlag, Berlin Heidelberg), 35–53.Crossref, Google Scholar
  • Prins C (2014) The capacitated arc routing problem: Heuristics. Corberán A, Laporte G, eds. Arc Routing: Problems, Methods, and Applications (SIAM, Philadelphia), 131–157.Google Scholar
  • Prins C, Bouchenoua S (2005) A memetic algorithm solving the VRP, the CARP and general routing problems with nodes, edges and arcs. Hart WE, Krasnogor N, Smith JE, eds. Recent Advances in Memetic Algorithms, Studies Fuzziness Soft Comput., Vol. 166 (Springer-Verlag, Berlin Heidelberg), 65–85.Crossref, Google Scholar
  • Røpke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Sci. 40(4):455–472.Link, Google Scholar
  • Santos L, Coutinho-Rodrigues J, Current JR (2010) An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Res. Part B: Methodological 44(2):246–266.Crossref, Google Scholar
  • Shaw P (1997) A new local search algorithm providing high quality solutions to vehicle routing problems. Technical report, University of Strathclyde, Glasgow, UK.Google Scholar
  • Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. Maher M, Puget J-F, eds. Proc. Fourth Internat. Conf. Principles Practice Constraint Programming, Lecture Notes Comput. Sci., Vol. 1520 (Springer-Verlag, Berlin Heidelberg).Crossref, Google Scholar
  • Taillard ÉD (1993) Parallel iterative search methods for vehicle routing problems. Networks 23(8):661–673.Crossref, Google Scholar
  • Toth P, Vigo D (2002) An overview of vehicle routing problems. Toth P, Vigo D, eds. The Vehicle Routing Problem, SIAM Monographs Discrete Math. Appl. (SIAM, Philadelphia), 1–26.Crossref, Google Scholar
  • Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications, 2nd ed., SIAM Monographs Discrete Math. Appl. (SIAM, Philadelphia).Crossref, Google Scholar
  • Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60(3):611–624.Link, Google Scholar
  • Wøhlk S (2006) New lower bound for the capacitated arc routing problem. Comput. Oper. Res. 33(12):3458–3472.Crossref, Google Scholar
  • Wøhlk S (2008) A decade of capacitated arc routing. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Oper. Res./Comput. Sci. Interfaces Series, Vol. 43 (Springer-Verlag, Berlin Heidelberg), 29–48.Crossref, 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