陈佳慧

（北京物资学院，北京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 进行配送任务调度与状态查询等功能的开发。尽管无人机配送发展道路上还存在着如政策缺失、维护成本高等问题，但无人机配送具有的独特优势使其再一次成为行业内的焦点话题，无人机配送的发展已经迎来新的市场与机遇。