基于启发式搜索的快递员配送路径规划Android端设计与实现

徐易杰，夏小云，袁建中，庄鹤林，刘会娟，刘一卓

（嘉兴学院数理与信息工程学院，嘉兴 314001）

0 引言

随着互联网的快速发展和信息技术的不断演变，电子商务已经进入密集创新和快速扩张的阶段，成为我国新兴产业的重要组成部分，极大地影响和改变着人们的生活生产方式。在电子商务飞速发展的背景下，对快递业的发展也产生了深远的影响。2018年，全国快递包裹量突破500亿件，快递从业人员超过300万。根据国家邮政局统计数据，“十二五”期间国内快递业务量连续5年保持50%左右的高速增长，邮政业发展“十三五”规划预计，2018年至2020年快递业务量复合增长率为19.5%。

然而，当前快递产业的发展仍然落后于电子商务爆炸式增长的需求，不断增长的业务量给物流运输行业终端带来极大的配送压力。快递企业也逐渐认识到，要想获得绝对的竞争优势，必须要在最短的时间内，花费最低的成本，给顾客提供最好的产品和服务[1]。

近年来，研究人员从理论的角度研究了物流配送车辆路径问题，如考虑交通拥堵情况[2]、考虑驾驶员满意度[3]等。这类问题考虑了配送过程中的一些特殊情况，但是还不能用于实际应用中。此外，有学者研究了路径规划的搜索算法，分析比较了混合搜索算法[4]、遗传算法[5]等在路径规划中的应用。物流配送问题已成为当前物流行业研究的热点领域，非常有必要开发一款针对快递员的自动配送路径规划软件，快递员可以通过Android手机端App自动获取配送任务，根据自动规划好的路线进行快递配送。

1 问题描述及数学模型

智慧物流配送路径规划问题是物流系统中最受关注的问题之一。该问题自提出之后就受到物流科学、运筹学、计算机科学等相关学科的学者和研究人员的广泛关注，成为运筹学与组合优化领域的前沿与热点研究问题，也是一直困扰学术界和工业界的难题。快递配送路径规划问题可以建模为一个带约束的优化问题，是一类NP-难问题，传统的优化算法设计复杂、收敛速度慢、且不易找到较优解。路径规划问题可以描述为给定一定数量的配送车辆或快递员，以及已知的客户数量及位置，在满足需要的约束条件之下，要求从配送中心由快递员将商品送到不同的客户手中。目标是确定一个配送方案，使得快递员的总路程或者总代价最小。基本的物流配送路径规划问题如图1所示。

图1 快递配送路线规划示意图

一般的，我们可以将快递配送路径规划问题表示为一个具有n+1个节点的带全完全图G=(V,E)[6]。其中V=(0,1,2,...,N)为顶点集合，代表客户或者运输点i(i=1,2,...,N)和配送中心 0，E={(i,j)：i≠j}为边的集合。每一条边(i,j)上具有一个非负的权重dij，表示客户i与j之间的距离。客户i的需求为qi，快递员k的最大运输容量为Qk。则物流配送路径规划问题的数学模型描述如下。

其中，N表示客户数，K为车辆数目为由车辆k从客户i运输到客户j的代价。约束以及确保每个客户不被重复服务确保任何一条路径的总需求不能超过快递员的最大运输容量。

需要指出的是，客户或运输点之间的为欧氏距离，可以根据配送点的经纬度进行计算。假定当前派出五名快递员，则需要动态规划五个配送区域。蚁群算法是一种非常有效的启发式搜索算法，在TSP问题、调度问题等NP难问题中获得广泛应用[7]。系统中在服务器端采用蚁群算法自动生成配送路径，然后推送到Android端给快递员分配相应任务。

2 系统分析及设计

整个软件主要分为以下五个模块，每个模块对应的功能如下：

（1）快递数据入库：快递员通过快递扫件入库端对快递扫码入库，并存入订单数据库中。

（2）快递地址逆编码：把数据库里面的快递的地址进行逆编码，将地址转换成经纬度信息，再重新更新数据库，数据库增加经度和纬度字段。

（3）定时任务：每天在规定时间启动任务，对当天订单进行运算。主要是通过经纬度信息和快递员数量并结合算法进行运算，得到配送顺序，将配送顺序以数组的方式存入数据库中。

（4）配送信息获取：快递员打开配送端App，App将通过对应快递员的id查询对应配送路线数据。

（5）路线导航：规划配送路线，将已规划好的路线推送到App上，快递员进行配送时，App将根据已有路线自动导航。

Android客户端采用MVP架构，多模块化设计，代码复用，降低耦合度，提高内聚性。项目的逻辑流程如图2所示。

图2 项目逻辑流程图

3 数据库设计

数据库采用开源MySQL数据库，在数据库中建立四个表，分别为用户表、总订单表、当天订单表、路线规划表。这些数据表是软件的数据基础。

（1）用户表（user）：对注册的快递员用户进行统一管理，包括快递员id、用户名、密码、配送公司、实名及所在配送驿站地址；

（2）总订单表（all_orders）：快递中心对当天所有客户下单所产生的快递订单入库登记表，包括订单id、订单编号、配送地址、收件人、寄件地址、联系方式、下单时间；

（3）当天订单（daily_orders）：快递员对当天的订单进行扫码入库，来源为总订单库。包括订单id、订单编号、配送地址、收件人、寄件地址、联系方式、下单时间；

（4）路线规划表（router_plan）：后端根据当天快递订单及分派快递员进行路线规划，生成配送路线。包括路径方案id、快递员id、规划路线数组。

4 系统功能实现

本节主要介绍系统的具体功能。系统Android端主要是数据采集及数据展示。请求服务器数据接口，获取对应数据，供快递员查看。然后通过数据信息在地图上进行标识，快递员只需查看对应配送点的信息，包括配送路线、收货人姓名、收货人联系方式等。图3为App软件的首页界面，显示当前天气情况，派送所在地点。快递员能够查看派单的历史记录，当前的派送任务等。快递员还能查看所在的快递站点，如图4所示。服务器端根据派送的订单情况，订单所在位置等信息自动计算派送路线，然后推送给Android端供快递员接收派递任务，如图5所示。快递员能够在Android端收到派送任务之后，根据规划好的路线进行快递配送。

5 结语

物流行业是当下热门行业，其存在的物流配送效率低等问题也较为突出。通过研究快递配送路线的合理规划，确实帮助快递小哥寻找最优的配送路线，解决当前快递不快的现象，减少客户因为包裹的迟到而发生的抱怨、负面情绪甚至投诉等现象的发生，真正帮助快递企业树立良好的企业形象，降低快递成本，创造更多价值。实现了快递员配送路线自动规划需求，极大地将快递员从繁琐的任务中解脱出来。软件基于智能手机Android端实现，使用非常方便。不仅能够有效提高物流配送效率，增强客户服务的满意度，减少因客户投诉以及客户退货退款的经济损失，缓解城市交通压力，而且能够减少物流配送过程给环境带来的影响。

图3 App软件首页界面

图4 快递站点列表

图5 快递员配送路线规划示意图