Parking is necessary for 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, the researchers address this challenge of finding parking through the Capacitated Delivery Problem with Parking (CDPP).
Unlike other models in the literature, the CDPP accounts for parking time in the objective and minimizes the completion time of the delivery tour. Parking time represents the delivery person searching for a parking spot and then parking the vehicle at the chosen location.
When the researchers restrict the customer geography to a complete grid, they identify conditions for when a Traveling Salesman Problem (TSP) solution that parks at each customer is an optimal solution to the CDPP. The researchers then determine when the parking time is large enough for the CDPP optimal solution to differ from this TSP solution. The researchers 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 show the greatest advantage when parking time is high. The CDPP outperforms industry practices and models in the literature, highlighting the value of determining the service order and including parking time in optimal routing decisions. Routing in last-mile delivery must include optimizing customer service orders to make more efficient choices of parking spot locations and walking paths for the delivery person. Including parking time in the objective for last-mile delivery, routing is critical to achieving optimal trade-offs between driving, walking, and parking.