Column generation approach for feeder vessel routing and synchronization at a congested transshipment port
Abstract
With increasing container-shipping traffic in major transshipment ports, unsynchronized shipping services at hub ports usually lead to loss of transshipment connections, significant vessel port-stay time, and congestion. This calls for the design of feeder vessel services to pick up from and deliver containers to neighboring local ports, and, at the same time, synchronize them with long-haul services in a manner that enables efficient container transshipment. In this paper, we present a mixed integer linear programming model to optimize the feeder vessel routes and hub port synchronization with an objective to minimize the total operating and connection cost. We exploit the model structure and design an enhanced column generation based approach. We develop new techniques to expand the size of the column set and solve the pricing sub-problem more efficiently, and hence greatly improve performance of the column generation approach. Two real-world case studies and additional experiments based on randomly generated test instances are conducted. Results demonstrate that the proposed approach is applicable for solving real-world-sized problems efficiently. In addition, the container transshipment connection can be significantly enhanced by integrating the synchronization decision with feeder vessel routing.