An integrated approach to empty container repositioning and vessel routing in marine transportation

Abstract

In recent decades, the rapid development of international economy has led to significant inter-regional trade imbalances. In marine transportation, the voluminous empty containers accumulated at ports in import dominated countries have to be re-circulated back to ports in export dominated countries for re-deployment. This repositioning of empty containers is crucial for shipping companies to provide effective transportation services. At present, empty container repositioning has proved to be highly expensive, contributing to 27% of the overall operation cost of shipping companies. Consequently, major stakeholders including the shipping companies have strived to reduce the repositioning cost. Unfortunately, few major improvements have been made over the years and there are still lingering research issues. The objective of this research, therefore, is to develop efficient and effective methodologies to obtain empty container repositioning plans that can significantly reduce transportation cost while fulfilling customer demands of empty and laden containers.

In this research, the empty container repositioning problem under two related real marine transportation scenarios has been studied. The first scenario considers multi-vessel transportation for both laden and empty containers with split vessel routing (denoted as ECRSVR). A mathematical model of ECRSVR is developed based on the formulation of the Pickup and Delivery Problem with Time Windows (PDPTW). However, a major research issue arises due to such integrated consideration of split vessel routing and transportation of empty and laden containers. The resulting model will encompass many more new decision variables and constraints. Thus, it cannot be readily solved by existing algorithms. To address this issue, a new Branch-and-Price (B&P) algorithm incorporating B&B and column generation is developed. Specifically, a new dynamic programming algorithm with new label structure and dominance rules is established to solve the pricing problem in B&P, and a new multi-layer branching scheme is developed for implementing the algorithm. The effectiveness and robustness of the proposed methodology are then tested on a set of randomly generated problems.

The second scenario extends the first by including transshipment activities in the ECRSVR (denoted as ECRSVRTS). Apparently, the inclusion of transshipment activities will significantly increase the size of the solution space of feasible routing and distribution schemes. Also, more constraints have to be included in the model to account for the interdependence between the distribution schemes of separate vessels. To tackle this problem, two mathematical models are developed. The first is a port-based model that explicitly characterizes the routing plans and distribution volumes for each vessel at each time interval as decision variables. The resulting integer program is non-linear and difficult to solve. Therefore, an equivalent event-driven node-based model inspired by the formulation of PDPTW is constructed. In this model, the pickup/delivery tasks and transshipment events are represented as nodes in a generated topology. The B&P scheme is then modified to solve the node-based model and a Hybrid Scatter Tabu Search (HSTS) is developed to solve the pricing problems. Results obtained from the numerical experiments using randomly generated test problems show that the proposed HSTS algorithm outperforms conventional scatter search and tabu search algorithms.