교통상황과 확률적 수요를 고려한 차량경로문제의 Hybrid 유전자 알고리즘 A Hybrid Genetic Algorithm for Vehicle Routing Problem which Considers Traffic Situations and Stochastic Demands원문보기
도심지에서 수요지간의 이동시간은 복잡한 도로사정과 외부환경으로 인하여 실시간 변화하는 교통상황에 큰 영향을 받고 있으며, 수요는 시기나 성향에 따라 확률적으로 변화하고 있다. 대부분의 차량경로문제 연구는 차량경로를 선정함에 있어 수요지간의 이동거리와 평균속력, 확정된 수요를 고려하여 경로를 구성하고 있으며, 교통상황과 확률적인 수요의 동적인 외부환경 반영이 미흡하였다. 본 연구에서는 원활 지체 정체의 교통상황과 확률적인 수요를 고려한 현실적인 차량경로문제를 제안하였다. 수리모형을 구축하고, CPLEX 11.1을 이용하여 검증하였으며, 총 소요시간을 최소화하는 Hybrid유전자 알고리즘을 제안하였다. 교통상황과 확률적 수요를 고려한 차량경로문제의 결과를 기존의 휴리스틱 알고리즘과 비교하였으며, 본 연구에서 제안한 알고리즘이 가장 우수한 해를 제공하였다.
도심지에서 수요지간의 이동시간은 복잡한 도로사정과 외부환경으로 인하여 실시간 변화하는 교통상황에 큰 영향을 받고 있으며, 수요는 시기나 성향에 따라 확률적으로 변화하고 있다. 대부분의 차량경로문제 연구는 차량경로를 선정함에 있어 수요지간의 이동거리와 평균속력, 확정된 수요를 고려하여 경로를 구성하고 있으며, 교통상황과 확률적인 수요의 동적인 외부환경 반영이 미흡하였다. 본 연구에서는 원활 지체 정체의 교통상황과 확률적인 수요를 고려한 현실적인 차량경로문제를 제안하였다. 수리모형을 구축하고, CPLEX 11.1을 이용하여 검증하였으며, 총 소요시간을 최소화하는 Hybrid 유전자 알고리즘을 제안하였다. 교통상황과 확률적 수요를 고려한 차량경로문제의 결과를 기존의 휴리스틱 알고리즘과 비교하였으며, 본 연구에서 제안한 알고리즘이 가장 우수한 해를 제공하였다.
The vehicle travel time between locations in a downtown is greatly influenced by both complex road conditions and traffic situation that changes real time according to various external variables. The customer's demands also stochastically change by time period. Most vehicle routing problems suggest ...
The vehicle travel time between locations in a downtown is greatly influenced by both complex road conditions and traffic situation that changes real time according to various external variables. The customer's demands also stochastically change by time period. Most vehicle routing problems suggest a vehicle route considering travel distance, average vehicle speed, and deterministic demand; however, they do not consider the dynamic external environment, including items such as traffic conditions and stochastic demand. A realistic vehicle routing problem which considers traffic (smooth, delaying, and stagnating) and stochastic demands is suggested in this study. A mathematical programming model and hybrid genetic algorithm are suggested to minimize the total travel time. By comparing the results considering traffic and stochastic demands, the suggested algorithm gives a better solution than existing algorithms.
The vehicle travel time between locations in a downtown is greatly influenced by both complex road conditions and traffic situation that changes real time according to various external variables. The customer's demands also stochastically change by time period. Most vehicle routing problems suggest a vehicle route considering travel distance, average vehicle speed, and deterministic demand; however, they do not consider the dynamic external environment, including items such as traffic conditions and stochastic demand. A realistic vehicle routing problem which considers traffic (smooth, delaying, and stagnating) and stochastic demands is suggested in this study. A mathematical programming model and hybrid genetic algorithm are suggested to minimize the total travel time. By comparing the results considering traffic and stochastic demands, the suggested algorithm gives a better solution than existing algorithms.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구에서는 교통상황을 원활ㆍ지체ㆍ정체의 3가지 상황으로 구분하고, 수요지의 수요가 확률적으로 변화하는 상황에서 제한된 차량의 적재능력을 고려하여 총 소요시간을 최소화하는 차량경로의 구성을 위한 수리모형과 Hybrid 유전자 알고리즘을 제시하였다.
본 연구에서는 교통상황을 원활ㆍ지체ㆍ정체의 3가지 상황으로 구분하고, 수요지의 수요가 확률적으로 변화하며, 제한된 차량의 적재능력을 고려하여 총 소요시간을 최소화하는 차량경로문제(VRPTSSD)를 제시하였다.
본 연구에서는 원활ㆍ지체ㆍ정체의 3가지 교통상황과 수요지의 수요가 확률적으로 변화하는 차량경로문제에서 총 소요시간을 최소화하기 위하여 유전자 알고리즘에 Saving 알고리즘과 2-opt 휴리스틱 기법을 혼합한 Hybrid 유전자 알고리즘을 구축하였으며, 수행절차는 과 같다.
제안 방법
교통상황은 원활ㆍ지체ㆍ정체의 3개 상황으로 구분하고, 차량의 속력은 원활 60㎞/h, 지체 30㎞/h, 정체 15㎞/h로 적용하였으며, 각 경로별 교통상황은 와 같다.
돌연변이 방법으로 차량의 방문 우선순위는 돌연변이를 통해 중복되는 유전자가 발생하지 않도록 교환(Exchange) 돌연변이를 적용하였으며, 차량번호는 같은 차량이 할당되어도 무방하여 점(Point) 돌연변이를 적용하였다.
본 연구에서 제안한 수리모형의 검증을 위해 수요지 5개, 차량 2대, 수요를 중간 값으로 하는 예제를 구성하고, CPLEX 11.1과 Hybrid 유전자 알고리즘을 이용하여 차량경로의 이동거리 및 총 소요시간을 산출한 후 비교하였으며, 수리모형 검증 결과는 와 같다.
본 연구에서는 단일 차고지를 중심으로 전체 N개의 수요지와 제한된 차량 대수를 보유하고 있고, 수요지별서비스 시간과 차량의 적재용량은 일정하며, 수요지의 위치와 수요의 범위가 알려져 있는 것으로 모형을 구축하였다.
본 연구에서는 원활ㆍ지체ㆍ정체의 3가지 교통상황이 존재하고, 수요지의 수요가 확률적으로 변화하는 상황에서 제한된 차량의 적재용량을 고려하여 총 소요시간을 최소화하는 차량경로문제에 최단거리의 수요지를 선정하여 경로를 형성하는 기법인 Nearest Neighbor Search(NNS), Saving 알고리즘(SAV), 일반 유전자 알고리즘(GGA, General GA), Hybrid 유전자 알고리즘(HGA)을 이용하여 각 10회 실험을 실시하였고, 경로를 구성한 후 이동거리와 총 소요시간의 평균값을 비교하였으며, 비교 결과는 과 같다.
본 연구에서는 유전 파라미터들이 적합도에 미치는 영향을 반복 실험을 통해 비교한 후 알고리즘과 문제의 특성에 맞는 파라미터를 적용하였으며, 본 연구의 유전 파라미터는 와 같다.
본 연구의 유전자 표현(Gene Representation)은 과 같이 2개의 String으로 이루어진 이중구조로 설정하였다.
수요지간의 거리는 유클리드 내적을 이용하였으며, 각 수요지에서의 서비스 시간은 10분, 차량의 용량은 150으로 실험을 수행하였다. 수요지별 수요는 알려진 범위 내에서 임의의 확률로 결정하여 적용하였으며, 수요의 범위와 중간 값은 <표 3>과 같다.
본 연구의 유전자 표현(Gene Representation)은 <표 1>과 같이 2개의 String으로 이루어진 이중구조로 설정하였다. 수요지는 수요지의 번호를 나타내지만 불필요한 부분으로 실제 구성은 하지 않았으며, 우선순위는 각 수요지의 방문 우선순위를 표현하였고, 차량번호는 각 수요지의 방문차량을 나타내는 것으로 유전자에서 표현된 개체는 차량번호를 의미한다.
임의생성 기법은 다양한 해 공간을 탐색할 수 있다는 장점이 있으나 실행 불가능해가 다수 포함되어 효과적인 해의 탐색이 어려운 단점이 있다. 이러한 단점을 극복하기 위하여 임의 생성된 초기 해를 바탕으로 각 차량에 대한 수요지를 순서대로 방문하여 적재용량의 제약조건을 만족하면 차량의 경로에 포함시키고, 제약조건을 만족하지 못하면 다른 수요지로 바꾸어 주었다. 이는 차량과 수요지간의 재결합 과정으로 차량의 용량제약을 만족하도록 초기 해를 교정하여 실행 불가능 해를 실행 가능해로 바꾸어 주었다.
대상 데이터
본 연구에서는 Solomon(1987)이 제시한 실험 예제 중에서 차고지 1개, 수요지 25개인 예제에 대하여 유형별로 1문제씩(R-101, C-101, RC-101) 선정하여 실험하였다. Solomon의 예제는 수요지의 분포에 따라 3가지 유형으로 분류되는데 사분면에 임의(Randomly)로 분포된 R-type, 밀집(Clustered)되어 있는 C-type, 임의와 밀집이 혼합(Mixed)되어 있는 RC-type이 있으며, <그림 9>와 같다.
데이터처리
본 연구에서 제안한 Hybrid 유전자 알고리즘의 해 개선속도를 확인하기 위하여 R-101예제를 대상으로 세대별 해를 일반 유전자 알고리즘과 비교하였으며, 비교 결과는 과 같다.
이론/모형
교차 방법은 각 수요지의 방문 우선순위가 차량경로를 구성함에 있어 중복되면 경로가 형성되지 않으므로 우선순위의 상대적인 순서가 유지되는 순서교차(Order Crossover)를 적용하였으며, 각 수요지에 할당된 차량번호는 2점 교차(Two-Point Crossover)를 적용하였다.
구성된 차량경로를 개선하기 위하여 차량의 경로를 조정하는 방법으로 2-opt 기법을 적용하였다. 2-opt 기법은 차량경로에서 임의의 두 경로를 바꾸어 적합도 개선 여부를 확인한 후 적합도가 개선되면 그 결과를 반영하는 지역 탐색(Local Search) 알고리즘으로 <그림 8>과 같으며, 세대 초기부터 우수한 해를 얻기 위하여 매 세대 적합도 평가 이후 가장 우수한 해에 적용하였다.
선별(Selection)은 적자생존의 자연법칙에 기초하여 환경에 대한 적합도에 의해 현 세대의 모집단으로부터 다음 세대에 생존할 개체를 선택하는 과정이다. 세대별 우수한 해의 생존을 보장하고, 지역해로의 수렴을 방지하기 위하여 적합도가 작은 해의 생존을 확률적으로 보장해주는 룰렛 휠(Roulette Wheel) 방법을 적용하였으며, 집단 내에서 가장 강한 개체가 다음 세대로 변경되지 않고 전달되는 것을 보장하기 위하여 세대별 우수한 해는 반드시 생존할 수 있도록 하는 엘리트 보전전략(Elitism Strategy)을 적용하였다.
초기 모집단(Population)을 생성하는 방법으로는 문제의 특성에 따라 발견적 기법, 임의생성 기법, 혼용 기법이 사용되는데 본 모형에서는 임의생성 기법과 Saving 알고리즘을 혼합한 혼용 기법을 이용하여 구성 하였다.
성능/효과
CPLEX 11.1을 이용하여 산출한 수리모형의 이동거리 및 총 소요시간과 본 연구에서 제안한 Hybrid 유전자 알고리즘의 결과가 동일하게 도출되어 본 연구에서 제시한 수리모형의 타당성을 입증하였다.
Hybrid 유전자 알고리즘의 초기 해가 일반 유전자 알고리즘에 비해 월등하게 우수한 결과를 보여주고 있다. 이는 초기 모집단 생성시 Saving 알고리즘을 적용함으로써 우수한 초기 해를 생성할 수 있었기 때문이다.
또한 세대가 진행될수록 그래프 간격의 차이가 점점 벌어지고, 약 100세대 이상 진행된 이후에 그래프의 간격이 점진적으로 줄어드는 것을 확인할 수 있었다. Hybrid 유전자 알고리즘이 우수한 초기 해를 바탕으로 해의 개선이 초기에 급격하게 진행되었으며, 이는 지역탐색 알고리즘인 2-opt 과정을 통하여 해의 개선이 가속됨으로써 약 230세대가 진행된 이후에 우수한 해로 수렴하는 등 본 연구에서 제안한 Hybrid 유전자 알고리즘의 효율성과 우수성을 확인하였다.
도심지에서 발생하는 원활ㆍ지체ㆍ정체 교통상황과 확률적인 수요를 고려한 차량경로문제를 위한 Hybrid 유전자 알고리즘을 제시하였고, Nearest Neighbor Search, Saving 알고리즘, 일반 유전자 알고리즘과 이동거리 및 총 소요시간을 비교하였으며, 실험 결과 기존 해법에 비해 이동거리가 약간 증가하였으나 교통상황이 원활한 경로의 선정을 통하여 총 소요 시간을 단축할 수 있었다.
둘째, 각 수요지의 수요는 1회 방문에 의해서 만족되며, 각 수요지는 차량의 1회 방문만 허용한다.
또한 Nearest Neighbor Search, Saving 알고리즘, 일반 유전자 알고리즘을 이용한 실험 결과에 비해 89.5∼1,798.1분의 총 소요시간을 단축할 수 있었다.
이는 초기 모집단 생성시 Saving 알고리즘을 적용함으로써 우수한 초기 해를 생성할 수 있었기 때문이다. 또한 세대가 진행될수록 그래프 간격의 차이가 점점 벌어지고, 약 100세대 이상 진행된 이후에 그래프의 간격이 점진적으로 줄어드는 것을 확인할 수 있었다. Hybrid 유전자 알고리즘이 우수한 초기 해를 바탕으로 해의 개선이 초기에 급격하게 진행되었으며, 이는 지역탐색 알고리즘인 2-opt 과정을 통하여 해의 개선이 가속됨으로써 약 230세대가 진행된 이후에 우수한 해로 수렴하는 등 본 연구에서 제안한 Hybrid 유전자 알고리즘의 효율성과 우수성을 확인하였다.
셋째, 각 차량의 경로에 포함된 수요지의 수요의 합은 적재용량을 초과할 수 없다.
알고리즘별 10회 실험을 실시한 후 평균값을 비교한 결과 모든 유형의 예제에서 차량의 이동거리는 Saving 알고리즘이 최단경로를 산출하였다. 이는 Saving 알고리즘이 교통상황은 고려하지 않고, 수요지간의 거리 절약 값만을 이용하여 경로를 구성하기 때문이며, 본 연구에서 제안한 Hybrid 유전자 알고리즘은 교통상황을 고려하여 경로를 구성하므로 Saving 알고리즘에 비해 이동거리는 11.
이는 Saving 알고리즘이 교통상황은 고려하지 않고, 수요지간의 거리 절약 값만을 이용하여 경로를 구성하기 때문이며, 본 연구에서 제안한 Hybrid 유전자 알고리즘은 교통상황을 고려하여 경로를 구성하므로 Saving 알고리즘에 비해 이동거리는 11.7∼55.2㎞ 증가하였으나 차량경로의 총 소요시간은 모든 유형의 예제에서 최단시간을 도출하였다.
절약 값을 구한 후 크기의 내림차순으로 정리하여 절약목록을 작성하고, 이 절약목록에서 절약이 가장 큰 수요지로 경로를 형성하는데 이는 최초 구성된 경로보다 Sij만큼의 거리가 절약된다.
후속연구
본 연구의 알고리즘을 활용하여 수요지간의 이동시간이 교통상황에 큰 영향을 받으므로, 이동경로의 교통이 혼잡하다면 다른 수요지를 선정하여 이동함으로서 소요시간을 줄일 수 있으며, 변화하는 수요를 포함하는 최적의 차량경로를 구성함으로써 기업의 물류비용을 줄일 수 있을 것이다.
향후 연구방향으로 교통 데이터의 시계열 자료나 도로형태, 신호체계 등을 활용하여 교통 흐름의 분포를 추정함으로써 실질적인 교통상황을 적용하고, 신뢰성이 높은 고객의 예측된 수요를 반영하여 발전시킨다면 보다 효과적으로 현실문제에 적용될 수 있을 것으로 판단된다.
질의응답
핵심어
질문
논문에서 추출한 답변
Saving 알고리즘의 역할은 무엇인가?
Saving 알고리즘은 <그림 2>와 같이 더 경제적인 경로를 형성할 수 있도록 유도하여 우수한 초기 해를 산출해주는 역할을 한다.
임의생성 기법의 장단점은 무엇인가?
임의생성 기법은 다양한 해 공간을 탐색할 수 있다는 장점이 있으나 실행 불가능해가 다수 포함되어 효과적인 해의 탐색이 어려운 단점이 있다. 이러한 단점을 극복하기 위하여 임의 생성된 초기 해를 바탕으로 각 차량에 대한 수요지를 순서대로 방문하여 적재용량의 제약조건을 만족하면 차량의 경로에 포함시키고, 제약조건을 만족하지 못하면 다른 수요지로 바꾸어 주었다.
유전자 알고리즘의 성능을 좌우하는 요인들로는 어떤 것들이 있는가?
유전자 알고리즘이 확률과 파라미터에 의하여 다양한 결과를 발생시키기 때문에 유전자 알고리즘의 성능을 좌우하는 몇 가지 요인들을 고려해야 한다. 이러한 요인들로는 모집단 크기(Population Size), 교차 확률(Pc), 돌연변이 확률(Pm), 종료 세대수 등을 들 수 있다. 본 연구에서는 유전 파라미터들이 적합도에 미치는 영향을 반복 실험을 통해 비교한 후 알고리즘과 문제의 특성에 맞는 파라미터를 적용하였으며, 본 연구의 유전 파라미터는 <표 2>와 같다.
Clark, G. and J. W. Wright(1964), "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research, Vol.12, pp.568-581.
Gendreau, M., A. Hertz and G. Laporte(1992), "New Insertion and Postoptimization Procedures for the Traveling Salesman Problem", Operations Research, Vol.60, pp.1086-1094.
Goldberg, D. and R. Lingle(1985), "Alleles, Loci, and The Traveling Salesman Problem", Proceedings of the First International Conference on Genetic Algorithms and their applications, pp.154-159.
Haughton, M. A.(1998), "The Performance of Route Modification and Demand Stabilization Strategies in Stochastic Vehicle Routing", Transportation Research, Vol.32, pp.551-566.
Haughton, M. A. and A. J. Stenger(1999), "Comparing Strategies for Addressing Delivery Shortages in Stochastic Demand Settings", Transportation Research, Vol.35, pp.25-41.
Hill, V. and W. C. Benton(1992), "Modeling Intra-City Time-Dependent Travel Speeds for Vehicle Scheduling Problems", Journal of Operational Research Society, Vol.43, pp.343-351.
Laporte, G.(1992), "The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms", European Journal of Operational Research, Vol.59, pp.345-358.
Laporte, G., F. V. Louveaux and L. Van Hamme(2002), "An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands", Operations Research, Vol.50, pp.415-423.
Malandraki, C. and M. S. Daskin(1992), "Time Dependent Vehicle Routing Problems: Formulation, Properties and Heuristic Algorithms", Transportation Science, Vol.26, pp.185-200.
Reimann, M.(2005), "Analyzing a Vehicle Routing Problem with Stochastic Demands Using Ant Colony Optimization", Advanced OR and AI Methods in Transportation, Poznan Technical University Publishers, pp.764-769.
Solomon M. M.(1987), "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints", Operations Research, Vol.35, pp.254-265.
Stewart, W. R. and B. L. Golden(1983), "Stochastic Vehicle Routing: A Comprehensive Approach", European Journal of Operational Research, Vol.14, pp.371-385.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.