Evaluasi Rute Pelayaran Kapal dengan Pendekatan Modified Minimum Spanning Tree

Abstract

This research aims to optimize the shipping routes of the largest container shipping liner company in Indonesia. Route optimization is essential for improving the efficiency of the company in the face of increasingly intense business and industry competition. In this study, a multi-objective approach is used, considering both demand and distance factors. The proposed evaluation model utilizes a modified minimum spanning tree (MST) with probabilistic calculations based on historical data. The modification takes into account probabilistic factors derived from past data, enabling better decision-making.Additionally, for scenarios where the route needs to return to the depot, the Christofides algorithm is employed. The Christofides algorithm is used to solve the Traveling Salesman Problem (TSP), where the objective is to find the shortest path that visits all points and returns to the starting point. This algorithm is based on the MST. The results of the conducted case studies using this model show an improvement in the performance of shipping routes, with a 1.13% increase in ship utility and a 2.83% decrease in total distance. Therefore, it can be concluded that the evaluation model for shipping routes, employing a multiobjective approach, modified MST with probabilistic considerations, and the Christofides algorithm, can provide more efficient solutions and opportunities for operational improvements in the company.