The continuous-time service network design problem

Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time, i.e., the carrier must solve a Service Network Design problem. Most service network design models rely on discretization of time, i.e., instead of determining the exact time at which a dispatch should occur, the model determines a time interval during which a dispatch should occur. While the use of time discretization is widespread in service network design models, a fundamental question related to its use has never been answered: “Is it possible to produce an optimal continuous time solution without explicitly modeling eachpoint in time?” We answer this question in the affirmative. We develop an iterative refinement algorithm using partially time-expanded networks that solves continuous time service network design problems. An extensive computational study demonstrates that the algorithm is not only of theoretical interest, but also performs well in practice.