논문KCI 등재
시간 제약을 갖는 차량 라우팅 문제에서 염색체 해석에 기초한 유전자 알고리듬과 부분 최적화 알고리듬
An Interpretation-based Genetic Algorithm and a Post Local Search Method for Vehicle Routing Problems with Time Windows
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
주제분류산업공학
초록
본 논문은 시간 제약을 갖는 차량 라우팅 문제를 해결하기 위해 유전자 알고리듬과 부분 최적화 알고리듬을 적용한 방법을 소개한다. 유전자 알고리듬에서의 염색체는 노드를 나타내는 정수의 순열로 표현되어 직접적인 해를 나타내지 않지만, 경험적 방법에 의한 해석을 통해 유효한 해로 변형되도록 하였다. 유전자 알고리듬에 의해 생성된 주어진 수의 우수한 해들에는 세 부분 최적화 방법이 순차적으로 적용되어 보다 좋은 해를 생성하도록 하였다. 부분 최적화 방법들에 의한 해는 다시 유전자 알고리듬의 해로 바뀌지 않도록 하여 두 알고리듬은 느슨하게 연결되도록 하였다. 솔로몬의 데이터를 이용한 실험에서 본 연구에서의 방법이 모든 문제에 대해 우수한 해를 생성함을 나타내었다. 특히, 지금까지 알려진 가장 우수한 경험적 방법에 비교될 만한 결과를 가져옴을 보였다.
참고문헌 (18)
- Baker, B. M., "A genetic algorithm for the vehicle routing problem", Computers and Operations Research, 30, pp.787~800 (2003)
- Berger, J., "parallel hybrid genetic algorithm for the vehicle routing problem with time window", Computers and Operations Research, 31, pp.2037~2053 (2004)
- Berger, J., "new hybrid genetic algorithm for the capacitated vehicle routing problem", Journal of Operations Research Society, 54, pp.1254~1262 (2004)
- Blanton, J. L., "Multiple vehicle routing with time and capacity constraints using genetic algorithms", Proceedings of the fifth International Conference on Genetic Algorithms, pp.452~459 (1993)
- Clark, G., "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research, 12, pp.568~581 (1964)
- Davis, L., "Applying Adaptive Algorithms to epistatic domains", Proceedings of the International Joint Conference on Artificial Intelligence, pp.162~164 (1985)
- Goldberg, D. E, "Loci, and the TSP", Proceedings of the First International Conference on Genetic Algorithms, pp.154~159 (1985)
- Jones, D. R, "Solving partitioning problems with genetic algorithms", Proceedings of the Fourth International Conference on Genetic Algorithms, pp.442~449 (1991)
- Kallehauge, Brian, "Formulations and exact algorithms for the vehicle routing problem with time windows", Computers and Operations Research, 35(7), pp.2307~2330 (2008)
- Liu, F. H., "A route-neighborhood- based metaheuristic for vehicle routing problem with time windows", European Journal of Operations Research, 118, pp.485~504 (1999)
- Oliver, I. M., "A study of permutation crossover operators on the Traveling Salesman Problem", Proceedings of the First International Conference on Genetic Algorithms, pp.224~230 (1985)
- Osman, I. H., "Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem", Operations Research, 41, pp.421~451 (1993)
- Osman, I. H., "Capacitated clustering problem by hybrid simulated annealing and tabu search", International Transaction in Operations Research, 1(3), pp.317~336 (1994)
- Prins, C. A., "simple and effective evolutionary algorithm for the vehicle routing problem", Computers and Operations Research, 31, pp.1985~2002 (2004)
- Rochat, Y., "Probabilistic diversification and intensification in local search for vehicle routing", Journal of Heuristics, 1, pp.147~167 (1995)
- Solomon, M. M., "Algorithm for the vehicle routing and scheduling problems with time window constraints", Operations Research, 35, pp.254~265 (1987)
- Tan, K. C., "Artificial intelligence heuristics in solving vehicle routing problems with time window constraints", Engineering Applications of Artificial Intelligence, 14, pp.825~837 (2001)
- Tangiah, S. R., "Vehicle routing with time deadlines using genetic and local algorithms", Proceedings of the Fifth International Conference on Genetic Algorithms, pp.506~513 (1993)
관련 논문AI추천
유전자 알고리즘을 이용한 시간제약 차량경로문제이윤희, 전건욱한국산업경영시스템학회 · 한국산업경영시스템학회지2006 · 제29권 제4호시간종속 재고경로 문제를 위한 적응적 유전 알고리즘이영해, 이태연, 조동원한국교통연구원 · 교통연구2012 · 제19권 제1호시간제약이 있는 차량경로문제에 대한 Hybrid 탐색이성우, 이승우, 이홍희, 이화기한국산업경영시스템학회 · 한국산업경영시스템학회지2006 · 제29권 제3호차량 경로 스케줄링 문제 해결을 위한 개미 군집 최적화 휴리스틱유영훈, 조근식, 홍명덕한국정보처리학회 · 정보처리학회 논문지2010 · 제17권 제5호납품시간창을 고려한 동적 로트크기 결정문제를 위한 유전알고리즘김병수, 이운식한국생산관리학회 · 한국생산관리학회지2010 · 제21권 제4호생산 배송 통합모형의 유전알고리듬 - 해법강성민, 이동준한국로지스틱스학회 · 로지스틱스연구2010 · 제18권 제2호