The capacitated trick-or-treat problem with stochastic demands

Your kid is about to go out to collect some candies. You have learnt how to build, given a set of houses H and an energy consumption matrix \{c_{ij}: i, j\in H\}, a single tour that visits all those houses with the minimum possible consumption of energy. You have realized that this solution may not be feasible if your kid has not the capacity to collect all of the candies that he is expected to collect. Several tours may be necessary to accommodate to the constraint of having a maximum capacity in the bag. No problem, you have learnt how to handle that as well. The tour are still too long and you are afraid that he may not be capable of walking all the given houses in a tour at once without asking you to grab him in your arms? No problem, the OR Guy still has a solution for you!

But now you face the following dilemma. You have a teenager kid too whom himself used to collect candies for several years in the past. He knows how much candies each house in the neighborhood is likely to give away from his past experience. So you wonder, may it be possible to exploit your teen kid’s knowledge so as to build tours that are less likely to fill you younger kid’s bag before completion?

The short answer is YES, IT IS POSSIBLE. A longer answer though would require a little more explanation to do. From your teen kid past experience, you may build a probability distribution of the amount of candy that each house is likely to give away to each kid. From the multiple possible probability distributions, you may use a method to calibrate which one fits best the behavior of each particular case. The CVRP instance that we explored in this post should now be seen as a problem in which the amount of candy given away in each house is a random variable.

But now you face another problem: the amount of candy given away in each house is not known in advance and you should consider (in principle) all the possible outcomes of such random variables. How do you select the best possible decision for the whole set of potential outcomes? The first (and possibly the most intuitive) approach that one would consider is to find a solution for every possible outcome. What if one finds plenty of those solutions? Indeed, not only you have the problem of considering one solution among many, but also you may select one that is good for a single possible outcome and potentially VERY BAD for the rest. This also takes us to the next issue. A solution may be feasible for a given outcome (it respects the bag capacity), but unfeasible for another one (you end up collecting on a tour more candies that you were originally expecting and your bag becomes full before completing it). How should you then compute the cost of a solution? This type of decision is usually referred to as the recourse in the slang of stochastic optimization. A typical recourse consists in getting back home after your kid’s bag becomes full of candies and then retake your tour whenever you left it.

A good solution in the language of stochastic optimization then is one that is good on average, this is that, when considering the costs + the recourse for every possible outcome of the random variables, becomes minimum in expectancy. In the case of vehicle routing, the problem just described is known in the literature as the vehicle routing problem with stochastic demands and is substantially harder than its deterministic counterpart if the number of possible outcomes is too large. Fortunately for you (and your kid), a number of algorithmic tricks allows for the heuristic solution of real-size problems in moderate computing times.

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!