Vehicle routing via column generation (Q1058983)

This paper explores an approximate method for solving a routing problem in a four-level distribution which has ''double-ended'' demand. Routes are represented as columns in a linear program and column generation is used to improve the solution by generating new routes. The generation of new routes is based on an LP subproblem. Its solution is rounded down to integer values to insure its feasibility as a route for inclusion in the restricted master problem. Finally, an illustrative problem is solved.