Column generation based primal heuristics for routing and loading problems

In this paper, we explore a set of new heuristic strategies integrated within the column generation algorithm to solve the Capacitated Vehicle Routing Problem with 2-Dimensional Loading constraints. These heuristics rely on constructive procedures that iteratively build a solution using the solutions of a mixed integer linear programming model. The pricing subproblem is also heuristically solved, using strategies relying on variable neighborhood search algorithms proposed in literature. Column generation approaches for the 2L-CVRP are not quite explored. This paper aims to contribute with new strategies to tackle this problem. All the approaches were implemented and an exhaustive computational study is performed.This work has been supported by FEDER funding through the Programa Operacional Factores de Competitividade COMPETE and through the Portuguese Science and Technology Foundation (FCT): project UID/CEC/00319/2013 and grant SFRH/BD/73584/2010