The Same-Day Delivery Problem for Online Purchases

Same-day delivery for online purchases is a recent trend in online retail. We introduce a multi-vehicle dynamic pickup and delivery problem with time constraints that incorporates key features associated with same-day delivery logistics. To make better informed decisions, our solution approach incorporates information about future requests into routing decisions. We also introduce an analytical result that identifies when it is beneficial for vehicles to wait at the depot. We present a wide range of computational experiments that demonstrate the value of our approach. The results show that more requests can be filled when time windows are evenly spread throughout the day compared to when many requests' time windows occur late in the day. However, the anticipation of future requests is most valuable when many requests' time windows occur late in the day. As a result of increased flexibility, experiments also demonstrate that the value of anticipating the future decreases when the number of vehicles or the arrival rate of requests increases. The online appendix is available at https://doi.org/10.1287/trsc.2016.0732 .