Column generation based primal heuristics for routing and loading problems

Abstract

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.