Parking is a necessary component of traditional last-mile delivery practices, but finding parking can be difficult. Yet, the routing literature largely does not account for the need to find parking. In a new paper by Reed et.al., the researchers address this challenge of finding parking through the Capacitated Delivery Problem with Parking (CDPP).
Including the search time for parking in routing optimization for last-mile delivery provides the greatest advantage in urban environments where parking is a challenge. Parking matters in last-mile delivery optimization. The CDPP outperforms industry practice and models in the literature highlighting the value of including the search time for parking in optimal routing decisions. When parking time is ignored, routing decisions that focus on the fastest way to service all customers may result in unnecessary time spent searching for parking.
Unlike other models in the literature, the CDPP accounts for the search time for parking in the objective and minimizes the completion time of the delivery tour. The researchers provide tight bounds for the CDPP using a Traveling Salesman Problem (TSP) solution that parks at each customer. They then demonstrate the circumstances under which this TSP solution is the optimal solution to the CDPP as well as counterexamples to show that the TSP is generally not optimal.
They also identify model improvements that allow reasonably-sized instances of the CDPP to be solved exactly. They introduce a heuristic for the CDPP that quickly finds high-quality solutions to large instances. Computational experiments show that parking matters in last-mile delivery optimization. The CDPP outperforms industry practice and models in the literature showing the greatest advantage when the search time for parking is high. This analysis provides immediate ways to improve routing in last-mile delivery. Allowing multiple customer service sets to be served from the same parking spot is advantageous when the search time for parking is high.
