Submodular Dispatching with Multiple Vehicles

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 because of batching. Our model extends the current state-of-the-art for single-vehicle work, focusing 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 machine scheduling with family setups and same-day delivery.

History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete.

Funding: This work was supported by the Office of Naval Research [Grant N00014-18-1-2075].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0886) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0886). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.