陳佳慧

（北京物資學(xué)院，北京101149）

1 概述

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

本文針對(duì)無(wú)人機(jī)配送任務(wù)調(diào)度問(wèn)題，以無(wú)人機(jī)配送成本最低為原則，以選擇最佳調(diào)度方案為目的，結(jié)合匈牙利算法對(duì)配送任務(wù)進(jìn)行合理調(diào)度指派，在Eclipse+ADT 開(kāi)發(fā)環(huán)境下集成Android SDK 與百度地圖API，并運(yùn)用Java 語(yǔ)言嵌入算法代碼對(duì)APP 中配送任務(wù)調(diào)、訂單信息查詢等功能進(jìn)行設(shè)計(jì)。

2 無(wú)人機(jī)配送任務(wù)調(diào)度相關(guān)理論

2.1 指派問(wèn)題與匈牙利算法

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

2.2 問(wèn)題描述與模型建立

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

其中，定義決策變量xij：

在（1）式中，當(dāng)xij為1 時(shí)，表示無(wú)人機(jī)Ui將由配送中心飛去配送地址j；否則值為0。

給出目標(biāo)函數(shù)：

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

對(duì)于這一目標(biāo)函數(shù)，本文做出以下約束條件：

a.一架無(wú)人機(jī)只能服務(wù)一個(gè)訂單，見(jiàn)（3）式；

b.每一個(gè)配送訂單任務(wù)只能接受一架無(wú)人機(jī)的服務(wù)，見(jiàn)（4）式；

c.每個(gè)配送地址可以接受多個(gè)無(wú)人機(jī)服務(wù)，見(jiàn)（5）式；

d.第i 架無(wú)人機(jī)在配送第j 個(gè)訂單任務(wù)時(shí)，配送成本效率計(jì)算需考慮無(wú)人機(jī)載物配送與空載返回站點(diǎn)情況，見(jiàn)（6）式；

表達(dá)如下：

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

3 無(wú)人機(jī)配送任務(wù)調(diào)度APP 相關(guān)模塊設(shè)計(jì)

3.1 無(wú)人機(jī)配送系統(tǒng)Android 客戶端概要設(shè)計(jì)

本文基于移動(dòng)端無(wú)人機(jī)配送系統(tǒng)選擇EclipseNeon.3 集成框架進(jìn)行環(huán)境開(kāi)發(fā)[3]，當(dāng)業(yè)務(wù)人員使用本文所設(shè)計(jì)的移動(dòng)端無(wú)人機(jī)配送系統(tǒng)APP 時(shí)，可以通過(guò)創(chuàng)建訂單輸入訂單信息，APP端會(huì)根據(jù)輸入信息匹配出適合配送該訂單的無(wú)人機(jī)進(jìn)行配送，同時(shí)可以查看配送狀態(tài)與配送路徑等功能，相關(guān)操作流程如下圖1 所示：

圖1 客戶端操作業(yè)務(wù)流程圖

3.2 無(wú)人機(jī)配送系統(tǒng)APP 端各模塊設(shè)計(jì)

用戶登錄功能模塊開(kāi)發(fā)：這一模塊的設(shè)計(jì)用于業(yè)務(wù)人員在移動(dòng)端APP 注冊(cè)登錄成功后，進(jìn)入主功能界面，便于使用后續(xù)功能。模塊包括登錄、注冊(cè)、忘記密碼3 個(gè)功能。

百度地圖功能模塊開(kāi)發(fā)：首先打開(kāi)百度地圖開(kāi)發(fā)平臺(tái)，在網(wǎng)頁(yè)導(dǎo)航欄中的開(kāi)發(fā)文檔中選擇Android 地圖開(kāi)發(fā)SDK，注冊(cè)成為百度地圖開(kāi)發(fā)者，獲取密鑰后將百度地圖API 集成在APP 項(xiàng)目中，即可獲得使用百度地圖。定位顯示由MapBaiduActivity.Java 文件控制，通過(guò)從百度地圖坐標(biāo)拾取系統(tǒng)獲取的配送中心的坐標(biāo)與定位的目的地坐標(biāo)(lat, lon)，調(diào)用嵌入的地圖SDK 獲取坐標(biāo)經(jīng)緯度并計(jì)算兩個(gè)位置點(diǎn)的直線距離即可顯示配送路徑[5]。

無(wú)人機(jī)功能模塊開(kāi)發(fā)：無(wú)人機(jī)顯示頁(yè)面中含有標(biāo)題欄“無(wú)人機(jī)型號(hào)”與添加按鈕，主界面顯示形式為L(zhǎng)istview，Listview 中的無(wú)人機(jī)數(shù)據(jù)來(lái)源于在后臺(tái)數(shù)據(jù)存儲(chǔ)文件。

無(wú)人機(jī)配送任務(wù)調(diào)度功能模塊開(kāi)發(fā)：在UAVTask.java 文件中存放匈牙利算法的整體代碼，在UAVSchedule.java 中存放模型中的約束條件相關(guān)代碼，UAVService.java 文件中存放無(wú)人機(jī)的相關(guān)數(shù)據(jù)設(shè)置如無(wú)人機(jī)自重等。當(dāng)用戶在APP 端輸入訂單信息保存后，被添加的訂單數(shù)據(jù)信息保存至數(shù)據(jù)庫(kù)并回調(diào)讀取[6]，UAVSchedule.java 文件代碼獲取數(shù)據(jù)的同時(shí)，連接UAVService.java 文件與bean 類(lèi)文件對(duì)數(shù)據(jù)與數(shù)據(jù)屬性進(jìn)行讀取后，按照匈牙利算法運(yùn)算規(guī)則代碼計(jì)算矩陣效率值。在UAVTask.java 中用接入U(xiǎn)AVSchedule.java 使用計(jì)算并輸出結(jié)果，在訂單詳情界面中輸出訂單任務(wù)與無(wú)人機(jī)型號(hào)匹配結(jié)果。

4 結(jié)論

本文對(duì)無(wú)人機(jī)配送任務(wù)調(diào)度問(wèn)題結(jié)合匈牙利算法做出簡(jiǎn)要分析，并設(shè)計(jì)無(wú)人機(jī)配送APP 進(jìn)行配送任務(wù)調(diào)度與狀態(tài)查詢等功能的開(kāi)發(fā)。盡管無(wú)人機(jī)配送發(fā)展道路上還存在著如政策缺失、維護(hù)成本高等問(wèn)題，但無(wú)人機(jī)配送具有的獨(dú)特優(yōu)勢(shì)使其再一次成為行業(yè)內(nèi)的焦點(diǎn)話題，無(wú)人機(jī)配送的發(fā)展已經(jīng)迎來(lái)新的市場(chǎng)與機(jī)遇。