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

AUTOR(ES)
DATA DE PUBLICAÇÃO

2010

RESUMO

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 an exact 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, a Branch-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. We present 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.

ASSUNTO(S)

otimização matemática teses. transporte rodoviário processamento de dados teses. algorimos de computador teses. computação teses.

ACESSO AO ARTIGO

Documentos Relacionados