Penyelesaian Stacker Crane Problem dengan Algoritme Largearcs dan Smallarcs

Abstract

In graph theory, the Rural Postman Problem (RPP) aims to determine the shortest route with minimum cost, in which only certain edges or arcs are necessarily traversed. One type of RPP is Stacker Crane Problem (SCP) which deals with a mixed graph but only arcs are necessarily traversed. SCP can be solved by using two heuristic algorithms, i.e. Largearcs and Smallarcs algorithms, which include other algorithms in their steps, such as: Dijkstra algorithm to determine shortest route, Hungaria method to determine minimum bipartite matching, Prim algorithm to determine minimum spanning tree, and van Aardenne-Ehrenfest & de-Bruijn algorithm and Fleury algorithm to determine Euler circuits. The shortest Euler circuit resulted from two heuristic algorithms can be used to find a solution of SCP. The application of SCP is illustrated in establishing the minimum distance route of catering delivery.