빙판도로 최소 제설 거리 문제의 오일러 사이클 알고리즘 (Algorithm for Eulerian Cycle of Minimum Gritting Length Problem in Ice Roads)

서지정보

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

초록

논문은 개 정점 (교차로)과 개 간선 (도로)로 구성된 방향그래프 도시에 대해 오일러 사이클을 형성하는도로 제설차량 운행거리를 최소로 하는 제설계획 문제에 대해 선형시간 복잡도의 휴리스틱 알고리즘을 제안하였다. 제안된 알고리즘은 각 정점의 유입과 유출차수가 동일하도록, 부족한 유출차수 정점들과 유입차수 정점들을 도출하고, 이들간의 최단거리 경로를 선택하는 규칙을 적용해 추가로 필요한 도로들을 도출하였다. 도출된 오일러 사이클 도로망에 대해 출발 정점에서 모든 도로를 한 번씩만 거쳐 되돌아오는 오일러 사이클 제설 도로들의 방문 순서 계획을 결정하였다.
제안된 알고리즘을 실제 실험 데이터에 적용한 결과 선형계획법과 동일한 해를 얻었다. 반면에, 선형계획법은 오일러사이클을 찾는 과정에서 추가로 필요한 최소거리 도로들을 찾는 최적화 과정을 수행하는 반면에, 제안된 알고리즘은 사전에 추가로 필요한 도로들을 결정하여 오일러 사이클을 형성하기 때문에 최적화 과정이 필요하지 않은 장점이 있다.

영어초록

This paper suggests heuristic algorithm with linear time complexity to decide the minimum gritting truck moving length of gritting plan for digraph cities with m vertices (intersections) and  edges (roads). This algorithm draws the shortage out-degree and in-vertices in order to equal of in-degree and out-degree in each vertex. And this algorithm can be find the additional shortest length of roads using the minimum shortest path selection method between shortage out-degree vertex and in-degree vertex.
For the derived Eulerian cycle roads network, we decide the Eulerian cycle roads gritting sequence plan which starts and ends on the same starting vertex and visits every edge exactly once. For real experimental data, the proposed algorithm can be get the same solution as linear programming (LP).
While LP performs optimization process in the Eulerian cycle finding process in order to find the additional roads need to Eulerian cycle, the proposed algorithm has a unnecessary merit of optimization process because of this algorithm decides the additional roads beforehand for Eulerian cycle.
Notwithstanding linear time complexity, this algorithm is more simple than linear programming and can be gets the identical solution of linear programming.

참고자료

· 없음