We study the tactical problem of determining a last-mile delivery fleet size while accounting for day-to-day uncertainty in the number and location of customer requests. An optimally sized fleet must balance the cost of contracting vehicles against the penalty costs of unserved customers: a larger fleet reduces the risk of unserved demand, but a smaller fleet is cheaper. This trade-off resembles the structure of a newsvendor problem, and we model the fleet sizing decision problem accordingly. However, unlike the classical newsvendor setting, the expected ‘return’ (i.e., the number of served requests) associated with a particular fleet size is difficult to characterize because of the complexity entailed by combinatorial vehicle routing and customer selection decisions. Therefore, a key technical challenge lies in estimating how many requests can be served by fleets of different sizes. As an alternative to solving a hard stochastic team orienteering problem for each fleet size, we present two continuous approximation approaches that capture the fleet sizing problem’s structure at an aggregate level. The first treats linehaul time as constant, while the second models it as variable depending on each vehicle’s route location; both approaches rely on the well-known Beardwood-Halton-Hammersley Theorem. Our approximations require low computational effort while providing structural insights. Crucially, we show that the resulting total cost functions are convex with respect to fleet size, just as the classical newsvendor cost function is convex with respect to inventory quantity. This result allows optimal fleet sizes to be efficiently computed by leveraging first-order optimality conditions. We use our models to evaluate optimal fleet sizes and associated costs under different linehaul time formulations, information structures regarding future demand, and depot locations. Finally, we also validate our continuous approximation models through simulation experiments on both synthetic and real road networks, demonstrating their effectiveness and practical usability.