Penyelesaian Masalah Chinese Postman pada Graf Campuran Menggunakan Metode Heuristik Balans-Genap

Abstract

One of the problems in determining an optimal route is the well-known Chinese Postman Problem (CPP). Among many kinds of CPP, this work discusses the mixed one (MCPP), where the representing graph has two types of edge: directed and undirected edges. We employ a heuristic based method, namely balance-even method, to solve the problem. A series of algorithms such as Dijkstra’s and van Aardenne-Ehrenfest and de Bruijn are used in constructing the shortest path and the Euler circuit. In particular, inoutdegree and largecycle methods are implemented in performing balance-even condition. We apply this approach in determining Euler circuit related to the shortest path in the case of electrical devices installation in the city of Bogor.