The continuous-time service network design problem (CTSNDP) occurs widely in practice. It aims to minimize the total operational cost by optimizing the schedules of transportation services and the routes of shipments for dispatching, which can occur at any time point along a continuous planning horizon. In order to be cost effective, shipments often wait to be consolidated, which incurs a holding cost. Despite its importance, the holding cost has not been taken into account in existing studies on the CTSNDP, since introducing it significantly complicates the problem and makes the solution development very challenging. To tackle this challenge, we develop a new dynamic discretization discovery algorithm, which can solve the CTSNDP with holding cost to exactly optimum. The algorithm is based on a novel relaxation model and several new optimization techniques. Results from extensive computational experiments validate the efficiency and effectiveness of the new algorithm, and also demonstrate the benefits that can be gained by taking into account holding costs in solving the CTSNDP. In particular, we show that the significance of the benefits depends on the connectivity of the underlying physical network, and on the flexibility of the shipments’ time requirements.
Citation
09/2021