無人機飛行路徑與公共設施配置之最佳化研究

Drone Path Planning and Optimum Location of Public Facilities

黃雋元(CHUN- YUAN HUAMG)

指導教授 ： 周敏貞

嶺東科技大學/資訊學院/資訊科技系碩士班/碩士(2020年)

摘要

現今社會因地狹人稠以至於大樓越蓋越高，人們來往各個摩天大樓之間必須搭乘電梯上上下下，浪費時間且不便利。因此我們利用最小生成樹的演算法規劃大樓間的天橋，因此得到連接所有大樓群的天橋鋪設決策。基於便利的考量與提高工作效率，大樓中的公共設施也採用最小權重支配集的方式分析每棟大樓之需求度，決定公共設施最適合建置的地點。各個公共設施中商品有效的存貨管理能帶給人們更為便利。這裡我們運用馬可夫鏈模型去預測並採用問卷的方式，詢問前次與這次選購的商品品牌來調查消費者長期購買商品的消費模式，並提供各商品的鋪貨比例為參考指標。
隨著科技日新月異，如今已發展出體積更小，且速度更快的高負載高續航的商用無人機(UAV)。由於經濟發展迅速，道路上的車輛愈來愈多，塞車問題已成為配送業者每日面臨的難題。若能使用商用無人機運送貨物，不僅可減少運送人力的成本支出，更可以避開塞車問題，及減少運送過程中的不確定性。送貨到各個公共設施進行鋪貨，我們則希望利用無人機連續運輸貨物的方式。送貨講求的就是速度，尤其有些食用商品是有時效性，所以時間控管非常重要。若能達到最短時間與最短路徑，減少人與人接觸及路途塞車等減緩貨物到達的時間問題。我們利用弗洛伊德演算法(Floydalgorithm)，計算出任意兩個運送地點間的最短航線距離，進而規劃出商用無人機運送到三個地點再返回出發地的最短路徑。

關鍵字

最小生成樹 ； 最小支配集 ； 馬可夫鏈模型 ； 弗洛伊德演算法

並列摘要

A Markov chain is a model of a sequence of events in which the probability of each event depends only on the state attained in the previous event. In our search, we apply the Markov chain in discrete time and we want to apply the Markov chain to predict the proportions of goods. These proportions can he used as indicators of goods.
We want to build the bridges connecting some buildings. Assume that the buildings are the vertices, that means that we have to find a minimum spanning tree. Hence we apply the Prim's algorithm to find a minimum cost spanning tree T. Besides, we also propose an appropriate location for building. We find the minimum cost dominating set to locate the stores. Then we use Markov chain to determine the proportions of goods which are sold in the stores.
UAVs in the present can help survivors in a disaster. They are also used for carrying goods. The distance between two places U and V is the weight of the edge UV. The weight graph is a graph in which every edge has a value associate with it. We want to use Floyd′s Algorithm, which is an efficient algorithm, for finding the shortest distance and shortest path. The UAV’s flight path is the shortest path.

並列關鍵字

minimum cost spanning tree ； minimum dominating set ； Markov chain ； Floyd Algorithm

參考文獻

[1] G. Agnarsson and R. Greenlaw (2007), Graph Theory: Modeling, Applications,and Algorithms. Pearson Press, London.

[2] Gerard Jennhwa Chang (2011), Algorithmic Aspects of Domination in Graphs.

[3] Min-Jen Jou and Jenq-Jong Lin (2018), Algorithms for Weighted Domination Number and Weighted Independent Domination Number of a Tree, International Journal of Contemporary Mathematical Sciences 13, 133–140.

[4] Bang Ye Wu and Kun-Mao Chao (2004), Spanning Trees and Optimization Problems, Chapman & Hall/CRC Press. USA .

[5] 高崑銘、吳信宏、謝俊逸(2005) ，「利用馬可夫鏈模式分析便利商店顧客之消費模式」，價值管理第九期,頁44–50。