Solving the capacitated vehicle routing problem with stochastic demands applying the simulated annealing algorithm

Abstract

A new hybrid algorithm for solving the capacitated vehicle routing problem (CVRP) with stochastic demands is proposed. This new approach combines the simulated annealing (SA) with the savings algorithms and is implemented to obtain results of several Solomon’s instances of CVRP. This approach is named simulated annealing with metropolis cycle based on savings algorithm (SAMCSA). SA is a bio-inspired metaheuristic, an emulation of the heating and cooling processes of solids to solve optimization problems. On the other hand, the savings algorithm is a deterministic heuristic for solving CVRP. In order to generate high quality solutions of CVRP, this approach applies the savings algorithm into metropolis cycle of simulated annealing. An initial solution of SA is also generated by the savings algorithm. This simple change has lead to increase the solution quality for the CVRP with respect to the classical simulated annealing and savings algorithms

Keywords

• simulated annealing
• savings algorithm
• vehicle routing problem
• metaheuristic