 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
 |
 |
 |
||
1장 VRPPD란?
2장 학문적 역사
3장 연구 필요성
4장 수리모형
5장 적용사례
6장 항공산업에서의 활용 가능성
vrppd 한국항공대학교 생산시스템관리
목차
vrppd란?
학문적 역사 연구 필요성 수리모형 적용사례 항공산업에서의 활용 가능성
마치며.
vrppd란?
vrppd란?
배달과 수거를 고려한 차량경로문제
(vehicle routing problem pick-up and delivery )
중앙차고지에서 출발한 차량이 고객의 물품을 배달, 수거하거나 또는 배달 후 고객의 물품을 수거하여 중앙차고지로 복귀하는 문제
크게 3가지 형태로 나눌 수 있음 구분 내용 비고 vrpb 배달지점과 수거지점이 분리 배달이 모두 완료된 후에 수거를 실시 delivery-first, pickup-second vrpmdp 배달지점과 수거지점이 분리 배달이 모두 완료되기 전에 수거 가능함 mixed delivery and pickup vrpsdp 배달지점과 수거지점이 동일 배달과 수거를 동시에 실시 가능함 simultaneous delivery and pickup 차량경로문제의 경험적 기법 구 분 내 용 constructive methods
모든 고객의 수요가 만족될 때까지 순차적으로 고객을 차량에 할당하여 경로를 생성하는 기법
-clarke & wright의 saving method
-altinkemer & gavish의 matching based algorithm
-thompson& psarafti의s multi-route improvement algorithm
2-phase methods
차량에 대해 고객을 할당한 후 각각을 외판원 문제 해법을 이용하여 경로를 구하는 기법
-fisher m.l.[26], fisher & jaikumar algorithm
-ryan, hjorring & glover : the petal algorithm
-gillett & miller : sweep algorithm
route-first cluster-second method : brays incomplete optimization methods 가능해를 근사 최적해로 선택하는 기법 christofides의 경험해법을 이용한 분지 한계법 route improvement methods
초기 가능해를 구한 후 가능해의 부분을 교환하여 해를 향상시키는 기법
stewart의 라그랑지안 완화법(lagrangian relaxation)
meta heuristic methods
특정 문제의 정보에 구속되지 않고 다양한 문제에 적용 가능한 상위 수준의 경험적 기법
-ant algorithm-simulated annealing
-tabu search-genetic algorithm
-harmony search (이하 생략)
