Skip to main content
Log in

Fine-tuning a parametric Clarke and Wright heuristic by means of EAGH (empirically adjusted greedy heuristics)

  • Technical Note
  • Published:
Journal of the Operational Research Society

Abstract

Altınel and Öncan (2005) (A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem) proposed a parametric Clarke and Wright heuristic to solve the capacitated vehicle routing problem (CVRP). The performance of this parametric heuristic is sensitive to fine-tuning. Antinel and Öncan used an enumerative parameter-setting approach and improved on the results obtained with the original Clarke and Wright heuristic, but their approach requires much more computation time to solve an instance. Battarra et al (2008) (Tuning a parametric Clarke–Wright heuristic through a genetic algorithm) proposed a genetic algorithm to set the parameter values. They succeeded in reducing the time needed to solve an instance, but the quality of the solution was slightly worse. In this paper, we propose to use the EAGH (empirically adjusted greedy heuristics) procedure to set the parameter values. A computational experiment shows the efficiency of EAGH; in an even shorter time, we improve on the best results obtained with any parametric Clarke and Wright heuristic method proposed in the literature.

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

Access this article

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2

Similar content being viewed by others

References

  • Altınel IK and Öncan T ( 2005 ). A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem . J Opl Res Soc 56 : 954 – 961 .

    Article  Google Scholar 

  • Augerat P, Belenguer JM, Benavent E, Corberán A, Naddef D and Rinaldi G ( 1995 ). Computational results with a branch and cut code for the capacitated vehicle routing problem . Technical Report RR 949-M, University Joseph Fourier : Grenoble, France .

  • Battarra M, Golden B and Vigo D ( 2008 ). Tuning a parametric Clarke–Wright heuristic via a genetic algorithm . J Opl Res Soc 59 : 1568 – 1572 .

    Article  Google Scholar 

  • Christofides N and Eilon S ( 1969 ). An algorithm for the vehicle-dispatching problem . Opl Res Q 20 : 309 – 318 .

    Article  Google Scholar 

  • Christofides N, Mingozzi A and Toth P ( 1979 ). The vehicle routing problem . In: Christofides N, Mingozzi A, Toth P and Sandi C (eds) . Combinatorial Optimization . Chichester: Wiley, pp . 318 – 338 .

    Google Scholar 

  • Clarke G and Wright J ( 1964 ). Scheduling of vehicles from a central depot to a number of delivery points . Opns Res 12 : 568 – 581 .

    Article  Google Scholar 

  • Corominas A ( 2005 ). Empirically adjusted greedy algorithms (EAGH) : A new approach to solving combinatorial optimisation problems, Working paper IOC-DT-P-2005-22, Universitat Politècnica de Catalunya, Spain . Available at http://hdl.handle.net/2117/510 .

  • Gaskell TJ ( 1967 ). Bases for vehicle fleet scheduling . Opl Res Q 18 : 281 – 295 .

    Article  Google Scholar 

  • Nelder JA and Mead R ( 1965 ). A simplex method for function minimization . Comp J 7 : 308 – 313 .

    Article  Google Scholar 

  • Paessens H ( 1988 ). The savings algorithm for the vehicle routing problem . Eur J Opl Res 34 : 336 – 344 .

    Article  Google Scholar 

  • Yellow P ( 1970 ). A computational modification to the savings method of vehicle scheduling . Opl Res Q 21 : 281 – 283 .

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to R Pastor.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Corominas, A., García-Villoria, A. & Pastor, R. Fine-tuning a parametric Clarke and Wright heuristic by means of EAGH (empirically adjusted greedy heuristics). J Oper Res Soc 61, 1309–1314 (2010). https://doi.org/10.1057/jors.2009.89

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

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

Keywords

Navigation