skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Integrated column generation for volunteer‐based delivery assignment and route optimization
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.  more » « less
Award ID(s):
2125600
PAR ID:
10571675
Author(s) / Creator(s):
 ;  ;  ;  
Publisher / Repository:
Wiley-Blackwell
Date Published:
Journal Name:
Computer-Aided Civil and Infrastructure Engineering
Volume:
40
Issue:
15
ISSN:
1093-9687
Format(s):
Medium: X Size: p. 2227-2243
Size(s):
p. 2227-2243
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Transportation Research Part E: Logistics and Transportation Review)
    The rapidly growing online food delivery (OFD) market presents substantial logistical challenges for last-mile delivery operations. Sidewalk delivery robots (SDRs) have emerged as a promising alternative to on-demand workers, as these compact, box-sized robots efficiently deliver food or groceries over short distances via sidewalks. We propose a two-stage stochastic optimization model for a single-depot SDR system with integrated battery-swapping operations. In the first stage, a continuous approximation (CA) method determines the optimal fleet size and the required number of additional swappable batteries. The second-stage solutions are critical to facilitate the first-stage method. These involve solving a routing problem that incorporates battery-swapping decisions and penalties for late arrivals. To address this, we develop a customized heuristic based on adaptive large neighborhood search (ALNS) to generate high-quality solutions for the second stage. The fitted CA model integrates key factors, including time windows, battery swapping, and pickup-delivery orders. Numerical examples highlight the proposed approach’s efficiency in reducing computational time while maintaining solution accuracy. A case study and sensitivity analysis conducted on Purdue University’s campus illustrate the practical impacts of fleet size and the number of swappable batteries. 
    more » « less
  2. ; ; ; (, Naval Research Logistics (NRL))
    Abstract Urban air mobility (UAM) is an emerging air transportation mode to alleviate the ground traffic burden and achieve zero direct aviation emissions. Due to the potential economic scaling effects, the UAM traffic flow is expected to increase dramatically once implemented, and its market can be substantially large. To be prepared for the era of UAM, we study the fair and risk‐averse urban air mobility resource allocation model (FairUAM) under passenger demand and airspace capacity uncertainties for fair, safe, and efficient aircraft operations. FairUAM is a two‐stage model, where the first stage is the aircraft resource allocation, and the second stage is to fairly and efficiently assign the ground and airspace delays to each aircraft provided the realization of random airspace capacities and passenger demand. We show that FairUAM is NP‐hard even when there is no delay assignment decision or no aircraft allocation decision. Thus, we recast FairUAM as a mixed‐integer linear program (MILP) and explore model properties and strengthen the model formulation by developing multiple families of valid inequalities. The stronger formulation allows us to develop a customized exact decomposition algorithm with both benders and L‐shaped cuts, which significantly outperforms the off‐the‐shelf solvers. Finally, we numerically demonstrate the effectiveness of the proposed method and draw managerial insights when applying FairUAM to a real‐world network. 
    more » « less
  3. ; (, International Transactions in Operational Research)
    Abstract We propose easy‐to‐implement heuristics for time‐constrained applications of a problem referred to in the literature as the facility location problem with immobile servers, stochastic demand, and congestion, the service system design problem, or the immobile server problem (ISP). The problem is typically posed as one of allocating capacity to a set of M/M/1 queues to which customers with stochastic demand are assigned with the objective of minimizing a cost function composed of a fixed capacity‐acquisition cost, a variable customer‐assignment cost, and an expected‐waiting‐time cost. The expected‐waiting‐time cost results in a nonlinear term in the objective function of the standard binary programming formulation of the problem. Thus, the solution approaches proposed in the literature are either sophisticated linearization or relaxation schemes, or metaheuristics. In this study, we demonstrate that an ensemble of straightforward, greedy heuristics can rapidly find high‐quality solutions. In addition to filling a gap in the literature on ISP heuristics, new stopping criteria for an existing cutting plane algorithm are proposed and tested, and a new mixed‐integer linear model requiring no iterating algorithm is developed. In many cases, our heuristic approach finds solutions of the same or better quality than those found by exact methods implemented with expensive, state‐of‐the‐art mathematical programming software, in particular a commercial nonlinear mixed‐integer linear programming solver, given a five‐minute time limit. 
    more » « less
  4. ; ; (, Management Science)
    We consider the placement, delivery promise, and fulfillment decisions of an online retailer. We have a set of products with given numbers of units to be placed at capacitated fulfillment centers. Once we make the placement decisions, we face demands for the products arriving from different demand regions randomly over time. In response to each demand, we pick a delivery promise to offer, which determines the probability that the demand converts into sales as well as choose a fulfillment center to use to serve the demand. Our goal is to decide where to place the units at the beginning of the selling horizon and to find a policy to make delivery promise and fulfillment decisions over the selling horizon so that we maximize the total expected profit. We give an approximation strategy to obtain solutions with performance guarantees for this joint placement, delivery promise, and fulfillment problem. In our approximation strategy, we construct a bounding function that upper bounds the total expected profit from the delivery promise and fulfillment policy when viewed as a function of the placement decisions. To make the placement decisions, we maximize the bounding function subject to the capacity constraints at the fulfillment centers. To make the delivery promise and fulfillment decisions, we construct a policy that obtains a constant fraction of the bounding function. Using our approximation strategy with appropriate bounding functions, we obtain a solution with a constant factor performance guarantee, but if the size of the system, measured by the numbers of units that we need to place and capacities of the fulfillment centers, is large, then we get an asymptotically optimal solution. We compare our approximation strategy with approaches that ignore the interactions between the placement, delivery promise, and fulfillment decisions as well as heuristics that are based on Lagrangian relaxation, demonstrating that our approximation strategy compares quite favorably. 
    more » « less
  5. ; ; ; (, Service Science)
    Amidst the COVID-19 pandemic, restaurants become more reliant on no-contact pick-up or delivery ways for serving customers. As a result, they need to make tactical planning decisions such as whether to partner with online platforms, to form their own delivery team, or both. In this paper, we develop an integrated prediction-decision model to analyze the profit of combining the two approaches and to decide the needed number of drivers under stochastic demand. We first use the susceptible-infected-recovered (SIR) model to forecast future infected cases in a given region and then construct an autoregressive-moving-average (ARMA) regression model to predict food-ordering demand. Using predicted demand samples, we formulate a stochastic integer program to optimize food delivery plans. We conduct numerical studies using COVID-19 data and food-ordering demand data collected from local restaurants in Nuevo Leon, Mexico, from April to October 2020, to show results for helping restaurants build contingency plans under rapid market changes. Our method can be used under unexpected demand surges, various infection/vaccination status, and demand patterns. Our results show that a restaurant can benefit from partnering with third-party delivery platforms when (i) the subscription fee is low, (ii) customers can flexibly decide whether to order from platforms or from restaurants directly, (iii) customers require more efficient delivery, (iv) average delivery distance is long, or (v) demand variance is high. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email