A New Exact Algorithm for Continuous-Time Service Network Design with Splittable Deliveries

The Continuous-Time Service Network Design Problem (CTSNDP) arises in consolidation-based transportation systems, where shipments share paths in space and time to reduce cost. The CTSNDP determines minimum-cost transportation plans over a continuous-time horizon. To provide more consolidation opportunities and achieve further cost reductions, CTSNDP with Splittable Deliveries (SCTSNDP) allows each commodity to be divided into smaller shipments which may follow different routes and schedules. However, solving SCTSNDP exactly is computationally challenging. A direct formulation based on a complete time discretization is typically too large to be solved efficiently. Alternatively, CTSNDP with Unsplittable Deliveries (USCTSNDP) provides a restriction for SCTSNDP when each multi-unit commodity is replaced by predefined multiple sub-commodities. However, such construction substantially enlarges the commodity set and limits the effectiveness of the existing dynamic discretization discovery (DDD) algorithms. To address this challenge, we establish feasibility and optimality equivalences between SCTSNDP and the solution-induced USCTSNDP counterparts, and develop a new DDD algorithm for the SCTSNDP, which iteratively derives upper bounds and refines time discretization by leveraging established DDD components for USCTSNDP. Computational results show that the proposed method outperforms benchmark approaches for SCTSNDP. Extensive experiments further show that splittable deliveries yield significant cost savings with high time flexibility and tight relative network capacity.

Article

Download

View PDF