next up previous contents
Next: Nurse Scheduling: A Mathematical Up: Selected Senior Design Project Previous: A Simulation Study of

Design and Implementation of a Multiple-Vehicle Routing Scheme for Meals on Wheels, Dallas

(Pablo Addison-Smith, Mario Peon, 1990)

Since 1976, Meals on Wheels has delivered hot, nutritious meals to people who cannot prepare the meals for themselves. Mostly, these people are elderly folks who live on their own, or crippled persons who require such assistance.

In Dallas, the MOW program is operated and managed by the Visiting Nurse Association, or VNA. This organization is responsible for providing health care services to many elderly people, and the Meals on Wheels project is only one of the programs that they run. VNA is also in charge of providing the food services through separate contractors. Funding for the Meals on Wheels program comes from three main sources. First, the United Way contributes vast resources. Also, the state government of Texas provides many of the necessary funds to operate the program. However, due to budget deficit constraints and the long legislative procedures, the latter source of income cannot be depended on fully. Finally, the MOW clients themselves pay for the service, according to their financial situation. This means that clients who can afford the service, pay for it in its entirety. Those who cannot afford this, pay whatever they can, or in some cases, even nothing at all.

As seen by the limited funding, human and financial resources for the MOW program are very limited. This means that MOW must make full use of whatever they have, and must contend to these limited resources. However, this has not put any hindrances on the programs growth. In fact, the Dallas Meals on Wheels is one of the largest projects of its kind in the nation.

Although Meals on Wheels is a nationwide program, no centralized coordination effort exists, and these programs operate independently from each other. Also, since funding is limited, MOW does not have the capital to spend on expensive computer systems to assist in the routing process, such as those that a company like UPS would use. Until recently, MOW used manual methods to solve not only their routing problems, but also their data base storage and updates. Only in the past few years has the trend toward computerized storage and routing schemes began to gain widespread acceptance. With the help of a retired Arco engineer, and SMU students under the supervision of an Operations Research instructor, the MOW program has successfully implemented computerized routing techniques to make operations more efficient.

Background For the third year in a row, SMU students have worked together with the Meals on Wheels staff to solve the program's complex routing problems. The participation of SMU began in 1988 when three students, under the guidance of a professor in the department of Operations Research tried to implement a low technology routing algorithm using a minimum of computer and human resources. The program had been successfully used in the Atlanta program of MOW. However, the Dallas customers far outnumbered those in the Atlanta area, the constraints were different, and the program did not produce the results the group was expecting. But perhaps most importantly, this paved the road for another group of SMU students who in 1989 set out to improve on what the previous group had accomplished.

The second group was very successful in implementing a computer program that optimized the individual routes. In fact, the routing algorithm that these SMU students presented, is still being used today by the Dallas MOW project. This simple algorithm, known as 2-opt, revolutionized the routing procedures performed by the MOW staff.

In early 1990, a third group of SMU students, once again under the supervision of the professor that pioneered SMU's involvement with MOW, set out to implement and test even a more complex routing algorithm. Inspired by the previous work done, these two students attempted a totally different approach to the routing process. The previous work indicated that computer results proved to be very efficient and beneficial. Furthermore, the success of the lower technology routing algorithms opened the door to the implementation of more complex programs that are better suited to the actual routing system of MOW. The previous projects were an attempt to find the best or optimal route for a given set of clients. However, this set of clients was chosen arbitrarily. Therefore, the question that remained to be answered was ``what if the computer not only finds the optimal path for a route, but also chooses the routes?" This meant allowing a routing algorithm to chose the routes and to find the optimal path for each one. Although this was a very different approach than those previously taken, and would most likely alter the schemes currently used by MOW, the concept was interesting and worthy of being tested.

next up previous contents
Next: Nurse Scheduling: A Mathematical Up: Selected Senior Design Project Previous: A Simulation Study of

Richard S. Barr
Fri Feb 17 16:09:51 CST 2006