2 단계 수송문제에 대한 협력적 공진화 알고리즘 기반의 혁신적 해법
An Innovative Approach to the Two Stage Transportation Problem Based on the Cooperative Coevolutionary Algorithm
0
조회
0
다운로드
8
인용
0
참고문헌
키워드
초록
본 연구에서는 제품의 공급지, 유통센터 및 수요지의 3 계층으로 이루어진 공급사슬 상에서 각 공급지와 각 유통센터간의 1단계 수송비용, 각 유통센터와 각수요지 사이의 2단계 수송비용 및 유통센터의 운영비용의 합을 최소화할 수 있는 제품의 수송계획 문제를 대상으로 한다. 본 연구에서는 유전 알고리즘의 선행 연구를 바탕으로 이 문제에 대하여 우수한 해를 생성할 수 있는 협력적 공진화 알고리즘을 다음과 같이 설계한다. 먼저 이 문제를 2개의 부분문제로 분할하고, 각 부분문제에 대하여 우선순위 기반의 표현을 사용한 염색체 개체들로써 모집단을 구성한다. 그리고 두 모집단내 각 개체에 대한 적합도의 평가 원리를 소개하고, 사용할 적합도 함수를 설정하고, 각 개체에 대한 적합도 평가 알고리즘을 제시한다. 마지막으로 두 모집단의 세대교체에 사용될 선택, 교배 및 돌연변이 연산자를 선정한다. 이러한 설계를 기반으로 만들어진 협력적 공진화 알고리즘을 기존의 유전 알고리즘과 그 성능을 비교해 보기 위하여 여러 개의 테스트 문제에 대하여 반복 실험한다. 그 결과, 협력적 공진화 알고리즘은 문제의 크기가 커짐에 따라 기존의 유전 알고리즘에 비해 해의 평균적인 품질이나 해의 변동성 면에서 상대적으로 더 우수한 해를 얻을 수 있었다. 본 연구에서 제시한 협력적 공진화 알고리즘 기반의 해법은 현실적인 다단계 수송문제에도 확장 적용될 수 있다.
Abstract
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.
참고문헌 (23)
- 김홍배, "크로스도킹 터미널 내에서 운송비용과 상차비용을 최소화하는 도크 위치 결정", 상경연구, 24(1), pp.155~169 (2008), 산업개발연구소
- 신경석, "공생 진화알고리듬을 이용한 확장된 hub-and-spoke수송네트워크 설계", 한국경영과학회지, 31(2), pp.141~155 (2006), 한국경영과학회
- 신경석, "다목적 최적화를 위한 공생 진화알고리듬", 한국경영과학회지, 32(1), pp.77~91 (2007), 한국경영과학회
- 이현수, "부산지역 물류산업 경쟁력 분석 및 발전 전략", 상경연구, 13, pp.93~113 (1997)
- 정기호, "물류합리화를 위한 공동물류단지의 효율적인 입지 선정에 관한 연구", 상경연구, 5(2), pp.237~251 (1999)
- Amiri,A, "Designing a Distribution Network in a Supply Chain System:Formulation and Efficient Solution Procedure", European Journal of Operational Research, 171(2), pp.567~576 (2006)
- Chandra, C, "Supply Chain Configuration: Concepts, Solutions and Applications" (2007), Springer
- De Jong,K.A, "Evolutionary Computation:A Unified Approach" (2006), MIT Press.
- Dogan, K, "A Primal Decomposition Method for the Integrated Design of Multi-Period Production-Distribution Systems", IIE Transactions, 31(11), pp.1027~1036 (1999)
- Engelbrecht,A.P, "Computational Intelligence, Second Edition" (2007), Wiley
- Gen, M., "A Genetic Algorithm for Two-stage Transportation Problem Using Priority-based Encoding", OR Spectrum, 28(3), pp.337~354 (2006)
- Geoffrin, A. M, "Multicommodity Distribution System Design by Benders Decomposition", Management Science, 20(5), pp.822~844 (1974)
- Geofflin, A. M, "Twenty Years of Strategic Distribution System Design:An Evolutionary Perspective", Interfaces, 25(5), pp.105~128 (1995)
- Jang, Y. J., "A Combined Model of Network Design and Production", Distribution Planning for a Supply Network, 2002, pp.43(1-2), 263~281
- Li, Y. Z., "Improved Genetic Algorithm,for Solving Multi-Objective Solid Transportation problem with Fuzzy Number", Journal of Japan Society for Fuzzy Theory and Systems, 4(3), pp.307~316 (1988)
- Park, K., "Planning for Remarshaling in an Automated Container Terminal using Cooperative Coevolutionary Algorithms", Proceedings of the 24th Annual ACM Symposium on Applied Computing 2009(ACM SAC 2009),, pp.1098~1105 (2009)
- Pirkul, "A Multi-commodity Multi-plant Capacitated Facility Location Problem:Formulation and Efficient Heuristic Solution", Computers & Operations Research, 25, pp.869~878 (1998)
- Popovici, E, "Sequential versus Parallel Cooperative Coevolutionary Algorithms for Optimization", 2006 IEEE Congress on Evolutionary Computation, pp.1610~1617 (2006)
- Potter,M.A, "The Design and Analysis of a Computational Model of Cooperative Coevolution", Ph. D., pp.1997
- Michalewicz, Z., "A Nonstandard Genetic Algorithm for the Nonlinear Transportation Problem", ORSA Journal on Computing, 3(4), pp.307~316 (1991)
- Syarif, A., "Double Spanning Tree-based Genetic Algorithm for Two Stage Transportation Problem", Research Report Ashicaga Institute of Technology, (31), pp.153~158 (2000)
- Syarif, A., "Study on Multi-Stage Logistic Chain Network:A Spanning Tree Based Genetic Algorithm Approach", Computers and Industrial Engineering, 43(1-2), pp.299~314 (2002)
- Vignaux, G. A, "A Genetic Algorithm for the Linear Transportation Problem", IEEE Transactions on Systems, Man and Cybernetics, 21(2), pp.445~452 (1991)