Uma abordagem heurística para o problema de roteamento de veículos com designação de entregadores extras

Abstract

The pursuit of excellence in customer service drives companies to investigate strategies that help to produce satisfactory solutions to the market, as is the case of beverage companies. One of the obstacles faced by this sector is the difficulty in distributing the demanded products within regular working hours due to long service times in each demand site. An alternative for reducing violations of route time consists in including the assignment of extra deliverymen to the usual routing and scheduling decisions. Such treatment is hardly often explored in the literature and it was not found any evidence of commercial softwares that consider it. In this sense, the current work addresses the Vehicle Routing Problem with the assignment of extra deliverymen, with the aim of generating routes in which the number of unserved clients in regular working hours is minimized. To this end, we propose an extension of Clarke and Wright heuristic. The proposed extension is applied to sets of examples generated based on classic instances of Solomon (1987) and Christofides et al. (1979). The results of the application are compared to those provided by the heuristic of Clarke and Wright according to a set of performance criteria.