Uma solução computacional para otimização do problema de roteamento de veículos com coletas e entregas simultâneas e janelas de tempo em uma transportadora rodoviária de cargas

Abstract

According to the National Transport Confederation (CNT), the road transport system represents the means by which approximately 60% of the cargo is transported in Brazil, thus making it more representative of existing modes. In the field of road transport, freight carriers play a decisive role in the movement of goods in productive chains of different segments of the economy. To meet the requirements of quality and operational excellence, such as carriers to plan their routes interconnecting their warehouses to customers of efficient and economical efficiency, meeting the demand, respecting a transport capacity, collection and delivery sequence and windows of visits. Scale planning is called in the literature as the vehicle routing problem (PRV). Considered an NP-Hard class problem, it is not known computationally efficient algorithm for its resolution, especially when evaluating real practical situations. In this sense, this work proposes the construction of a tool (software), called Roteirizador, based on a hybrid metaheuristic algorithm (AH). Formed by the combination of Tabu Search (TB) and Genetic Algorithm metaheuristics (AG), AH allows to combine the best characteristics of both techniques, providing superior results when compared to the application of each technique individually. In this way, the Roteirizador, inserted in the computational environment of a road transport operator of loads, looks for to improve the efficiency of the planning of routes. The AH presented in 50% of the experiments, results superior or very close to the optimal values presented in the literature, and in the experiments performed in an unit of the Carrier, all the scenarios presented a gain in relation to the currently executed process. The Roteirizador, based on the AH, presented the possibility of saving an amount of more than R$ 500,000 per year, solely by reducing the distance traveled by vehicles. In addition to the distance gain, the correct sizing of crew work hours eliminated the need for expenses related to the payment of overtime. Finally, there is also the possibility of a higher gain both in distance and in the number of vehicles used if Carrier reviews its policy of grouping customers by regions.