New Technique Aims to Make Food Deliveries More Efficient

North Carolina State University researchers have developed a new technique to improve the efficiency of food-delivery operations. The technique accounts for the location of food distribution sites and delivery locations to develop optimized delivery routes that make food delivery faster and more fuel efficient.

“We developed this methodology in order to assist food banks to deliver food to those in need,” says Leila Hajibabai, corresponding author of a paper on the work and an associate professor in NC State’s Edward P. Fitts Department of Industrial and Systems Engineering. “However, the technique can be used by any operation that needs to address similar challenges, whether that’s a for-profit food delivery business or an operation that delivers vehicle parts to auto repair shops.”

The technique the researchers developed accounts for four key factors: the supply of food that is available; where that food is located; the location of the people who need the food and limitations on what they can accept; and the number of vehicles available to deliver that food, as well as the capacity of each vehicle.

“We identified these factors after consulting with food-bank operations and food pantries, to ensure that any techniques we developed were accounting for real-world challenges,” Hajibabai says.

The researchers developed a mathematical model that represents the problem of identifying food-distribution sites and determining the most efficient routes to deliver food from the distribution centers to the people who need it. To solve this problem, the research team applied an optimization approach that integrates multiple algorithms, leveraging operations research techniques to enhance efficiency and effectiveness.

“Food-bank delivery is a very dynamic situation,” Hajibabai says. “For example, the amount of food available for delivery changes from day to day – and the number of volunteer drivers available can change from hour to hour. We needed to come up with approaches capable of handling this degree of variability.”

The researchers then collected data from a food bank in North Carolina and used computational modeling to predict how well the new technique would work.

“The results of the model were promising,” Hajibabai says. “We are now in the process of converting this technique into a software package and conducting proof-of-concept testing with food banks under real-world conditions.”

The paper, “Integrated column generation for volunteer-based delivery assignment and route optimization,” is published in the journal Computer-Aided Civil and Infrastructure Engineering. Co-lead authors of the paper are Asya Atik and Kuangying Li, former Ph.D. students at NC State. The paper was co-authored by Ali Hajbabaie, an associate professor of civil, construction, and environmental engineering at NC State.

This work was done with support from the National Science Foundation under grant 2125600.

-shipman-

Note to Editors: The study abstract follows.

“Integrated column generation for volunteer-based delivery assignment and route optimization”

Authors: Asya Atik, Kuangying Li, Leila Hajibabai and Ali Hajbabaie, North Carolina State University

Published: Feb. 11, Computer-Aided Civil and Infrastructure Engineering

DOI: https://doi.org/10.1111/mice.13439

Abstract: This study develops an integrated delivery assignment and route planning strategy for food banking operations, considering food supply and demand constraints, food item restrictions, and vehicle capacity constraints. A mixed-integer linear model is formulated to maximize the total demand served and minimize the total travel cost imposed on delivery volunteers. An integrated solution algorithm is developed that includes Lagrangian relaxation and column generation. The algorithm decomposes the problem into assignment and routing components and solves each iteratively. The proposed methodology is applied to a case study in Wake County, NC. A series of sensitivity analyses are conducted to draw insights. The numerical results demonstrate the proposed methodology’s capacity to solve complex problems in food delivery operations efficiently.

This post was originally published in NC State News.