Eulerian Circuit and Determination of Optimal Route

Abstract

Chinese Postman Problem (CPP) is well-known as a problem of determining the optimal route. In this work, the problem of CPP is studied by using two algorithms, namely Fleury algorithm and van Aardenne-Ehrenfest - de Bruijn algorithm. The solution of CPP can then be stated as an optimal route, which satisfies a condition, where every single edge must be traversed exactly once, i.e., Eulerian circuit. Graph balancing process in determining Eulerian circuit is done by using Orloff transportation method. The determination of extra shortest path is solved using Dijkstra algorithm. We discuss the application of determining Eulerian circuit for the case of determining the shortest route of garbage collection.