Metaheurísticas para as variantes do problema de roteamento de veículos: capacitado, com janela de tempo e com tempo de viagem estocástico

Abstract

The assigning and the planning of vehicles routes is a crucial problem in thesupply chain management. In the real-life environment it is common to find problems inwhich there is a large number of customers. Those problems can not be solved by exactmethods in reasonable time. In this context, this work aims to develop metaheuristicsthat are able to solve some of the most important versions of the vehicle routingproblems (VRP): the Capacitated VRP, the Capacitated VRP with maximum distanceand the VRP with Time Windows. The developed metaheuristics combine the strengthsof the successful strategies such as Tabu Search, Guided Local Search and AdaptiveMemory Procedure into an Iterated Local Search and Variable Neighborhood Descentstructure.The real-life environment is also made of probabilistic data by nature,as the travel time between two customers. This fact makes the models that consider theenvironment uncertain more appropriate. In this context, the present work develops ametaheuristic capable to solve a VRP with Time Windows in which the travel timeamong the customers is known just probabilistically. This problem is known asStochastic Vehicle Routing Problem with Time Windows (SVRPTW). This problemcombines stochastic travel times with VRP with Time Windows (VRPTW). Amethodology is developed to estimate the vehicle arriving time at each customerlocation and also to estimate the vehicle`s probability to respect the customer`s timewindow. To our knowledge, this method is unprecedented in the literature. Thealgorithm finds the best route with minimum expected cost while it guarantees thatcertain levels of service are met. Simulation results are used to demonstrate that theproposed methodology outperformed other recent methods in the literature.