대규모 불균형 수송문제의 간단한 해법 (Simple Algorithm for Large-scale Unbalanced Transportation Problem)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 15권 / 4호 / 223 ~ 230페이지
· 저자명 : 이상운

초록

본 논문은 대규모 불균형 수송 문제의 최적 해를 구하는 발견적 방법을 제안한다. 대규모 수송문제의 최적해를 찾는 방법은 일반적인 수송문제의 최적 해를 구하는 TSM을 적용하는데 어려움이 있어, 대부분은 상용화된 선형계획법 패키지를 활용한다. 그러나 상용화된 선형계획법 패키지가 최적 해를 얻었는지 검증할 방법이 없다. 본 논문은 공급지와 수요지가 31×15 인 대규모 불균형 수송문제에 대해 공급지를 기준으로 수요지가 몇 개인지를 파악하여 수요지 개수의 오름차순으로 수행하며, 각 수요지 개수에 대해서는 수요지가 1개인 경우 무조건 요구량을 배정하고, 수요지가 2개 이상인 경우, 공급지 기준의 최소 비용을 선택하고, 수요지 기준으로 비용 오름차순으로 요구량을충족시키도록 배정하여 초기 해를 구하였다. 해 개선은 보다 큰 비용에 배정된 량을 보다 작은 비용으로 이동 가능한조건을 만족하면 배정량을 조정하는 방법을 적용하였다. 제안된 방법을 31×15 비용행렬에 적용한 결과, 상용 선형계획법 패키지의 최적 해를 8.9% 개선하는 효과를 나타내었다.

영어초록

As the Transportation Simplex Method of the general transportation problem are inapplicable to thelarge-scale unbalanced transportation problem, a commercialized linear programming package remains as the onlyviable means. There is, however, no method made available to verify the optimality of solutions attained by thepackage. This paper therefore proposes a simple heuristic algorithm to the large-scale unbalanced transportationproblem. From a given problem of  31×15 supply and demand areas, the proposed algorithm determines thenumber of demands areas for each supply area and executes on the latter in the ascending order of each oftheir corresponding demand areas. Next, given a single corresponding demand area, it supplies the full demandvolume and else, it supplies first to an area of minimum associated costs and subsequently to the rest so as tomeet the demand to the fullest extent. This initial optimal value is then optimized through an adjustmentprocess whereby costs are minimized as much as possible. When tested on the 31×15 cost matrix, the proposedalgorithm has obtained an optimal result improved from the commercial linear programming package by 8.9%.

참고자료

· 없음