Request acceptance in same-day delivery

We study request acceptance dynamics in same-day delivery systems by formulating the Dynamic Dispatch Waves Problem with Immediate Acceptance, which models integrated management and distribution for dynamically arriving customer requests. We consider an e-commerce platform that attempts to serve most customers with same-day delivery service. When a shopper attempts to place an order, a decision is made immediately to offer same-day delivery service (accept the request) or to deny service. Accepted requests are not available for immediate dispatch; they must be processed (picked and packed) before they are loaded for delivery. Vehicle routes are updated dynamically and serve each accepted delivery request no later than the end of the service day. In this work, we limit the study to the case of a single vehicle serving requests, potentially using multiple trips from the distribution center. The objective is to make request acceptance and distribution decisions that minimize the expected sum of vehicle travel costs and penalties for service denials. We develop a framework for dynamic decision policies over continuous time for such systems, where a feasible vehicle dispatch plan is redesigned and used to guide decisions over time. We design methods for determining an initial optimal a priori plan and for updating the plan using a heuristic roll-out procedure. Our methods are tested on a family of simulated instances against two common-sense benchmarks and an infeasible relaxed policy that allows the dispatcher to delay the acceptance or rejection of a request until the end of the service day. We demonstrate in our computational study that the cost-per-request of the best benchmark policy is on average 9.7% higher than our proposed dynamic policy and furthermore that the dynamic policy leads to only a 4.4% cost increase over the infeasible relaxed policy lower bound.