.png){kind=icon}
.png){kind=icon}
Return
Submodular Dispatching with Multiple Vehicles
.png){kind=icon}
PRE
AI
DOI：10.1287/ijoc.2024.0886.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
submodular
machine scheduling
same-day delivery
column generation
Journal
I
IF:
2.1
Papers:
86
Citations:
3.2K