Optimal Solution Algorithm for Delivery Problem on Graphs

국문 초록 (Abstract)

그래프에서의 배달문제는 m개의 정점으로 구성된 그래프에서 m개의 서로 다른 속도를 갖는 로봇 에이전트들을 이용하여 배달물을 그래프의 한 노드에서 다른 노드로 배달하는 최소 배달순서를 구하는 문제이다. 본 논문에서는 그래프에서의 배달문제에 대하여 최적해를 계산하는O(㎥n)과 O(㎥) 시간복잡도를 갖는 두 개의 알고리즘을 제안한다. 알고리즘은 그래프의 모든 쌍에 대한 최단경로를 구하는 전처리를 한 후, 최소배달시간이 작은 정점의 순으로 최단배달경로를 구하는 방법으로 개발하였다. 이 문제에서 그래프가 문제를 해결하고자 하는 지형을 반영하고 있다고 하면, 다양한 로봇 에이전트의 배치에 대하여 전처리를 1회만 실행되면 되므로 O(㎥)알고리즘은 실제로 O(㎡n)의 시간복잡도를 갖는다고 할 수 있다.

다국어 초록 (Multilingual Abstract)

The delivery problem on a graph is that of minimizing the object delivery time from one vertex to another vertex on a graph with m vertices using n various speed robot agents. In this paper, we propose two optimal solution algorithms for the delivery problem on a graph with time complexity of O(㎥n) and O(㎥). After preprocessing to obtain the shortest path for all pairs of the graph, our algorithm processed by obtaining the shortest delivery path in the order of the vertices with the least delivery time. Assuming that the graph reflects the terrain on which to solve the problem, our O(㎥) algorithm actually has a time complexity of as O(㎡n) only one preprocessing is required for the various deployment of n robot agents.

목차 (Table of Contents)

• Abstract
• 요약
• I. Introduction
• II. Preliminaries
• III. The Proposed Scheme
• IV. Conclusions
• REFERENCES

참고문헌 (Reference)

1 이광의, "트리에서의 배달문제에 대한 최적해 알고리즘" 한국컴퓨터정보학회 19 (19): 143-150, 2014

2 유견아, "동적 환경에서 그룹 이동을 위한 경로 계획" 한국컴퓨터정보학회 18 (18): 117-126, 2013

3 김형일, "가상지도를 이용한 청소로봇 경로계획" 한국컴퓨터정보학회 14 (14): 31-40, 2009

4 S. M. Lavalle, "Planning Algorithms" Cambridge University Press 2006

5 KwangEui Lee, "Near Optimal Algorithm for Delivery Problem" 11 (11): 25-28, 2011

6 K. Rajchandara, "Multiple Robot Path Planning Algorithms for Static Environment and Dynamic Environment : A Review" 119 (119): 1273-1290, 2018

7 "Motion planning"

8 KwangEui Lee, "Genetic Algorithm for Delivery Problem" 9 (9): 248-251, 2009

9 R. Neapolitan, "Foundations of Algorithms Using C++ Pseudocode" Addison Wesley 2003

10 K. Azarm, "Conflict-Free Motion of Multiple Mobile Robots Based on Decentralized Motion Planning and Negotiation" 4 : 3526-3533, 1997

11 D. K. Liu, "A force field method based multi-robot collaboration" 662-667, 2006

12 Y. Guo, "A distributed and optimal motion planning approach for multiple mobile robots" 2612-2619, 2002