선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
제안 방법
- 경로의 선정은 총 7회 있었으며, 최단경로와 우회경로의 총소요 시간을 비교하여 4회는 최단경로를 이용하였고, 3회는 우회경로를 이용하였으며, 본 연구의 최종해 차량경로는 다음[Figure 13]과 같다.
- 서비스 시간대는 출근ㆍ오후ㆍ퇴근 시간대의 3개 시간대로 지정하고, 0∼100분을 출근 시간대, 100∼300분을 오후 시간대, 300∼400분을 퇴근 시간대로 구분하였다. 교통상황은 원활ㆍ지체ㆍ정체의 3개 상황으로 구분하고, 원활은 60㎞/h, 지체는 30㎞/h, 정체는 15㎞/h로 적용하였으며, 서비스 시간대별 각 경로의 교통상황은 다음 [Table 4]와 같다.
- 기존의 차량경로 구성시에는 교통상황을 고려하지 않고, 단지 수요지간의 최단거리와 평균 속력을 고려하여 이동 시간을 추정하고 경로를 구성하였다. 하지만 실제 도심지에서는 차량의 증가, 집회, 공사 등 복잡한 도로사정과 외부 환경으로 인해 교통상황은 실시간으로 변화하고 있으며, 다음 [Figure 1]과 같이 원활ㆍ지체ㆍ정체 구간이 존재하게 된다.
- 본 연구에서는 출근ㆍ오후ㆍ퇴근의 서비스 시간대별로 도심지에서 발생하는 원활ㆍ지체ㆍ정체 교통상황을 고려한 차량경로문제를 제시하였으며, 기존 해법에 비해 다소 이동 거리는 증가하였으나 우회경로의 선정을 통하여 총 소요 시간을 단축할 수 있었다. 또한 본 연구에서 제시한 하이브리드 유전자 알고리즘 해법의 유효성을 입증하기 위해 Nearest Neighbor Search 및 Saving 알고리즘, 유전자 알고리즘과 총 이동 거리 및 소요 시간을 비교하였다.
- 본 연구에서 제안한 해법의 유효성을 평가하기 위하여 서비스 시간대별 교통상황을 고려하지 않고 속력을 60㎞/h로 가정하여 각각 발견적 해법인 Nearest Neighbor Search(NNS), Saving 알고리즘(SA), 유전자 알고리즘(GA), 하이브리드 유전자 알고리즘(HGA)으로 경로를 구성한 후 총 이동 거리 및 소요 시간을 비교하였으며, 비교 결과는 다음 [Table 6]과 같다.
- 본 연구에서는 단일 차고지를 중심으로 전체 N개의 수요지와 제한된 차량 대수를 보유하고 있고, 수요지별 서비스 시간과 차량의 적재용량은 일정하며, 수요지의 위치와 수요량은 알려져 있는 것으로 모형을 구축하였다.
- 본 연구에서는 서비스 시간대를 출근ㆍ오후ㆍ퇴근 3개의 시간대로 나누고, 각 시간대별로 원활ㆍ지체ㆍ정체의 교통상황으로 구분하여 모형을 설정하였다. 서비스 시간대별 교통상황을 고려하여 필요시 우회경로를 선정하고, 차량의 적재 능력을 고려하여 차량경로를 구성하며, 수요지에서의 서비스 시간을 합산한 총 소요 시간을 최소화하는 수리모형 및 하이브리드 유전자 알고리즘을 제시하였다.
- 본 연구에서는 서비스 시간대별 교통상황을 고려하여 총 소요시간을 최소화하는 하이브리드 유전자 알고리즘을 구축하였으며, 수행절차는 다음 [Figure 3]과 같다.
- 이러한 요인들로는 모집단 크기(Population size), 교차 확률(Pc), 돌연변이 확률(Pm), 부호화(coding) 방법 등을 들 수 있다. 본 연구에서는 유전 파라미터들이 적합도에 미치는 영향을 반복 실험을 통해 비교한 후 알고리즘과 문제의 특성에 맞는 파라미터를 적용하였으며 본 연구의 유전 파라미터는 다음 [Table 2]와 같다.
- 본 연구에서는 서비스 시간대를 출근ㆍ오후ㆍ퇴근 3개의 시간대로 나누고, 각 시간대별로 원활ㆍ지체ㆍ정체의 교통상황으로 구분하여 모형을 설정하였다. 서비스 시간대별 교통상황을 고려하여 필요시 우회경로를 선정하고, 차량의 적재 능력을 고려하여 차량경로를 구성하며, 수요지에서의 서비스 시간을 합산한 총 소요 시간을 최소화하는 수리모형 및 하이브리드 유전자 알고리즘을 제시하였다.
- 선별은 적자생존의 자연법칙에 기초하여 환경에 대한 적응도에 의해 현 세대의 모집단으로부터 다음 세대에 생존할 개체를 선택하는 과정이다. 세대별 우수한 해의 생존을 보장하고, 지역해로의 수렴을 방지하기 위하여 적합도가 작은 해의 생존을 확률적으로 보장해주는 룰렛 휠 방법을 적용하였으며, 집단 내에서 가장 강한 개체가 다음 세대로 변경되지 않고 전달되는 것을 보장하기 위하여 세대별 우수한 해는 반드시 생존할 수 있도록 하는 엘리트 보전전략을 각각 적용하였다.
- 예를 들어, [Table 1]에서 3번 차량의 경우는 차량 경로가 D(Depot)-4-6-8-D인데, 방문 우선순위를 고려하면 D-6-4-8-D인 경로를 구성하게 된다. 위와 같이 각 수요지에 차량을 할당하는 경우 할당된 노드의 수요량은 차량 용량을 초과할 수 없다는 제약을 만족해야 하는데, 이는 수요지를 생성 후 차량번호를 랜덤 생성 할당하는 방식을 사용하여 초기 해에서 실행 불가능해가 생성시 다음과 같은 과정을 통하여 해의 탐색을 유도하였다.
- 임의생성 기법은 다양한 해 공간을 탐색할 수 있다는 장점이 있으나 실행 불가능해가 다수 포함되어 효과적인 해의 탐색이 어려운 단점이 있다. 이러한 단점을 극복하기 위하여 임의 생성된 초기 해를 바탕으로 각 차량에 대한 수요지를 순서대로 방문하여 적재용량의 제약조건을 만족하면 차량의 경로에 포함시키고, 제약조건을 만족하지 못하면 다른 수요지로 바꾸어 주었다. 이는 차량과 수요지간의 재결합 과정으로 차량의 용량제약을 만족하도록 초기 해를 교정하여 실행 불가능해를 실행 가능해로 바꾸어 주었다.
- 교차와 같이 차량의 방문 우선순위와 차량번호의 돌연변이 방법도 상이하다. 차량의 방문 우선순위는 돌연변이를 통해 중복되는 유전자가 발생하지 않도록 교환 돌연변이를 적용하였고, 차량번호는 같은 차량이 할당되어도 무방하여 점 돌연변이를 적용하였다.
- 교차는 두 부모해의 유전자를 조합하여 자손 유전자를 생성해 나가는 과정으로 부모해보다 우수한 자손 유전자를 만들어낼 수 있다는 장점이 있다. 차량의 방문 우선순위는 차량 경로를 구성함에 있어서 우선순위가 중복되면 차량의 경로가 형성되지 않으므로 순서교차를 실시하였으며, 각 수요지에 할당된 차량번호는 2점 교차를 실시하였다.
대상 데이터
- 본 연구에서는 다음 [Table 3]과 같이 서울시청을 차고지로 하여 서울ㆍ경기지역에 위치한 32개 대학교를 수요지로 최단 및 우회경로를 구성하였으며, 거리는 실제 주행거리를 사용하였고, 각 수요지에서의 서비스 시간은 10분, 차량의 용량은 150으로 하여 실험을 수행하였다.
데이터처리
- 본 연구에서 제시한 수리모형의 검증을 위해 ILOG CPLEX 와 하이브리드 유전자 알고리즘을 이용하여 수요지 5개, 차량 2대로 구성된 경로의 총 소요 시간을 산출하여 각각 비교하였으며, 수리모형 검증 결과는 다음 [Table 5]와 같다.
이론/모형
- 2∼3개의 서비스 시간대로 구분하고, 각 서비스 시간대별 차량의 평균 속력을 적용하여 총 이동 시간을 추정하였는데, Malandraki and Daskin(1992)은 Nearest Neighbor Search와 Cutting Plane을 이용하였으며, Moon and Yang(2004)은 TSP 알고리즘을 이용하였다.
- 구성된 차량경로를 개선하기 위하여 차량의 경로를 조정하는 방법으로 2-Opt 기법을 적용하였다. 2-Opt 기법은 차량 경로의 임의의 두 지점을 바꾸어 적합도 개선 여부를 확인한 후 적합도가 개선되면 그 결과를 반영하는 지역탐색 알고리즘으로 다음 [Figure 11]과 같으며, 매 세대별 적합도 평가 이후 가장 우수한 해에 적용함으로써 세대 초기부터 우수한 해를 얻을 수 있었다.
- 초기 모집단을 생성하는 방법으로는 문제의 특성에 따라 발견적 기법, 임의생성 기법, 혼용 기법이 사용되는데 본 모형에서는 임의생성 기법과 Saving Heuristic 기법을 이용하여 구성 하였다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.