Feeder Vessel Routing and Synchronization at a Congested Transshipment Port : an Enhanced Column Generation Based Approach

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 neighbouring 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 of minimizing 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 solution quality comparing to the standard column generation method and another benchmark heuristic based on the Clarke-Wright savings algorithm. 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