| 1 |
1
최대 용량 및 최대 운행시간이 설정되어 있는 k 대(k는 자연수)의 차량 각각이 출발지에서 출발하여 N(N은 자연수)개의 노드를 한번만 경유한 후 다시 출발지로 돌아오도록 임의의 경로를 설정하는 제 1 단계;상기 설정된 경로들 중 상기 최대 용량이 위반되는 적어도 하나의 제 1 경로 및 상기 최대 운행시간이 위반되는 적어도 하나의 제 2 경로의 존재 여부를 판단하는 제 2 단계;상기 제 1 경로가 존재하는 경우 라그랑지안 완화법(Lagrangian Relaxation)을 이용한 목적함수의 항들 중 차량의 용량에 관련된 항의 제 1 라그랑지안 승수를 a배(a는 1 보다 큰 실수)로 증가시키는 제 3 단계;상기 제 2 경로가 존재하는 경우 상기 라그랑지안 완화법을 이용한 목적함수의 항들 중 차량의 운행시간에 관련된 항의 제 2 라그랑지안 승수를 b배(b는 1 보다 큰 실수)로 증가시키는 제 4 단계;k-opt 알고리즘을 이용하여 상기 경로를 수정하는 제 5 단계; 및상기 제 5 단계를 수행하여 수정된 경로들 중 상기 제 1 경로 및 상기 제 2 경로가 존재하지 않을 때까지 상기 제 3 단계 내지 제 5 단계를 반복하여 수행하는 단계를 포함하고,상기 라그랑지안 완화법을 이용한 목적함수()는,(는 연료의 화학에너지가 차량의 운동에너지로 변환되는 계수, 는 온실가스 배출계수, 는 에너지계수, 는 구름저항과 공기저항과 경사도에 의한 저항과 관성 저항을 극복하는 힘, 는 노드 i에서 출발한 시간, 는 노드 j에 도착한 시간, 는 노드 i에서 노드 j까지의 거리, 는 노드 i에서 노드 j까지의 차량의 속력, 는 차량의 최대 용량, 는 차량의 최대 운행시간, 은 노드 i에서 노드 j사이의 경로가 차량 p, q, k의 경로에 포함되는 경우, 은 노드 i에서 노드 j사이의 경로가 차량 p, q, k의 경로에 포함되지 않는 경우, 는 상기 제 1 라그랑지안 승수, 는 상기 제 2 라그랑지안 승수)인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 2 |
2
제1항에 있어서, 상기 제 4 단계는,상기 제 2 경로가 존재하는 경우 상기 제 2 경로를 운행하는 차량의 속도를 h(h는 양의 실수)만큼 증가시키는 단계; 및상기 차량의 속도를 증가시켜도 상기 제 2 경로가 존재하는 경우에만 상기 제 2 라그랑지안 승수를 b배로 증가시키는 단계를 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 3 |
3
제1항에 있어서, 상기 온실가스 배출량을 최소화하는 차량 경로 설정 방법은,상기 제 2 단계에서 상기 제 1 경로 또는 상기 제 2 경로가 존재하는 경우, 상기 k-opt 알고리즘을 이용하여 상기 경로를 수정하는 제 6 단계; 및상기 제 6 단계를 통해 수정된 경로들 중 상기 제 1 경로 및 상기 제 2 경로의 존재여부를 판단하는 제 7 단계를 더 포함하고,상기 제 3 단계는,상기 제 7 단계에서 수정된 경로들 중 상기 제 1 경로가 존재하는 경우 상기 제 1 라그랑지안 승수를 a배(a는 1 보다 큰 실수)로 증가시키는 단계를 포함하고,상기 제 4 단계는,상기 제 7 단계에서 수정된 경로들 중 상기 제 2 경로가 존재하는 경우 상기 제 2 라그랑지안 승수를 b배(b는 1 보다 큰 실수)로 증가시키는 단계를 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 4 |
4
제3항에 있어서, 상기 제 4 단계는,상기 제 7 단계에서 수정된 경로들 중 상기 제 2 경로가 존재하는 경우 상기 제 2 경로를 운행하는 차량의 속도를 h(h는 양의 실수)만큼 증가시키는 단계; 및상기 차량의 속도를 증가시켜도 상기 제 2 경로가 존재하는 경우에만 상기 제 2 라그랑지안 승수를 b배로 증가시키는 단계를 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 5 |
5
삭제
|
| 6 |
6
삭제
|
| 7 |
7
제1항에 있어서, 상기 라그랑지안 완화법을 이용한 목적함수와 관련된 제약식들은,(는 운행 가능한 최대 차량 수, 은 노드 i에서 노드 j사이의 경로가 차량 k의 경로에 포함되는 경우, 은 노드 i에서 노드 j사이의 경로가 차량 k의 경로에 포함되지 않는 경우, 및 는 보조 더미 변수, 는 노드 i의 요청사항, 는 노드 i에서 노드 j까지의 거리, 는 노드 i에서 노드 j까지의 차량의 속력, 는 차량의 최대 운행시간)인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 8 |
8
제1항에 있어서, 상기 제 1 라그랑지안 승수()는,(, , 는 노드 i에서 노드 j까지의 거리, 는 차량의 최대 용량, 는 노드 i의 요청사항, 은 노드 i에서 노드 j사이의 경로가 차량 p의 경로에 포함되는 경우, 은 노드 i에서 노드 j사이의 경로가 차량 p의 경로에 포함되지 않는 경우)이고,상기 제 2 라그랑지안 승수()는,(, , 는 노드 i에서 노드 j까지의 거리, 는 노드 i에서 노드 j까지의 차량의 속력, 은 노드 i에서 노드 j사이의 경로가 차량 q의 경로에 포함되는 경우, 은 노드 i에서 노드 j사이의 경로가 차량 q의 경로에 포함되는 경우)인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 9 |
9
제1항에 있어서, 상기 제 1 단계는,스윕(sweep) 알고리즘을 이용하여 상기 임의의 경로를 설정하는 단계를 더 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 10 |
10
제1항에 있어서,상기 k-opt 알고리즘은 계층형 2-opt 알고리즘인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 11 |
11
제1항에 있어서, 상기 온실가스 배출량을 최소화하는 차량 경로 설정 방법은,상기 차량의 대수를 1대부터 1대씩 더해가거나 경로를 설정할 수 있는 최소한의 차량 대수부터 1대씩 더해가면서 운행 가능한 최대 차량 수인 K 대까지 상기 단계들을 수행하는 단계; 및상기 단계들을 수행한 결과 중 온실가스 배출량이 최저인 경우의 차량 대수와 경로를 선택하는 단계를 더 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
| 12 |
12
제11항에 있어서, 경로를 설정할 수 있는 최소한의 차량 대수()은,(는 각 그룹의 고객, )인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법
|
