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