Contact Name: Daniele Vigo
Abstract
Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, a carrier must consolidate shipments, which requires coordinating shipment paths in both space and time, i.e., the carrier must solve a Scheduled Service Network Design (SSND) problem. To represent time, most service network design models rely on a discretization of time and are formulated on a time-expanded network. That said, how a discretization is done can impact both the accuracy of the resulting SSND model and its solvability. On the one hand, the more granular the discretization, the more accurate the estimation of consolidation opportunities, albeit at the expense of a larger network and harder optimization model to solve. On the other hand, a coarser discretization will yield a smaller network and easier optimization model, albeit one that is less accurate. However, this trade-off between accuracy and model size is primarily a function of determining a discretization of time in a static, a priori manner.
Thus, this talk will first present a Dynamic Discretization Discovery algorithm that determines a discretization of time in a dynamic and iterative fashion, wherein at each iteration a SND is solved on a carefully constructed time-expanded network based upon the current discretization of time. Having reviewed the fundamental steps of the algorithm, the talk will then focus on two extensions: (1) how the algorithm can be enhanced through the use of valid inequalities and other integer programming-inspired techniques, and, (2) how the algorithm can be adapted to variants of the SSND that represent operational realities. Finally, the talk will present a new Scheduled Service Network Design problem, one which can inform shipper-carrier negotiations regarding delivery time windows, and discuss how the algorithm can be applied to this new problem.