본문 바로가기
  • Home

A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2005, 10(1), pp.181-188
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

ByungHyun Jun 1 Kang, Myung-Ju 2 Chi-Geun Han 1

1경희대학교
2청강문화산업대학교

Candidate

ABSTRACT

Chinese Postman Problem (CPP) is a problem that finds a shortest tour traversing all edges or arcs at least once in a given network. The Chinese Postman Problem on Mixed networks (MCPP) is a practical generalization of the classical CPP and it has many real-world applications. The MCPP has been shown to be NP-complete. In this paper, we transform a mixed network into a symmetric network using virtual arcs that are shortest paths by Floyd's algorithm. With the transformed network, we propose a Genetic Algorithm (GA) that converges to a near optimal solution quickly by a multi-directional search technique. We study the chromosome structure used in the GA and it consists of a path string and an encoding string. An encoding method, a decoding method, and some genetic operators that are needed when the MCPP is solved using the proposed GA are studied. In addition, two scaling methods are used in proposed GA. We compare the performance of the GA with an existing Modified MIXED2 algorithm (Pearn et al., 1995). In the simulation results, the proposed method is better than the existing methods in case the network has many edges, the Power Law scaling method is better than the Logarithmic scaling method.

Citation status

* References for papers published after 2022 are currently being built.