$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

하이브리드 유전자알고리즘을 이용한 엄격한 시간제약 차량경로문제
A Vehicle Routing Problem Which Considers Hard Time Window By Using Hybrid Genetic Algorithm 원문보기

한국국방경영분석학회지 = Journal of the Military Operations Research Society of Korea, v.33 no.2, 2007년, pp.31 - 47  

백정구 (국군수송사령부 항만운영단) ,  전건욱 (국방대학교 국방관리대학원 운영분석)

초록
AI-Helper 아이콘AI-Helper

본 연구는 엄격한 시간제약 차량경로문제에 대하여 유전자알고리즘과 휴리스틱 기법을 이용하여 최적해를 산출하는 것이다. 문제해결을 위해 수리적 모형을 구성하고, ILOG-CPLEX를 이용하여 최적해를 산출하였다. 임의 생성방법과 세이빙 휴리스틱을 적용한 초기해 생성, 실행불가능해의 교정과 유전자 알고리즘 종료 후 2-opt, Or-opt 등 해교정 및 해개선을 위한 과정이 추가된 하이브리드 유전자 알고리즘을 구축하여 엄격한 시간제약이 있는 차량경로 문제에 적용하여 솔로몬 예제와 비교하고, 제안한 알고리즘의 해공간탐색능력, 수렴성, 휴리스틱 기법의 효과를 확인하였다.

Abstract ▼ AI-Helper 아이콘AI-Helper

The main purpose of this study is to find out the best solution of the vehicle routing problem with hard time window by using both genetic algorithm and heuristic. A mathematical programming model was also suggested in the study. The suggested mathematical programming model gives an optimal solution...

주제어

#하이브리드 유전자 알고리즘   #차량경로문제   #세이빙 휴리스틱  

참고문헌 (25)

  1. 김경훈, 이영훈, '고객의 배달량을 고려한 차량경로 문제의 발견적 기법', 한국과학회/대한산업공학회 춘계 공동 학술대회, 2001 

  2. 김여근, 윤복식, 이상복, 메타휴리스틱, 영지문화사, 2000 

  3. 이정만, '수요지 제한이 있는 복수차량 유형의 차량경로모형에 관한 연구', 국방대학교 석사학위 연구, 2004 

  4. 박민우, '귀로수송 소요를 고려한 차량 경로 문제에 관한 연구',국방대학교 석사학위 연구, 2004 

  5. 허재성, '유전자 알고리즘을 이용한 다용량 차량 경로문제에 대한 연구', 국방대학교 석사학위 연구, 2003 

  6. Berger, J, Salois, M., and Begin, R., 'A H ybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows,' Lecture Notes in Artificial Intelligence, AI'98, Advances in Artificial Intelligence, 114-127, (1998) 

  7. Blanton, J. L . and Wainwright, R. L., 'Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms,' Proc. 5th Int Con on Genetic Algorithms, 452-459, (1993) 

  8. Christofides, N. and Eilon, S., 'An Algorithm for the Vehicle Dispatching Problem', Operational Reasearch Quarterly, Vol.20(3), 309-318, (1969) 

    상세보기 crossref

  9. Chiang, W. C. and Russell, R. A, 'Simulat ed Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows,' Annals of Operations Research, Vol.63, 3-27, (1996) 

    상세보기 crossref

  10. Fisher, M. L. and Jaikumar, R., 'A Generalized Assignment Heuristic for Vehicle Routing,' Networks, Vol.11, 109-124, (1981) 

    상세보기 crossref

  11. Garcia, B. L., Potvin, J. Y., and Rousseau, J. M., 'A Parallel Implementation of the Ta bu Search Heuristic for Vehicle Routing Problems with Time Window Constraints,' Computers and Operations Research, Vol.21, 1025-1033, (1994) 

    상세보기 crossref

  12. Gehring, H. and Homberger, J, 'Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows,' Asia Pacific Journal of Operational Research, 57 -64, (2001) 

  13. Jeon, Geonwook and Lee, Yoon Hee, 'Vehicle routing problem with time window constraints by using genetic algorithm,' Journal of the Society of Korea Industrial and System Engineering, Vol. 29(4), 75-82, (2000) 

  14. Laporte, G., Hertz, A, and Gendreau, M., 'A Tabu Search Heuristic for the Vehicle R outing Problem,' Management Science, Vol. 40(10), 1276-1290, (1994) 

    상세보기 crossref

  15. Lenstra, J. K. and Rinnooy, K., 'Complexity of vehicle routing and scheduling problems,' Networks, Vol.11, 221-227, (1981) 

    상세보기 crossref

  16. Or, I., 'Traveling Salesman-Type Combinational Problems and their Relation to the Logistics if Regional Blood Banking,' PhD. Dissertation, Northwestern University, (1976) 

  17. Osman, I. H., 'Metastrategy Simulated An nealing and Tabu Search Algorithm for the Vehicle Routing Problem,' Annals of Operai ion Research, Vol.41 , 421-451, (1993) 

    상세보기 crossref

  18. Potvin, J. Y, 'The Vehicle Routing Problem with Time Window Part I Tabu Search,' Informs Journal of Computing, 158-164, (1996) 

  19. Potvin, J. Y, 'The Vehicle Routing Problem with Time Window Part II Genetic Search,' Informs Journal of Computing, 165-172, (1996) 

  20. Potvin, J. Y and Rousseau, J. M., 'An Exchange Heuristic for Routing Problems with Time Windows,' Journal of the Operation al Research Society, 46, 1433-1446, (1995) 

    상세보기 crossref

  21. Rochat, Y.and Thangiah, E., 'Probabilistic diversification and Intensification in Local Search for Vehicle Routing,' Journal of Heuristics, Vol. 1, 147-167, (1995) 

    상세보기 crossref

  22. Schulze, J. and Fahle, T., 'A Parallel Algorithm for the Vehicle Routing Problem with Time Window Constraints,' Annals of Operations Research, Vol.86, 585-607, (1999) 

    crossref

  23. Shin, H. W. and Kang, M. K., 'An Accelerated Genetic Algorithm for the Vehicle Routing Problem,' Journal of the Korean OR/ MS Society, Vol.21(1), 101-114, (1996) 

    원문보기 상세보기

  24. Solomon, M. M, 'Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,' Operations Research, Vol.35, 254-265, (1987) 

    상세보기 crossref

  25. Thangiah, S., 'Vehicle Routing with Time Windows Using Genetic Algorithms,' In Ap plication Handbook of Genetic Algorithms : New Frontiers 2, 253-277, (1995) 

저자의 다른 논문 :

관련 콘텐츠

이 논문과 함께 이용한 콘텐츠

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로