A heuristic for cumulative vehicle routing using column generation

Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we computationally study, an inexact approach for constructing solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation and is solved using column generation. The pricing subproblem is solved heuristically using dynamic programming. Simulation results show that a simple scalable strategy gives solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation.