AN ALGORITHM WITH COLUMN AND CUT GENERATION FOR THE CAPACITATED VEHICLE ROUTING PROBLEM / UM ALGORITMO DE GERAÇÃO DE COLUNAS E CORTES PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS

AUTOR(ES)

MARCELO LADEIRA REIS

DATA DE PUBLICAÇÃO

2004

RESUMO

The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80`s when a suitable Lagrangean relaxation algorithm has demonstrated to be far better than the contemporary ones. This algorithm suggested the use of column generation algorithms that succeeded to become the best ones in the late 80`s and early 90`s. Finally, in the mid 90`s, cutting plane methods presented results that convinced the community that this should be the approach for solving the hardest CVRP problems. This dissertation presents an overview of those early algorithms and proposes a formulation that allows uniting the best contributions of them. The resulting algorithm, labeled as a branch-and-cut-and-price algorithm, deals with exponentially many variables and constraints that define a relaxed solution space that is the intersection of the relaxed solution spaces considered in the previous algorithms. The dissertation also describes a specially devised dynamic programming algorithm to solve the column generation subproblem and discusses robust branching strategies that altogether allowed to build an algorithm that perfoms well on several different classes of instances. The computational experience has shown that the approach here proposed leads to lower bounds superior than the previous ones. Moreover, it allowed to consistently solve instances with up to 135 vertices, including 18 that were solved for the first time.

ASSUNTO(S)

column generation roteamento de veiculos programacao inteira metodos de planos de corte vehicle routing integer linear programming geracao de colunas cutting planes methods

Documentos Relacionados

• Busca tabu aplicada ao problema de roteamento periodico de veiculos
• Geração de colunas para o problema de dimensionamento de lotes de produção com limitações de capacidade
• INTEGRATING METAHEURISTICS WITH MIP SOLVERS TO THE CAPACITATED VEHICLE ROUTING PROBLEM
• The period vehicle routing problem.
• Uma abordagem heurística para o problema de roteamento de veículos com designação de entregadores extras