Motivated by applications in e-commerce logistics and production planning where orders (or items, or jobs) arrive at different times and must be dispatched or processed in batches, we consider a multi-vehicle dispatching problem that captures the tension between waiting for orders to arrive and the economies of scale due to batching. Our model extends the single-vehicle work in Erazo and Toriello (2023), and we focus primarily on the case of identical vehicles with submodular dispatch times. We propose four different mixed-integer programming formulations to solve this problem; we analyze the complexity of solving each formulation’s linear relaxation, study the quality of the corresponding bounds, and leverage column generation to create heuristics. Moreover, we analyze solutions where all batches are intervals of consecutive orders and identify two classes of functions for which such a solution is optimal. Finally, we computationally test our methods on applications in same-day delivery and machine scheduling with family setups.