Tactical vessel deployment and empty container repositioning considering container turnover times

Global trade imbalances lead to the common occurrence of empty container flows from export-dominated to import-dominated ports in container shipping networks. Efficient strategies for repositioning empty containers are essential for addressing deficits at major ports. Existing studies often assume an arbitrary supply of empty containers at a port before repositioning. However, the actual quantity depends on laden containers shipped and turnover times. Considering this interdependence is crucial for reliable repositioning plans, especially at the tactical planning level. This paper explores an integrated problem of vessel deployment and empty container repositioning, aiming to deploy vessels along a route and periodically reposition empty containers, accounting for turnover times. We present an integer programming model minimizing operational and container shortage costs. A novel branch-and-price algorithm is developed, efficiently solving the master problem at each branching tree node using a novel approach that combines column generation and Lagrangian relaxation. Performance evaluation and computational experiments on instances generated from container port turnover statistics and shipping line operational data demonstrate the algorithm's efficacy. The study highlights the impact of container turnover times on repositioning decisions, emphasizing the need for a comprehensive understanding of this dynamic in strategic planning.