Optimizing the Trade-off Between Batching and Waiting: Subadditive Dispatching

• 成果类型: Article; Early Access
• 署名作者: Erazo, Ignacio; Toriello, Alejandro
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0327
• 发表日期: 2025
• 关键词: release dates; minimizing makespan; simple mechanisms; E-commerce; machine; algorithm; buyers; times; jobs

摘要

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 nondecreasing 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, the best possible for solutions using at most two or three dispatches. Furthermore, we analyze first in, first out 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.