Applying A* algorithm in routing for Inter-Terminal Transport System at Busan Port

  • Long Le Ngoc Bao Korea Maritime and Ocean University, Busan, South Korea
  • Duy Anh Nguyen Vietnam National University Ho Chi Minh City-Ho Chi Minh University of Technology, Vietnam
  • Kim Hwan-Seong Korea Maritime and Ocean University, Busan, South Korea
Keywords: Inter-Terminal Transport, Monorail, Busan Port, Dispatching, Heuristics, Metaheuristics

Abstract

This paper proposes a heuristic approach named A* algorithm to find the shortest routes for the Inter-Terminal Transport Monorail System (ITT system) that are being applied in Busan Port (Korea). In every transport system, vehicle routing and task assignment are significant problems that strongly affect the overall system’s efficiency, especially travel cost and time taken. At present, Busan Port is still using a roadway transportation mode, with manually driven trucks coming in and out of each terminal to load and unload containers, causing casual traffic congestion and wasting lots of time due to waiting at traffic lights. Expenses for fuel and drivers are also challenges for managers. From this, we try to create a new ITT system that could help handle the increasing demand at Busan Port, as well as be operated automatically in order to lower labour and operational costs. The proposed ITT system will use shuttles to carry containers along a monorail that links the internal terminals. A* algorithm is used to guide the shuttles in the shortest way automatically, from a known loading position to a designated unloading one. One of the most crucial problems in this new system is that there must be a method to guide these shuttles automatically and correctly, since the departure and destination points need to be recognized in a pre-defined layout to transfer containers. There are many terminals, resulting in many ways to reach the goal, and shuttles should pick the best way to optimize performance. In the first part of the paper, we will briefly describe briefly the ITT system that being considered in Korea. Next, we will explain why and how we implement A* algorithm in dispatching. Finally, we will give some comparisons between the performance of the new ITT system and the traditional transport system through simulation in MATLAB. The obtained results would prove the superior advantages of the new ITT system versus the traditional system (expressed through the complete time spent at each terminal), as well as emphasize the correctness of A* algorithm in the dispatching problem, as it helps substantially reduce the computational cost.

Downloads

Download data is not yet available.

References

Abdesslem, L., Meryem, A., & Salim, C. (2013). A GRASP algorithm based on new randomized heuristic for vehicle routing problem. Journal of Computing and Information Technology, 21(1), 35-46. doi:10.2498/cit.1002085

Dorigo, M., & Stützle, T. (2004). The ant colony optimization metaheuristic (pp. 25-64). MIT Press eBook, USA.

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems Man and Cybernetics Part B: Cybernetics, 26(1), 29-41. doi:10.1109/3477.484436

Duinkerken, M. B., Dekker, R., Kurstjens, S. T. G. L., Ottjes, J. A., & Dellaert, N. P. (2006). Comparing transportation systems for inter-terminal transport at the Maasvlakte container terminals. OR Spectrum, 28(4), 469-493. doi:10.1007/s00291-006-0056-1

Edmond, C. (2005). A graph search heuristic for shortest distance paths. Center for Applied Scientific Computing, Lawrence Livermore National Laboratory.

Feo, T. A., & Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6, 109-133. doi:10.1007/BF01096763

Heilig, L., & Voss, S. (2017). Inter-terminal transportation: An annotated bibliography and research agenda. Flexible Services and Manufacturing Journal, 29(1), 35-63. doi:10.1007/s10696-016-9237-7

Kim, H. S. (2019). Busan Port New Port ITT Infrastructure Project (in Korea). Project Document, Korea Maritime and Ocean University.

Lee, D. H., Jin, J. G., & Chen, J. H. (2012). Terminal and yard allocation problem for a container transshipment hub with multiple terminals. Transportation Research Part E: Logistics and Transportation Review, 48(2), 516-528. doi:10.1016/j.tre.2011.09.004

Long, L. N. B., Duy-Anh, N., & Hanh, L. D. (2018). Application of combinatorial optimization in logistics. In: Proceedings of the 2018 4th International Conference on Green Technology and Sustainable Development. HCMC University of Technology and Education, Vietnam.

Rodrigue, J. P., Comtois, C., & Slack, B. (2017). Transportation Modes: The Geography of Transport Systems. 4th eds. London: Taylor & Francis.

Shi, J., Li, J., Cao, H., & Wang, X. (2008). Study on near-optimal path finding strategies in a road network. Journal of Algorithms & Computational Technology, 2(3), 319-333. doi:10.1260/174830108785302878

Stützle, T., & Dorigo, M. (2002). A short convergence proof for a class of ant colony optimization algorithms. IEEE Transactions on Evolutionary Computation, 6(4), 358-365. doi:10.1109/TEVC.2002.802444

Yao, J., Zhang, B., & Zhou, Q. (2009). The optimization of A* algorithm in the practical path finding application (pp. 514-518). In: Proceedings of the 2009 WRI World Congress on Software Engineering. Xiamen, China.

Zhen, L., Wang, S., & Wang, K. (2016). Terminal allocation problem in a transshipment hub considering bunker consumption. Naval Research Logistics, 63(7), 529-548. doi:10.1002/nav.21717

Published
2020-05-11
How to Cite
Le Ngoc Bao, L., Nguyen, D. A., & Hwan-Seong, K. (2020). Applying A* algorithm in routing for Inter-Terminal Transport System at Busan Port. Maritime Technology and Research, 2(4), 218-230. https://doi.org/10.33175/mtr.2020.240342