2 단계 수송문제에 대한 협력적 공진화 알고리즘 기반의 혁신적 해법 (An Innovative Approach to the Two Stage Transportation Problem Based on the Cooperative Coevolutionary Algorithm)

서지정보

· 발행기관 : 경성대학교 산업개발연구소
· 수록지 정보 : 산업혁신연구 / 25권 / 4호 / 227 ~ 251페이지
· 저자명 : 한용호

초록

본 연구에서는 제품의 공급지, 유통센터 및 수요지의 3 계층으로 이루어진 공급사슬 상에서 각 공급지와 각 유통센터간의 1단계 수송비용, 각 유통센터와 각수요지 사이의 2단계 수송비용 및 유통센터의 운영비용의 합을 최소화할 수 있는 제품의 수송계획 문제를 대상으로 한다. 본 연구에서는 유전 알고리즘의 선행 연구를 바탕으로 이 문제에 대하여 우수한 해를 생성할 수 있는 협력적 공진화 알고리즘을 다음과 같이 설계한다. 먼저 이 문제를 2개의 부분문제로 분할하고, 각 부분문제에 대하여 우선순위 기반의 표현을 사용한 염색체 개체들로써 모집단을 구성한다. 그리고 두 모집단내 각 개체에 대한 적합도의 평가 원리를 소개하고, 사용할 적합도 함수를 설정하고, 각 개체에 대한 적합도 평가 알고리즘을 제시한다. 마지막으로 두 모집단의 세대교체에 사용될 선택, 교배 및 돌연변이 연산자를 선정한다. 이러한 설계를 기반으로 만들어진 협력적 공진화 알고리즘을 기존의 유전 알고리즘과 그 성능을 비교해 보기 위하여 여러 개의 테스트 문제에 대하여 반복 실험한다. 그 결과, 협력적 공진화 알고리즘은 문제의 크기가 커짐에 따라 기존의 유전 알고리즘에 비해 해의 평균적인 품질이나 해의 변동성 면에서 상대적으로 더 우수한 해를 얻을 수 있었다. 본 연구에서 제시한 협력적 공진화 알고리즘 기반의 해법은 현실적인 다단계 수송문제에도 확장 적용될 수 있다.

영어초록

We consider a two stage transportation problem in which the objective is to minimize the total cost including shipping cost from plants to distribution centers, shipping cost from distribution centers to customers, and the opening costs of distribution centers in a three tiers of supply chain consisting of plants, distribution centers and customers. We design a cooperative coevolutionary algorithm to solve the problem as follows. First, the problem is decomposed into two different subproblems. In each subproblem we construct a population of chromosome individuals, each of which is denoting a priority and is represented as a permutation. Then we introduce the evaluation principle for a given individual, set the evaluation function, and suggest the evaluation algorithm. Finally we set selection operator, crossover operator, and mutation operator, each of which is used to generate individuals to be included in the next generation. An experiment study is carried out to compare the performance of our cooperative coevolutionary algorithm with that of the genetic algorithm from previous study. In this experiment we obtained the result that in general our coevolutionary algorithm generates better solution than genetic algorithm as the problem size get larger, in term of both the average quality of solutions and the variance of solutions.

참고자료

· 없음