차량 경로 스케줄링 문제 해결을 위한 개미 군집 최적화 휴리스틱
An Ant Colony Optimization Heuristic to solve the VRP with Time Window
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
차량 경로 스케줄링 문제(VRSPTW, the Vehicle Routing and Scheduling Problem with Time Window)는 여러 고객의 시간 제약과 요구량을 만족시키면서 최소 이동 비용을 가지는 경로를 구성하는 문제이다. 이 문제는 NP-Hard 문제이기 때문에 해를 산출하는데 시간이 오래 걸린다. 본 연구는 VRSPTW를 빠른 시간 내에 최근사해를 구하기 위한 멀티 비용 함수(Multi Cost Function)를 갖는 개미 군집 최적화(Ant Colony Optimization)을 이용한 휴리스틱을 제안하였다. 멀티 비용 함수는 각 개미가 다음 고객 노드로 이동하기 위해 비용을 평가할 때 거리, 요구량, 각도, 시간제약에 대해 서로 다른 가중치를 반영하여 우수한 초기 경로를 구할 수 있도록 한다. 본 연구의 실험결과에서 제안된 휴리스틱이 Solomon I1 휴리스틱과 기회시간이 반영된 하이브리드 휴리스틱보다 효율적으로 최근사 해를 얻을 수 있음을 보였다.
Abstract
The Vehicle Routing and Scheduling Problem with Time Windows(VRSPTW) is to establish a delivery route of minimum cost satisfying the time constraints and capacity demands of many customers. The VRSPTW takes a long time to generate a solution because this is a NP-hard problem. To generate the nearest optimal solution within a reasonable time, we propose the heuristic by using an ACO(Ant Colony Optimization) with multi-cost functions. The multi-cost functions can generate a feasible initial-route by applying various weight values, such as distance, demand, angle and time window, to the cost factors when each ant evaluates the cost to move to the next customer node. Our experimental results show that our heuristic can generate the nearest optimal solution more efficiently than Solomon I1 heuristic or Hybrid heuristic applied by the opportunity time.
참고문헌 (21)
- L. Bodin, "Routing and Scheduling of Vehicles and Crews:The State of the Art", Computer and Operations Research, 10(2), pp.63~211 (1983)
- J. K. Lenstra, "Complexity of vehicle routing and scheduling problems", Networks, 11(2), pp.221~227 (1981)
- M. W. P. Savelsbergh, "Vehicle routing and computer graphics", Centre for Mathematics and Computer Science, ~ (1984), Note OS-N8402
- M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints", Operations Research, 35(2), pp.254~265 (1987)
- B.-L. Garcia, "A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints", Computers and Operations Research, 21(9), pp.1025~1033 (1994)
- O. Braysy, "Vehicle Routing Problem with Time Windows,Part II-Metaheuristics", Transportation Science, 39(1), pp.119~139 (2005)
- S. R. Thangiah, "GIDEON:A genetic algorithm system for vehicle routing with time windows", Artificial Intelligence Application, Proceedings., 7th IEEE Conference on, pp.322~328 (1991)
- E. Taillard, "A Tabu Search heuristic for the Vehicle Routing Problem with Soft Time Windows", Transportation Science, 31(2), pp.170~186 (1997)
- B. Bullnheimer, "Applying the Ant System to the Vehicle Routing Problem", MIC97, 1~12 (1997)
- L. M. Gambardella, "MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, New Ideas in Optimization", pp.63~76 (1999), McGraw-Hill
- M. Reimann, "D-ants:Saving Based Ants Divide and Conquer the Vehicle Routing Problems with Time Window", Computer and Operations Research, 31(4), pp.563~591 (2004)
- Q. Chengming, "Using Ant Colony System and Local Search Methods to Solve VRPTW", IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, pp.478~482 (2008)
- R. A. Russell, "An Effective heuristic for the M-tour traveling salesman problem with some side conditions", Operations Research, 25(3), pp.517~524 (1977)
- P. Prosser, "Study of greedy search with multiple improvement heuristics for vehicle routing problems", Working paper, university of Strathclyde, ~ (1996)
- M. Zargayouna, "Proceedings of the International Workshop on Engineering Societies in the Agents World", Proceedings of the International Workshop on Engineering Societies in the Agents World (2008), Springer Verlag
- O. Braysy, "Vehicle Routing Problem with Time Windows,Part I-Route Construction and Local Search Algorithms", Transportation Science, 39(1), pp.104~118 (2005)
- H. Nazif, "Optimized Crossover Genetic Algorithm for Vehicle Routing Problem with Time Windows", American Journal of Applied Sciences, 7(1), pp.95~101 (2010)
- N. A. El-Sherbeny, "Vehicle routing with time windows:An overview of exact,heuristic and metaheuristic methods", Journal of King Saud University - Science, 22(3), pp.123~131 (2010)
- 유영훈, "시간 제약을 가지는 차량 경로 스케줄링 문제 해결을 위한 기회시간 반영 하이브리드 휴리스틱", 지능정보연구, 15(3), pp.137~150 (2009), 한국지능정보시스템학회
- 홍명덕, "차량 경로 스케줄링 문제 해결을 위한 멀티 비용 함수를 갖는 개미 군집 최적화 기법 기반의 휴리스틱", 제 33회 한국정보처리학회 춘계학술발표대회 논문집, 17(1), pp.314~317 (2010)
- 이승관, "Ant Colony System에서 효율적 경로 탐색을 위한 지역갱신과 전역갱신에서의 추가 강화에 관한 연구", 정보처리학회논문지B, 10(3), pp.237~242 (2003), 한국정보처리학회