Skip to main content
SpringerLink
Log in

A heuristic method for the capacitated arc routing problem with refill points and multiple loads

  • Case-Oriented Paper
  • Published:
Journal of the Operational Research Society

Abstract

We describe a solution procedure for a capacitated arc routing problem with refill points and multiple loads. This problem stems from the road network marking in Quebec, Canada. Two different types of vehicles are used: the first type (called servicing vehicle—SV) with a finite capacity to service the arcs and the other (called refilling vehicle—RV) to refill the SV vehicle. The RV can deliver multiple loads, which means that it meets the SV several times before returning to the depot. The problem consists of simultaneously determining the vehicle routes that minimize the total cost of the two vehicles. We present an integer formulation and a route first-cluster second heuristic procedure. Computational results are provided.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7

Similar content being viewed by others

References

  • Amaya CA, Langevin A and Trépanier M ( 2007 ). The capacitated arc routing problem with refill points . Opns Res Lett 35 : 45 – 53 .

    Article  Google Scholar 

  • Assad AA and Golden BL ( 1995 ). Arc routing methods and applications . In: Ball MO, Magnanti TL, Monma CL and Nemhauser GL (eds) . Network Routing, Handbooks in Operations Research and Management Science . North-Holland: Amsterdam, The Netherlands, pp . 375 – 483 .

    Google Scholar 

  • Belenguer JM and Benavent E ( 1998 ). The capacitated arc routing problem: Valid inequalities and facets . Comput Optim Appl 10 : 165 – 187 .

    Article  Google Scholar 

  • Belenguer JM, Benavent E, Lacomme P and Prins C ( 2006 ). Lower and upper bounds for the mixed capacitated arc routing problem . Comput Opns Res 33 : 3363 – 3383 .

    Article  Google Scholar 

  • Benavent E, Campos V, Corberán A and Mota E ( 1990 ). The capacitated arc routing problem: Lower Bounds . Networks 22 : 669 – 690 .

    Article  Google Scholar 

  • Christofides N, Campos V, Corberán A and Mota E ( 1986 ). An algorithm for the rural postman problem on a directed graph . Math Program Stud 26 : 155 – 166 .

    Article  Google Scholar 

  • Dror M ( 2000 ). Arc Routing: Theory, Solutions and Applications . Kluwer Academic Publishers: Boston .

    Book  Google Scholar 

  • Eglese R and Letchford A ( 2000 ). Polyhedral theory for arc routing problems . In: Dror M (ed) . Arc Routing: Theory, Solutions and Applications . Kluwer Academic Publishers: Boston, pp . 199 – 226 .

    Chapter  Google Scholar 

  • Golden BL and Wong RT ( 1981 ). Capacitated arc routing problems . Networks 11 : 305 – 315 .

    Article  Google Scholar 

  • In: Gross J and Yellen J (eds) . Handbook of Graph Theory. Discrete Mathematics and its Applications . CRC Press: London .

  • Hertz A ( 2005 ). Recent trends in arc routing . In: Golumbic MC and Ben-Arroyo Hartman I (eds) . Graph Theory, Combinatorics and Algorithmics: Interdisciplinary Applications . Springer: Berlin, pp . 215 – 236 .

    Chapter  Google Scholar 

  • Hertz A and Mittaz M ( 2000 ). Heuristics algorithms . In: Dror M (ed) . Arc Routing: Theory, Solutions and Applications . Kluwer Academic Publishers: Boston, pp . 327 – 386 .

    Chapter  Google Scholar 

  • Hirabayashi R, Saruwatari Y and Nishida N ( 1992 ). Tour construction algorithm for the capacitated arc routing problems . Asia Pac J Opns Res 9 : 155 – 175 .

    Google Scholar 

  • Marzolf F, Trépanier M and Langevin A ( 2006 ). Road network monitoring: Algorithms and a case study . Comput Opns Res 33 : 3494 – 3507 .

    Article  Google Scholar 

  • Perrier N, Langevin A and Amaya A ( 2008 ). Vehicle routing for urban snow plowing operations . Transport Sci 42 ( 1 ): 44 – 56 .

    Article  Google Scholar 

  • Sniezek J, Bodin L, Levy L and Ball M ( 2002 ). Capacitated arc routing problem with vehicle-site dependencies: The Philadelphia experience . In: Toth P and Vigo D (eds) . The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications . SIAM: Philadelphia, pp . 287 – 330 .

    Google Scholar 

  • Ulusoy G ( 1985 ). The fleet size and mix problem for capacitated arc routing . Eur J Opl Res 22 : 329 – 337 .

    Article  Google Scholar 

  • Wøhlk S ( 2006 ). New lower bound for the capacitated arc routing problem . Comput Opns Res 33 : 3458 – 3472 .

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universidad de Los Andes, Bogotá, Colombia

    C-A Amaya

  2. École Polytechnique de Montréal, Québec, Canada

    A Langevin & M Trépanier

Authors
  1. C-A Amaya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A Langevin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M Trépanier
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A Langevin.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Amaya, CA., Langevin, A. & Trépanier, M. A heuristic method for the capacitated arc routing problem with refill points and multiple loads. J Oper Res Soc 61, 1095–1103 (2010). https://doi.org/10.1057/jors.2009.58

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.58

Keywords

Search

Navigation