본문 바로가기
  • Home

A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems

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

Kang, Myung-Ju 1

1청강문화산업대학교

Accredited

ABSTRACT

Undirected Rural Postman Problem(URPP) is a problem that finds a shortest tour traversing the given arcs at least once in a given network. The URPP is one of the basic network problems used in solving the various real-world problems. And it is known as NP-Complete. URPP is an arc-oriented problem that the direction of a tour in an arc has to be considered. Hence, in URPP, it is difficult to use the algorithm for Traveling Salesman Problem (TSP), which is a node-oriented problem, directly. This paper proposes the decoding algorithm using graph transformation in the genetic algorithm for URPP. That is, you can find the entire tour traversing without considering the direction of arcs by transforming the arc-oriented graph into the node-oriented graph. This paper compares the performances of the proposed algorithm with an existing algorithm. In the simulation results, the proposed algorithm obtained better than the existing algorithm

Citation status

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