Considerations on Applying Cross Entropy Methods to the Vehicle Routing Problem

  • Marta Cabo ITAM, Department of Mathematics
  • Edgar Possani ITAM, Department of Mathematics
Keywords: Cross Entropy, Heuristics, Vehicle Routing Problem

Abstract

The cross entropy method was initially developed to estimate rare event probabilities through simulation, and has been adapted successfully to solve combinatorial optimization problems. In this paper we aim to explore the viability of using cross entropy methods for the vehicle routing problem. Published implementations to this problem have only considered a naive route-splitting scheme over a very limited set of instances. In addition of presenting a better route-splitting algorithm we designed a cluster-first/route-second approach. We provide computational results to evaluate these approaches, and discuss its advantages and drawbacks. The innovative method, developed in this paper, to generate clusters may be applied in other settings. We also suggest improvements to the convergence of the general cross entropy method.

Published
2015-11-15
How to Cite
Cabo, M., & Possani, E. (2015). Considerations on Applying Cross Entropy Methods to the Vehicle Routing Problem. International Journal of Combinatorial Optimization Problems and Informatics, 6(3), 22-33. Retrieved from https://ijcopi.org/ojs/article/view/49
Section
Articles