Article ID: | iaor20104936 |
Volume: | 32 |
Issue: | 3 |
Start Page Number: | 663 |
End Page Number: | 685 |
Publication Date: | Jul 2010 |
Journal: | OR Spectrum |
Authors: | Chew Ek Peng, Lee Loo Hay, Wang Yuan, Tan Kok Choon |
Keywords: | heuristics: genetic algorithms, vehicle routing & scheduling, networks: flow |
This paper seeks to address the dispatching problem for vehicles (or prime movers) in a transshipment hub by considering the quay cranes and yard cranes capacity. The objective of this paper is to minimize the makespan time at the quay side. This issue is particularly important for a port which uses information technology in making real time decision because the port can exploit information technology to make full use of the data in making good decision. A mixed integer programming (MIP) model is developed to formulate the problem. As the existing solver cannot solve the MIP model in reasonable time, we develop two heuristics to tackle the problem. The first method is based on the neighborhood search, while the second method is based on genetic algorithm (GA) and minimum cost flow (MCF) network model. Unlike the typical GA which usually represents the chromosome using job sequence, we use the ready time for jobs as the representation of the chromosome, and MCF model is then used to decode the chromosome to determine the job sequence for prime movers. The experiment results indicate the superiority of the GA–MCF-based algorithm over the neighborhood search algorithm.