In this chapter, a hybrid meta-heuristic algorithm is proposed, which is based on simulated annealing in order to solve the Vehicle Routing Problem (VRP) with stochastic demands. The proposed algorithm has several annealing phases, which are named Simulated Multi-annealing (SMA). This algorithm is combined with the Clarke and Wright saving algorithm (CW). This last algorithm was placed inside the Metropolis Cycle of Simulated Multi-annealing algorithm. The hybrid algorithm is applied to obtain optimal routes for a cleaning distribution company. The initial solution of VRP is generated by the CW Algorithm, and it was improved by the multi-annealing phases. The solutions into the metropolis cycle were generated by a solution perturbation approach, each solution was compared with a previous one in order to obtain an optimal one.
Top1. Introduction
The Planning of optimal routes for the distribution of goods to several business´s customers can generate important savings for companies. In order to improve the delivery services of goods to customers with different demands, distribution centers must arrange optimal vehicle routes to ensure lowest transportation and distribution costs. The Vehicle Routing Problem (VRP) is an important task in many private and public corporations, because several benefits can be obtained if it is solved.
This problem was introduced by Dantzig and is applied to design optimal routes, with the goal of servicing a number of customers with a fleet of vehicles subject to the following conditions and constraints: each customer is served by only one vehicle, the demands of all customer must be met, and the capacity of the vehicles may not be violated (Dantzig, 1954).
The objective of this problem is to determine the optimal route for each vehicle in order to serve multiple customers with known demands. There is a fleet of identical vehicles, which supply goods to a set of customers. In this problem, each vehicle of the fleet is assumed to have a common start point, a home base, which is called depot, so, each vehicle must start and finish at the depot. All customers are served by exactly one vehicle, such that the overall transportation cost of the routes are minimized (Dantzig, 1959). The cost of traveling between each pair of customers and between the depot and each customer is given.
There are different variants to the VRP, which are formulated based on the nature of the transported goods, the quality of service required, and the characteristics of the customers and the vehicles. Some of these variants are multi-depot VRP (MDVRP) (vidal, 2013), periodic VRP (PVRP), stochastic VRP (SVRP) (Flatberg, 2005), VRP with indows (VRPTW) among others.
The Vehicle Routing Problem and its variants are classified as NP-Hard Problems (Chiang, 1996; Braysy, 2004; Nagy, 2007). This problem has become one of the most widely studied problems in combinatorial optimization. There are many factors considered and many possibilities of permutation and combinations in order to find an optimal solution of a particular instance of this problem, VRP becomes more complex as constraints and the number of customers increases.
There are several computational algorithms, which are clustered in exact, heuristic and meta-heuristic methods. Those algorithms have been applied to solve VRP, but it is best solved by heuristics and meta-heuristics (Braysy, 2005; Laporte, 2014). Some exact algorithms have been proposed for solving the Vehicle Routing Problem (Laporte, 1987; Laporte, 1992). The advantage of using exact algorithms is that they always obtain optimal solutions to a certain size of the problem, but they become time inefficient for large instances. Due to this reason, several meta-heuristic methods have been designed to obtain sub-optimal solution of VRP variants, e.g., Ant Colony Optimization (Bell, 2010), Simulated Annealing (Hassan, 1993; Czech, 2002), Genetic Algorithm (Thangiah, 1995), (Homberger, 2005) and Tabu Search (Garcia, 1994; Ta, 2013) among others. The disadvantage of meta-heuristics is that they do not guarantee optimal solutions, but can generate solutions very close to the optimal in a reasonable processing time.