11 0

다종 차량경로문제를 위한 유전자알고리듬

Title
다종 차량경로문제를 위한 유전자알고리듬
Other Titles
A Genetic Algorithm for the Heterogeneous Vehicle Routing Problems
Author
유영선
Alternative Author(s)
Yu, Young-Sun
Advisor(s)
최경현 교수님
Issue Date
2007-02
Publisher
한양대학교
Degree
Master
Abstract
본 논문에서는 Vehicle Routing Problem(VRP)에서 경로뿐만 아니라 그 경로를 서비스하는 차량의 타입도 함께 결정해야하는 Heterogeneous Vehicle Routing Problem(HVRP)를 다룬다. HVRP는 차량 타입별 고정비와 변동비가 다르고 용량이 다른 것이 특징이다. 이러한 환경에서 차량경로와 함께 차량타입을 결정하는 문제를 풀기 위하여 본 논문에서는 Sweep algorithm과 Clark&Wright algorithm을 이용하여 초기 모집단을 생성한 후 이를 향상시키기 위하여 유전자 알고리듬을 기반으로 하는 여러 가지 발견적 방법을 제시하고 이에 대한 결과를 비교하였다. 제안할 알고리듬은 교배과정에서 BCRC를 개선한 MBCRC의 두 가지 방법과 자가향상기법(SIM)등을 포함하고 있으며, 돌연변이 과정에서는 새로운 노드 교환방법을 제시하였고 선별과정의 전략을 구현하였다. 벤치마크 테스트 문제의 적용결과 기존의 연구 결과에 못지않은 좋은 결과를 얻었으며, 평균적으로는 그들을 능가하는 문제도 있었음을 확인하였다.
In this thesis, we consider the heterogeneous vehicle routing problems(HVRP), a variant of the classical vehicle routing problems(VRP), The HVRP differs from the classical VRP in that it deals with a heterogeneous fleets of vehicles having various capacities as well as, fixed, and variables costs, Therefor the HVRP is to find the fleet composition and a set of routes with minimum total cost. we propose a specially designed genetic algorithm for HVRP. This method is composed of the initial solution generation, Crossover, Mutation and finally Selection strategies. We propose use two kinds method for the crossover stage. and also a new node exchange method and implementation the strategy for the selection. According to the test results using the benchmark test data, we can conclude that the proposed algorithm performs well comparing to the other well known methods.
URI
http://dcollection.hanyang.ac.kr/jsp/common/DcLoOrgPer.jsp?sItemId=000000048608https://repository.hanyang.ac.kr/handle/20.500.11754/150101
Appears in Collections:
GRADUATE SCHOOL[S](대학원) > INDUSTRIAL ENGINEERING(산업공학과) > Theses (Master)
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE