earticle

논문검색

중개수송 문제 최적 알고리즘

원문정보

Optimal Algorithm for Transshipment Problem

이상운, 최명복

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

This paper proposes the most simple method for optimal solution of the transshipment problem. Usually the transshipment problem is solved by direct linear programming or TSM (Transportation Simplex Method). The method using TSM has two steps. First it is to get a initial solution using NCM, LCM, or VAM, second to refine the initial solution using MOD or SSM. However the steps is complex and difficult. The proposed method applies the method that transforms transshipment problem to transportation problem. In the proposed method it simply selects the minimum cost of rows about transportation problem, and then it applies the method that assigns a transported volume as an ascending sort of the costs of rows about the selected costs. Our method makes to be very fast got the initial value. Also we uses the method that controls assignment volume, if a heavy item of cost is assigned to a transported volume and it has a condition to be able to transform to more lower cost. The proposed algorithm simply got the optimal solution with applying to 11 transshipment problem.

한국어

본 논문은 중개수송 문제의 최적 해를 찾는 가장 단순한 방법을 제안하였다. 중개 수송문제는 직접 선형계 획법이나 TSM을 적용하거나 일반적인 수송문제로 변환시켜 TSM을 적용하여 최적해를 구한다. 그러나 TSM을 적용 하여 최적해를 구하기 위해서는 초기해를 구하고 해 개선 과정을 거치는 방법이 어렵다. 초기해를 구하기 위해서는 NCM, LCM이나 VAM을 적용하며, 해 개선을 위해서는 MODI나 SSM을 적용한다. 본 논문은 중개수송 문제를 수송 문제로 변환시키는 방법을 적용하였다. 수송문제에 대해서는 단순히 열의 최소 비용을 선택하고, 선택된 비용들에 대 해 행의 비용 오름차순으로 수송량을 배정하는 방법을 적용하여 초기해를 빠르게 배정할 수 있었다. 해 개선은 보다 큰 비용에 수송량이 배정된 경우 보다 작은 비용으로 변경할 수 있는 조건을 만족하면 배정량을 조정하는 방법을 적 용하였다. 제안된 방법을 11개의 다양한 중개수송 문제에 적용한 결과 10개 문제는 초기 배정만으로 최적해를 구할 수 있었으며, 단지 2개 문제만이 해 개선과정을 1개의 비용만 변경하여 최적해를 구할 수 있었다. 따라서 제안된 방 법은 중개수송 문제에 대해 가장 간단한 최적해 방법으로 적용할 수 있을 것이다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 관련 연구와 연구 배경
 Ⅲ. 최적 중개수송 알고리즘
  1. 알고리즘 제안
  2. 알고리즘 적용
 Ⅳ. 알고리즘 적용성 평가
  1. 실험 적용 데이터
  2. OTM 적용 최적해 도출
 Ⅴ. 결론 및 향후 연구과제
 참고문헌

저자정보

  • 이상운 Sang-Un Lee. 정회원, 강릉원주대학교, 멀티미디어공학과
  • 최명복 Myeong-Bok Choi. 종신회원, 강릉원주대학교 멀티미디어공학과

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 기관로그인 시 무료 이용이 가능합니다.

      • 4,000원

      0개의 논문이 장바구니에 담겼습니다.