Fleet Sizing and Service Region Partitioning for Same-Day Delivery Systems

We study the linked tactical design problems of fleet sizing and partitioning a service region into vehicle routing zones for same-day delivery (SDD) systems. Existing SDD studies focus primarily on operational dispatch problems and do not consider system design questions. Prior work on SDD system design has not considered the fleet sizing decision when a service region may be partitioned into zones dedicated to individual vehicles; such designs have been shown to improve system efficiency in related vehicle routing settings. Using continuous approximations to capture average-case operational behavior, we consider first the problem of independently maximizing the area of a single-vehicle delivery zone. We characterize area-maximizing dispatching policies and leverage these results to develop a procedure for calculating optimal areas as a function of a zone’s distance from the depot, given a maximum number of daily dispatches per vehicle. We then demonstrate how to derive fleet sizes from optimal area functions and propose an associated Voronoi approach to partition the service region into single-vehicle zones. We test the fleet sizing and partitioning approach in a computational study that considers two different service regions and demonstrate its pragmatism and effectiveness via an operational simulation. Using minimal computation, the approach specifies fleet sizes and builds vehicle delivery zones that meet operational requirements, verified by simulation results.