국내택배시스템에 개미시스템 알고리즘의 적용가능성 검토

서지정보

· 발행기관 : 대한교통학회
· 수록지 정보 : 대한교통학회지 / 23권 / 4호
· 저자명 : 조원경, 이종호

목차

Ⅰ. 서론
Ⅱ. 개미시스템알고리즘(ASA)
Ⅲ. 타 발견적 알고리즘과의 비교
Ⅳ. 국내 택배시스템에 ASA의 적용가능성 검토
Ⅴ. 결론 및 향후 연구과제

초록

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

영어초록

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 the real optimum has. This paper
reviews the Ant System Algorithm(ANS), an heuristic algorithm of TSP and its applicability in the parcel delivery
service in Korea.
ASA, which is an heuristic algorithm of NP-complete has been studied by M. Dorigo in the early 1990. ASA finds
the optimum route by the probabilistic method based on the cumulated pheromone on the links by ants. ASA has
been known as one of the efficient heuristic algorithms in terms of its calculation time and result. Its applications
have been expanded to vehicle routing problems, network management and highway alignment planning.
The precise criteria for vehicle routing has not been set up in the parcel delivery service of Korea. Vehicle routing
has been determined by the vehicle deriver himself or herself. In this paper the applicability of ASA to the parcel
delivery service has been reviewed. When the driver's vehicle routing is assumed to follow the Nearest Neighbor
Algorithm (NNA) with 20 nodes(pick-up and drop-off places) in 10 Km×10 Km service area, his or her decision was
compared with ASA's one. Also, ASA showed better results than NNA as the number of nodes increases from 10 to
200. If ASA is applied, the transport cost savings could be expected in the parcel delivery service in Korea.

참고자료

· 없음