Well, you now know how to model and solve the problem of visiting all the houses in your neighborhood in the uncapacitated case and also in the case in which your kid has a limited capacity for collecting candies. But now you again analyze the solution given by the solver and realize that each single tour would require a substantial amount of effort for your kid and you are not sure whether he can accomplish that. You would like to add the following requirement: impose every tour to consume a bounded amount of a certain resource (e.g. time or energy).

What do we do? Yes… let us call The OR Guy! But how might he help us? After analyzing the scientific literature we realize that these types of constraints are usually modeled as restrictions on every possible (feasible) tour in the solution. This takes us to the following question. Is there an efficient manner to incorporate such type of requirement in the model? Well, more or less. The two models introduced before do not take into account the relationship between all the decisions associated to the same tour. Indeed, the edge variables make it difficult to incorporate that information explicitly in the model. Column generation (CG) is a modeling technique that allows us to label each routing decision using the tour to which it is associated. Route length constraints can then be easily incorporated as they only link the routing decisions associated to a single tour. Although CG is a technique not especially devised for vehicle routing problems only (it has been applied with success to a variety of other problems  such as crew scheduling, clustering, location analysis, to name a few), it is in vehicle routing applications that it has shown to be extremely efficient when compared to their classic flow-based counterparts. Not only it allows for a more efficient solution of vehicle routing problems, it also allows the modeling of complex features that may be otherwise impossible to model using flow-based models. A set-partitioning model for the problem would now be as follows: Let be the set of feasible tours of the problem, this is tours that satisfy –each of them separately– the maximum ride time constraints. For each , let be a binary variable taking the value 1 iff the tour is used in the optimal routing, with cost . For every house , let be a binary constant taking the value 1 iff the house is visited in the route . The model is:

subject to

This model contains a HUGE number of variables, and cannot be solved explictly by a priori enumerating all the possible routes in . CG mimics the simplex method by solving a restricted master problem (RMP) including a limited number of variables associated to a set and then pricing on the remaining variables to either prove the optimality of the current basis or to find new variables to enter it. Successful applications of CG for vehicle routing include the articles of Pecin et al. 2014, 2017, Contardo & Martinelli 2014.