胡小文，韩剑辉，黄弘毅，韩飞驰，刘宏昕，曹雨琛
（哈尔滨理工大学 计算机科学与技术学院，黑龙江 哈尔滨 150080）
互联网的发展以及人们生活水平的提高，催生了众多新型行业，外卖就是最近几年一个典型的例子。这几年外卖行业交易额以及用户规模增长迅速，CNNIC发布的第44次《中国互联网络发展状况统计报告》显示[1]，如图1所示，截至2019年6月，中国网上外卖用户规模达4.21亿，并且呈现出逐年升高的趋势。
图1 2015-2019年外卖行业市场行情
数据显示，2019年外卖销售额占餐饮业销售额的82%。由于外卖的便利性，种类繁多等诸多优点，其在学生群体中受欢迎程度越来越高。虽然受2020年疫情的影响，外卖行业销售额有所减少，但是仍不影响其在餐饮行业所占的比重。虽然外卖业蓬勃发展，但由此衍生出来的社会问题却让人诟病已久。特别是在校园等地，“最后一公里”的配送是一个亟待解决的问题[2]。
1 系统的功能描述
本系统实现校园内外卖自动配送，解决校园外卖配送“最后一公里”问题。首先，外卖送餐员将外卖放置到指定的餐盒中，并在车载触摸屏上输入取餐信息。待所有餐盒都装满外卖或者达到最大等待时间后，利用路径规划算法，送餐机器人将餐食依次送到指定地点，并且通过阿里云向用户发送短信，通知用户到指定地点取餐，并通过扫描屏幕上的二维码或者输入取餐码来打开餐盒上的锁，如图2所示，完成取餐。待所有外卖都被取走之后，机器人回到起点，等待下一次送餐。
图2 机器人取餐界面
2 整体设计
整个系统的硬件框图如图3所示。主控板收集GPS和各种传感器采集到的数据，通过串口发送给上位机；通过显示界面引导快递员输入取餐人信息，并通过4G DTU模块将部分数据存储到阿里云RDS数据库和物联网平台；上位机汇总各种传感器数据以及激光雷达和摄像头采集到的数据，通过高效的路径规划算法，通过串口向主控板发送行驶指令，控制机器人行驶。
图3 送餐机器人硬件框图
本文利用PyQt5[3]，设计显示在触摸屏上的用户界面。如图4（a）所示，存界面引导送餐员输入用户信息；如图4（b）所示，取界面引导用户取餐。
图4 用户界面
通过对stm32系列、51系列和arduino系列等各个系列的模块比较，综合考虑各种芯片的各项指标之后，决定选用arduino作为主控板。上位机选择搭载具有较小内核且适用于安全操作的Linux系统，通过串口与各个模块之间传输数据。
本地与云端数据通信部分，通过4G DTU模块，基于MQTT协议[4]，将本地数据传输到阿里云物联网平台和RDS数据库实现数据的可视化[5]和云端存储。
在路径规划算法设计方面，传统的算法主要有广度优先搜索（BFS）、深度优点搜索（DFS）、Dijkstra算法和A*的算法等。现在主流的路径规划算法包括蚁群算法[6]、slam算法[7]、遗传算法[8]。通过考虑综合因素，决定选用蚁群算法来进行路径规划。
3 基于蚁群算法的路径规划算法的设计
校园内外卖配送是一个很典型的TSP问题，针对不同的使用环境，蚁群算法可以很好地解决这个问题。
蚁群算法（ant colony algorithm）是一种启发式的随机搜索算法，模拟蚂蚁合作觅食行为的性质来寻找从蚁巢出发经过所有食物源并回到蚁巢的最佳路径。自然环境下，蚂蚁群体出去觅食，当它们第一次遇到分叉路口时，会随机选择一个方向，并在行走路线上留下一种特殊的物质——信息素（pheromone）。信息素会随着时间挥发掉，当第二只蚂蚁到这个分叉路口的时候，会选择信息素浓度较高的路线，这样就形成了一种正反馈，当行走的蚂蚁数量足够多的时候，最佳的行走路径上信息素浓度最高。
蚁群算法就是模拟现实中蚂蚁觅食的情况，通过不断更新路径上的信息素来求解最短路径，其算法流程如图5所示。
图5 蚁群算法流程图
4 实验分析
为了验证蚁群算法的迭代速度以及迭代准确率等是否适用于校园内的外卖配送路径规划，通过实地调研校园内的环境，设置了25个校园内外卖取餐点，根据相对坐标使用python语言生成坐标点并使用tkinter库实现可视化，效果如图6（a）所示。
图6 蚁群算法实验结果图
使用蚁群算法，可以得到迭代次数以及最佳距离如表1所示，得到的最佳路径如图6（b）所示，完全可以应用于校园内外卖配送的路径规划。
表1 蚁群算法迭代次数及其最佳路径总距离
5 结束语
本文描述了一种校园内外卖自动配送的设计方案，旨在解决外卖配送“最后一公里”问题。本文是以校园内外卖配送为基础进行设计开发，但其使用范围不仅仅是校园内，在小区、医院内同样适用。但由于本文使用的是蚁群算法来进行路径规划，当外卖取餐点较多时，其迭代速度会很慢而且容易陷入局部最优解的情况，这是未来设计过程中需要克服的一大难题。
