유전자알고리즘 및 발견적방법을 이용한 통합차량운송계획 모델

1. 개요

본 연구는 Heuristic 알고리즘 및 유전자알고리즘(GA)을 이용한 3단계의 통합차량운송계획 모델의 개발이다. 차량경로문제(VRP : Vehicle Routing Problem)를 해결하기 위한 접근방법으로 기존의 Saving 알고리즘을 개선하여 사용하였으며 유전자알고리즘(Genetic Algorithm)의 각종 연산자(Operators)들을 계산하여 사용하였다.
본 모델은 다음 3단계의 접근방법을 사용하였다 ; 1) 다 물류센터의 문제해결을 위한 영역할당(Sector Clustering) 모델, 2) 경로계획모델(VRP Model), 및 3) 최적 운송계획모델(GA-TSP Model).
본 모델들을 다양한 운송환경에서 거리산정방법, 가용운송장비 대수, 운송시간의 제한, 물류센터 및 운송지점의 위치 및 수요량 등 다양한 파라메터들을 고려한 통합시스템으로 3개의 Component로 구성된 GUI-Type 프로그램을 개발하고 Sample 응용결과를 보였으며 기존의 모델들보다 우수한 결과를 보였다.

본 연구는 객체지향적 프로그래밍기법(Object Orie-nted Programming)을 기반으로 한 다 물류센터의 최적차량운송계획을 위한 S/W의 연구이다. 본 연구는 다음과 같은 3단계의 접근방법을 사용하였다 : 1) 다 물류센터를 단일 물류센터로 변환하기 위한 영역할당(Sector-Clustering)알고리즘을 개발하고, 2) 이를 이용하여 각 단일물류센터의 차량경로계획을 수립하기 위한 GA-VRP를 개발하여 최적 차량경로계획을 구하였으며 3) 차량운송거리(비용, 시간)를 최소화하는 차량운송순서계획을 위한 GA-TSP 알고리즘을 개발하였다.
사용자가 쉽게 활용할 수 있도록 GUI-Type 프로그래밍 방법을 사용하여 위의 3단계의 모듈들을 통합한 통합차량경로계획 S/W를 개발하였다.
<그림 1>은 위의 3단계의 접근방법을 요약한 것이다. 본 연구에서 개발한 통합 차량경로계획모델은 보완 개발될 경우 지금까지의 다 물류센터의 문제를 단일 S/W로 해결하지 못하던 문제를 사용자 입장에서 쉽게 처리할 수 있다.

2. 통합운송계획모델

본 S/W는 3개의 Component를 직접 개발하므로 기존의 개별모델들보다 효과적이고 통합된 시스템으로 개발되었다. 본 연구에서 개발한 프로그램은 사용자에게 쉽고, 사용하기 간편한 사용자 인터페이스(User-Interface)에 초점을 맞추어 설계되었고, 크게 3개의 모듈들을 기반으로 개발되었다. 본 모델의 각 Compon ent는 <그림 2>와 같다.

2.1 영역할당 모듈(Sector-Clustering Module)
본 모듈은 다 물류센터를 단일 물류센터로 구역할당을 하는 모듈로서 다음과 같은 알고리즘에 따라 영역할당이 이루어진다.
- 영역할당 알고리즘
① 각 물류센터에서 모든 수요지간의 거리를 계산한다. 여기서는 LP-Distance 방법을 사용하였다.
d(x,p) = (|x - ai |p + |y - bi |p)
여기서, d(x, p)=거리, (x, y)=시작점, (ai , bi )=끝점, 일반적으로 P값은 도로의 직선 및 굴곡도 정도와 기타 교통 변화에 따른 요소들로부터 예측할 수 있다.
② M개의 물류센터와 N개의 수요지가 있는 경우 이를 각 물류센터별로 계산된 거리를 오름차순으로 정렬하고, 물류센터에서 가장 가까운 거리에 있는 수요지를 먼저 할당한다.
③ 이미 할당된 수요지는 다른 물류센터에서 상위 우선 순위와 비교 후 총 거리의 최소화에 기여 정도가 적을때에는 제외시킨다.
④ 각 물류센터의 공급능력을 만족할 때까지 수요 지를 할당한다. 그렇지 않으면 단계②로 간다.
⑤ 각 물류센터에 할당된 수요지가 중복되지 않을 경우 종료한다.
그 예는 <그림 3>과 같다. 물류센터가 3개인 경우에 구역을 할당한 것이다.

2.2 경로계획모듈(Improved VRP Module)
본 모듈은 Sector-Clustering Module을 상속받아서 다 물류센터를 단일물류센터로 변화하여 차량운송경로 계획을 수립하기 위한 모듈로서, 차량종류별, 차량대수, 운반능력을 고려하고, 차량운행시간제한 및 물류센터의 공급능력을 고려하여 차량경로문제를 해결하는 복합적인 프로그램을 개발하였다.

－ Improved VRP Module의 알고리즘
① Saving Algorithm을 적용하여 Saving 값을 구한다. S x,y =d0.x+d0.x - d x,y (Saving 거리)
② Saving 값 중에서 가장 큰 Cell을 선택한다.
(차량의 적재용량을 체크하여 초과 여부를 확인한다.) C 0 ?A D x1?A D y1?A ≤ Kv
③ 추가 경로를 정하기 위하여 두 경로 연결가능성(a)과 거리절약효과를 고려한 삽입기법(c)을 사용한다.
－C 0 ?A D x1?A D y1?A D x2?A D y2≤Kv (쌍을 이루는 Cell이 존재할 경우, 두 경로 연결가능성 검토)
－C 0 ?A D x1?A D y1?A D x2?A D y2＞Kv (쌍을 이루는 Cell이 존재하지 않을 경우, 두 경로 연결성 배제)
－C 0 ?A D x1?A D y1?A D x2≤Kv - a (하나의 수요지만 추가한다. 거리절약효과를 고려한 삽입기법)
－물류센터별 모든 수요지를 할당할 때까지 단계 ②를 반복한다.

2. 3 GA-TSP Module
본 모듈은 Improved VRP Module을 상속받아서 차량운행거리(시간, 비용)를 최소화하는 모듈로서 다양성, 편리성, 통합성이 우수하며, 개선된 유전자 알고리즘을 이용하여 최적차량순서계획을 위한 모듈이다.

－ 개선된 GA 연산자(Operator) 개발
본 모듈에서 제시한 개선된 인접인자 재결합 교차 연산자(Improved Edge-2 Recombination Crossover Operator)는 수요지의 순서를 기반으로 하여 다음과 같은 절차에 의해 개선하였다. 먼저 초기 모집단으로 구성된 각 개체를 적응도 함수(Fitness Function)에 의하여 평가하고 이를 오름차순으로 정렬한 후 교차 연산자를 적용시켰다.
즉 어떤 수요지가 두 부모에서 모두 특정 수요지 에 인접된 경우, 이를 인접 표에서 “-"로 표시하고 이 인접 수요지를 우선하여 선택하는 방법으로서 다음 단계들을 따라서 자손(Offspring)을 생성한다.
Step 1 : 인접표(Edge List)를 작성한다.
Step 2 : 인접표가 가장 적은 수요지의 번호를 두 개 선택한다.(인접표상의 수요지의 번호 수는 4개에서 2개 사이에 존재한다. )
Step 3 : 선택된 수요지 중 번호순으로 자손(O1)과 자손(O2)을 생성한다.(만약, 동률인 경우 번호순별로 선택)
Step 4 : 인접한 수요지 중 “-"로 표시한 수요지 부터 번호순으로 선택하고, 인접표에서 지운다.(만약, 인접표에서 선택할 번호가 존재하지 않는 특수한 경우가 발생하면 숫자순서별 수요지를 찾아 선택한다.)
Step 5 : 완전히 새로운 자손이 생성될 때까지 단계 4를 반복한다.
<그림 4>는 3개의 물류센터의 경우 각 물류센터의 차량경로계획을 본 연구에서 개발한 프로그램으로 구한 예이다. <그림 3>에서 물류센터-2의 결과를 위한 Data를 보이고 있다.

3. Component 개발에 의한 통합운송계획 프로그램 구축

본 모델은 사용자를 위한 다양한 기능, 편리성, 객체지향성, 통합성에 최대한의 중점을 두고 프로그램을 개발하였으며, 프로그래밍 측면에서 본 모델은 <그림 5>와 같이 크게 3가지 모듈로 개발되었다.
즉, Sector-Clustering Module, VRP Module 및 TSP Module로 나누었다. 이 3가지 모듈은 객체지향 프로그래밍 언어인 C++언어를 사용하여 데이터, 추상화(Data Abstraction), 상속성(Inheritance), 그리고 다형성(Polymorphism) 등 세가지의 특징을 가질 수 있도록 Class구조로 캡슐화(Encapsulation)시켰고, 객체 지향적 기법에 사용되는 언어의 가장 큰 특징인 코드의 재사용(Code Reusability)을 중심으로 작성하였다. 따라서 VRP 모듈과 TSP 모듈은 코드 재사용을 극대화 시킬 수 있고, 확장성을 높일 수 있으며, 외부 다른 모듈에 대해서 독립적이며, 다른 프로그래머들도 사용이 용이하도록 하기 위해서 컴포넌트(Component)로 개발하였다. 그리고 VRP, TSP Component는 C++ 언어로 작성되었지만 컴포넌트 소스를 컴파일하여 Package Library(*.bpl)로 만들면, 파스칼 언어를 사용하는 Delphi에서도 사용할 수 있도록 하였다. 또한 개발에 사용된 모든 Class들의 List구조들은 내부적으로 Linked-List 구조를 따르며 이는 VCL(Visual Component Library)에서 제공하는 TList Class를 Wrapping한 것이다.

3.1 Sector-Clustering Module
<그림 6>은 다 물류센터의 구역할당을 담당하는 Module로써 TObject로부터 상속을 받은 TMultiCluster의 Class의 상속도이다. 이 모듈의 Class는 아래와 같다.
- TMultiCluster Class
●Class 인스턴스 변수
·PosList: 수요지에 대한 좌표값들, Streaming 가능
·Demand: 수요지별 수요량
·SectorList: 물류센터별 구역할당 후의 결과를 산출
●메소드
·SectorCluter(): 구역할당을 수행하는 것

3.2 VRP Component
<그림 7>은 VRP 컴포넌트로써 TComponent로부터 상속받은 Time을 고려하지 않은 TVrp 컴포넌트와 TVrp로부터 상속받은 Time을 고려한 TVrpTW 컴포넌트로 나눌 수 있다. 그에 따른 컴포넌트를 개략적으로 설명하면 아래와 같다.

1) TVrp 컴포넌트
●Class 인스턴스 변수
·PosList: 수요지에 대한 좌표값들을 TPoint 설정
·Vehicle: 차량관련 설정
·Demand: 수요지별 수요량 설정
·ResultList: 차량운송경로와 관련된 결과치 산출
●메소드
·LoadFromFile(): 가상함수로 선언되어 있으며 인자 값으로 파일이름만 넘겨주면 단 한줄의 코딩만으로 결과치를 얻을 수 있다.
·Prepared(): Saving Table을 구성하고 여러가지 준비과정을 거친다.
·VrpPerform(): 실제적인 VRP 계산과정을 수행하는 것
●이벤트
·OnVrpChanged: VRP의 결과치가 나올 때 이벤트가 발생
·OnVrpProgress: VRP의 진행도를 나타내는 이벤트

2) TVrpTW 컴포넌트
●메소드
·LoadFromFile(): 가상함수로 선언되어 있어 Dynamic Binding을 할 수 있으므로 모델타입에 따라서 상속된 메소드 혹은 인스턴스 메소드를 자동으로 호출한다.
·VrpTWPerform(): 실제적인 Time VRP 계산과정을 수행하는 것
●이벤트
·OnVrpTWChanged: Time VRP의 결과치가 나올 때마다 이벤트가 발생
·OnVrpTWProgress: Time VRP의 진행도를 나타내는 이벤트

3) TSP Component
<그림 8>은 TSP 컴포넌트로써 TComponent로부터 상속받은 Random TSP를 기반으로 한 TTsp컴포넌트와 TTsp로부터 상속받은 TGATsp 컴포넌트로 나눌 수 있다. 그에 따른 컴포넌트를 개략적으로 설명하면 아래와 같다.

1) TTsp 컴포넌트
●Class 인스턴스 변수
·PosList: 수요지에 대한 좌표값들, TVrp의 PosList 인스턴스와 Streaming 가능
●메소드
·LoadFromFile(): 가상함수로 선언되어 있으며 인자 값으로 파일이름만 넘겨주면 단 한 줄의 코딩만으로 결과치를 얻을 수 있다.
·TspPerform(): Random TSP를 수행하는 것
●이벤트
·OnTspChanged: Generation 수행 중에 최적해가 변화할 때마다 발생
·OnTspProgress: Generation의 진행율을 나타내는 이벤트

2) TGATsp 컴포넌트
●Class 인스턴스 변수
·Permutation: 초기해 구성에 사용되는 순열발생 인스턴스
·MutationList: 돌연변이를 하기 위해서 선택된 개체들
·EliteList: Elite를 수행하기 위한 개체들
●메소드
·LoadFromFile(): 가상함수로 선언되어 있어 Dynamic Binding을 할 수 있으므로 모델타입에 따라서 상속된 메소드 혹은 인스턴스 메소드를 자동으로 호출한다.
·GATspPerform(): GATSP를 수행하는 것
●이벤트
·OnGATspChanged: Generation 수행 중에 최적해가 변화할 때마다 발생
·OnGATspProgress : Generation의 진행율을 나타내는 이벤트

4. 개발 S/W의 응용

본 연구의 Sample Test를 위하여 수요지가 50, 75 및 1백개소인 Sample 문제의 제약과 차량의 총 이동거리는 <표 1>과 같다. 본 연구에서 개발된 프로그램의 중요 입력화면과 결과화면을 요약정리하면 아래 그림 9, 10, 12, 및 그림 13과 같다.

5. 결론

본 연구는 유전자 알고리즘(GA :Genetic Algorith-m)을 사용하여 량의 시간 제약이 존재하는 차량운송경로계획문제를 위한 모델을 개발한 것이다. 이를 위하여 다 물류센터를 단일 물류센터의 문제로 변환하는 영역할당 모듈과 VRP 및 GA-TSP 등 3단계의 접근 방법을 사용하였다. 통합시스템을 위하여 프로그램은 3개의 Component로 구성된 GUI-Type으로 개발하였으며 Sample 예제를 통하여 차량의 종류별 차량운송경로계획과 운송하는데 소요되는 시간 및 적재된 차량의 용량을 고려하여 최적운송계획을 쉽게 구할 수 있게 하였다.
향후에는 기존에 개발된 프로그램들과 본 알고리즘과 비교 검토하기 위한 추가 연구를 계속할 예정이다.