A Comparison of Cross Entropy Approaches for the Classical Vehicle Routing Problem

The cross entropy method (CEM) is a relatively new stochastic metaheuristic, initially developed to estimate rare event probabilities through simulation, that has been successfully applied to combinatorial optimization problems. However, it has not been widely applied to the vehicle routing problem (VRP). In this paper we review such applications of the CEM method to VRP, and propose new heuristics for the problem based on CEM. The main idea is to use a cluster-first route-second scheme, which yields better results than previous approaches of CEM for the same problems. To the authors' knowledge this is the first such application of the CEM scheme for clustering in general that could be applied to other problems. We provide computational results to evaluate this approach, and discuss its advantages and drawbacks