SIMULATED ANNEALING ALGORITHM FOR SOLVING THE SHIP ROUTING PROBLEM

• Main Author: TRY LIPUTRA ( NIM: 23410015 ); Pembimbing : Suprayogi, Ph.D, DAVID
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/18254
• Institution: Institut Teknologi Bandung

Indonesia, as the largest archipelagic country in the world, realizes the <br /> <br /> <br /> <br /> <br /> importance of inter-regional transportation system in encouraging the national <br /> <br /> <br /> <br /> <br /> development. The implementation of effective and efficient transportation system <br /> <br /> <br /> <br /> <br /> will smoothen the traffic flow of people, goods, services, and information. By the <br /> <br /> <br /> <br /> <br /> condition of Indonesia geographic that consisting of islands, then ship, as a <br /> <br /> <br /> <br /> <br /> means of sea transport, has very important role and function in the structure of <br /> <br /> <br /> <br /> <br /> national transportation system. Therefore, this research is focused on solving <br /> <br /> <br /> <br /> <br /> problems related to the ship routing problem. <br /> <br /> <br /> <br /> <br /> A national company engaged in the sea transportation (especially passenger <br /> <br /> <br /> <br /> <br /> ship), namely PT Pelayaran Nasional Indonesia (PT Pelni) is used as the object of <br /> <br /> <br /> <br /> <br /> study in this research. At present (2012), PT Pelni operates 24 units of passenger <br /> <br /> <br /> <br /> <br /> ship to serve 90 units of port that spread across Indonesia. PT Pelni wants to <br /> <br /> <br /> <br /> <br /> make an evaluation on determination of the existing route and deployment of its <br /> <br /> <br /> <br /> <br /> passenger ships and expects to increase the efficiency of ship operations. <br /> <br /> <br /> <br /> <br /> Therefore, this research is aimed to propose the feasible route and deployment of <br /> <br /> <br /> <br /> <br /> ships which minimize the total operating costs. <br /> <br /> <br /> <br /> <br /> This research develops a metaheuristic approach, i.e. simulated annealing (SA) <br /> <br /> <br /> <br /> <br /> algorithm in solving the ship routing problem, where the initial solution is <br /> <br /> <br /> <br /> <br /> generated using sequential insertion (SI) algorithm and improved using three <br /> <br /> <br /> <br /> <br /> types of operator, i.e. exchange, crossover, and mutation. In addition, this <br /> <br /> <br /> <br /> <br /> research also develops a procedure for switching ship to ensure that the resulting <br /> <br /> <br /> <br /> <br /> ship deployments are the best ones. <br /> <br /> <br /> <br /> <br /> From this research, it can be known that the proposed ship routes provide the less <br /> <br /> <br /> <br /> <br /> total operating costs than the existing ones applied by PT Pelni at this time, with <br /> <br /> <br /> <br /> <br /> the difference of IDR 1,253,890,048.00 (saving of operating costs by 2.34%). In <br /> <br /> <br /> <br /> <br /> addition, the total voyage time of proposed ship routes by 333.97 days to visit <br /> <br /> <br /> <br /> <br /> 305 units of port is also shorter than the existing ones which spend the total voyage <br /> <br /> <br /> <br /> <br /> time by 343.28 days to visit 222 units of port.