The container transportation problem involves designing routing plans for a fleet of vehicles to accommodate requests from multiple ports. A request is a transshipment activity that involves loading a commodity at the source port and then unloading it at the destination port. This problem is closely related to the classic vehicle routing problem (VRP). This thesis investigates a real-world, multi-shift container transportation problem with a limited fleet size. In this problem, requests are sent from the customs office via declaration forms. Each declaration form contains several container transport tasks that share the same time window, source port and destination port. The time windows for container transportation in this problem can generally span across several shifts, thus container transportations can be arranged at any shift. Delaying some transportations to later shifts may cause the violation of time window constraints. As a result, strategies that prioritise tasks with closer deadline need to be developed to ensure that all tasks can be completed.
This thesis presents the following research efforts towards the container transshipment problem. Firstly, two formulations have been proposed to describe the problem, in which the representation of transshipment requests are simplified as nodes. The network of the ports is then discussed and, based on the network, three sets of problem instances are introduced. This thesis then introduces several insertion-based heuristics, which are able to generate solutions that complete all container transshipment tasks. In order to further reduce the travelling distance in the solutions, two multi-neighbourhood algorithms are implemented and experimental results are presented. The characteristics of solutions are discussed to get a deeper understanding of the problem characteristics. The dynamic version of the problem, in which declaration forms arrive over time, is then studied. A discrete event simulation framework is developed to accommodate the experiment of various commodity holding strategies. This research leads to an intelligent container transportation system that automates the task assignment.
|Date of Award
|1 Jul 2016
- Univerisity of Nottingham
|Ruibin Bai (Supervisor), Rong Qu (Supervisor) & Graham Kendall (Supervisor)