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 subadditive dispatching problem (SAD), a strongly NP-hard problem defined by a set of orders with release times and a non-decreasing subadditive 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 propose a mixed-integer linear formulation for SAD; based on the linear relaxation’s optimal solution, we construct a two-dispatch solution with a 3/2 approximation ratio, and a solution with at most three dispatches that has a 4/3 approximation ratio under an additional assumption. The guarantees are respectively best possible for solutions using at most two or three dispatches. Furthermore, we analyze FIFO solutions, discuss cases when they are optimal, and provide a dynamic program to obtain them. Finally, we computationally test our methods on applications inspired by same-day delivery and routing on restricted topologies.
Citation
Industrial and Systems Engineering, Georgia Tech, June 2024