Vehicle Routing Problem Solved through Heuristics Procedures

A Case Study

Abstract

This paper presents a Vehicle Routing Problem (VRP) to be solved through heuristics procedures. The methodology used consisted in a two-phase process: 1) Defining clusters in order to divide the region into pieces and then 2) Develop the routes in each of these smaller regions. To solve the first part, we used the Facility Location Problem (FLP) mathematical model, the heuristics Genetic Algorithm (GA), Teitz & Bart (T&B) Algorithm and also a hybrid method, combining GA and T&B, comparatively. We have to emphasize that the T & B algorithm has hardly been used by the researchers, although it provides quite promising results. For the second part, we use the Chinese Postman Problem (CPP) to develop the routes. We applied those methods in order to find routes for employees of an electric energy company, located in São José dos Pinhais, Paraná, Brazil. Two scenarios were developed and we found that in both scenarios the hybrid method (GA and T&B) presented the best result in order to create better routes for the employees.