Uma abordagem exata unificada para uma classe de problemas de roteamento de veículos com coleta e entrega simultâneas

Abstract

The Vehicle Routing Problem (VRP) is a classical combinatorial optimization problem widely studied in the literature. By de nition, it consists in determining least-cost routes, starting and ending at the depot, to meet the demands of a set of customers. There is a substantial number of variants of the problem, which might include additional attributes such as a heterogeneous eet of vehicles, time windows, and so on. Among them, there is the VRP with Simultaneous Pickup and Delivery (VRPSPD), where customers have both pickup and delivery demands to be satis ed in a single visit. In this context, this work aims at proposing a uni ed exact approach based on column generation and cutting planes to solve ten VRPSPD variants including the classic version of the problem. This approach uses the VRPSolver, which is a state-of-the-art branch-cut-and-price solver for routing and similar problems. The results show that the proposed approach is highly e ective in obtaining the optimal solutions or improving the dual bounds for many open benchmark instances.