최대 용량 및 최대 운행시간이 설정되어 있는 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 라그랑지안 승수)인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제1항에 있어서, 상기 제 4 단계는,상기 제 2 경로가 존재하는 경우 상기 제 2 경로를 운행하는 차량의 속도를 h(h는 양의 실수)만큼 증가시키는 단계; 및상기 차량의 속도를 증가시켜도 상기 제 2 경로가 존재하는 경우에만 상기 제 2 라그랑지안 승수를 b배로 증가시키는 단계를 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제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 보다 큰 실수)로 증가시키는 단계를 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제3항에 있어서, 상기 제 4 단계는,상기 제 7 단계에서 수정된 경로들 중 상기 제 2 경로가 존재하는 경우 상기 제 2 경로를 운행하는 차량의 속도를 h(h는 양의 실수)만큼 증가시키는 단계; 및상기 차량의 속도를 증가시켜도 상기 제 2 경로가 존재하는 경우에만 상기 제 2 라그랑지안 승수를 b배로 증가시키는 단계를 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

삭제

삭제

제1항에 있어서, 상기 라그랑지안 완화법을 이용한 목적함수와 관련된 제약식들은,(는 운행 가능한 최대 차량 수, 은 노드 i에서 노드 j사이의 경로가 차량 k의 경로에 포함되는 경우, 은 노드 i에서 노드 j사이의 경로가 차량 k의 경로에 포함되지 않는 경우, 및 는 보조 더미 변수, 는 노드 i의 요청사항, 는 노드 i에서 노드 j까지의 거리, 는 노드 i에서 노드 j까지의 차량의 속력, 는 차량의 최대 운행시간)인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제1항에 있어서, 상기 제 1 라그랑지안 승수()는,(, , 는 노드 i에서 노드 j까지의 거리, 는 차량의 최대 용량, 는 노드 i의 요청사항, 은 노드 i에서 노드 j사이의 경로가 차량 p의 경로에 포함되는 경우, 은 노드 i에서 노드 j사이의 경로가 차량 p의 경로에 포함되지 않는 경우)이고,상기 제 2 라그랑지안 승수()는,(, , 는 노드 i에서 노드 j까지의 거리, 는 노드 i에서 노드 j까지의 차량의 속력, 은 노드 i에서 노드 j사이의 경로가 차량 q의 경로에 포함되는 경우, 은 노드 i에서 노드 j사이의 경로가 차량 q의 경로에 포함되는 경우)인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제1항에 있어서, 상기 제 1 단계는,스윕(sweep) 알고리즘을 이용하여 상기 임의의 경로를 설정하는 단계를 더 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제1항에 있어서,상기 k-opt 알고리즘은 계층형 2-opt 알고리즘인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제1항에 있어서, 상기 온실가스 배출량을 최소화하는 차량 경로 설정 방법은,상기 차량의 대수를 1대부터 1대씩 더해가거나 경로를 설정할 수 있는 최소한의 차량 대수부터 1대씩 더해가면서 운행 가능한 최대 차량 수인 K 대까지 상기 단계들을 수행하는 단계; 및상기 단계들을 수행한 결과 중 온실가스 배출량이 최저인 경우의 차량 대수와 경로를 선택하는 단계를 더 포함하는 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.

제11항에 있어서, 경로를 설정할 수 있는 최소한의 차량 대수()은,(는 각 그룹의 고객, )인 것을 특징으로 하는 온실가스 배출량을 최소화하는 차량 경로 설정 방법.