In this month’s installment of the Innovation of the Month series, we explore a collaboration between Carnegie Mellon University, Allies for Children and several other community groups in Allegheny County, Pa., applying machine learning technology to addressing the disruption to school meal programs caused by COVID-19. MetroLab’s Ben Levine spoke with Karen Lightman and Stephen Smith at Carnegie Mellon University about the background and development of their project.
Ben Levine: Can you describe the origin and objective of this project and who has been involved in it?
Karen Lightman: This project was conceived in collaboration with Allies for Children, a local nonprofit focused on the welfare of K-12 school children in Allegheny County. In late 2019, the Metro21 Institute at Carnegie Mellon University (CMU) established a collaboration with Allies for Children to investigate the potential to use machine learning to develop more cost-effective transport of K-12 students to charter and private schools through consolidation of bus routes across school districts. Then, as public schools were forced to close when the COVID-19 pandemic hit in March 2020 and school meal programs were disrupted, many families in need were scrambling to provide meals to their children who normally would receive breakfast and lunch at school. Therefore, given our partnership with Allies for Children, it was natural to consider how school buses could be alternatively used to remotely deliver school meals, even if existing school bus routes might not offer the best solution.
Metro21’s sister organization, Traffic21 Institute, offered some startup funding and Allies for Children connected us with the Penn Hills School District, an area where students were particularly vulnerable to food insecurity. Other critical partners to this deployment include the United Way of Southwestern Pennsylvania, Greater Pittsburgh community Food Bank, ACCESS Transportation Systems and Eat’n Park Restaurants. I also meet weekly with a group of community leaders and volunteers to ensure that the project is coordinated, and not duplicative, with other food security programs.
Levine: How did you determine where to place the stops on these routes? What kind of data did you collect to design the model?
Stephen Smith: We used the existing set of school bus stops as candidates, recognizing that the constraints for remote food delivery are somewhat different than those for transporting students. For example, it is acceptable to stop traffic while students are boarding and alighting, but not for extended stops to deliver meals. Using student home address data provided by the district together with a maximum walking distance constraint, we developed a search procedure informed by a machine learning algorithm to determine the most effective set of stops and produce a set of vehicle routes for visiting them. At each step of the search, the number of students that could be serviced at each remaining candidate stop is computed, and the stop capable of servicing the most is chosen. This stop is then assigned to one of the available delivery vehicles so as to maximize the number of meals that can be delivered within the overall meal delivery time window. This process is repeated until either (1) no additional stops can be fit into the existing vehicle itineraries, (2) the carrying capacity of delivery vehicles has been exceeded or (3) all students have been serviced. Once final routes were generated, each was physically driven to determine whether there were any factors not considered by our model, such as heavy traffic or no parking space, that could impact the safety of delivering meals at the chosen stops. Stops found to have problems were eliminated as candidates, and new nearby stops were substituted.
Image courtesy Carnegie Mellon University
Levine: What challenges did you encounter while designing and implementing this project?
Lightman: One of the first challenges we encountered is that while we originally thought we’d have access to bus drivers and buses in Penn Hills, we soon learned that this would not be feasible. Thankfully, through our partners at United Way, we were connected to ACCESS Transportation who had several shuttle buses and drivers willing and able to participate. We also were challenged by how to communicate the bus stop locations where food would be delivered; we overcame this challenge by working closely with a wide network of community leaders and volunteers to get the word out. Allies for Children paid for yard signs to identify the bus stops, they printed handouts to be delivered at other food pickup and pantry locations, and our network used social media to help spread the word. Based on feedback from our partners, we then realized that it wasn’t clear that the shuttles were the vehicles that were carrying the meals, so we secured magnets to put on the side of the vehicles and help promote and advertise. At each step, we addressed the challenges by reaching out to our network of partners who helped us problem-solve. It truly has taken a village.
Levine: What was the process for pivoting this project from its original intent? Are there other, similar technologies that might be adapted to address COVID-19 challenges?
Smith: For many years, my research lab has focused broadly on artificial intelligence and machine learning techniques for automated planning, scheduling and optimization, and we have built up a substantial set of software systems and tools for solving these types of problems. Although the remote meal delivery problem has presented some unique routing and scheduling challenges, our ability to leverage this technology base has enabled us to pivot to this application domain and provide useful results as quickly as we have been able to. That said, we are continuing to refine our current route planning and scheduling engine, and we believe there are additional opportunities to utilize machine learning technology to enhance the quality of generated delivery routes. Determination of the areas of greatest need in a given region, for example, may be enhanced through use of more sophisticated multi-dimensional clustering. We are also interested in exploring the use of techniques for discovering patterns in video data as a means of autonomously recognizing desirable features of candidate stops, like the presence of a nearby parking lot, that are not captured in the current optimization model.
Levine: How are other communities using your model? Does this have the potential to be implemented at an even larger scale?
Lightman: Word soon spread about the success of our meal delivery deployment in Penn Hills. Since launching the Penn Hills project, we have received interest from other municipalities in the greater Pittsburgh region, as the issue of food insecurity is widespread and nationwide. Working in collaboration with our regional partners, we are exploring the expansion of our model into other school districts. We’ve also received funding from the National Science Foundation’s Rapid Response Research (RAPID) funding in direct response to COVID-19. This funding will enable our work to expand and address the challenges of changing food security needs of our region’s children. We are very confident that this model is replicable and can be deployed at a larger scale. What’s probably most important is that the right partners are at the table so they can inform the model, using machine learning in an iterative manner to continuously improve it. Another critical component is data; we get weekly reports on the daily delivery of meals, stops and routes so we can use that information to ensure that needs are met and families are fed. We recently tweaked the model in Penn Hills so that we could offer meals to seniors, for example.
Levine: What are your next steps? Where do you see the project going from here?
Lightman: As mentioned previously, we recently received funding from the National Science Foundation that will allow us to continue to support the Penn Hills meal delivery program as we move into the fall school year, and proceed with efforts to establish similar services in other school districts. It will also allow us to improve our algorithms and heuristics for solving this class of delivery problem, and to formalize and provide reference problems for the broader research community. With the prospect of a hybrid model of remote versus in-person school options, which will remain fluid and ever-changing, we expect that the food security of school children will become more complicated — which is exactly the kind of dynamic problem we love to solve at CMU.
