Algoritmo memético paralelo baseado em ilhas com busca local Lin- Kernighan para solução do problema de roteamento de veículos heterogêneos em duas fases inspirado em um modelo de distribuição usado por atacadistas

Abstract

This thesis deals with a Two-Echelon Fixed Fleet Heterogeneous Vehicle Routing Problem faced by brazilian wholesale companies. Vehicle routing problems with more than one phase consider situations in which freight is moved through some intermediate facilities (e.g., cross-docks or distribution centers) before reaching its destination. The first phase of the problem dealt here is to choose a first-level vehicle, from an heterogeneous set, that will leave a depot and reach an intermediate uncapacitated facility (satellite) to serve a set of second-level vehicles. After that, it is necessary to define routes for smaller vehicles, also from an heterogeneous set, that will visit a set of customers departing from and returning to a satellite. The solution proposed here is an efficient island based memetic algorithm with a local search procedure based on Lin-Kernighan heuristic. In order to attest the algorithm’s efficiency, first it was tested in single echelon heterogeneous fleet vehicle routing benchmark instances. After that the instances were adapted for two-echelon context and used for validation alongside with real world instances created using normalized real data. Localsolver tool was also executed for comparison purposes. Promising results (which corroborate results obtained on the real problem) and future works are presented and discussed.