008001018s1998        ulk                AB  0  0a    kor
■090    ▼a004.62▼b강255r
■1001  ▼a강명주
■24510▼aRural  Postman  Problem  해법을  위한  메타휴리스틱  알고리즘  비교  분석▼xA  Comparative  Analysis  on  Metaheuristic  Algorithms  for  Rural  Postman  Problems▼d강명주
■260    ▼a서울▼b경희대학교▼c1998.
■300    ▼a158  p.▼b삽도▼c26  cm.
■5020  ▼a학위논문(석사)▼b경희대학교  대학원▼c전자계산공학과▼d1998
■520    ▼b그래프  및  네트워크  문제는  실생활의  다양한  문제들을  풀기  위해  적용되는  가장  기본적인  문제이다.  그  중  여러  분야에서  응용되는  라우팅  문제들은  Traveling  Slaesman  Problem(TSP)이나  Chinese  Postman  Problem(CPP),  Vehicle  Routing  Problem(VRP)  그리고  지리정보시스템(GIS)에서의  최적  경로  설정  등에  사용된다.  따라서,  본  논문에서는  RPP와  RPP를  확장시킨  문제인  시간제약이  있는  RPP(Rural  Postman  Problem  with  Time  Windows  :  RPPTW)에  대해서  3가지의  메타휴리스틱  알고리즘을  적용하였다.  RPP는  노드의  집합  V자와  에지의  집합  E  그리고  E의  부분집합  E'이  주어진  그래프  G=(V,  E,  E')에서  E'에  속한  에지들을  한번  이상  경유하면서  전체  라우팅  비용을  최소로  하는  문제로  NP-Complete  문제로  알려져  있다.  그리고  시간제약이  있는  RPP는  RPP의  확장된  문제로서  E'의  각  에지에  대해  서비스  기간으로  구성된  시간제약을  설정하여  주어진  시간내에  그  에지에  대한  서비스가  이루어지도록  하는  다중  목적  최적화의  문제이다.  본  논문에서는  이러한  RPP  및  RPPTW의  해법으로  다음과  같은  메타휴리스틱  알고리즘을  적용하였다.  첫째,  지역탐색(Local  Search  :  LS)  알고리즘은  초기해로부터  해  공간(Solution  Space)상의  이웃해들을  탐색하여  근사최적해를  구하는  방법이며,  반복적  지역탐색(Iterative  Local  Search  :  ILS)알고리즘은  초기해를  변화시키면서  LS  알고리즘을  반복  실행시키는  방법이다.  LS  알고리즘은  근사최적해의  탐색시간이  빠른  반면,  지역  최소해(Local  Minima)에  빠질  가능성이  높다.  그리고  ILS  알고리즘은  근사최적해의  탐색  시간이  느리지만,  LS  알고리즘에  비해  지역  최소해에  빠질  가능성이  낮다는  장점이  있다.  본  논문에서는  LS  및  ILS  알고리즘을  이용한  문제  해법을  제안하고,  LS와  ILS  알고리즘의  비교  분석을  통해  LS  알고리즘의  성능을  분석하였다.  둘째,  Simulated  Annealing(SA)  알고리즘은  금속의  담금질의  특성을  이용한  Metropolis  알고리즘  의  확률적  탐색  방법이다.  SA  알고리즘은  냉각  스케줄에  의해  구한  온도에  따라  알고리즘  성능이  크게  좌우된다.  따라서,  본  논문에서는  새로운  냉각  스케줄을  제안하고,  또한  기존의  냉각  스케줄을  이용한  SA와  본  논문에서  제안된  냉각  스케줄을  이용한  SA  알고리즘의  성능을  비교분석  하였다.  셋째,  유전자  알고리즘(Genetic  Algorithm  :  GA)은  자연의  진화  및  적자생존의  원리를  이용하여  프로그램의  알고리즘으로  적용시킨  방법으로,  유전염색체의  구성  방법과  유전  연산자의  적용  방법에  따라  알고리즘의  성능이  좌우된다.  따라서,  본  논문에서는  2가지의  염색체  구성  방법을  제안하고,  기존  방법과의  비교를  통해  유전자  알고리즘의  성능을  분석하였다.  각각의  메타휴리스틱  알고리즘들은  임의로  생성한  9개의  문제와  부록1에서  설명한  실제  지도상의  특정  지역을  모델링한  문제  및  [11]에서  적용한  18개의  문제를  포함한  28개의  RPP  문제와  임의로  생성된  12개의  시간제약이  있는  RPP  문제에  대해  적용  되었으며,  실험결과를  통해  각  알고리즘의  성능  분석  및  평가가  이루어졌다.  실험  결과를  통해  RPP  문제에  대해서는  유전자  알고리즘이  다른  두  알고리즘에  비해  좋은  결과를  얻을  수  있었고,  시간제약이  있는  RPP  문제에  대해서는  유전자  알고리즘과  ILS  알고리즘이  SA  알고리즘에  비해  좋은  결과를  얻을  수  있었다.
■653    ▼aRURAL▼aPOSTMAN▼aPROBLEM▼a위한▼a메타▼a알고리즘▼a비교▼a분석