Heurísticas e algoritmo exato para o problema de roteamento de veículos com coleta e entrega simultâneas

Abstract

This work adresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery, where routes must be devised to fulfil the pickup and delivery requests of a set of customers. Each customer must be served by only one route, the load it receives isbrought from a central depot, to where the picked-up load is also taken. The capacity of the used vehicles must not be violated at any point of the routes. Heuristics and anexact algorithm are proposed to solve the problem. Initially, we devise some heuristics based on ideas of many metaheuristics, specially ILS, GRASP, and VND. These heuristics are tested in many instances and are compared to the best results of the literature, obtaining results comparable to the best existing algorithms. Afterwards, aBranch-and-price method is developed, and in this context, we propose new strategies to the resolution of the subproblem, an Elementary Resource Constrained Shortest Path Problem. Based on computational experiments, these strategies show considerable reduction on the computational time of the Column Generation resolution. Wepresent a strategy in which lower bounds obtained from the column generation are used in the branching process. The Branch-and-price algorithm is tested and compared to a Branch-and-cut-and-price algorithm from the literature.