New Dynamic Discretization Discovery Strategies for Continuous-Time Service Network Design

Service Network Design Problems (SNDPs) are prevalent in the freight industry. While the classic SNDP is defined on a discretized planning horizon with integral time units, the Continuous-Time SNDP (CTSNDP) uses a continuous-time horizon to avoid discretization errors. Existing CTSNDP algorithms primarily rely on the Dynamic Discretization Discovery (DDD) framework, which iteratively refines discretization and constructs a partially time-expanded network based on the discretization to derive relaxation and feasible solutions. However, the existing DDD algorithms struggle with computational performance, particularly for instances with a high-cost ratio of vehicle-based costs over flow-based costs and high time flexibility, leaving many instances unsolved. This study enhances the DDD solution framework by introducing three new strategies: (i) a new initial relaxation strategy based on timed-node-based time-expanded commodity networks and significant time points identified by solving minimum-hitting set problems; (ii) a new mixed-integer-programming-based strategy for computing upper bounds; and (iii) a new discretization refinement strategy based on eliminating too-long paths in a newly defined dispatch-node graph. Computational experiments demonstrate that our enhanced DDD algorithm achieves exceptional performance, optimally solving all classic CTSNDP instances within one hour. These results validate the effectiveness of the proposed strategies in addressing the limitations of existing DDD algorithms.

Article

Download

View PDF