移動端無人機配送任務調度與APP 設計

陳佳慧

（北京物資學院，北京101149）

1 概述

當今經濟的快速發展使得人們對物質的需求逐漸提高，網絡在人們的日常生活中也扮演著不可或缺的角色。在電子商務的蓬勃發展與跨境電商的大勢興起的今天，網上購物這種方便快捷的購物模式不斷吸引著越來越多的人群。線上購物，線下配送早已成為我們的生活中必不可少的重要內容[1]。然而，在人們對網上購物的熱情不斷高漲的同時，消費者對物流末端配送的不滿也有所增加。配送訂單數量的增漲將給物流配送行業帶來極大的壓力，在目前的物流末端配送的環境中，存在很多如人工交貨延遲率很高，偏遠地區難度高，物流成本逐年增加等問題。物流配送市場越來越迫切的需要便捷、高效、現代化的物流配送方式，結合當下行業背景，無人機配送的發展早已成為解決該問題的不二之選[2]。移動端無人機配送系統APP 配送任務調度功能的實現，不僅可以通過合理指派調度無人機配送任務來提高配送效率，還能使業務人員在移動端有效且直觀的掌握配送訂單任務調度的進行情況。

本文針對無人機配送任務調度問題，以無人機配送成本最低為原則，以選擇最佳調度方案為目的，結合匈牙利算法對配送任務進行合理調度指派，在Eclipse+ADT 開發環境下集成Android SDK 與百度地圖API，并運用Java 語言嵌入算法代碼對APP 中配送任務調、訂單信息查詢等功能進行設計。

2 無人機配送任務調度相關理論

2.1 指派問題與匈牙利算法

在任務調度指派問題中，我們給出一個可行的指派方案，即一個匹配。選擇這樣的邊數最大的子集稱為二分圖中的最大匹配問題，如果這個匹配是最優的，就是求解得到的最大匹配。而所謂經典的任務指派（AP）問題（也稱為資源合理配置問題或最優配置問題）通常是指設有n 項工作，要由m 個人來承擔，由于每個人對于同一份工作的工作能力不同，所以不同的人能勝任不同的工作。存在m 個人申請這項工作的情況，但每個工作只能由一個人承擔，且每個人只能承擔一個工作。根據工作效率、產生的成本等為衡量標準，來匹配出最優的工作與人的組合，使得工作總效率最高。雖然指派問題可以當作0-1 規劃問題隱枚舉法求解，但其局限性就在于，當問題中樣本太大時，無法通過枚舉法求解，因此對于這類問題的解決，我們往往選擇更有效的方法——匈牙利算法進行求解。需要注意的是，基于匈牙利算法求解該問題時，必須具有三個運算前提：目標函數求最小值、人數m 與任務數n 相等以及效率非負[4]。

2.2 問題描述與模型建立

本文將做出如下假設：系統中的無人機配送中心具有滿足用戶需求的儲備能力；無人機配送采取一單一往返的模式配送，飛行路徑僅考慮配送地址與配送中心的直線距離，且無人機往返距離相同；配送范圍為以配送中心為圓心的半徑5 公里區域內。

其中，定義決策變量xij：

在（1）式中，當xij為1 時，表示無人機Ui將由配送中心飛去配送地址j；否則值為0。

給出目標函數：

（2）式表示無人機在配送時總配送效率最小，式中Cij為無人機從配送中心飛往配送地址再返回的配送成本效率。

對于這一目標函數，本文做出以下約束條件：

a.一架無人機只能服務一個訂單，見（3）式；

b.每一個配送訂單任務只能接受一架無人機的服務，見（4）式；

c.每個配送地址可以接受多個無人機服務，見（5）式；

d.第i 架無人機在配送第j 個訂單任務時，配送成本效率計算需考慮無人機載物配送與空載返回站點情況，見（6）式；

表達如下：

配送中心所配備的無人機集合{U}中，無人機編號為{U1,U2,U3…U10}共10 架不同類型的輕型載物無人機；無人機配送集合次數N，即{1,2,3…n}；配送地點集合P={P1,P2…Pn}；無人機配送單位成本Ci；單程飛行距離li；無人機自重記為Mi；包裹重量記為mj；Yoin表示無人機i 由配送中心o 駛向配送地址n 的次數。模型中所涉及的包裹重量與配送距離數據需要從無人機配送系統APP 中訂單信息模塊獲取。所配送的貨物僅考慮如3C 類等高價值產品（貨物自重在5kg 以內），配送中心所配備的無人機類型均為輕型載貨無人機（參考零度智控ZERO 系列，續航能力30 分鐘，機身自重6.5kg）。

3 無人機配送任務調度APP 相關模塊設計

3.1 無人機配送系統Android 客戶端概要設計

本文基于移動端無人機配送系統選擇EclipseNeon.3 集成框架進行環境開發[3]，當業務人員使用本文所設計的移動端無人機配送系統APP 時，可以通過創建訂單輸入訂單信息，APP端會根據輸入信息匹配出適合配送該訂單的無人機進行配送，同時可以查看配送狀態與配送路徑等功能，相關操作流程如下圖1 所示：

圖1 客戶端操作業務流程圖

3.2 無人機配送系統APP 端各模塊設計

用戶登錄功能模塊開發：這一模塊的設計用于業務人員在移動端APP 注冊登錄成功后，進入主功能界面，便于使用后續功能。模塊包括登錄、注冊、忘記密碼3 個功能。

百度地圖功能模塊開發：首先打開百度地圖開發平臺，在網頁導航欄中的開發文檔中選擇Android 地圖開發SDK，注冊成為百度地圖開發者，獲取密鑰后將百度地圖API 集成在APP 項目中，即可獲得使用百度地圖。定位顯示由MapBaiduActivity.Java 文件控制，通過從百度地圖坐標拾取系統獲取的配送中心的坐標與定位的目的地坐標(lat, lon)，調用嵌入的地圖SDK 獲取坐標經緯度并計算兩個位置點的直線距離即可顯示配送路徑[5]。

無人機功能模塊開發：無人機顯示頁面中含有標題欄“無人機型號”與添加按鈕，主界面顯示形式為Listview，Listview 中的無人機數據來源于在后臺數據存儲文件。

無人機配送任務調度功能模塊開發：在UAVTask.java 文件中存放匈牙利算法的整體代碼，在UAVSchedule.java 中存放模型中的約束條件相關代碼，UAVService.java 文件中存放無人機的相關數據設置如無人機自重等。當用戶在APP 端輸入訂單信息保存后，被添加的訂單數據信息保存至數據庫并回調讀取[6]，UAVSchedule.java 文件代碼獲取數據的同時，連接UAVService.java 文件與bean 類文件對數據與數據屬性進行讀取后，按照匈牙利算法運算規則代碼計算矩陣效率值。在UAVTask.java 中用接入UAVSchedule.java 使用計算并輸出結果，在訂單詳情界面中輸出訂單任務與無人機型號匹配結果。

4 結論

本文對無人機配送任務調度問題結合匈牙利算法做出簡要分析，并設計無人機配送APP 進行配送任務調度與狀態查詢等功能的開發。盡管無人機配送發展道路上還存在著如政策缺失、維護成本高等問題，但無人機配送具有的獨特優勢使其再一次成為行業內的焦點話題，無人機配送的發展已經迎來新的市場與機遇。