Um método para a roteirização de veículos em regiões com restrições de circulação

Abstract

Traffic restrictions for trucks in urban centers are increasingly being adopted to try to reduce congestion levels. With this, distribution companies need to create routes optimized to meet the demand of their customers, but respecting the restrictions of tra c of vehicles. This work aims to propose a method for vehicle routing in regions with tra c restrictions. Because it is an NP-di cult problem, exact methods require unacceptable computational times in problems involving many clients, i.e. actual problems. Thus, the proposed method uses, separately, the Variable Neighborhood Search (VNS) and the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristics to find sub-optimal routes, which may be optimal for vehicles. Four algorithms were developed and compared using the VNS and GRASP metaheuristics; both being applied once with time dependence and again with clustering. As validation, this work used the data of a real distributor of the city of São Paulo, from these were created 27 instances for the accomplishment of the experiments in the cities of Fortaleza, Recife and São Paulo. These cities were chosen because they have tra c restrictions. The results show that the method is able to handle di erent routing scenarios, achieving a good result for the VNS and GRASP metaheuristics