An official website of the United States government
Crowdsourced delivery platforms face the unique challenge of meeting dynamic customer demand using couriers not employed by the platform. As a result, the delivery capacity of the platform is uncertain. To reduce the uncertainty, the platform can offer a reward to couriers that agree to be available to make deliveries for a specified period of time, that is, to become scheduled couriers. We consider a scheduling problem that arises in such an environment, that is, in which a mix of scheduled and ad hoc couriers serves dynamically arriving pickup and delivery orders. The platform seeks a set of shifts for scheduled couriers so as to minimize total courier payments and penalty costs for expired orders. We present a prescriptive machine learning method that combines simulation optimization for off-line training and a neural network for online solution prescription. In computational experiments using real-world data provided by a crowdsourced delivery platform, our prescriptive machine learning method achieves solution quality that is within 0.2%-1.9% of a bespoke sample average approximation method while being several orders of magnitude faster in terms of online solution generation.
more »
« less
Robust optimization of dynamic route planning in same‐day delivery networks with one‐time observation of new demand
Abstract Local delivery networks expect drivers to make deliveries to and/or pickups from customers using the shortest routes in order to minimize costs, delivery time, and environmental impact. However, in real‐world applications, it is often the case that not all customers are known when planning the initial delivery route. Instead, additional customers become known while the driver is making deliveries or pickups. Before serving the new demand requests, the vehicle will return to the depot for restocking. In other words, there exists a precedence relation in the delivery route to visit the depot before delivering new orders. The uncertainty in new customer locations can lead to expensive rerouting of the tour, as drivers revisit previous neighborhoods to serve the new customers. We address this issue by constructing the delivery route with the knowledge that additional customers will appear, using historical demand patterns to guide our predictions for the uncertainty. We model this network delivery problem as a precedence‐constrained asymmetric traveling salesman problem using mixed‐integer optimization. Experimental results show that the proposed robust optimization approach provides an effective delivery route under the uncertainty of customer demands.
more »
« less
- Award ID(s):
- 1617148
- PAR ID:
- 10461439
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Networks
- Volume:
- 73
- Issue:
- 4
- ISSN:
- 0028-3045
- Page Range / eLocation ID:
- p. 434-452
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract This article formulates and solves a stochastic optimization model to investigate the impact of crowdsourced platforms (e.g., ridesharing, on‐demand delivery, volunteer food rescue, and carpooling) offering small, personalized menus of requests and incentive offers for drivers to choose from. To circumvent nonlinear variable relationships, we exploit model structure to formulate the program as a stochastic linear integer program. The proposed solution approach models stochastic responses as a sample of variable and fixed scenarios, and to counterbalance solution overfitting, uses a participation ratio parameter. The problem is also decomposed and iterated among two separate subproblems, one which optimizes menus, and another, which optimizes incentives. Computational experiments, based on a ride sharing application using occasional drivers demonstrate the importance of using multiple scenarios to capture stochastic driver behavior. Our method provides robust performance even when discrepancies between predicted and observed driver behaviors exist. Computational results show that offering menus and personalized incentives can significantly increase match rates and platform profit compared to recommending a single request to each driver. Further, compared to the menu‐only model, the average driver income is increased, and more customer requests are matched. By strategically using personalized incentives to prioritize promising matches and to increase drivers' willingness to accept requests, our approach benefits both drivers and customers. Higher incentives are offered when drivers are more likely to accept, while fewer incentives and menu slots are reserved for driver‐request pairs less likely to be accepted.more » « less
-
The boom of e-commerce and the increasing demand for fast and reliable delivery services have led to the thriving of on-demand delivery (ODD), which provides delivery services to food takeout, grocery, pharmacy, and other light-weighted goods. The operational efficiency of ODD is subject to many factors—access to curbside, delays at the pick-up and drop-off locations, order dispatching mode, vehicle routing schedule, and vehicle refueling needs. The fast-growing delivery orders coupled with operational inefficiencies of ODD may lead to higher vehicle miles traveled (VMT) and pollutant emissions. Policymakers as well as practitioners need to evaluate the VMT and emissions impact of ODD, given the consumer behavior, operational paradigm, and business models. This paper conducted a systematic review of the existing literature to synthesize and summarize the impacts of ODD with a specific focus on VMT and emissions. The PRISMA (Preferred Reporting Items for Systematic Reviews and Meta-Analysis) guideline was employed to systematically search for related studies in multiple databases and to crystallize the review scope. The impact evaluation was delved into three aspects: customer shopping behavior (online shopping vs. in-store shopping), ODD operational strategy (truck/van vs. green vehicles, professional delivery vs. crowdsourcing), and business models (home delivery vs. depot/collection point). Overall, this study found that online shopping with coordinated ODD can achieve significant VMT and emissions reduction compared with in-store shopping. The reduction extent depends on the customer trip chaining, travel mode choice, residential area type, and the ratio of product return. The use of zero-emissions vehicles in ODD, such as electric van/truck/vehicle, cargo-bike, UAV, provides relatively higher emissions reductions, but also brings new issues such as charging needs or capacity limits. Collection points (e.g., parcel locker, retailer store, postal service point) can reduce the VMT and emissions if they are optimally distributed, and customers visit them in zero-emissions modes or through trip chaining.more » « less
-
New York City’s food distribution system is among the largest in the United States. Food is transported by trucks from twelve major distribution centers to the city’s point-of-sale locations. Trucks consume large amounts of energy and contribute to large amounts of greenhouse gas emissions. Therefore, there is interest to increase the efficiency of New York City’s food distribution system. The Gowanus district in New York City is undergoing rezoning from an industrial zone to a mix residential and industrial zone. It serves as a living lab to test new initiatives, policies, and new infrastructure for electric vehicles. We analyze the impact of electrification of food-distribution trucks on greenhouse gas emissions and electricity demand in this paper. However, such analysis faces the challenges of accessing available and granular data, modeling of demands and deliveries that incorporate logistics and inventory management of different types of food retail stores, delivery route selection, and delivery schedule to optimize food distribution. We propose a framework to estimate truck routes for food delivery at a district level. We model the schedule of food delivery from a distribution center to retail stores as a vehicle routing problem using an optimization solver. Our case study shows that diesel trucks consume 300% more energy than electric trucks and generate 40% more greenhouse gases than diesel trucks for food distribution in the Gowanus district.more » « less
-
In this paper, we consider an integrated vehicle routing and service scheduling problem for serving customers in distributed locations who need pick-up, drop-off, or delivery services. We take into account the random trip time, nonnegligible service time, and possible customer cancellations, under which an ill-designed schedule may lead to undesirable vehicle idleness and customer waiting. We build a stochastic mixed-integer program to minimize the operational cost plus expected penalty cost of customers’ waiting time, vehicles’ idleness, and overtime. Furthermore, to handle real-time arrived service requests, we develop K-means clustering-based algorithms to dynamically update planned routes and schedules. The algorithms assign customers to vehicles based on similarities and then plan schedules on each vehicle separately. We conduct numerical experiments based on diverse instances generated from census data and data from the Ford Motor Company’s GoRide service, to evaluate result sensitivity and to compare the in-sample and out-of-sample performance of different approaches. Managerial insights are provided using numerical results based on different parameter choices and uncertainty settings.more » « less
