“Meals on Wheels” implementation

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:

 

Capture

 

Following this initial partition, each subsection is divided using an identical process until the curve “fills” the entire area, as seen in this figure:

 

Capture2.PNG

 

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:
Capture3.PNG

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

 

References

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.

Advertisements

3 thoughts on ““Meals on Wheels” implementation

  1. Thanks for the interesting post! This is a really cool implementation of OR. I love how simple the solution turned out to be after the problem seemed so complex. TSPs can be tricky problems, and adding the huge amount of uncertainty in terms of number of clients certainly complicates matters. What strikes me most about the solution is how creative it is – it’s so nice and neat (although I’m sure it involves all sorts of high-level math I don’t understand). Do you know if anything similar has been applied elsewhere? It seems like it could be useful for general types of deliveries, not just Meals on Wheels. I also really like the fact that it’s so straightforward for end users to implement. That’s often a big hurdle for OR, especially when optimization is involved.

    Like

    1. I know the original authors (Bartholdi et al.) said they intended to make resources available for free so other organizations could use this same approach, but I’m not sure how widespread the use ended up being. Kaplan mentioned that the Atlanta Red Cross used it for their blood bank deliveries, though, so that’s one other example!

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s