The capacitated trick-or-treat problem

Ok, you modeled for your kid the problem of visiting all the possible houses using the minimum energy consumption as a traveling salesman problem. But now that you look at the solution and realize that it will be not possible to visit all the houses without a bag, and even though, the amount of candies to be collected may be too large (too many or too heavy) and suggest your son : 1) to use a bag to collect all the candies; and 2) to return home to empty the bag whenever it becomes full. How would one model and solve this combinatorial optimization problem? Let us call The OR Guy!


The OR Guy looks at our problem and discovers that, the bag capacity imposes a novel type of constraint that was not taken care of in our previous model. You may think, no problem bro! if CONCORDE could solve the TSP for very large instances, there must be something of the like that shall solve this new –capacitated– problem for similarly large instances! Well… not… like… so…

When a TSP is constrained using capacities and becomes impossible to visit all the nodes using single tour, the resulting problem becomes substantially much harder. That is the problem with these not-so-scalable algorithms. They are very problem-specific and may not scale AT ALL even for small changes. The problem faced by this enthusiast father and his kid is known in the scientific literature as the capacitated vehicle routing problem (CVRP). A model similar to the one of Dantzig, Fulkerson & Johnson may be devised in which the capacity constraints are set by modifying the subtour elimination constraints by constraints of the form:

x(\delta(I)) \geq 2 k(I)\qquad I\subset H, |I|\geq 2,

where k(I) is a lower bound on the number of different tours that need to be used to visit all the nodes in I. How difficult becomes this new problem with respect to the uncapacitated version (the TSP)? For the reader to have an idea, while the CONCORDE algorithm can solve problems containing several thousand nodes, the state-of-the-art solver for the CVRP (Pecin et al. 2014) can solve problems containing no more than a few hundred nodes.

Leave a Reply