Solving Vehicle Routing Problem With Multi-Phases Simulated Annealing Algorithm

Solving Vehicle Routing Problem With Multi-Phases Simulated Annealing Algorithm

Ernesto Liñán-García (Instituto Tecnológico de Saltillo, Mexico), Helue I. De la Barrera-Gómez (Instituto Tecnológico de Saltillo, Mexico), Ana Laura Vázquez-Esquivel (Instituto Tecnológico de Saltillo, Mexico), Jesús Aguirre-García (Instituto Tecnológico de Saltillo, Mexico), Andrea Isabel Cervantes-Payan (Instituto Tecnológico de Saltillo, Mexico), Edgar Osvaldo Escobedo-Hernández (Instituto Tecnológico de Saltillo, Mexico) and Luis A. López-Alday (Instituto Tecnológico de Saltillo, Mexico)
DOI: 10.4018/978-1-5225-2990-3.ch022


In this chapter, a new multi-phases meta-heuristic algorithm based on Simulated Annealing(SA) is proposed in order to solve the Capacitated Vehicle Routing Problem (CVRP) with stochastic demands. This algorithm is named Multi-Phases Simulated Annealing (MPSA), which has four phases of annealing, which are Fast Quenching Phase (FQP), the Annealing Boltzmann Phase (ABP), the Bose-Einstein Annealing Phase (BEAP), and the Dynamical Equilibrium Phase (DEP). These four phases are applied in different ranges of temperature in the Simulated Annealing. The proposed algorithm is applied to generate very close to optimal solution for a cleaning distribution company. Proposed approach is focused to the Vehicle Routing Problem with homogeneous capacities and stochastic demands to gain solutions where routes are the most economical, so based on this, the proposed algorithm is applied to solve the limited Capacity Vehicle Routing Problem (CVRP), trying to provide more effective and efficient metaheuristics.
Chapter Preview

Due to the fact that Vehicle Routing Problem could have many variables, as the number of vehicles, the vehicles capacity, demands of clients, amount of depots or distribution centers, as the amount of clients, among others, there are several variants or extensions of Vehicle Routing Problem. Some of the most typical variants are described as follows:

Complete Chapter List

Search this Book: