Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems

The capacitated vehicle routing problem (CVRP) is one of the elemental problems in supply chain management. The objective of CVRP is to deliver a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a delivery depot. CVRP is a difficult combinatorial problem, since it contains both the bin packing problem and the traveling salesperson problem as special cases. A simulated annealing combining local search approach is developed in this research to solve the capacitated vehicle routing problems. Computational results are reported on a sample of fourteen benchmark problems which have different settings. The developed approach obtained six solutions which are equal to the best solution found so far using the reasonable computing time. And the solutions obtained have the smaller relative deviation percentage (RDP) when compared with the best solution found so far in the literature. Therefore, the developed approach can perform well in different problem settings.