Enhanced simulated annealing in the vehicle routing problem

The vehicle routing problem (VRP) is to find routes for a fleet of vehicles located at a central depot and for several distant customers. This problem is NP-hard because it can be seen as a merge of the travelling salesman problem and the bin packing problem. In this paper we describe an enhanced simulated annealing approach and an algorithm for the VRP based on this approach. We present computational results of this algorithm on benchmark instances of the VRP.