基於Dijkstra's演算法結合動態規劃法應用於智慧口罩販賣機物流達到最佳路線配置

Based on Dijkstra's Algorithm Combined with Dynamic Programming Mechanism Applied to Intelligent Mask Vending Machine Logistics Service to Achieve an Optimal Vehicle Routing Path

李驊娟(Hua-Jyuan Li)

指導教授 ： 魯大德

健行科技大學/電資學院/資訊工程系碩士班/碩士(2020年)

摘要

近年來，無人化的經營模式越來越發展，也讓智慧販賣機跟著盛行起來，智慧販賣機的發展實現了無店鋪、無銷售人員的商品銷售模式，其中有許多新型支付的功能，如QR code碼、近距離無線通訊軟體、藍牙以及電子標籤…等，此外由於結合多種行銷手法，而抽獎型販賣機、零食型販賣機、果汁型販賣機…等，掀起了一股流行，但由於智慧販賣機內存貨空間有限，而使得商品配送成本常佔總營運成本的30%以上。而此研究也因應新型冠狀病毒，從而實作一款用於智慧口罩販賣機的最優配送路線規劃。
本研究因應新型冠狀病毒將實作一項以五種演算法進行比較整合出符合智慧口罩販賣機的最優配送路線來進行物流管理規劃，這能使智慧口罩販賣機的配送路線達到最優化，本研究整合Dijkstra's演算法結合動態規劃法，除了能夠改善Google Map因無法多點規劃最短配送路線，而造成重複行走之路線，也可降低物流出車之時間成本，使得配送路線達到最佳化，除了能夠有效降低空氣污染，減少排放廢氣量，也能達到綠色城市的概念。本文中除了一般常見的規劃路線之比較，也增加了一些不可抗之因素，像是天氣之變化(晴天、雨天)以及各個時段(早上、下午、晚上)來進行比較，其優勢能夠減少人力成本，降低缺貨發生率提升物流效率。
本實驗於室外城市所分成的四個區域進行實驗，而此研究主要功能在於透過五種演算法進行規劃，合理分成例行性及即時性配送路線模式，並將實驗結果的各個時間之差異計算出來進行比較，經實例研究發現本研究所提的Dijkstra's演算法結合動態規劃法可迅速規劃合理配送路線，可有效降低智慧口罩販賣機商品之配送成本。

關鍵字

智慧口罩販賣機 ； 最優配送路線規劃 ； 五種演算法 ； Dijkstra's演算法結合動態規劃法

並列摘要

In recent years, the unmanned business model has developed causing smart vending machines to become popular. The development of smart vending machines reflects a product sales model with no stores and no sales staff. There are many payment functions used, such as Quick Response (QR) code, Near-field communication (NFC) software, Bluetooth and electronic tags... etc. In addition, due to the combination of multiple marketing methods, this has set off a trend including lottery vending machines, snack vending machines, juice vending machines, etc. However, due to the limited storage space of smart vending machines, commodity distribution costs often account for more than 30% of the total operating costs.
The Dijkstra's algorithm combined with the dynamic planning method in this study can quickly plan a delivery routing path to reduce the delivery cost of smart mask vending machines effectively. This experiment was conducted in four areas divided into outdoor cities. Unlike Google Maps which is unable to plan the shortest delivery route at multiple points, causing repeated routing paths, this study can reduce the time cost of logistics delivery and optimize the delivery route. In addition to effectively reducing air pollution and reducing emissions, it can also achieve the concept of green city.

並列關鍵字

Smart vending machines ； Optimize the delivery route ； Dijkstra's algorithm ； dynamic planning method

參考文獻

參考文獻

(1) 勵心如、黃家慧(2018 )。自販機i起來 點燃新零售戰火。今周刊1131期, 17-20 January 2020。

(2) Hanna Grzybowska、Briscoe Kerferd、Charles Gretton、S.Travis Waller (2020).A simulation-optimisation genetic algorithm approach to product allocation in vending machine systems. Expert Systems with Applications,Volume 145,Article 113110, 21-23 March 2019.

(3) La Ode Mohamad Zulfiqar, R. Rizal Isnanto, Oky Dwi Nurhayati(2018). Optimal Distribution Route Planning based on Collaboration of Dijkstra and Sweep Algorithm. 2018 10th International Conference on Information Technology and Electrical Engineering (ICITEE) , 02-05 December 2019.

(4) Jing Zhang, Jia Yu, Xiangju Qu, Yu Wu(2017). Path planning for carrier aircraft based on geometry and dijkstra's algorithm. 2017 3rd IEEE International Conference on Control Science and Systems Engineering (ICCSSE) , 12-15 September 2019.