This paper presents a column generation algorithm for the Capacitated Vehicle Routing Problem (CVRP) and the Vehicle Routing Problem with Time Windows (VRPTW). Traditionally, column generation models of the CVRP and VRPTW have consisted of a Set Partitioning master problem with each column representing a route. Elementary routes (no customer visited more than once) have shown superior results for both CVRP and VRPTW. However, the pricing problems do not scale well when the number of feasible routes increases. We suggest to relax that ‘each column is a route’ into ‘each column is a part of the giant tour’; a so-called partial path, i.e., not necessarily starting and ending in the depot. This way, the length of the partial path can be bounded and a better control of the size of the solution space for the pricing problem can be obtained.
column generation; elementary shortest path problem; vehicle routing problem