@article{ART001175994},
author={ByungHyun Jun and Kang, Myung-Ju and Chi-Geun Han},
title={A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2005},
volume={10},
number={1},
pages={181-188}
TY - JOUR
AU - ByungHyun Jun
AU - Kang, Myung-Ju
AU - Chi-Geun Han
TI - A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks
JO - Journal of The Korea Society of Computer and Information
PY - 2005
VL - 10
IS - 1
PB - The Korean Society Of Computer And Information
SP - 181
EP - 188
SN - 1598-849X
AB - 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.
KW - Chinese Postman Problem;CPP;MCPP;Genetic Algorithm
DO -
UR -
ER -
ByungHyun Jun, Kang, Myung-Ju and Chi-Geun Han. (2005). A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks. Journal of The Korea Society of Computer and Information, 10(1), 181-188.
ByungHyun Jun, Kang, Myung-Ju and Chi-Geun Han. 2005, "A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks", Journal of The Korea Society of Computer and Information, vol.10, no.1 pp.181-188.
ByungHyun Jun, Kang, Myung-Ju, Chi-Geun Han "A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks" Journal of The Korea Society of Computer and Information 10.1 pp.181-188 (2005) : 181.
ByungHyun Jun, Kang, Myung-Ju, Chi-Geun Han. A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks. 2005; 10(1), 181-188.
ByungHyun Jun, Kang, Myung-Ju and Chi-Geun Han. "A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks" Journal of The Korea Society of Computer and Information 10, no.1 (2005) : 181-188.
ByungHyun Jun; Kang, Myung-Ju; Chi-Geun Han. A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks. Journal of The Korea Society of Computer and Information, 10(1), 181-188.
ByungHyun Jun; Kang, Myung-Ju; Chi-Geun Han. A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks. Journal of The Korea Society of Computer and Information. 2005; 10(1) 181-188.
ByungHyun Jun, Kang, Myung-Ju, Chi-Geun Han. A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks. 2005; 10(1), 181-188.
ByungHyun Jun, Kang, Myung-Ju and Chi-Geun Han. "A Genetic Alogorithm for the Chinese Postman Problem on the Mixed Networks" Journal of The Korea Society of Computer and Information 10, no.1 (2005) : 181-188.
