본문 바로가기
  • Home

A Genetic Algorithm using A Modified Order Exchange Crossover for Rural Postman Problem with Time Windows

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

Kang, Myung-Ju 1

1청강문화산업대학교

Candidate

ABSTRACT

This paper describes a genetic algorithm and compares three crossover operators for Rural Postman Problem with Time Windows (RPPTW). The RPPTW which is a multiobjective optimization problem, is an extension of Rural Postman Problem(RPP) in which some service places (located at edge) require service time windows that consist of earliest time and latest time. Hence, RPPTW is a multiobject optimization problem that has minimal routing cost being serviced within the given time at each service place.To solve the RPPTW which is a multiobjective optimization problem, we obtain a Pareto-optimal set that the superiority of each objective can not be compared. This paper performs experiments using three crossovers for 12 randomly generated test problems and compares the results. The crossovers using in this paper are Partially Matched Exchange(PMX), Order Exchange(OX), and Modified Order Exchange(MOX) which is proposed in this paper. For each test problem, the results show the efficacy of MOX method for RPPTW.

Citation status

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