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

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.