Exploring a column generation approach for a routing problem with sequential packing constraints

By Pinto, T.; Alves, C.; De Carvalho, J.V.

Operations Research and Big Data: IO2015-XVII Congress of Portuguese Association of Operational Research (APDIO)



In this work we propose a computational study of a column generation based heuristic prototype for the vehicle routing problem with two-dimensional loading constraints. This prototype was recently proposed in literature (Pinto et al., 2013) and it relies in a column generation algorithm whose subproblem is relaxed. After solving the subproblem, the feasibility of the routes is verified using lower bounds and the classical bottom-left heuristic, enhanced with sequential constraints. For the infeasible routes, a simple route shortening process is applied, and the feasibility is tested again. The effectiveness of our approach is evaluated using benchmark instances from the literature.


Google Scholar: