Journal of the Society of Korea Industrial and Systems Engineering Vol 9 No 4 pp75 8 December 006 유전자 알고리즘을 이용한 시간제약 차량경로문제 * ** * ** 1 Vehicle Routing Problems with Time Window Constraints by Using Genetic Algorithm Geon-Wook Jeon* Yoon-Hee Lee** *Department of Operations Research Korea National Defense University Seoul 1-875 **LBC The 1st Air-Borne Special Forces Brigade ROKA The main objective of this study is to find out the shortest path of the vehicle routing problem with time window constraints by using both genetic algorithm and heuristic Hard time constraints were considered to the vehicle routing problem in this suggested algorithm Four different heuristic rules modification process for initial and infeasible solution -opt process and lag exchange process were applied to the genetic algorithm in order to both minimize the total distance and improve the loading rate at the same time This genetic algorithm is compared with the results of existing problems suggested by We found better solutions concerning vehicle loading rate and number of vehicles in R-type s examples R103 and R106 Keywords Genetic Algorithm Vehicle Routing Problem with Time Windows Meta Heuristic 1 서 론 (Vehicle Routing Problem VRP) ( ) ( ) VRP VRP Dantzig and Ramser(1959) NPhard (VRP with Time Windows) VRP (soft) (hard) ( ) NP-hard ( 1987) greedy (Blanton and Wainwright 1993) Cluster First Route Second (Thangiah 1995) (Potvin 1996)
(Berger et al 1998) (Bräysy and Gendreau 001) Or-opt(Or 1976) -interchanges(osman 1993) -opt(potvin and Rousseau 1995) -opt Two Evolutionary Meta-heuristics(Gehring and Homberger 001) -opt < 1> Initial population Random Heuristic (Tan et al 001) Fltting Evaluation Selection Crossover Mutation Fitting/-opt Evaluation 30 00 Satisfy condition yes no Heuristic End < 그림 1> 엄격한 시간제약 알고리즘 1 유전자 표현 유전자 알고리즘을 이용한 모형 구축 < > C S < 그림 > 유전자 표현 1 5 3 1 D( ) 10 5 D( )
초기 모집단 : 수요지 에서 로차량 이동시 5 선별 100% 80% 90% (Kang and Lee 001) 000) (Kim et al 6 교 차 3 실행 불가능해 교정 과정 et al 000) (Kim ) ( 1 3 5 4 1 3 1 3 4 5 4 4 1 4 적합도 평가 4 5 4 1 3 1 3 4 5 5 1 4 3 3 4 1 5 (1) (1) 1 1 3 1 1 3 1 1 1 1 3 3
7 변동 돌연변이 1 lag lag 1 3 4 5 6 7 8 9 10 lag = -1= 9 lag 05( ) lag 8 -opt 과정 1 3 4 5 6 7 8 9 10 10 3 4 5 6 7 8 9 1 1 10 lag 1 04 1 3 -opt < 3> 4 4 3 1 1 3 4 5 6 7 8 9 10 lag (1) lag case 1( ) : 1 3 4 5 6 7 8 9 10 case ( ) : 1 3 4 5 6 7 8 9 10 case 1( ) : 9 3 4 5 6 7 8 1 10 case ( ) : 1 10 3 4 5 6 7 8 9 6 3 5 6 3 5 case 1 04( ) case 07( ) D 5 6 4 3 1 8 5 3 4 6 1 8 1 1 1 1 1 1 1 1 1 1 Before -opt After -opt D 4 lag (1) 5 lag 1 Lag 9 < 그림 3> -opt 과정 최종해 확인과정 lag (Sule 1996) 1
10 유전 파라메터 (popsize) < 4> < > 540 530 50 510 -opt -opt 500 490 -opt Lag exchange 480 470 460 < 1> 450 1 51 101 151 < 그림 4> 근사해 수렴결과 < 표 1> 유전 파라메터 Parameters Value Ranges Number of population 00 10 500 Initial solution generation rate 03 01 08 Crossover(Pc) 085 05 10 Mutation(Pm) 00 0001 005 Max mutation rate 0 01 05 Number of generation 10000 500 0000 -opt 900 (47801) 6 (48153) 3 예제적용 및 결과분석 3 의 실험예제 적용 31 기존 예제 적용 (http://neolccumaes) < 표 > 결과 비교 R-type C-type RC-type < 3> Jung and M in (000) Suggested algorithm #of Pop Convergence (Gen) Terminate condition (Gen) Distance 0 900 10000 47801 50 6 00 48153 (Jung and Min 000) 1 6000 4 < 표 3> 문제 유형별 특징 Type Characteristics No R-type (3) C-type (17) RC-type (16) uniformly distributed customers clustered customers a mix of R and C types R101 R01 C101 C01 RC101 RC01 R11 R11 C109 C08 RC108 RC08 < 5>
R-type C-type RC-type < 그림 5> 문제의 유형별 수요지 분포 5 00 5 RC-Type 차량수 8 7 6 5 4 3 1 R101 R10 유전자 알고리즘 R103 R106 C106 Best solution C-Type R-type < 7> RC0 RC06 C06 RC10 RC106 C08 R-type C-type RC-type < 4> 0 의 문제 유형별 사용된 차량대수 비교 구분 < 표 4> 예제 실험결과 Best solution #of vehicle Distance #of vehicle suggested algorithm Distance Distance/ #ofvehicle R101 8 6171 8 673 +1013/same R10 7 5471 7 56636 +196/same R103 5 4546 3 57935 +1475/- R106 5 4654 4 59411 +1871/-1 C106 3 1913 5 5635 +6505/+ C06 147 4 830 +685/+ C08 145 3 9938 +8488/+1 RC10 3 3518 4 4350 +711/+1 RC106 3 3455 4 3795 +3375/+1 RC0 3 3380 5 41371 +7571/+ RC06 3 340 4 3883 +643/+1 거리 600 R101 R10 < 6> R106 < 5> < 그림 7> 유형별 차량대수 비교 < 4> < 7> R103 R-type < 표 5> 수요지 및 차량정보 Example 1 Example # of demand point 50 100 Capacity/ # of vehicle 100 / 3 00 / 3 300 / 3 400 / 3 150 / 6 00 / 6 50 / 6 300 / 6 500 400 R103 R106 유전자 알고리즘 RC10 RC106 RC0 RC06 < 6> 300 Best solution C106 C06 C08 < 표 6> 확대 실험결과( 차량대수 및 총거리) 00 100 0 R-type C-type RC-type 의 문제 유형별 차량 운행거리 비교 < 그림 6> 유형별 운행거리 비교 Capacity/ # of vehicle (used) Example1 100 / 3 00 / 3 300 / 3 400 / 3 Example 150 / 6 00 / 6 50 / 6 300 / Distance 190808 418149
33 결과분석 < 표 8> 다용량 차량경로문제 차량별 적재량 -opt RC-Type (Jung and Min 000) local search lag R-type C-type RC-type C-Type R-type R-type R103 R106 1 < 7> R103 R106 < 표 7> 차량대수 및 평균 적재율 비교 Example 1 (load/capacity) Example (load/capacity) Veh 1 88 / 100 74 / 150 Veh 67 / 100 105 / 150 Veh 3 87 / 100 111 / 150 Veh 4 154 / 00 117 / 150 Veh 5 145 / 00 133 / 150 Veh 6 167 / 00 135 / 150 Veh 7 178 / 300 138 / 00 Veh 8 16 / 300 150 / 00 Veh 9 74 / 300 160 / 00 Veh10 331 / 400 163 / 00 Veh11 334 / 400 183 / 00 Veh1 309 / 400 193 / 00 Veh13-00 / 50 Veh14-08 / 50 Veh15-13 / 50 Veh16-1 / 50 Veh17-5 / 50 Veh18-8 / 50 Veh19-3 / 300 Veh0-63 / 300 Type Best solution #of veh Avg loading rate #of veh Suggested algorithm Avg loading rate Percent Increased R103 5 33 3 553 1% R-type R106 5 33 4 415 83% clustering set-covering < 8> 7968% 참고문헌 4 결론및향후연구방향 [1] Berger J Salois M and Begin R; A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows Lecture Notes in Artificial Intelligence AI 98 Advances in Artificial Intelligence : 114-17 1998 [] Blanton J L and Wainwright R L; Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms Proc 5th Int Con on Genetic
Algorithms : 45-459 1993 [3] Bräysy O and Gendreau M Metaheuristics for the Vehicle Routing Problem with Time Windows SINTEF REPORT SINTEF Applied Mathematics Research Council of Norway 001 [4] Danzig G B and Ramser J H; The Truck Dispatching Problem Management Science 6 : 80-91 1959 [5] Gehring H and Homberger J; Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows Asia-Pacific Journal of Operational Research : 57-64 001 [6] Jung Y M and Min K R; A Vehicle Routing Problem using Heuristic Journal of Military Operations Research Society of Korea 6(1) : 47-55 000 [7] Kang K H and Lee Y H; Heuristic for Vehicle Routing Problem to Minimize total delivery waiting time Con on KIIE and KORMS : 687-690 001 [8] Kim Y K Yoon B S and Lee S B; Meta Heuristic Yeongji Moonhwasa Seoul Korea 000 [9] Or I; Traveling Salesman-Type Combinational Problems and their Relation to the Logistics if Regional Blood Banking PhD Dissertation Northwestern University 1976 [10] Osman I H; Metastrategy Simulated Annealing and Tabu Search Algorithm for the Vehicle Routing Problem Annals of Operation Research 41 : 41-451 1993 [11] Potvin J Y and Rousseau J M; An Exchange Heuristic for Routing Problems with Time Windows Journal of the Operational Research Society 46 : 1433-1446 1995 [1] Potvin J Y; The Vehicle Routing Problem with Time Window Part Genetic Search Informs Journal of Computing 8 : 165-17 1996 [13] M M; Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints Operations Research 35 : 54-65 1987 [14] Sule D R Industrial Scheduling Louisiana Tech University 1996 [15] Tan K C Lee L H and Ou K; Hybrid Genetic Algorithms in Solving Vehicle Routing Problems with Time Window Constraints Asia-Pacific Journal of Operational Research 18 : 11-130 001 [16] Thangiah S; Vehicle Routing with Time Windows Using Genetic Algorithms In Application Handbook of Genetic Algorithms New Frontiers : 53-77 1995 [17] http://neolccumaes/radi-aeb/webvrp/