胡小文，韓劍輝，黃弘毅，韓飛馳，劉宏昕，曹雨琛

（哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080）

互聯(lián)網(wǎng)的發(fā)展以及人們生活水平的提高，催生了眾多新型行業(yè)，外賣就是最近幾年一個(gè)典型的例子。這幾年外賣行業(yè)交易額以及用戶規(guī)模增長迅速，CNNIC發(fā)布的第44次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示[1]，如圖1所示，截至2019年6月，中國網(wǎng)上外賣用戶規(guī)模達(dá)4.21億，并且呈現(xiàn)出逐年升高的趨勢。

圖1 2015-2019年外賣行業(yè)市場行情

數(shù)據(jù)顯示，2019年外賣銷售額占餐飲業(yè)銷售額的82%。由于外賣的便利性，種類繁多等諸多優(yōu)點(diǎn)，其在學(xué)生群體中受歡迎程度越來越高。雖然受2020年疫情的影響，外賣行業(yè)銷售額有所減少，但是仍不影響其在餐飲行業(yè)所占的比重。雖然外賣業(yè)蓬勃發(fā)展，但由此衍生出來的社會(huì)問題卻讓人詬病已久。特別是在校園等地，“最后一公里”的配送是一個(gè)亟待解決的問題[2]。

1 系統(tǒng)的功能描述

本系統(tǒng)實(shí)現(xiàn)校園內(nèi)外賣自動(dòng)配送，解決校園外賣配送“最后一公里”問題。首先，外賣送餐員將外賣放置到指定的餐盒中，并在車載觸摸屏上輸入取餐信息。待所有餐盒都裝滿外賣或者達(dá)到最大等待時(shí)間后，利用路徑規(guī)劃算法，送餐機(jī)器人將餐食依次送到指定地點(diǎn)，并且通過阿里云向用戶發(fā)送短信，通知用戶到指定地點(diǎn)取餐，并通過掃描屏幕上的二維碼或者輸入取餐碼來打開餐盒上的鎖，如圖2所示，完成取餐。待所有外賣都被取走之后，機(jī)器人回到起點(diǎn)，等待下一次送餐。

圖2 機(jī)器人取餐界面

2 整體設(shè)計(jì)

整個(gè)系統(tǒng)的硬件框圖如圖3所示。主控板收集GPS和各種傳感器采集到的數(shù)據(jù)，通過串口發(fā)送給上位機(jī)；通過顯示界面引導(dǎo)快遞員輸入取餐人信息，并通過4G DTU模塊將部分?jǐn)?shù)據(jù)存儲(chǔ)到阿里云RDS數(shù)據(jù)庫和物聯(lián)網(wǎng)平臺(tái)；上位機(jī)匯總各種傳感器數(shù)據(jù)以及激光雷達(dá)和攝像頭采集到的數(shù)據(jù)，通過高效的路徑規(guī)劃算法，通過串口向主控板發(fā)送行駛指令，控制機(jī)器人行駛。

圖3 送餐機(jī)器人硬件框圖

本文利用PyQt5[3]，設(shè)計(jì)顯示在觸摸屏上的用戶界面。如圖4（a）所示，存界面引導(dǎo)送餐員輸入用戶信息；如圖4（b）所示，取界面引導(dǎo)用戶取餐。

圖4 用戶界面

通過對stm32系列、51系列和arduino系列等各個(gè)系列的模塊比較，綜合考慮各種芯片的各項(xiàng)指標(biāo)之后，決定選用arduino作為主控板。上位機(jī)選擇搭載具有較小內(nèi)核且適用于安全操作的Linux系統(tǒng)，通過串口與各個(gè)模塊之間傳輸數(shù)據(jù)。

本地與云端數(shù)據(jù)通信部分，通過4G DTU模塊，基于MQTT協(xié)議[4]，將本地?cái)?shù)據(jù)傳輸?shù)桨⒗镌莆锫?lián)網(wǎng)平臺(tái)和RDS數(shù)據(jù)庫實(shí)現(xiàn)數(shù)據(jù)的可視化[5]和云端存儲(chǔ)。

在路徑規(guī)劃算法設(shè)計(jì)方面，傳統(tǒng)的算法主要有廣度優(yōu)先搜索（BFS）、深度優(yōu)點(diǎn)搜索（DFS）、Dijkstra算法和A*的算法等?，F(xiàn)在主流的路徑規(guī)劃算法包括蟻群算法[6]、slam算法[7]、遺傳算法[8]。通過考慮綜合因素，決定選用蟻群算法來進(jìn)行路徑規(guī)劃。

3 基于蟻群算法的路徑規(guī)劃算法的設(shè)計(jì)

校園內(nèi)外賣配送是一個(gè)很典型的TSP問題，針對不同的使用環(huán)境，蟻群算法可以很好地解決這個(gè)問題。

蟻群算法（ant colony algorithm）是一種啟發(fā)式的隨機(jī)搜索算法，模擬螞蟻合作覓食行為的性質(zhì)來尋找從蟻巢出發(fā)經(jīng)過所有食物源并回到蟻巢的最佳路徑。自然環(huán)境下，螞蟻群體出去覓食，當(dāng)它們第一次遇到分叉路口時(shí)，會(huì)隨機(jī)選擇一個(gè)方向，并在行走路線上留下一種特殊的物質(zhì)——信息素（pheromone）。信息素會(huì)隨著時(shí)間揮發(fā)掉，當(dāng)?shù)诙晃浵伒竭@個(gè)分叉路口的時(shí)候，會(huì)選擇信息素濃度較高的路線，這樣就形成了一種正反饋，當(dāng)行走的螞蟻數(shù)量足夠多的時(shí)候，最佳的行走路徑上信息素濃度最高。

蟻群算法就是模擬現(xiàn)實(shí)中螞蟻覓食的情況，通過不斷更新路徑上的信息素來求解最短路徑，其算法流程如圖5所示。

圖5 蟻群算法流程圖

4 實(shí)驗(yàn)分析

為了驗(yàn)證蟻群算法的迭代速度以及迭代準(zhǔn)確率等是否適用于校園內(nèi)的外賣配送路徑規(guī)劃，通過實(shí)地調(diào)研校園內(nèi)的環(huán)境，設(shè)置了25個(gè)校園內(nèi)外賣取餐點(diǎn)，根據(jù)相對坐標(biāo)使用python語言生成坐標(biāo)點(diǎn)并使用tkinter庫實(shí)現(xiàn)可視化，效果如圖6（a）所示。

圖6 蟻群算法實(shí)驗(yàn)結(jié)果圖

使用蟻群算法，可以得到迭代次數(shù)以及最佳距離如表1所示，得到的最佳路徑如圖6（b）所示，完全可以應(yīng)用于校園內(nèi)外賣配送的路徑規(guī)劃。

表1 蟻群算法迭代次數(shù)及其最佳路徑總距離

5 結(jié)束語

本文描述了一種校園內(nèi)外賣自動(dòng)配送的設(shè)計(jì)方案，旨在解決外賣配送“最后一公里”問題。本文是以校園內(nèi)外賣配送為基礎(chǔ)進(jìn)行設(shè)計(jì)開發(fā)，但其使用范圍不僅僅是校園內(nèi)，在小區(qū)、醫(yī)院內(nèi)同樣適用。但由于本文使用的是蟻群算法來進(jìn)行路徑規(guī)劃，當(dāng)外賣取餐點(diǎn)較多時(shí)，其迭代速度會(huì)很慢而且容易陷入局部最優(yōu)解的情況，這是未來設(shè)計(jì)過程中需要克服的一大難題。