Improving parametric Clarke and Wright algorithms by means of iterative empirically adjusted greedy heurístics,

• Autores: Albert Corominas Subias , Alberto García Villoria , Rafael Pastor Moreno
• Localización: Sort: Statistics and Operations Research Transactions, ISSN 1696-2281, Vol. 38, Nº. 1, 2014, págs. 3-12
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Resumen

  • Since Clarke and Wright proposed their well-known savings algorithm for solving the Capacitated Vehicle Routing Problem, several enhancements to the original savings formula have been recently proposed, in the form of parameterisations. In this paper we first propose to use Empirically Adjusted Greedy Heuristics to run these parameterized heuristics and we also consider the addition of new parameters. This approach is shown to improve the savings algorithms proposed in the literature. Moreover, we propose a new procedure which leads to even better solutions, based on what we call Iterative Empirically Adjusted Greedy Heuristics.

• Referencias bibliográficas
  • Adenso-Dı́az, B. and Laguna, M. (2006). Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research,...
  • Altinel, I. K. and Öncan, T. (2005). A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem....
  • Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D. and Rinaldi, G. (1995). Computational results with a Branch and Cut...
  • Battarra, M., Golden, B. and Vigo, D. (2008). Tuning a parametric Clarke-Wright heuristic via a genetic algorithm. Journal of the Operational...
  • Christofides, N. and Eilon, S. (1969). An algorithm for the vehicle routing dispatching problem. Operations Research Quarterly, 20, 309–18.
  • Christofides, N., Mingozzi, A. and Toth, P. (1979). The Vehicle Routing Problem. Combinatorial Optimization, Christofides, N., Mingozzi, A.,...
  • Clarke, G. andWright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568–81.
  • Corominas, A. (2005). Empirically Adjusted Greedy Algoriths (EAGH): A new approach to solving combinatorial optimisation problems. Working...
  • Corominas, A., Garcı́a-Villoria, A. and Pastor, R. (2010). Fine-tuning a parametric Clarke and Wright heuristic by means of EAGH (empirically...
  • Doyuran, T. and Çatay, B. (2011). A robust enhancement to the Clarke-Wright savings algorithm. Journal of the Operational Research Society,...
  • Gaskell, T. J. (1967). Bases for vehicle fleet scheduling. Operations Research Quarterly, 18, 281–95.
  • Lagarias, J. C., Reeds, J. A., Wright, M. H. and Wright, P. E. (1998). Convergence properties of the NelderMead simplex method in low dimensions....
  • Laporte, G., Gendreau, M., Potvin, J.and Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International...
  • Nelder, J. A. and Mead, R. (1965). A simplex method for function minimization. The Computer Journal, 7, 308–13.
  • Paessens, H. (1988). The savings algorithm for the vehicle routing problem. European Journal of Operational Research, 34, 336–44.
  • Yellow, P. (1970). A computational modification to the savings method of vehicle scheduling. Operations Research Quarterly, 21, 281–83.