시간종속 재고경로 문제를 위한 적응적 유전 알고리즘
An Adaptive Genetic Algorithm for Time Dependent Inventory Routing Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
이 연구에서는 주어진 계획기간에 다수의 소매점에 대하여 재고보충 의사결정과 시간종속 차량경로 의사결정이 동시에 이루어지는 시간종속 재고경로 문제를 논의한다. 이 연구의 목적은 러시아워와 같은 교통상황 때문에 방문하고자 하는 지점 간에 교통 시간이 일정하지 않은 상황을 고려한 재고와 수송에 총비용을 최소화하는 것이다. 시간종속 재고경로 문제는 혼합정수 수리모델로 수립된다. 그러나 이러한 문제는 풀기 어려운 조합 최적화 문제들 중에 하나로서 NP-hard 문제에 속한다. 그러므로 합리적인 시간 내에 적절한 해를 얻을 수 있는 적응적 유전 알고리즘을 개발한다. 시간종속 재고경로 문제의 재고 보충량, 재고 보충시기 및 차량경로의 세 가지 의사결정변수를 결정하기 위하여 2차원 행렬의 유전자 표현이 고안되었으며, 또한 적절한 교차, 돌연변이 및 적응적 유전자가 개발되었다. 수치실험에서 얻어진 결과는 시간종속 재고경로 문제를 해결하기 위해 개발된 적응적 유전 알고리즘이 좋은 해를 제시하고 있음을 입증한다.
Abstract
This paper addresses time dependent inventory routing problem in which inventory control and time dependent vehicle routing decisions for a set of retailers are to be determined simultaneously over a given planning time horizon. This study is motivated by the effect of dynamic changes in traffic, such as rush hour traffic jams, and the resulting inventory and logistics cost. The time dependent inventory routing problem can be formulated as a mixed integer programming formulation. But this problem is one of the most challenging combinational optimization problems and belongs to the category of NP-hard problems. Therefore, an adaptive genetic algorithm is developed to provide solutions to the time dependent inventory routing problem in polynomial time. For determining the three decision variables of replenishment amount, replenishment time, and routing, the genetic representation of a two-dimensional matrix were devised. And then, suitable crossover,mutation and adaptive operators were developed. The computational results show that the proposed adaptive genetic algorithm can provide a good heuristic solution.
참고문헌 (37)
- 박양병, "2단계 VMI 공급사슬에서 통합 재고", 차량경로 문제를 위한 유전알고리듬 해법, 2008, pp.34(3), 362~372[DOI]
- 이용식, "이동시간의 변화를 고려한 차량경로 문제의 분지평가법을 이용한 최적화 해법", 대한산업공학회지, 37(2), pp.144~152 (2011), 대한산업공학회
- 전건욱, "유전자 알고리즘을 이용한 시간제약 차량경로문제", 산업경영시스템학회지, 29(4), pp.75~82 (2006), 한국산업경영시스템학회
- Abdelmaguid, T. F., "A Genetic Algorithm Approach to the Integrated Inventory Routing Problem", International Journal of Production Research, 44(21), pp.4445~4464 (2006)
- Arnold, N., "A Comparison of Complete Global Optimization Solvers", Mathematical Programming, 103(2), pp.335~356 (2005)
- Atamturk, A., "Integer- Programming Software Systems", Annals of Operations Research, 140(11), pp.67~124 (2005)
- Baita, F., "Dynamic Routing and Inventory Problems: a Review", Transportation Research-A, 32(8), pp.585~598 (1998)
- Bell, W., "Improving the Distribution of Industrial Gases with an On-line Computerized Routing and Scheduling Optimizer", Interface, 13(6), pp.4~23 (1983)
- Beltrami, E. J., "Networks and Vehicle Routing for Municipal Waste Collection", Networks, 4(1), pp.65~94 (1974)
- Balseiro, S. R., "an Ant Colony Algorithm Hybridized with Insertion Heuristics for Time Dependent Vehicle Routing Problem with Time Window", Computers & Operations Research, 38(6), pp.954~966 (2011)
- Bertazzi, L., "Deterministic Order-up-to Level Policies in an Inventory Routing Problem", Transportation Science, 36(1), pp.119~132 (2002)
- Blumenfeld, D. E., "Analyzing Trade-offs Between Transportation, Inventory and Production Costs on Freight Networks", Transportation Research, 19(5), pp.361~380 (1985)
- Chan, F. T. S., "A Hybrid Genetic Algorithm for Production and Distribution", Omega, 33(4), pp.345~355 (2004)
- Chien, T. W., "An Integrated Inventory Allocation and Vehicle Routing problem", Transportation Science, 28(2), pp.67~77 (1989)
- De Jong, K. A., "Analysis of Behavior of a Class of Genetic Adaptive Systems", 박사, pp.1975
- Donati, A. V., "Time Dependent Vehicle Routing Problem with a Multi Ant Colony System", European Journal of Operational Research, 185(3), pp.1174~1191 (2008)
- Dror, M., "Inventory", Routing: Reduction from an Annual to a Short-Period Problem, 1987, pp.34(6), 891~905
- Dror, M., "A Computational Comparison of Algorithms for the Inventory Routing Problem", Annals of Operations Research, 4(1), pp.1~23 (1985)
- Ernst, R., "Optimal Base Stock Policies and Truck Capacity in a Two-echelon System", Naval Research Logistics, 40(7), pp.879~903 (1993)
- Federgruen, A., "A Combined Vehicle Routing and Inventory Allocation Problem", Operations Research, 32(5), pp.1019~1037 (1984)
- Gen, M., "Hybrid Genetic Algorithm for Multi-time Period Production", Distribution Planning, 2005, pp.48(4), 799~809
- Golden, B., "Analysis of a Large Scale Vehicle Routing Problem with an Inventory Component", Large Scale Systems, 7(2), pp.181~190 (1984)
- Hall, R. W., "Determining Vehicle Dispatch Frequency When Shipping Frequency Differs Among Suppliers", Transportation Research Part B, 19(5), pp.421~431 (1985)
- Haghani, A., "A Dynamic Routing Problem with Time Dependent Travel Time", Computers & Operational Research, 32(11), pp.2929~2986 (2005)
- Hill, A. V., "Modelling Intra-city Time-Dependent Travel Speeds for Vehicle Scheduling Problems", Journal of the Operational Research Society, 43(4), pp.343~351 (1992)
- Herer, Y. T., "The Metered Inventory Routing Problem, an Integrative Heuristic Algorithm", International Journal of Production Economics, 51(1), pp.69~81 (1997)
- Ichoua, A., "Vehicle Dispatching with Time-Dependent Travel Times", European Journal of Operational Research, 144(2), pp.379~396 (2003)
- Kuo, Y., "Optimizing Goods Assignment and the Vehicle Routing Problem with Time-Dependent Travel Speeds", Computers & Industrial Engineering, 57(4), pp.1385~1392 (2009)
- Malandraki, C., "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristics Algorithms", Transportation Science, 32(3), pp.185~200 (1992)
- Mark, K. L., "An Adaptive Genetic Algorithm for Manufacturing Cell Formation", International Journal of Manufacturing Technology, 16(16), pp.491~497 (2000)
- Moin, N., "Inventory Routing Problems: a Logistical Overview", Journal of the Operational Research Society, 58(9), pp.1185~1194 (2007)
- Richard, L., "Solving Hard-Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study", INFORMA Journal on Computing, 21(2), pp.304~313 (2009)
- Sung, K., "Shortest Paths in a Network with Time Dependent Flow Speeds", European Journal of Operational Research, 121(1), pp.32~39 (2000)
- Trudeau, P., "Stochastic Inventory Routing: Route Design with Stockouts and Route Failures", Transportation Science, 26(3), pp.171~184 (1992)
- Youngqiang L., "An Improved Ant Colony Algorithm for the Time-Dependent Vehicle Routing Problem", IEICE TRANSACTIONS on Communications, 94(5), pp.1506~1510 (2011)
- Yun, Y., "Performance Analysis of Adaptive Genectic Algorithm with Fuzzy Logic and Heuristics", Fuzzy Optimization and Decision Making, 2(2), pp.161~175 (2003)
- Viswanathan, S., "Integrating Routing and Inventory Decisions in One Warehouse Multi-customer Multi-product Distribution System", Management Science, 43(3), pp.294~312 (1997)