Policies for the dynamic same-day delivery problem with walking and parking

A key decision in the dynamic setting of same-day delivery is when to dispatch the vehicle and provide last-mile delivery service to continuously arriving customer requests. To understand successful strategies in urban environments, we introduce the Same-Day Delivery Problem with Walking and Parking (SDDPWP). We model this problem as a Markov Decision Process and develop solution policies that consider waiting for customers to accumulate and specified consolidation levels at parking spots. Our computational results clearly demonstrate that including parking and walking times matter in same-day delivery, with the best solutions recommending drivers wait at the depot to achieve consolidation of multiple customers into walking routes from each parking spot. We find a significant percentage of waiting time occurs at the beginning of the day and provide managerial insights as to how to mitigate this inefficiency in labor utilization to improve profits by as much as 60%.