본 논문은 대규모 불균형 수송 문제의 최적 해를 구하는 발견적 방법을 제안한다. 대규모 수송문제의 최적해를 찾는 방법은 일반적인 수송문제의 최적 해를 구하는 TSM을 적용하는데 어려움이 있어, 대부분은 상용화된 선형계획법 패키지를 활용한다. 그러나 상용화된 선형계획법 패키지가 최적 해를 얻었는지 검증할 방법이 없다. 본 논문은 공급지와 수요지가 $31{\times}15$인 대규모 불균형 수송문제에 대해 공급지를 기준으로 수요지가 몇 개인지를 파악하여 수요지 개수의 오름차순으로 수행하며, 각 수요지 개수에 대해서는 수요지가 1개인 경우 무조건 요구량을 배정하고, 수요지가 2개 이상인 경우, 공급지 기준의 최소 비용을 선택하고, 수요지 기준으로 비용 오름차순으로 요구량을 충족시키도록 배정하여 초기 해를 구하였다. 해 개선은 보다 큰 비용에 배정된 량을 보다 작은 비용으로 이동 가능한 조건을 만족하면 배정량을 조정하는 방법을 적용하였다. 제안된 방법을 $31{\times}15$비용행렬에 적용한 결과, 상용 선형계획법 패키지의 최적 해를 8.9% 개선하는 효과를 나타내었다.
본 논문은 대규모 불균형 수송 문제의 최적 해를 구하는 발견적 방법을 제안한다. 대규모 수송문제의 최적해를 찾는 방법은 일반적인 수송문제의 최적 해를 구하는 TSM을 적용하는데 어려움이 있어, 대부분은 상용화된 선형계획법 패키지를 활용한다. 그러나 상용화된 선형계획법 패키지가 최적 해를 얻었는지 검증할 방법이 없다. 본 논문은 공급지와 수요지가 $31{\times}15$인 대규모 불균형 수송문제에 대해 공급지를 기준으로 수요지가 몇 개인지를 파악하여 수요지 개수의 오름차순으로 수행하며, 각 수요지 개수에 대해서는 수요지가 1개인 경우 무조건 요구량을 배정하고, 수요지가 2개 이상인 경우, 공급지 기준의 최소 비용을 선택하고, 수요지 기준으로 비용 오름차순으로 요구량을 충족시키도록 배정하여 초기 해를 구하였다. 해 개선은 보다 큰 비용에 배정된 량을 보다 작은 비용으로 이동 가능한 조건을 만족하면 배정량을 조정하는 방법을 적용하였다. 제안된 방법을 $31{\times}15$비용행렬에 적용한 결과, 상용 선형계획법 패키지의 최적 해를 8.9% 개선하는 효과를 나타내었다.
As the Transportation Simplex Method of the general transportation problem are inapplicable to the large-scale unbalanced transportation problem, a commercialized linear programming package remains as the only viable means. There is, however, no method made available to verify the optimality of solu...
As the Transportation Simplex Method of the general transportation problem are inapplicable to the large-scale unbalanced transportation problem, a commercialized linear programming package remains as the only viable means. There is, however, no method made available to verify the optimality of solutions attained by the package. This paper therefore proposes a simple heuristic algorithm to the large-scale unbalanced transportation problem. From a given problem of $31{\times}15$supply and demand areas, the proposed algorithm determines the number of demands areas for each supply area and executes on the latter in the ascending order of each of their corresponding demand areas. Next, given a single corresponding demand area, it supplies the full demand volume and else, it supplies first to an area of minimum associated costs and subsequently to the rest so as to meet the demand to the fullest extent. This initial optimal value is then optimized through an adjustment process whereby costs are minimized as much as possible. When tested on the $31{\times}15$cost matrix, the proposed algorithm has obtained an optimal result improved from the commercial linear programming package by 8.9%.
As the Transportation Simplex Method of the general transportation problem are inapplicable to the large-scale unbalanced transportation problem, a commercialized linear programming package remains as the only viable means. There is, however, no method made available to verify the optimality of solutions attained by the package. This paper therefore proposes a simple heuristic algorithm to the large-scale unbalanced transportation problem. From a given problem of $31{\times}15$supply and demand areas, the proposed algorithm determines the number of demands areas for each supply area and executes on the latter in the ascending order of each of their corresponding demand areas. Next, given a single corresponding demand area, it supplies the full demand volume and else, it supplies first to an area of minimum associated costs and subsequently to the rest so as to meet the demand to the fullest extent. This initial optimal value is then optimized through an adjustment process whereby costs are minimized as much as possible. When tested on the $31{\times}15$cost matrix, the proposed algorithm has obtained an optimal result improved from the commercial linear programming package by 8.9%.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 대규모 불균형 수송문제에 대해 선형계획법 상용 패키지를 적용하였을 경우 최적 해를 구하지 못하는 단점을 보완한 알고리즘을 제안하였다.
본 논문은 대규모의 불균형 수송문제의 최적 해를 구하는 간단한 방법을 제시한다. 제시된 방법을 적용한 결과 상용화된 선형계획법 패키지로 얻은 z 값이 최적 해가 아님을 증명한다.
표 1과 표 2의 대규모 수송문제에서 수송비용을 최소화시키는 문제를 풀기 위해서는 TSM 방법을 적용하기 어려우며, 일반적으로는 상용화된 선형계획법 패키지를 적용한다. 본 절에서는 상용화된 패키지를 적용하지 않고 직접 최적 해를 구하는 알고리즘을 제안한다.
제안 방법
(1) 선형계획법 패키지인 LINGO는 메모리 용량 문제로 대용량의 데이터 처리를 하지 못해 2개의 데이터로 분할하여 적용하였다.
만약, 공급량과 요구량을 만족하지 못하면 다시 최소 비용을 선택하여 위와 같은 방법으로 수송량을 배정한다. 다음으로, 초기해의 개선은 보다 큰 비용에 배정된 량을 보다 작은 비용으로 이동시킬 수 있는 조건을 만족하면 이동시키는 방법을 적용하였다.
제안된 알고리즘은 먼저, 공급지의 개수를 결정하고, 공급지가 1개인 수요지는 무조건 요구량을 배정하며, 공급지가 2개 이상인 수요지는 공급지 측면에서의 최소 비용을 선택하고, 수요지 측면에서 선택된 비용의 오름차순으로 수송량을 배정하는 방법을 택하였다. 만약, 공급량과 요구량을 만족하지 못하면 다시 최소 비용을 선택하여 위와 같은 방법으로 수송량을 배정한다.
대상 데이터
표 1과 표 2는 대한민국의 2030년 이후 수소 운송시스템의 최적화 모델을 상용화된 선형계획법 패키지인 LINGO를 적용해 시스템을 구축한 사례이다.[5] LINGO는 프로그램 용량 제약으로 1개의 시스템을 북부와 남부권역으로 구분하여 최적 해를 구하였다.
이론/모형
2단계에는 northwest corner method (NCM), least-cost method (LCM)과 Vogel's approximation method (VAM) 등을 이용하여 z값이 최소인 초기 해를 구한다.
그러나 철도나 송수관 수송의 경우 도달이 불가능한 경로를 가지는 경우가 많이 존재한다. 수송 문제를 해결하는 가장 일반적인 방법으로 transportation simplex method (TSM)을 적용한다.
성능/효과
(3) LINGO로 구한 최적 해는 특정 공급지의 가동률이 저조하여 효율적이지 못하다. 예로, 춘천은 공급 용량이 50,000톤인데 반해 실제 공급량은 14,970톤으로 가동율은 29.
5. 임의의 수요지 Dj의 비용 cij > cik 의 배정량이 xij > 0, xik ≥ 0 일 때, cij, cik 의 열에서 cij, cik 의 배정량 xij ≥ 0, xik > 0 을 모두 찾는다.
Step 5를 수행한 결과 z = 93,969.75 를 얻어 상용화된 선형계획법 패키지인 LINGO로 구한 z = 103,170.70에 대해 9,200.96/Ton/Km가 작은 값으로 8.9%의 해 개선 효과를 얻었다. 또한, 공급 용량이 실 공급량을 초과하는 공급지를 분석한 결과 표 8과 같이 가동율을 향상시키는 결과도 얻을 수 있었다.
9%의 해 개선 효과를 얻었다. 또한, 공급 용량이 실 공급량을 초과하는 공급지를 분석한 결과 표 8과 같이 가동율을 향상시키는 결과도 얻을 수 있었다.
본 논문은 대규모의 불균형 수송문제의 최적 해를 구하는 간단한 방법을 제시한다. 제시된 방법을 적용한 결과 상용화된 선형계획법 패키지로 얻은 z 값이 최적 해가 아님을 증명한다.
제안된 알고리즘은 초기 해를 구하는 과정과 해 개선 과정이 간단하여 전산화된 상용 패키지를 적용하지 않아도 되며, 선형계획법보다 나은 최적 해를 구하는 장점을 갖고 있다.
참고문헌 (7)
Wikipedia, "Transportation Problem," http://en.wikipedia.org/wiki/Transportation_problem, Wikimedia Foundation Inc., 2014.
W. L. Winston, J. B. Goldberg, and M. Venkataramanan, "Introduction to Mathematical Programming: Operations Research," Vol. 1, 4th edition, Duxbury Pr, 2003, ISBN-10: 0534359647.
L. Ntaimo, "Transportation and Assignment Problems," http://ie.tamu.edu/INEN420_2005Spring/SLIDES/Chapter7.pdf, 2005.
J. K. Khang, "Operations Research," http://secom.hanbat.ac.kr/or/ch06/right04.html, Hanbat University, 2006.
K. J. Boo, "Hydrogen Economy Ages, How to Supply Hydrogen?," Energy Journal, http://www.ejnews.co.kr/news/articleView.html, 2008.
S. U. Lee, "Optimal Solution for Transportation Problems," Journal of IIBC, Vol. 13, No. 2, pp. 93-102, Apr. 2013, doi: 10.7236/JIIBC.2013.13.2.93.
S. U. Lee and M. B. Choi, "The Optimal Algorithm for Transshipment Problem," Journal of IIBC, Vol. 13, No. 1, pp. 153-162, Feb. 2013, doi:10.7236/JIIBC.2013.13.1.153.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.