$\require{mediawiki-texvc}$

연합인증

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

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

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

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

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

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

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

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

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

국내택배시스템에 개미시스템 알고리즘의 적용가능성 검토
Application of Ant System Algorithm on Parcels Delivery Service in Korea 원문보기

大韓交通學會誌 = Journal of Korean Society of Transportation, v.23 no.4 = no.82, 2005년, pp.81 - 91  

조원경 (동부엔지니어링(주) 교통연구실) ,  이종호 (경기대학교 첨단산업공학부 도시.교통공학)

초록
AI-Helper 아이콘AI-Helper

외판원 문제(TSP; Traveling Salesman Problem)는 경로탐색 최적화문제로 '풀리지 않는 문제'(NP-complete; None-deterministic Polynomial-time complete)에 속하므로 경유지 수가 많아짐에 따라 급격히 계산시간이 증가한다. 때문에 적용시 정확한 최적해보다는 최적 근사해에 대한 발견적 (heuristic) 알고리즘들을 이용한다. 본 연구는 TSP에 적용되는 발견적 알고리즘으로 개미 시스템알고리즘(ASA; Ant System Algorithm)을 검토하고. 국내 택배시스템에 ASA의 적용가능성을 검토하였다. ASA는 NP-complete 문제를 위한 발견적 알고리즘으로, 1990년대 초 M. Dorigo 등에 의해 연구되어졌다. ASA는 개미들이 이동간에 페로몬이라는 일종의 화학물질을 분비할 때, 이동경로 상에 분비된 페로몬 누적에 따라 확률적 방법으로 경로를 결정하게 된다. 이러한 ASA는 NP-complete문제에서 계산시간이나 최단경로탐색에서 우수한 결과를 얻는 것으로 발표되고 있으며, 교통분야에서 차량경로탐색뿐만 아니라 네트워크 관리 및 도로선형계획 등 그 적용범위가 점차 확대되어지고 있다. 현재 국내 택배시스템에서 차량배차시 명확한 기준이 없으며 주로 담당 운전자의 경험과 판단에 의해 결정된다. 본 연구에서는 국내택배시스템에 ASA의 적용가능성을 검토하였다. 담당 운전자의 경로결정이 가로 10.0km, 세로 10.0km의 범위에서 인접이웃알고리즘(NNA: Nearest Neighbor Algorithm)을 따른다고 가정했을 때와 랜덤한 20개의 경유지를 가질 때, 그리고 경유지 수를 10개씩 증가하여 200개까지 증가할 때를 비교 분석한 결과, ASA이 NNA 보다 우수하였다. ASA을 국내택배시스템에 적용시 운송비용 절감 등의 운영개선을 기대할 수 있으며, 특히 영세한 택배업체에서 보다 저렴하고 우수한 택배시스템을 구축할 수 있을 것으로 보인다.

Abstract ▼ AI-Helper 아이콘AI-Helper

The Traveling Salesman Problem(TSP) is one of the NP-complete (None-deterministic Polynomial time complete) route optimization problems. Its calculation time increases very rapidly as the number of nodes does. Therefore, the near optimum solution has been searched by heuristic algorithms rather than...

주제어

#개미시스템알고리즘   #발견적 알고리즘   #차량경로탐색   #택배시스템  

참고문헌 (30)

  1. 건설교통부(2001), '국가물류기본계획(2001-2020)' 

  2. 장병만(1990), '공공차량 경로문제 최적해법', 서울산업대학논문집 제31집, pp.207-219 

  3. 류승헌, 김규호(1998), '진화계획법(EP)을 이용한 산업체 열병합발전시스템의 일간 최적운전계획', 영남대학교 연구논총 제4권, pp.61-71 

  4. 박준환(2001), 'Tabu Search를 이용한 지선버스 노선설계에 관한 연구', 서울대학교 환경대학원 

  5. 송성헌(1985), '배차문제의 발견적 해의 개선에 관한 연구', 홍대논총, Vol.17 No.2 

  6. 송성현, 강승우(1998), '분할배달을 고려한 발견적 배송경로 결정 방법', 과학기술연구논문집, Vol.9 No.2, pp.663-672 

  7. 신주쿠구 코우에이 시스템 주식회사(1999), '자동배차시스템의 실례소계', 로지스틱스 워크숍 세미나 '99 

  8. 양성민(2001), '메타휴리스틱을 이용한 다기능기계의 일정계획', 공학기술연구지, Vol.6, No.1 

  9. 윤대식(2001) , '교통수요분석', 박영사, pp.170-181 

  10. 윤민영(1999), '병렬 유전 담금질 알고리즘에 대한 연구', 정보산업기술논총 제4집 

  11. 이우승 외(2001), '서울시 택배제도 개선방안 연구', 서울시정개발연구원, pp13-50 

  12. 최진영 외(2001), 'Genetic Algorithm Toolbox', 서울대학교 

  13. 황홍석(1999), '차량경로문제를 위한 2-단계 발견적 방법', 동의대학교 산업기술연구지 제14권, pp.191-196 

  14. B.Bullnheimer, R.F.Hartl, C.Strauss(1999) , 'An improved ant system algorithm for the vehicle routing problem', Annals of Operations Research 89, pp.319-329 

    crossref

  15. B.Bullnheimer, R.F.Hartl, C.Strauss(1997), 'Applying the Ant System to the Vehicle Routing Problem', Sophia-Antipolis, France July, pp.21-24 

  16. Eric Bonabeau, Marco Dorigo, Guy Theraulaz (1999), 'Swarm Intelligence from Natural to Artificial Systems', Oxford University 

  17. J.C. Jong(1998), 'Optimizing Highway Alignments with Genetic Algorithms', University of Maryland, College Park, USA 

  18. John Sum, Hong Shen, Gilbert H. Young, Jie Wu(1999), 'Analysis on extended ant routing algorithms for network management', IEEE Transactions on Parallel and Distributed Systems 

  19. Karl Doerner, Richard F. Hartl. Marc Reimann(2001), 'A hybrid ACO algorithm for the Full Truckload Transportation Problem', Institut fur Information-sverarbeitung, Abt. Produktionsmanagement 

  20. Karl Doerner, Richard F. Hartl. Marc Reimann(2000), 'Ant Colony Optimization applied to the Pickup and Delivery Problem', Institut for Informationsverarbeitung, Abt. Produktionsmanagement 

  21. Karl Doerner, Richard F. Hartl. Marc Reimann(2000), 'Cooperative Ant Colonies for Optimizing Resource Allocation in Transportation', Institut fur Informationsverarbeitung, Abt. Produktionsmanagement 

  22. M. Dorigo, G. Di Caro, L.M. Gambardella(1999), 'Ant Algotithms for Discrete Optimization', Technical Report IRIDIA/98-10, Universite Libre de Bruxelles, Belgium & To appear in Artificial Life Vol. 5, No.3, pp.137-172 

    상세보기 crossref

  23. M. Dorigo, L.M. Gambardella(1997), 'Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem', IEEE Transactions on Evolutionary Computation, Vol.1 

    상세보기 crossref

  24. M.Dorigo, V.Maniezzo, A.Colorni(1991), 'Ant System: An Autocatalytic Optimizing Process', Technical Report No.91-016 

  25. M.Dorigo, V.Maniezzo, A.Colorni(1996), 'Ant System: Optimization by a Colony of Cooperating Agents', IEEE Transactions on Systems. Man. and Cybernetics-Part B: Cybernetics. Vol. 26 

    상세보기 crossref

  26. M.K Jha, Ph.D. Dissertation(2000), 'A Geographic Information Systems-Based Model for Highway Design Optimization', University of Maryland, College Park, USA 

  27. Manoj K. JHA(2001), 'Geographic Information Systems and Artificial Intelligence Integration in Transportation', SCI2001 & ISAS2001 

  28. Reimann, M. Shtovba, S. Nepomuceno(2001) , 'A hybrid ACO-GA approach to solve Vehicle Routing Problems', Student Papers of the Complex Systems Summer School. Budapest July 15 

  29. U.S. Department of Transportation(1981) 'The State of the Art in the Routing and Scheduling of Vehicles and Crews' 

  30. V. Maniezzo, A. Carbonaro, H. Hildmann(2001), 'An ANTS Heuristic for the Long Term Car Pooling Problem', Department of Computer Science University of Bologna & Amsterdam 

저자의 다른 논문 :

관련 콘텐츠

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

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

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

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

선택된 텍스트

맨위로