Dissertation
Value of parking and autonomous vehicles for last-mile delivery
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Summer 2021
DOI: 10.17077/etd.005810
Abstract
Last-mile delivery is the movement of goods from a transportation hub to their final destination. Parking is a necessary component of traditional last-mile delivery practices, but finding parking can be difficult. This thesis introduces the Capacitated Delivery Problem with Parking (CDPP) to address this challenge of finding parking. Unlike other models in the literature, the CDPP accounts for the search time for parking in the objective. We provide tight bounds for the CDPP using a Traveling Salesman Problem solution that parks at each customer. We also identify model improvements that allow reasonably-sized instances of the CDPP to be solved exactly. We introduce a heuristic for the CDPP that quickly finds high quality solutions to large instances. Computational experiments show that the CDPP outperforms industry practice and models in the literature with the greatest advantage in areas where the search time for parking is high. This analysis provides immediate ways to improve routing in last-mile delivery.
To further improve the productivity of the delivery person, we explore autonomous vehicle assisted delivery as an alternative business model. To do so, we introduce the Capacitated Autonomous Vehicle Assisted Delivery Problem (CAVADP). The autonomous vehicle in the CAVADP can drop off the delivery person at selected points where the delivery person makes deliveries to the final addresses on foot. Then, the vehicle picks up the delivery person and travels to the next reloading point. In this way, the delivery person would never need to look for parking or walk back to a parking place. Based on the number of customers, driving speed, walking speed, and the time for loading packages, we characterize the optimal solution to the CAVADP on a solid rectangular grid of customers, a reasonable assumption for an urban environment. To determine in what geographies autonomous-assisted delivery is most valuable, we model the CAVADP on a general graph. To solve this model on realistically-sized instances, we exploit the structure of the optimal solution to develop a number of preprocessing techniques and valid inequalities.
Autonomous-assisted delivery reduces the completion time of the delivery tour and provides the most cost-effective business model in all customer geographies. In particular, the reduction in the completion time of the delivery tour is higher in urban environments with 53% average savings relative to traditional delivery practices compared to rural environments with 26% average savings. Increases in productivity from the CAVADP with respect to other business models are greater than the increased operational costs of using an autonomous vehicle. These conclusions support businesses with urban deliveries considering investment in this technology.
Details
- Title: Subtitle
- Value of parking and autonomous vehicles for last-mile delivery
- Creators
- Sara Reed
- Contributors
- Ann Melissa Campbell (Advisor)Barrett W Thomas (Advisor)Samuel Burer (Committee Member)Renato de Matta (Committee Member)Jeffrey Ohlmann (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Applied Mathematical and Computational Sciences
- Date degree season
- Summer 2021
- DOI
- 10.17077/etd.005810
- Publisher
- University of Iowa
- Number of pages
- xiv, 167 pages
- Copyright
- Copyright 2021 Sara Reed
- Language
- English
- Description illustrations
- color illustrations
- Description bibliographic
- Includes bibliographical references (pages 162-167).
- Public Abstract (ETD)
Last-mile delivery is the movement of goods from a transportation hub to their final destination. One of the challenges in last-mile delivery is the need to find a parking spot and the associated expense of searching for parking. Including the search time for parking in routing decisions provides an immediate improvement to the completion time of the delivery tour by finding better trade-offs between searching for parking, driving, and walking for the delivery person. Urban environments, where parking presents the greatest challenge, realizes the greatest advantage of including the search time for parking in optimal routing decisions. In rural areas, where customers are further apart, serving customers individually and finding the shortest path to drive between customers may be sufficient.
Company attempts to improve productivity in last-mile delivery often include exploring the use of new technology. This thesis explores autonomous vehicle assisted delivery. An autonomous vehicle can drop off the delivery person at selected points where the delivery person makes deliveries to the final addresses on foot. Then, the vehicle picks up the delivery person and travels to the next reloading point. In this way, the delivery person would never need to look for parking or walk back to a parking place. Autonomous vehicle assisted delivery reduces the completion time of the delivery tour and provides the most cost-effective business model in all customer geographies. In particular, the reduction in the completion time of the delivery tour is higher in urban environments with 53% average savings relative to traditional delivery practices compared to rural environments with 26% average savings. This increased productivity could reduce fleet size and ultimately the number of vehicles on the road. These conclusions support businesses with urban deliveries considering investment in this technology.
- Academic Unit
- Interdisciplinary Graduate Program in Applied Mathematical & Computational Sciences
- Record Identifier
- 9984124761102771
Metrics
34 File views/ downloads
228 Record Views