An Exact Algorithm for Continuous Ship Unloading Based on Vehicle Routing

Port operations involving ship unloading have traditionally posed significant complexity and have proven difficult to solve optimally using exact methods. This study investigates the long continuous unloading of ships carrying liquid products, where transportation is carried out using full truckload deliveries. For the first time, this work integrates the problem of liquid-based ship unloading with full truckload vehicle routing and truck driver scheduling. The primary objective is to minimize the total transportation costs during the continuous unloading process, while satisfying extra constraints such as driver rest–break–drive regulations, time windows, a heterogeneous fleet structure, and port-specific constraints such as maintaining a minimum number of backup vehicles at the port during unloading. To address this complex problem, a route-based insertion heuristic is employed as an initial step in a column generation framework designed for exact optimization. The approach incorporates a nested label setting algorithm for column generation, enhanced with acceleration techniques involving multi-search strategies, and refined selection methods. Performance analysis, based on artificial datasets closely resembling real-world scenarios and consisting of 112 instances, demonstrates that optimality gaps below 1% can be achieved within computational times considered reasonable in the context of the existing literature, while the total number of customer nodes and the minimum number of required vehicles at the port are at most 100 and 5, respectively.