Since I didn’t get into the details of the “Meals on Wheels” example I cited during my presentation, I thought it would be interesting to discuss it here. As a quick reminder, the researchers’ objective in this example was to solve a traveling salesman problem for a nonprofit in Atlanta, Georgia that delivered meals to senior citizens each day.
While this problem may appear simple at first glance, there were two factors that made it more complicated than most traveling salesman problems. The first was how frequently the client base changed. Since senior citizens could recover from a temporary illness, be moved into a nursing home, or die, the number of clients served by the program was always in flux. Over the course of a year, the total number of clients could be as low as 159 or as high as 358. Given such large variations in the client base, the nonprofit often had to alter its routes on a weekly basis, which meant optimal solutions would quickly become obsolete. The second problem was that the organization operated on very limited resources. Things like a computer or even basic clerical support were out of the question, so any potential solutions could not be expensive or time-consuming. As a result of these constraints, the authors were unable to use any of the usual traveling salesman techniques.
Instead, the authors ended up taking a more creative approach by applying what’s called a “space-filling” or “Sierpinski” curve to solve this problem. While the geometric math describing how this curve is constructed is a bit over my head, the basic idea is that a unit square is repeatedly partitioned into “four identical subsections” and each of these are connected to form a “circuit” (Bartholdi & Platzman, 1982). The first step in this process can be seen below:
Following this initial partition, each subsection is divided using an identical process until the curve “fills” the entire area, as seen in this figure:
After this process repeats itself numerous times, Bartholdi et al. (1983) state that the final space-filling curve will look like an “infinitely crinkly version of the pattern above”. Then, using the completed curve, a list of (x,y) coordinates within the original area can be sequenced “as they appear along the space-filling curve” to provide a heuristic solution to the traveling salesman problem (Bartholdi & Platzman, 1982).
In terms of the Meals on Wheels problem, this technique was applied in a relatively straightforward manner. First, a space-filling curve was constructed based on a map of Atlanta. Next, each client’s (x,y) coordinates were converted to a theta (𝜃) value, which represents each location’s relative position on the space-filling curve. Finally, these locations were ordered according to their 𝜃 values from smallest to largest to determine the best route.
While this approach might still sound far too complicated for a non-technical workforce, the authors made sure the technique was extremely easy to use in practice. By providing the Meals on Wheels program with a map, a precomputed table of 𝜃 values, and two Rolodex card files, adding clients to the route was a simple three-step process, which can be seen in the picture below:
The resulting benefits of this approach were numerous. Most importantly, the problem didn’t need to be resolved every time the client base changed since employees could easily add or remove locations from the route using the card-sorting process described above. On top of that, having a stack of physical cards made it easy to divide up the work between employees by simply separating the cards into equal piles. If one of the four employees was unavailable on any given day, the cards just needed to be separated into three groups instead of four. In addition to the ease of use, however, the routes generated by this technique were also quite good. Compared to the routes the nonprofit had previously used, the researchers were able to develop routes that were 13% shorter, resulting in direct time and cost savings for the nonprofit. Finally, this system also came in at the low price of $50, which the nonprofit could actually afford. Altogether, it seems the solution the researchers developed addressed all the problems they had been presented with. Considering these outcomes, it’s understandable why Kaplan felt this was “a beautiful example of the OR mindset” (Kaplan, 2008).
Bartholdi, J.J, & Platzman, L.K. (1982). An O(N log N) planar travelling salesman heuristic based on spacefilling curves.Operations Research Letters, 1(4), 121-125.
Bartholdi, J.J.III, Platzman, L.K., Collins, R.L., & Warden, W.H.III. (1983). A Minimum Technology Routing System for Meals on Wheels. Interfaces, 13, 1-8.
Kaplan, E. H. (2008). Adventures in policy modeling! Operations research in the community and beyond. Omega, 36(1), 1-9.