A Branch-and-Price-and-Cut Algorithm for the Inland Container Transportation Problem with Limited Depot Capacity

As an effective solution to the first- and last-mile logistics of door-to-door intermodal container transportation, inland container transportation involves transporting containers by truck between terminals, depots, and customers within a local area. This paper is the first to focus specifically on the inland container transportation problem with limited depot capacity, where the storage of empty containers is constrained by physical space limitations. To reflect a more realistic scenario, we also consider the initial stock levels of empty containers at the depot. The objective of this problem is to schedule trucks to fulfill inland container transportation orders such that the overall cost is minimum and the depot is neither out of stock or over stocked at any time. A novel graphical representation is introduced to model the constraints of empty containers and depot capacity in a linear form. This problem is then mathematically modeled as a mixed-integer linear programming formulation. To avoid discretizing the time horizon and effectively achieve the optimal solution, we design a tailored branch-and-price-and-cut algorithm where violated empty container constraints for critical times are dynamically integrated into the restricted master problem. The efficiency of the proposed algorithm is enhanced through the implementation of several techniques, such as a heuristic label-setting method, decremental state-space relaxation, and the utilization of high-quality upper bounds. Extensive computational studies are performed to assess the performance of the proposed algorithm and justify the introduction of enhancement strategies. Sensitivity analysis is additionally conducted to investigate the implications of significant influential factors, offering meaningful managerial guidance for decision-makers.