Motivated by the parcel delivery industry, we study a network design problem with service time guarantees at industrial scale. This tactical service network design problem determines primary paths and delivery schedules for commodities to minimize transportation and handling costs while ensuring committed service times. To construct a solution for a real-world instance with over 1,000 nodes, one million arcs, and 40,000 commodities, we propose a recursive graph partitioning and batching method. This method partitions the network into smaller regions and solves the problem for each region, considering only commodities whose origin and destination are in the same region. For commodities crossing regions, we first determine an appropriate sub-network, then solve a restricted model on this sub-network. To handle the large number of commodities, we divide these into batches based on schedule slack (intuitively, how flexibly a commodity can be scheduled) and solve the problem sequentially over each batch. We demonstrate the scalability and efficiency of our approach through computational studies on real-world instances from an industry partner. Our method finds high-quality solutions after several hours of computing time, while a commercial solver is unable to even build a model for a much smaller instance.
Article