Column generation based heuristic for a vehicle routing problem with 2-dimensional loading constraints : a prototype

In this paper, we propose a new approach for a vehicle routing problem with 2- dimensional loading constraints. Our approach relies on a column generation based heuristic which can be described in two distinct phases. In the rst phase, strategies are proposed to generate initial columns for the restricted master problem corresponding to valid routes. In the second phase, the restricted master problem provides information for the solution of a relaxed subproblem. The aim of this subproblem is to nd attractive columns, which are in fact routes. A bottom-left heuristic is also proposed to validate the obtained routes both in terms of the packing and the sequencing constraints. A route shortening process is described to build a feasible route for the cases in which the bottom-left heuristic is not successful