서지주요정보
Heuristic algorithms for a variant of orienteering problem = 용량제약이 있는 다경로 오리엔티어링 문제의 해법에 관한 연구
서명 / 저자 Heuristic algorithms for a variant of orienteering problem = 용량제약이 있는 다경로 오리엔티어링 문제의 해법에 관한 연구 / Keum-Ae Park.
저자명 Park, Keum-Ae ; 박금애
발행사항 [대전 : 한국과학기술원, 2007].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8018228

소장위치/청구기호

학술문화관(문화관) 보존서고

MIE 07009

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

This study deals with a variant of the orienteering problem faced by managers of some department stores during peak-sale periods. We want to find a set of paths to be traveled by each vehicle that leaves a department store and arrives at a specified destination after visiting customers. The problem is formulated into the mathematical model with the objective of maximizing the sum of the rewards collected by the vehicles within a given time limit and a given capacity constraint. Since the problem is known to be NP-hard, a heuristic algorithm and a priority-based Genetic Algorithm (pGA) are developed to find the solution. For small sized problems, the performances of the algorithms are compared with the optimum solutions obtained from CPLEX.

본 논문은 실제 백화점 배송문제에 대한 해법을 찾는 것으로, 추석이나 연말연시와 같이 고객의 배달요구가 최대가 되는 시점에도 배송부서의 인원을 늘리지 않고 제품을 제때 배송할 수 있게 도와주는 일종의 변형된 오리엔티어링 문제를 다루고 있다. 본 논문은 차량이 여러 대이고 각 차량의 도착지 및 운행시간이 다르며 차량마다 최대 적재용량이 주어져 있는 문제의 해법을 다루었다. 여러 대의 차량이 동시에 출발하여 각 차량의 목적지까지 가는 도중에 최대한 많은 reward를 모으는 것이 본 연구의 목적이다. 각 차량의 목적지와 운행시간이 다르며, 차량의 용량제약을 고려하고 있다는 점에서 기존의 연구들과 차별화 된다. 본 논문에서는 위 문제를 수학적 모델로 모형화 하였다. 이러한 문제는 NP-hard임이 알려져 있기 때문에, 문제의 특성을 이용한 휴리스틱 알고리즘과 메타 휴리스틱의 일종인 유전 알고리즘을 제안하였다. 본 논문에서 제안한 휴리스틱과 유전 알고리즘의 유효성을 검증하기 위해, 고객 수와 직원 수에 따른 새로운 데이터 세트를 만들고 문제의 크기가 작은 경우에 대해 CPLEX를 이용한 최적해와 비교하였다.

서지기타정보

서지기타정보
청구기호 {MIE 07009
형태사항 iii, 46 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 박금애
지도교수의 영문표기 : Hark Hwang
지도교수의 한글표기 : 황학
학위논문 학위논문(석사) - 한국과학기술원 : 산업공학과,
서지주기 Reference : p. 44-46
주제 orienteering
heuristic
genetic algorithm
오리엔티어링
휴리스틱
유전알고리즘
QR CODE qr code