An Evaluation of the Cross Entropy Method to Solve Vehicle Routing Problems

We present in this paper the application of a cross entropy method (CEM) to the vehicle routing problem (VRP). The CEM is a heuristic based on the statistical method of importance sampling for rare event simulation. We found that the CEM can be easily adapted to different versions of the VRP, yielding consistently good quality solutions. We also present a short sensitivity analysis of the different parameters of the heuristic that sheds light on their impact on the performance of the heuristic and the quality of the solutions