Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/33356
Title: Integrated vehicle dispatching for container terminal
Authors: WANG YUAN
Keywords: Container Terminal, Dispatching, Scheduling, Real Time, Simulation, Metaheuristics.
Issue Date: 6-Jan-2012
Source: WANG YUAN (2012-01-06). Integrated vehicle dispatching for container terminal. ScholarBank@NUS Repository.
Abstract: The dispatching problem in container terminals has received considerable attention from researchers. However, few works have taken into account the coordination among various types of terminal equipment, including Quay Cranes (QC), Prime Movers (PM) and Yard Cranes (YC). To bridge the gap, we address the integrated vehicle dispatching problem in this thesis and design effective models and algorithms to solve the problem. Firstly, we address an integrated dispatching problem which considers both waiting time at quay side and yard side in a container terminal. In previous works [Kim and Bae (2004), Cheng (2005)], the waiting time at yard side is ignored for simplicity. We argue that this variable plays a significant role in the dispatching problem. To solve the new problem, we build a mixed integer programming (MIP) model. Since existing solvers cannot solve the MIP model in reasonable time, we develop two heuristic algorithms. The first is the variable neighborhood search (VNS) algorithm, which is based on the random exchange of neighborhood, but may terminate with only limited improvement. The second method is based on the combination of genetic algorithm (GA) and the minimum cost flow (MCF) network model. We prove that there exists a set of job ready times in the MCF model which produce the optimal vehicle job sequence. Unlike improving the vehicle job sequence directly in most GA algorithms, we use the job ready times as the chromosome and then use the MCF model to decode the job sequence. This converts the complex MIP model into a simple linear programming (LP) formulation. The experimental results indicate the superiority of the GA-MCF algorithm over the neighborhood search algorithm. Secondly, we extend the integrated dispatching problem by considering the locations to store the discharging containers. Previous studies simply assume that the yard locations for discharging jobs are given. However, in actual terminal operations, the port operators can also determine the yard location of discharging containers. Thus, we extend the previous problem by considering the storage locations for discharging containers. This has enlarged the solution space for the problem. In order to effectively find a good solution, we use a tree structure to represent the search space and propose three heuristic methods to solve the problem. The three methods are Nested Partition based method (NP), Buffered Semi Greedy method (BSG), and Buffered Probabilistic Greedy method (BPG). Extensive experiments are conducted and the results show that these heuristic methods can find promising solutions in seconds. Thirdly, we develop an efficient simulation platform to compare and evaluate different dispatching rules to facilitate real time dispatching. In real time dispatching, it is difficult for a port operator to choose a proper rule because the system is highly dynamic and stochastic. The rules might perform differently under different scenarios. In this thesis, we present this simulation platform to evaluate the effectiveness of different rules under different scenarios. This platform not only can work with simple rules, but can also evaluate complex heuristic models which most of the current commercial simulation software would not be able to do so. It can communicate effectively with different solvers which are needed to solve these complicated optimization models.
URI: http://scholarbank.nus.edu.sg/handle/10635/33356
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
WangY.pdf1.88 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

290
checked on Dec 11, 2017

Download(s)

418
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.