Formulações e algoritmos baseados em programação linear inteira para o problema quadrático da árvore geradora mínima = Formulations and algorithms based on linear integer programming for the quadratic minimum spanning tree problem.

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 setof 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 capacityof 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 heuristicsbased on ideas of many metaheuristics, specially ILS, GRASP, and VND. Theseheuristics are tested in many instances and are compared to the best results of theliterature, obtaining results comparable to the best existing algorithms. Afterwards, aBranch-and-price method is developed, and in this context, we propose new strategiesto the resolution of the subproblem, an Elementary Resource Constrained ShortestPath Problem. Based on computational experiments, these strategies show considerablereduction on the computational time of the Column Generation resolution. Wepresent a strategy in which lower bounds obtained from the column generation are usedin the branching process. The Branch-and-price algorithm is tested and compared toa Branch-and-cut-and-price algorithm from the literature.