基于GIS技术和加权kNN算法的实时揽件调度方法

应 毅，任 凯，刘亚军

1.三江学院 计算机科学与工程学院，南京 210012

2.南京大学 金陵学院，南京 210089

3.东南大学 计算机科学与工程学院，南京 210096

1 引言

随着信息通信技术的快速发展和基于互联网/移动互联网的各类应用的普及，以商品购销为核心的电子商务逐渐成为经济增长的新亮点。第三方物流是为电子商务活动提供物流服务的基础设施，其基本流程由仓储系统、运输主干网、“最后一公里”配送三个阶段组成[1]。

在物流末端的配送服务中，快递人员从网点出发，沿预先设置好的路径将快件派送到客户手中，同时从客户手中接收快件，最后将所有收件返回网点。在此情况下，快递人员频繁往返于客户和网点之间。该问题在理论上可归类为车辆路径问题（Vehicle Routing Problem，VRP）的应用。VRP 在 1959 年首次被提出[2]，现已广泛应用在分拨中心（仓库/集散地）之间的车辆调度和路径安排上。

物流管理尤其是物流配送过程对地理空间信息有着较强的依赖性，地理信息系统（Geographic Information System，GIS）[3]具备地理空间信息分析处理能力，能在获取、存储相关数据的基础上进行有效加工，帮助决策。在移动操作系统、3G/4G 通信网络和GPS 的支持下，基于位置服务（Location Based Service，LBS）越来越完善，结合GIS/移动GIS[4]，构成智慧物流建设的关键技术。文献[5]结合GIS手段和SPSS分析对模拟退火算法改进来求解VRP问题。文献[6]提出一种结合GIS模型约束的启发式-模拟退火混合搜索算法解决VRP 问题。文献[7]设计了GPS/GIS 协同下的智能车辆监控和调度系统，构建了基于实时信息且带时间窗的动态VRP 混合整数规划模型。文献[8]将3G技术运用于配送管理，设计了一个物流配送系统模型。文献[9]将Dijkstra算法与WebGIS相结合，调用pgRouting实现起始点定位查询最短路径的方法。文献[10]结合MapGIS的网络分析功能，探讨城市配送中心选址及路径优化问题。以上研究皆是依托GIS技术对传统VRP求解的扩充和优化，但物流末端的揽送混合业务与单纯的投递业务又有较大不同，揽送混合业务的目标是快速响应客户的寄件请求并保证行驶距离最短。针对此问题，本文在ArcGIS 平台基础上，构建智能物流信息系统，考虑寄件请求的动态性和任务调度的实时性，提出基于加权kNN 的实时揽件调度算法，实现快递人员的揽件调度。实验证明这种利用GIS技术和数据挖掘算法的人员调度方法，能更快地响应客户需求，更好地缩短行驶距离，有效提高末端物流的配送效率。

本文首先阐述了智能物流信息系统的架构设计；在此框架下，详述了实时揽件调度算法的原理和具体实现；最后在菜鸟驿站某网点的配送活动中进行算法实验和应用。

2 智能物流信息系统架构与实现

现代物流系统是在智能交通和信息技术的基础上运作的物流服务体系，通过对各物流环节的信息采集和数据处理，为物流企业和客户提供高效管理和高质量服务。本文基于GIS 技术、Web 技术和移动开发技术，构建了针对“最后一公里”配送的智能物流信息系统。

2.1 基于ArcGIS的智能物流信息系统架构

智能物流信息系统采用三层架构体系，由应用服务层、业务逻辑层、物流数据层组成。如图1 所示。系统整体基于Java语言和Esri ArcGIS 10.4开发实现。

图1 智能物流信息系统架构

业务逻辑层是本系统的核心，包含Web Server 和ArcGIS Server两部分，Web Server由传统的Java EE服务器JBoss和ArcGIS Web Adaptor组成。Web Adaptor组件使ArcGIS Server 和传统的Web 服务器相结合，提供更丰富的功能和更高的安全性（例如用户鉴权），Web Adaptor 是GIS 服务使用者的单一入口，接收客户端的请求，然后把请求转发给站点内的ArcGIS Server。与GIS 相关的服务由ArcGIS Server 负责提供，如：空间数据管理、地图可视化、路径分析等。

在应用服务层，ArcGIS for Desktop[11]是GIS资源（如地图）的创建者，并通过ArcMap 连接到ArcGIS Server将本地资源发布为Web 服务。ArcMap 是ArcGIS for Desktop中一个主要程序，具有基于地图的所有功能，包括地图制作、地理数据分析和编辑等。调度管理和移动终端是GIS服务的使用者和消费者，其中移动终端是物流配送人员的手持设备。

物流数据层完成数据的存储功能。地理数据对象在Oracle数据库中以表的形式保存；MySQL为Java EE应用存储系统的普通业务数据（如客户信息）。

2.2 智能物流信息系统的关键技术实现

（1）ArcGIS网络分析与二次开发

传统VRP 模型的搜索网络图比较简单，是以客户为节点、已知最短路径为边的无向图。基于GIS的VRP问题的搜索网络图由客户节点、路径节点和路径共同构成，还需考虑实际道路的通行限制（如单向/双向行驶、道路通行能力）。因此，GIS 环境下的VRP 模型更加贴合实际情况，也更加复杂。

GeoProcessing Service（地理处理服务）可以将自定义的各种分析处理模型发布为Web 服务。智能物流信息系统中针对派件/揽件业务的智能调度算法即通过GeoProcessing 组件的二次开发来实现，其中ArcGISNetwork Analyst扩展模块具有交通路网分析功能，可以求解实际道路的最短路径问题，求解过程是在Dijkstra算法基础上的效率优化改进。

（2）移动终端的实时定位和跟踪

移动终端主要针对Android 操作系统，以ArcGIS Runtime SDK for Android 为开发框架。Android 自身提供了三种定位方式：GPS定位、网络定位、基于基站的定位。移动终端每隔指定的时间（例如30 s）通过移动通信网络向物流系统报告一次定位信息，信息内容包括：经度/纬度、车辆速度、行驶方向、上报时间等。物流系统实时接收所有终端定时上报的位置信息，依托ArcGIS的地图服务可将这些位置数据反映在电子地图上，方便监控物流车辆的运行轨迹和配送人员的活动情况。

（3）移动端功能实现

移动端APP为配送人员提供上报位置信息、接收调度指令等物流服务功能。ArcGIS对微软Bing在线地图支持较好，但Bing地图要素精度较差，地址尤其是街道、小路标注不够详细，故选择国内高德地图。通过PcArc-BruTile 插件[12]在 ArcMap 中加载高德地图为 BaseMap，制作矢量数据、配置符号化显示、属性域等信息，发布FeatureServer 至ArcGIS Server，开启同步功能。ArcGIS Runtime SDK for Android 支持完全离线，移动端APP访问FeatureServer，下载离线地图数据。

2.3 智能物流业务流程

（1）大多数业务由调度管理或移动端应用（APP、微信小程序）触发。

（2）ArcGIS Server收到服务请求后，收集位置信息（包括网点、快递员、客户），按需进行地址定位服务。定位服务是利用全国邮政协定将地址转换成地理位置的方法，通过地址定位服务才可以由输入地址信息找到地图上对应的feature点，但是鉴于国内地理编码工作还不完善，地名数据库仅达到根据地名返回坐标范围的程度，所以使用了自开发的地名地址检索组件[13]。

（3）ArcGIS Server以地理位置作为输入数据，调用GeoProcessing 的路径查询服务或二次开发的智能调度算法，进行地理数据的分析处理。

（4）将处理结果转化成栅格格式数据，通过HTTP协议反馈给调度管理Web端或移动端APP。

（5）各客户端通过浏览器或ArcGIS 内置插件将ArcGIS Server提供的服务呈现出来。

3 实时揽件调度算法

当前，大多数网点的派件和揽件业务混合在一起由快递人员完成。基于成本考虑，快递人员会根据经验预先设置好送件路径，但有些寄件业务是实时发生的。而且，在一个区域内，会同时有若干个快递人员在工作。调度哪一个快递人员前去揽件，在某种程度上决定了物流成本的高低。

直观上看，快递人员距离客户的远近决定了收件是否及时。可以将客户视为kNN 算法中的未知样本，所有快递人员看作训练样本，调度最合适快递人员即为寻找最接近新样本的1个训练样本。

3.1 kNN分类算法理论

最近邻分类法（Nearest Neighbor Classifier）[14]基于类比学习，通过将给定的检验样本与和它相似的训练样本进行比较来学习。当给定一个未知样本时，kNN搜索模式空间，找出最接近未知样本的k个训练样本，这k个训练样本是未知样本的k个“最近邻”[15]。当k=1 时，未知样本被指派到模式空间中最接近它的训练样本所在的类。

世界是五彩缤纷的，色彩存在于人类生活的每一个空间，色彩既可以装点生活，美化环境，给人以美的享受，也是社会发展和人类精神文明的一种体现。色彩具有很强的心理作用,每一种颜色都具有特殊的心理作用，影响人的温度知觉，给人错落有致的节奏感，在园林景观设计中，色彩最容易将人的视觉美感激发起来，最明朗的体现园林景观的特色，作为园林景观的重要组成部分，色彩景观的妥善处理具有十分重要的意义。

3.2 基于加权kNN的实时揽件调度算法

作为一种惰性学习方法，kNN算法直到有样本需要分类时才建立分类模型，逐个计算与训练样本的相似程度，相似程度一般以样本间的距离作为评判指标。

传统kNN 算法对所有训练样本同等对待，但揽件调度的分类过程不仅要考虑实际距离，还要考虑快递人员是否顺路、当前道路状况等因素。因此，使用加权kNN 算法对训练样本赋予不同的权值以体现其贡献度的高低[16]。一般做法是将距离转换为权值，较近的训练样本被赋予较大的权值。

令di为训练样本i与未知样本x的距离，wi代表其权重，加权kNN 算法最简单的形式是返回距离的倒数，即wi=1/di。但倒数形式使得近邻的样本权重很大，稍远一点的样本权重又衰减迅速。高斯函数克服了倒数函数的缺点，在距离为0时权重为1，随着距离的增加，权重逐渐减小，但衰减不会过快，且保证衰减不会为0。其形式为：

同时，设置惩罚因子δ，通过快递人员的行驶方向是否与寄件人地址一致来调整样本权值的计算。定义如下：

经惩罚因子δ调整后的权值计算公式为：

计算所有训练样本的wi′，wi′最大的训练样本即为最合适的揽件人员。

在智能物流信息系统的基础上，结合加权kNN 算法的实时揽件调度过程如下：

（1）客户下单触发揽件调度任务，将寄件人地址通过地名地址检索技术转换为位置信息。

（2）利用GPS/4G 定位技术通过移动端APP 的定时上报功能得到各快递人员的位置信息。

（3）调用 ArcGIS GeoProcessing 的NAServer 模块，计算各快递人员与寄件人在道路网络中的实际最短距离di。

（4）根据di和快递人员的方向信息执行加权kNN算法计算wi′，选择最合适的揽件人员，发送调度指令。

整个流程如图2所示。

图2 实时揽件调度执行流程

4 应用实例

4.1 实验区域概况

菜鸟驿站莫愁新寓网点为客户提供自助提货和送件、收件等门到门服务。网点配送范围为汉北街、北圩路、水西门大街、莫愁湖西路、汉中门大街构成的四边形区域，区域面积大约0.4 km2，服务莫愁新寓、劲顺花园、金贸新寓、金基唐城等居民小区，服务人口约3.2 万人。区域内住宅小区多，人口密度大，对物流服务质量要求高，通过对网点实际配送情况的调研，将本文设计的智能物流信息系统进行应用，取得了较为成功的效果。

4.2 电子地图制作

城市道路网在电子地图中的表现形式为数字化的矢量地图，GIS 中矢量地图是按照图层组织的，每个图层存放一类专题或一类信息，它由点、线、面等空间对象的集合组成。本次实验所需的电子地图制作流程如下：

（1）以高德地图南京市鼓楼区地图为基础，使用ArcMAP建立配送区域的矢量地图底图（BaseMap）。

（2）制作道路图层，用于描述道路的地理静态信息，如通行车辆限制、单行/双行、平交/立交，这在NAServer模块计算最短路径时具有实际作用。

（3）制作网点和客户图层，标注网点和主要客户的经度/纬度数据，经纬度数据可以通过定位仪器实地勘测或高德地图抓取（例如网点门店地理坐标为32°03′86″N，118°75′59″E；金贸新寓西北门坐标为 32°03′97″N，118°76′16″E）。实际应用时，由于许多客户距离主干道有一定距离，如小区内的住户，车辆在小区内行驶不存在优化空间。因此，对于非临街客户点，简化的处理方法是将其映射到路边。这个映射过程由地名地址检索组件完成。

4.3 实验结果分析

网点共有4 名快递服务人员，根据业务繁忙情况，一般有2～3人进行上门服务。图3显示了一次快递人员揽件调度的移动端推送结果。表1 罗列了2019 年2 月25日上午的实际揽件情况。数据表明，快递人员每一次揽件行驶300～800 m不等，城市道路中电动自行车的行驶速度大约是20 km/h，故一次揽件的服务响应时间不超过5 min。

图3 揽件调度移动端推送结果

表1 2月25日上午的实际揽件情况

表2统计了2019年2月底至3月初网点整体的上门揽件情况。由于服务区域大多为居民小区，揽件需求明显呈现出节假日偏多的特性。15天共上门揽件447件，快递人员共行驶310 249 m，平均一次揽件行驶近700 m。根据行业报告[17]，单个收件包裹行驶1 km左右。与此相比，实时揽件调度方法降低了30%的行驶距离。

为了衡量新方法的有效性和优越性，将本文提出的基于加权kNN的实时揽件调度算法与基于预知时间的快递车辆揽件路径模型[18]进行了对比实验。以表1所示的2月25日上午的实际情况作为实验数据，假设有2名快递人员进行配送服务，初始时刻快递人员位于网点。根据客户的寄件需求，基于预知时间的快递车辆揽件路径模型规划出2条揽件路线，对路线结果在智能物流信息系统中统计总行驶距离，与基于加权kNN 的实时揽件调度算法的实际距离进行比较，如表3所示。

表2 网点整体揽件情况（15天）

表3 两种算法计算结果对比m

分析数据可知，基于预知时间的快递车辆揽件路径模型在未考虑实时性的前提下，即寄件需求全部提前知晓，规划出的总行驶距离为5 650 m，基于加权kNN 的实时揽件调度算法指派快递人员的实际行驶距离为5 171 m，后者比前者有8.5%的距离优化。由此可见，相比传统算法，本文设计的实时揽件调度方法，有效缩短揽件路程，节省了上门服务的时间和成本。

5 结束语

现代物流系统已经进入了信息化、网络化、智能化的发展阶段。本文利用ArcGIS、Android、GPS等关键技术构建了适用于物流末端配送业务的智能物流信息系统。在该系统中改进加权kNN分类算法应用于快递人员的实时揽件调度，实现了调度结果在移动端APP上的可视化推送。通过实验验证了算法的正确性与GIS 技术在物流行业中应用模式的有效性，提高了物流信息的管理效率。寄件订单的并单处理和人员调度是进一步研究的重点，在智能系统下改进传统VRP 模型进行送件路径规划也是一个较好的研究方向。