@article{ART001069886},

author={Kang, Myung-Ju},

title={A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems},

journal={Journal of The Korea Society of Computer and Information},

issn={1598-849X},

year={2007},

volume={12},

number={2},

pages={181-188}

TY - JOUR

AU - Kang, Myung-Ju

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

JO - Journal of The Korea Society of Computer and Information

PY - 2007

VL - 12

IS - 2

PB - The Korean Society Of Computer And Information

SP - 181

EP - 188

SN - 1598-849X

AB - 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

KW - Undirected Rural Postman Problem;Genetic Algorithm;Decoding

DO -

UR -

ER -

Kang, Myung-Ju. (2007). A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems. Journal of The Korea Society of Computer and Information, 12(2), 181-188.

Kang, Myung-Ju. 2007, "A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems", Journal of The Korea Society of Computer and Information, vol.12, no.2 pp.181-188.

Kang, Myung-Ju "A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems" Journal of The Korea Society of Computer and Information 12.2 pp.181-188 (2007) : 181.

Kang, Myung-Ju. A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems. 2007; 12(2), 181-188.

Kang, Myung-Ju. "A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems" Journal of The Korea Society of Computer and Information 12, no.2 (2007) : 181-188.

Kang, Myung-Ju. A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems. Journal of The Korea Society of Computer and Information, 12(2), 181-188.

Kang, Myung-Ju. A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems. Journal of The Korea Society of Computer and Information. 2007; 12(2) 181-188.

Kang, Myung-Ju. A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems. 2007; 12(2), 181-188.

Kang, Myung-Ju. "A Decoding Algorithm Using Graph Transformation in A Genetic Algorithm for Undirected Rural Postman Problems" Journal of The Korea Society of Computer and Information 12, no.2 (2007) : 181-188.