# 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.

# the capacitated trick-or-treat problem with route length constraints

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 $x$ 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 $\Omega$ 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 $r\in\Omega$, let $x_r$ be a binary variable taking the value 1 iff the tour $r$ is used in the optimal routing, with cost $c_r$. For every house $h\in H$, let $a_{hr}$ be a binary constant taking the value 1 iff the house $h$ is visited in the route $r$. The model is:

$\min \sum\{c_rx_r:r\in\Omega\}$

subject to

$\sum\{a_{hr}x_r : r\in\Omega\} = 1 \qquad h\in H$

$x \text{ binary}$

This model contains a HUGE number of variables, and cannot be solved explictly by a priori enumerating all the possible routes in $\Omega$. CG mimics the simplex method by solving a restricted master problem (RMP) including a limited number of variables associated to a set $\Omega'$ and then pricing on the remaining variables $x_r, r\in\Omega\setminus\Omega'$ 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.

# The traveling trick-or-treat problem

It is the 31st, YEAH! It is halloween, YEAH! You or someone in your family (in my case, my 3yo son) must be excited about it. Tonight we collect candies! If you have kids (like I do), you know they cannot walk long distances, and quickly after knocking at a few front doors will get tired and ask dad/mom may you grab me in your arms? If you want to avoid having to do that, or at least reduce as much as possible the amount of time that you must grab your kid in your arms, you can fortunately call The OR Guy (whom if existed would be pretty much like the science guy but a lot less fancy or entertaining).

Let us assume that your kid has built a list $H$ of the houses he would like to visit. For each pair $(h_1, h_2)$ of such houses, he has established the amount of energy he needs to spend to walk from $h_1$ to $h_2$. Imagine for a minute that your neighborhood is flat (no slopes or stairs) and so the energy consumptions are symmetric, this is the amount of energy required to go from $h_1$ to $h_2$ is the same as that required to go from $h_2$ to $h_1$. Also, let us assume that your kid can collect an infinite amount of candies and that the list of houses $H$ is short enough so he will be able to visit them all. The question is, how to find the itinerary that minimizes the total amount of energy consumed to visit all the houses in $H$?

This optimization problem known in the scientific literature as the traveling salesman problem (TSP) is arguably the most famous combinatorial optimization problem. It is a difficult problem for which there is no known polynomial-time algorithm capable of solving it. This apparent limitation does not necessarily mean that we cannot solve large instances of the TSP. In 1954 George B Dantzig聽(who by the way invented the simplex method and introduced the vehicle routing problem) along with colleagues R Fulkerson and S Johnson introduced the very first optimization algorithm for the TSP and solved (by hand!) an instance containing 49 cities, one per state in the continental US. In their 1998 code, Applegate, Bixby, Chvatal & Cook developed CONCORDE, a cutting planes algorithm based on the algorithm of Dantzig, but now capable of solving TSP problems containing several thousand nodes. In both cases, the algorithm is based upon a simple linear-integer program, described as follows.

For every pair of houses $(h_1, h_2)$ let $c(h_1, h_2)$ be the energy consumption required to go from $h_1$ to $h_2$, and let $x(h_1, h_2)$ be a binary variable indicating whether the child visited the hoses $h_1$, $h_2$ one after the other. For a subset $I\subset H$ let $\delta(I)$ be the pairs of sequences $(h_1, h_2)$ with exactly one endpoint in $I$. Let $x(\delta(I)) = \sum\{x_e : e \in \delta(I)\}$. The following is the linear-integer program that models the TSP:

$\min \sum\{c_{ij} x_{ij} : i, j\in H, i < j\}$

subject to

$x(\delta(\{h\})) = 2 \qquad h\in H$

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

$x \text{ binary}$

The first set of constraints (one per house) are named degree constraints and impose that every house must be linked to two other houses. The seond set of constraints are the so-called subtour elimination constraints (SEC) and impose that no subset of houses may be isolated from the rest. If you want to know more in depth how to solve TSP problems using the above model, check out the references cited above. You may also follow on Twitter who is one of the creators and maintainers of CONCORDE!