Function List>Search : The Library of Korea National Defense University

개미 군집 시스템을 이용한 시간제약이 있는 차량경로문제의 연구 = Ant Colony System for Vehicle Routing Problem with Time Window

QR Code

Preview Book Information

Book Detail
Data Type :	(군대학) 학위논문
Class No. :	393.8
Personal Author :	이승원
Title/Author :	개미 군집 시스템을 이용한 시간제약이 있는 차량경로문제의 연구= Ant Colony System for Vehicle Routing Problem with Time Window/ 이승원.
Imprint :	서울: 국방대학교, 2007.
Format :	48p.; 26cm.
General Notes :	이상헌
학위논문주기 :	석사, -- 국방대학교 대학원,: 운영분석, 2007
Language	Korean

Holdings Information

National Defense University Library

예Reservation
인Print
SSMS
서Missing
보Repository
우우선정리예약
무무인예약대출

예약

1. 예약현황은 홈페이지 로그인 후 예약 페이지에 확인 가능합니다.
2. 도착 통보된 예약자료 대출을 원하지 않는 경우에는 예약 현황에서 취소할 수 있습니다.
3. 기타 문의사항은 도서관에 문의 바랍니다.

무인예약대출

1. 무인예약대출 현황은 홈페이지 로그인 후 무인예약대출 페이지에 확인 가능합니다.
2. 무인예약대출자료 대출을 원하지 않는 경우에는 무인예약대출 페이지에서 신청 또는 접수상태인 경우만 취소할 수 있습니다.
3. 희망대출일은 신청일로부터 최대 1주일 까지 가능합니다.
4. 희망대출일을 선택하지 않은 경우 대출대기 통보 후 1주일까지 기기에서 대출가능합니다.
5. 기타 문의사항은 도서관에 문의 바랍니다.

차량경로문제 (Vehicle Routing Problem : VRP)는 하나의 거점(depot)에서 출발한 차량이 배달(delivery)이나 수집(pick-up) 등의 서비스를 요구하는 고객(customer)을 특정한 순서대로 방문하고 다시 거점으로 돌아오는 최소 비용의 경로를 결정하는 문제이다. VRP는 우리 주위에서 자주 발생하는 문제로서 항공, 기차, 선박, 트럭등을 이용한 수송분야의 현실적인 문제에 광범위하게 적용되고 있다.
VRP에 관한 연구는 오래 전부터 활발히 이루어지고 있으며 현실 문제에 적용할 때 여러 종류의 제약조건이 존재한다. 따라서 다양한 형태의 VRP가 존재하며 이들의 분류 기준도 거점의 수, 서비스의 종류(배달 또는 수집), 차량 유형의 동일성 유무(homogeneous 또는 heterogeneous), 서비스 시간 제약(time window)의 유무 등 매우 다양하다. 이 중 현실에서 많이 발생하는 서비스 가능시간이 한정되어 있는 경우를 시간제약이 있는 차량경로문제(Vehicle Routing Problem with Time Window : VRPTW)라고 하며 이 문제는 NP-hard[26]문제로 입증되었고 큰 해공간을 갖는 문제에 대해 최적해를 찾을 수 없었다.
본 연구는 NP-hard를 풀기 위한 알고리즘으로 개미 군집 시스템(Ant Colony System : ACS)을 적용하였으며 개미들이 이동간에 페로몬(pheromone)이라는 일종의 화학물질을 분비할 때, 이동경로 상에 분비된 페로몬 흔적(pheromone trail)에 따라 확률적 방법으로 경로를 설정하게 된다. 이러한 개미 군집 시스템은 TSP와 같은 NP-hard문제에서 계산시간이나 최적경로탐색에서 이미 우수한 결과를 도출하였다.
본 연구에서는 VRPTW에 대하여 개미 군집 시스템을 적용하여 고객이 요구하는 서비스 시간대에 수요량을 만족하면서 총 차량운행거리의 최소화를 목적으로 한다. 수리모형을 통해 문제의 목적함수와 제약식을 정리하고 제안한 알고리즘의 예제적용 후 기존연구에서 얻은 결과와 비교하여 알고리즘의 효율성을 입증하였다.

More View