We study order acceptance dynamics in same-day delivery systems by formulating the Dynamic Dispatch Waves Problem with Immediate Acceptance, which models integrated request management and order distribution for dynamically arriving requests. When a delivery request arrives, a decision is made immediately to accept (offer service) or reject (with a penalty). Accepted requests are not available for immediate dispatch; they must be processed (picked and packed) before they are loaded for delivery in dynamically updated vehicle routes visiting each request's delivery location by the end of the service day. We consider the case of dispatching a single vehicle from a distribution center, potentially on multiple trips. The objective is to make order acceptance and distribution decisions that minimize the expected sum of total penalties for rejected delivery requests and vehicle travel costs. 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 dispatch plan, and for updating it via a heuristic roll-out procedure. Our methods are tested over a family of simulated instances against two common-sense benchmarks and an infeasible relaxed policy that allows the dispatcher to delay a request acceptance decision until its corresponding dispatch time. We estimate the cost-per-request of the best benchmark policy to be 9.7% higher than our proposed dynamic policy. Conversely, imposing immediate order acceptance on the system results in a cost increase of 4.4%.
Citation
August 2019