Comparison Between the Branch and Bound and Evolutionary Algorithms to Solve the Classic Vehicle Routing Problem Known as VRP (#1499)

Authors

Moya Navarro, Marcos

Abstract

The routing model solution is an algorithmic challenge that seeks to optimize delivery routes to minimize the associated costs. Linear programming is a classical method proposed to find the minimum cost routes. Alternatively, heuristic and metaheuristic methodologies have been proposed to solve the routing problem. The objective of this work is to compare both the average time to find a solution and the average total distance traveled obtained by using an evolutionary genetic algorithm and a linear programming model. Five route configurations with ten, twenty, thirty, forty and fifty customers or nodes to visit were studied. Results pointed out that as the number of customers to visit is duplicated from ten to twenty, the average time to find the best solution is approximately ten times bigger when using a linear programming model. Moreover, when the number of customers doubles from twenty to forty, the average time to find the solution arises something about sixty-eight times the previous time. Conversely, the evolutionary genetic algorithm showed that the average time response to find a solution decreased significantly as the number of customers included in the model increased. Regarding the total distance traveled on the route, the linear programming model found a solution 96.26% lower than that found with the evolutionary method for a route with ten customers to visit, and 48.48% lower on a route with 50 clients. Recommendations based on results indicate that is convenient to find a solution through the linear programming model when fifty or less clients are included in the model. On the contrary, for more than fifty clients, it is more convenient to solve the vehicle routing problem by means of evolutionary genetic algorithms that needs significantly less time to find a problem solution and they also find solutions closer and closer than those found by the linear programming model as the numbers of customers increases.