File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleAn integrated approach to empty container repositioning and vessel routing in marine transportation
Authors
Issue Date2014
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Zhang, L. [張露]. (2014). An integrated approach to empty container repositioning and vessel routing in marine transportation. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5312327
AbstractIn 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.
DegreeDoctor of Philosophy
SubjectContainerization - Mathematical models
Dept/ProgramIndustrial and Manufacturing Systems Engineering
Persistent Identifierhttp://hdl.handle.net/10722/216236

 

DC FieldValueLanguage
dc.contributor.authorZhang, Lu-
dc.contributor.author張露-
dc.date.accessioned2015-09-04T23:11:11Z-
dc.date.available2015-09-04T23:11:11Z-
dc.date.issued2014-
dc.identifier.citationZhang, L. [張露]. (2014). An integrated approach to empty container repositioning and vessel routing in marine transportation. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5312327-
dc.identifier.urihttp://hdl.handle.net/10722/216236-
dc.description.abstractIn 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.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.lcshContainerization - Mathematical models-
dc.titleAn integrated approach to empty container repositioning and vessel routing in marine transportation-
dc.typePG_Thesis-
dc.identifier.hkulb5312327-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineIndustrial and Manufacturing Systems Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5312327-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats