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!

Leave a Reply