Motivated by applications in e-commerce logistics where orders or items arrive at different times and must be dispatched or processed in batches, we propose the submodular dispatching problem (SMD), a strongly NP-hard model defined by a set of orders with release times and a non-decreasing submodular dispatch time function. A single uncapacitated vehicle must dispatch orders in batches to minimize the makespan, the time at which all orders have been dispatched. We analyze FIFO solutions, discuss cases when they are optimal and provide a dynamic program to obtain such solutions. Furthermore, we give a polynomial-time 1.5-approximation algorithm based on the linear relaxation of an MILP formulation; we show that this approximation guarantee is best possible among a certain class of heuristics, and give additional results on the problem's approximability. We computationally test our methods on applications in same-day delivery and warehousing.
Citation
Industrial and Systems Engineering, Georgia Tech, June 2022