Value of parking and autonomous vehicles for last-mile delivery

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.