선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문은 중개수송 문제의 최적 해를 쉬우면서도 빠르게 도출할 수 있는 단일화된 방법을 제안한다. 제안된 방법은 중개수송문제를 보통의 수송문제로 변환하여 알고리즘을 적용한다.
제안 방법
- 2단계에는 북서코너법(Northwest Corner Method, NCM), 최소비용법(Least-Cost Method, LCM)과 보겔근사법(Vogel's Approximation Method, VAM) 등을 이용하여 가장 작은 z 값을 초기해로 한다. 3단계는 수정배분법(Modified Distribution Method, MODI) 또는 디딤돌법(Stepping-Stone Method, SSM)을 적용하여 최적 해를 얻었는지 검증하고 비용을 감소시키도록 수송량을 재조정한다.
- 기존의 수송문제 및 중개수송에 관련된 연구[1-7, 15]에 비해 본 논문은 중개 수송문제의 최적해를 빠르고 쉽게 구하는 방법을 제안하였다.
- 제안된 방법은 첫 번째로, 중개 수송문제를 일반적인 수송문제로 변환시킨다. 두 번째로, 각 열의 최소 비용을 결정하고, 각 행의 공급량을 결정된 최소 비용 오름차순으로 배정하였다. 만약 공급량이 남아 있고, 배정량이 요구량을 충족시키지 못하는 행렬의 셀의 비용 오름차순으로 남아 있는 공급량을 추가로 배정하여 초기해를 간단히 구하였다.
- 첫 번째로, 중개수송문제를 일반 수송문제로 변환시켜 행과 열의 차수를 최소화하여 문제를 단순화시킨다. 두 번째로, 초기해를 구하기 위해 각 열 (요구)의 최소 비용만을 찾아 각 행에 대해 선택된 최소 비용들의 오름차순으로 요구량을 충족시키도록 공급량을 배정한다. 초기 배정 결과 행의 공급량이 남아 있고, 요구량을 충족시키지 못하는 열이 존재하면 해당 행·열의 비용들만을 대상으로 오름차순으로 남아 있는 공급량을 배정한다.
- 만약 공급량이 남아 있고, 배정량이 요구량을 충족시키지 못하는 행렬의 셀의 비용 오름차순으로 남아 있는 공급량을 추가로 배정하여 초기해를 간단히 구하였다. 마지막으로, 열의 보다 큰 비용에 배정된 경우 배정량을 조절하여 최적해를 구하였다. 제안된 OTM은 TSM에 비해 초기해와 최적해를 구하는 과정을 매우 단순화시켰다.
- 두 번째로, 각 열의 최소 비용을 결정하고, 각 행의 공급량을 결정된 최소 비용 오름차순으로 배정하였다. 만약 공급량이 남아 있고, 배정량이 요구량을 충족시키지 못하는 행렬의 셀의 비용 오름차순으로 남아 있는 공급량을 추가로 배정하여 초기해를 간단히 구하였다. 마지막으로, 열의 보다 큰 비용에 배정된 경우 배정량을 조절하여 최적해를 구하였다.
- 본 장에서는 기존의 TSM이 갖고 있는 문제점들을 모두 해결한 최적의 단일화된 방법을 제안한다. 제안되는 방법은 불균형 수송문제를 균형 수송으로 변경하지 않는다.
- 본 장에서는 기존의 TSM이 갖고 있는 문제점들을 모두 해결한 최적의 단일화된 방법을 제안한다. 제안되는 방법은 불균형 수송문제를 균형 수송으로 변경하지 않는다. 또한.
- 본 논문은 중개수송 문제의 최적 해를 쉬우면서도 빠르게 도출할 수 있는 단일화된 방법을 제안한다. 제안된 방법은 중개수송문제를 보통의 수송문제로 변환하여 알고리즘을 적용한다. 제안된 알고리즘은 불균형 중개수송 문제에 대해서도 가상의 행이나 열을 추가하지 않고 직접 적용한다.
- 제안된 방법은 첫 번째로, 중개 수송문제를 일반적인 수송문제로 변환시킨다. 두 번째로, 각 열의 최소 비용을 결정하고, 각 행의 공급량을 결정된 최소 비용 오름차순으로 배정하였다.
- 제안된 방법은 중개수송문제를 보통의 수송문제로 변환하여 알고리즘을 적용한다. 제안된 알고리즘은 불균형 중개수송 문제에 대해서도 가상의 행이나 열을 추가하지 않고 직접 적용한다. 따라서 TSM의 1단계를 생략할 수 있다.
- 첫 번째로, 중개수송문제를 일반 수송문제로 변환시켜 행과 열의 차수를 최소화하여 문제를 단순화시킨다. 두 번째로, 초기해를 구하기 위해 각 열 (요구)의 최소 비용만을 찾아 각 행에 대해 선택된 최소 비용들의 오름차순으로 요구량을 충족시키도록 공급량을 배정한다.
대상 데이터
- 최적 수송 알고리즘의 적용성 평가는 그림 4의 13개 균형과 불균형 수송 문제를 대상으로 한다. T2는 Loucks[5], T3는 Niu[4], T4는 Loucks[5], T5는 Beasley[10], T6는 Mitchell과 Phillips[11], T7은 Hill[12], Jensen[13]과 Giallombardo[14]에서, T8, T9은 Jensen[13], T10은 Dantzig[6], T11은 Salassi[8]에서 인용되었다.
이론/모형
- 수송 문제의 최적 해를 찾는 TSM은 그림 2와 같이 3단계의 과정을 거쳐 수행된다. 초기 해를 구하는 VAM과 최적 해 검증 방법인 MODI도 참고로 제시하였다.[7,9]
성능/효과
- 따라서 TSM의 1단계를 생략할 수 있다. 다음으로, TSM의 초기해를 구하는 3가지 방법보다도 단순하게 한 단계만을 단순히 적용하여 초기해를 빠르고 쉽게 결정할 수 있다. 마지막으로 초기해가 최적해인지 검증하는 MODI나 SSM의 복잡한 과정을 간단히 해결하였다.
- 다음으로, TSM의 초기해를 구하는 3가지 방법보다도 단순하게 한 단계만을 단순히 적용하여 초기해를 빠르고 쉽게 결정할 수 있다. 마지막으로 초기해가 최적해인지 검증하는 MODI나 SSM의 복잡한 과정을 간단히 해결하였다. 따라서 TSM의 적용 어려움을 해결하였으며, 수행 방법도 단순화한 장점을 갖고 있다.
- OTM는 초기 배정을 간단히 결정하고, 배정량 조정 대상이 없어 초기 배정 결과가 최적해가 됨을 알 수 있다. 본 중개수송 문제에 대해 TSM과 OTM 모두 z = 5,200 의 동일한 최적해를 얻는데 성공하였다.
- 세 번째로, 열을 기준으로 보다 큰 비용에 배정된 수송량을 보다 작은 비용으로 수송 가능하면 수송량을 감소·증가시킨다.
- 마지막으로, 열의 보다 큰 비용에 배정된 경우 배정량을 조절하여 최적해를 구하였다. 제안된 OTM은 TSM에 비해 초기해와 최적해를 구하는 과정을 매우 단순화시켰다.
- 제안된 방법은 거의 모든 균형이나 불균형 중개수송 문제의 최적해를 찾을 수 있어 “최적 중개수송 방법 (Optimal Transshipment Method, OTM)”이라 한다.
후속연구
- 제안된 알고리즘은 불균형 수송 문제를 균형 수송문제로 변환하는 과정을 적용하지 않으며, 초기 해와 최적해를 매우 간단히 구할 수 있어 기존의 TSM을 대체하여 중개 수송문제의 최적해를 구하는 일반화된 방법으로 적용할 수 있을 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.