New Formulations for the Scheduled Service Network Design Problem

We propose a new approach to formulating the Scheduled Service Network Design Problem (SSNDP) that involves modeling with enumerated consolidations of shipments routed on the physical network. This is in contrast to the classical approach of capturing the synchronization of vehicles and shipments needed for consolidation with a time-expanded network. The proposed formulation has both a stronger linear relaxation and is less symmetric. We present multiple speed-up techniques and with an extensive computational study illustrate that the consolidation-based formulation is much easier to solve with an off-the-shelf solver than the classical formulation based on a time-expanded network. To avoid instances involving large numbers of consolidations we propose a hybrid formulation that combines ideas from the consolidation and time-expanded network-based approaches to formulating the SSNDP. We show that instances of the hybrid formulation are much easier to solve than both instances of the pure consolidation-based formulation and those based on a time-expanded network formulation. Finally, we discuss how formulating with consolidations facilitates modeling issues that have not yet been addressed in the literature, such as bin-packing considerations when computing vehicle capacity needs. In addition, the proposed modeling technique for bin-packing considerations in a consolidation-based formulation yields instances that are easier to solve than those wherein capacity is modeled in an aggregate sense