Relaxation induced methods based on column generation for vehicle routing problems
Rita Macedo, Cláudio Alves, José Valério de Carvalho, Said Hanafi
Proceedings of the 2nd International Conference on Business Sustainability - BS11
Póvoa de Varzim, Portugal, June 2011

ABSTRACT
We address an hybrid method for the vehicle routing problem that combines column generation, branch-and-bound and relaxation based heuristics. In particular, we combine the hybrid linear programming based algorithm proposed by Hanafi and Wilbaut for mixed integer programming problems with branch-and-price. The heuristics proposed by Hanafi and Wilbaut are convergent; they consist of solving iteratively the linear relaxation of the problem, and in deriving lower and upper bounds. The linear relaxation model within the proposed exact algorithm corresponds to the well-known column generation model. Preliminary computational results are reported.

BIBTEX ENTRY
@inproceedings{MacedoAlvesCarvalhoHanafiBS11,
author = {Rita Macedo and Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho and Sa{\"i}d Hanafi},
title = {Relaxation induced methods based on column generation for vehicle routing problems},
booktitle = {Proceedings of the 2nd International Conference on Business Sustainability - BS11},
address = {P{\'o}voa de Varzim, Portugal},
year = {2011}}