Incorporating Holding Costs in Continuous-Time Service Network Design: New Model, Relaxation, and Exact Algorithm
针对连续时间服务网络设计问题，提出一种新的动态离散发现算法，首次在精确求解中纳入持有成本，实验证明算法高效且能显著降低总成本。
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 exact solution methods for the CTSNDP because introducing it significantly complicates the problem and makes 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 the flexibility of the shipments’ time requirements. Funding: This work was partially supported by National Natural Science Foundation of China [Grant 71831008] and the Hong Kong Polytechnic University [Project P0043872]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0104 .