基于聚类和二分图匹配的物流派件调度方法

应 毅,唐 立,刘定一,刘亚军

(1.三江学院 计算机科学与工程学院,江苏 南京 210012;2.会津大学 计算机科学与工程研究生院,日本 会津若松 965-8580;3.东南大学 计算机科学与工程学院,江苏 南京 210096)

随着信息通信技术的快速发展和基于互联网/移动互联网的各类应用的普及,以商品购销为核心的电子商务逐渐成为经济增长的新亮点.电子商务物流的基本流程由仓储系统、运输主干网、“最后1 km”配送3个阶段组成.作为最末端的服务机构,网点在物流网络中承担了包裹的派送和收取任务.快递人员从网点出发,沿预先设置好的路线将包裹递送到客户手中,同时从客户手中接收包裹,最后将所收包裹送回网点.在此情况下,快递人员频繁往返于客户和网点之间.该问题在理论上可使用车辆路径问题(vehicle routing problem,VRP)进行刻画.车辆路径问题在1959年第1次被提出[1],现被广泛应用在物流分拨中心之间的车辆调度和路径安排上.但网点配送服务与分拨中心的VRP又有较大不同,网点服务的客户数量众多,分布在城市的各个大街小巷,在地理位置上相对集中又整体分散.对于大规模VRP的求解可以通过聚类算法缩小问题规模,降低求解难度.文献[2]采用模糊系统聚类方法进行客户分类,运用智能加权集成动态属性生成配送策略.文献[3]考虑地理及环境因素进行区域划分,采用k-means聚类算法进行车辆任务分配.文献[4]结合k-means聚类和模糊聚类划分配送区域,采用遗传算法规划车辆路径.但传统的聚类算法均采用客户之间的直线距离构造计算模型,未融入实际路径信息.

地理信息系统(geographic information system,GIS)具备地理空间信息分析处理能力,能为物流管理尤其是物流配送过程提供地理空间计算支持和决策帮助.文献[5]基于GIS路网描述的数学模型,建立启发式-模拟退火算法进行配送区域划分的求解.文献[6]基于GIS路径数学模型通过模糊聚类算法对物流配送线路进行划分.文献[7]借助GIS软件采用VRPTW模型和禁忌搜索算法获得在交通顺畅和交通拥堵情况下的最优配送路线.但以上研究仅讨论了配送问题求解的距离最短[5-6]或时间最少目标[7],未考虑任务分配的合理性和均衡性.针对此问题,笔者依托ArcGIS平台,构建智能物流信息系统,提出“先分区,后排班”的2阶段调度策略,简单描述如下:首先通过地名地址检索技术将分布密集的“客户面”聚合成“配送点”;然后针对配送任务经济平衡目标,利用k-medoids聚类算法划分派送区域;最后通过基于二分图匹配的派件调度KM(Kuhn-Munkres)算法实现快递人员的工作分配.试验证明这种混合了数据挖掘和图论算法的网点派件调度方法,能使配送区域更加聚集,各快递人员之间的工作分配更加均衡,有效提高末端物流的配送效率.

1 智能物流信息系统架构

现代物流系统是在智能交通和信息技术的基础上运作的物流服务体系,通过对各物流环节的信息采集和数据处理,为物流企业提供高效管理手段,为客户提供高质量的服务.

构建的针对末端配送的智能物流信息系统由物流数据层、业务逻辑层、应用服务层3部分组成,如图1所示.

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

业务逻辑层是本系统的核心,包含Web Server和ArcGIS Server两部分,Web Server由Java EE服务器JBoss和ArcGIS Web Adaptor组成.Web Adaptor组件使ArcGIS Server和传统的Web服务器相结合,它是GIS服务使用者的唯一入口,接收客户端的请求,然后把请求转发给ArcGIS Server.与GIS相关的服务由ArcGIS Server负责提供,如:空间数据管理、地图可视化和路径分析等.

在应用服务层,ArcGIS for Desktop是GIS资源(如电子地图)的创建者,并通过ArcMap(ArcGIS for Desktop中的一个主要程序)连接到ArcGIS Server将本地资源发布为Web服务.调度管理和移动终端是GIS服务的使用者和消费者,移动端APP为快递人员提供上报位置信息、接收调度指令等物流服务功能.

物流数据层负责数据存储:Oracle数据库以表的形式保存地理数据对象;MySQL为Java EE应用存储普通业务数据(如客户信息).

系统整体基于Java语言和Esri ArcGIS 10.4开发实现.主要软件包括:ArcGIS for Server,ArcGIS for Desktop,ArcGIS Run-time SDK for Java,ArcGIS Run-time SDK for Android,Oracle 11g R2.

2 配送区域划分方法

物流末端的配送服务对象是密集分布在某一区域内的众多客户,如果按照一般VRP模型,将众多客户直接作为路网节点进行求解,问题规模将会变得极为庞大,计算复杂耗时.笔者提出“点面聚合,区域聚类”配送目标划分方法,首先通过地名地址检索技术将一些分布较为密集的“客户面”聚合成“配送点”,然后在派件量均衡的原则下利用k-medoids聚类算法划分派送区域.这能较好地降低问题规模,提高调度算法效率.

2.1 点面聚合

电商客户特别是城区客户分布较为密集,经常有众多客户相邻的现象,如同一个小区、同一座写字楼.点面聚合用于合并距离过于接近的客户,它将逻辑上松散的收件地址映射为相同的地理位置,例如“金贸新寓3栋1单元201室”和“金贸新寓7栋2单元302室”都聚合到“金贸新寓西北门”这一地址(地理坐标:32°03′97″N,118°76′16″E).这个映射过程由自开发的地名地址检索组件[8]完成,它基于全文检索引擎Lucene实现,对于模糊查询具有更好的搜索效率和准确性.

2.2 区域聚类

划分法聚类将n个数据对象组织成k个簇(k≤n),使在同一个簇中的对象是相似的,而不同簇中的对象是相异的,算法最终使得每个对象对于簇中心的偏离总和最小.聚类分析的常用划分方法有k-means[9]和k-medoids,其中k-means算法适合发现球状簇且对离群点敏感,考虑到配送区域的一般形状不符合近似圆形,所以适合采用k-medoids算法.对点面聚合后的客户地址使用k-medoids聚类进行配送范围划分,可以使得到的区域比较紧密,并进一步简化问题规模.

k-medoids算法的思想:对n个对象,选择k个对象oi(i=1,2,…,k)作为簇中心对象,剩余的对象根据其与簇中心对象的距离分配给最近的簇,初步形成k个簇Ci(i=1,2,…,k).绝对误差标准E是数据集中所有对象p与簇Ci的代表对象oi的绝对误差之和,定义为

(1)

式中:dist为求距离的函数.

然后反复地用非中心对象orandom来替代簇中心对象oj(j=1,2,…,k),对对象进行重新归类.重新归类会引起E发生变化,可以用成本函数来计算重新归类前后E的变化.成本函数S表示E变化的累计,定义为

(2)

若S为负,说明这种替换能够减少E,oj可以被orandom替换;若S为正,表示oj可接受,本次迭代没有变化.

2.2.1k值的确定

k-medoids算法需要给定簇数k.在“先分区,后排班”方法中,前期的配送区域划分是为了之后的快递人员排班,故k值确定为当日在岗的快递人员数量.

2.2.2初始簇中心的选择

选择合适的初始簇中心对象可以使算法快速收敛,根据以往的物流数据,可以人为指定派送量较大的k个区域中心为初始的簇中心.

2.2.3对象间的距离计算

当前,物流配送领域的聚类算法多采用欧式距离计算对象差异度,不符合实际配送的交通情况,因为有些地址虽然直线距离很近,但之间无路可达,即使被分到同一个簇中也无法提高配送效率.因此,对象间的距离计算要符合城市路网的实际情况.在智能物流信息系统中,ArcGIS Network Analyst模块具有交通路网分析功能,可以求解实际道路的最短路径问题.

2.2.4算法结束条件

k-medoids算法的时间复杂度为O(t×k×n2),其中t为迭代次数,算法效率略低.结合实际应用情况,改进k-medoids算法,利用工作量均衡指标使算法提前结束,优化执行效率.

在实际工作中,不同配送区域之间存在着工作量不均衡的问题,派送量较大的区域需要加班加点完成,快递人员的薪酬收入也与派送量相关.区域间工作量的不均衡影响到配送服务的质量,也带来人员流失等管理问题.需要合理的标准来平衡配送区域的工作负荷,使工作量基本均衡,工作时间大致相同.故以工作周期内(0.5 d或1 d)派件量大体相等作为区域聚类算法结果优劣的衡量标准.

对于划分好的k个簇,计算包裹数Pi(i=1,2,…,k)中的最大值Pmax、最小值Pmin、平均值Pavg,由于划分的目的是使配送区域工作量均衡,即将Pmax和Pmin的差控制在合理范围之内,ε表示可接受的工作量差异,在算法实现中由决策者根据实际情况确定,一般设置为10%～15%.则定义算法的结束条件为

(3)

当此条件满足时,表示当前的簇划分能够满足工作量均衡的条件.

基于k-medoids的配送区域聚类算法如下:

输入:

k,结果簇的个数;

D,包含n个对象的数据集合,每个对象由收件地址的经度/纬度和包裹数构成;

O,k个初始簇中心对象;

ε,可接受的工作量差异.

输出:k个簇的集合.

操作方法如下:

do

调用ArcGIS NAServer,计算剩余对象到k个簇中心对象的实际距离,按照就近原则分配到最近的簇;

计算k个簇的包裹数;

if (Pmax-Pmin)/Pavg≤εthen 得到一个可行解,算法结束;

随机选择一个非簇中心对象orandom;

计算用orandom代替oj后产生的总代价S;

ifS<0 then用orandom代替oj,形成新的簇中心对象集合;

while簇集合不发生变化.

3 派件调度分配算法

图论中的二分图模型在资源分配、工作安排等问题求解中有重要应用,匈牙利算法和KM算法是二分图最大匹配问题的常见解法.在智能交通领域,文献[10]利用二分图构建网约车-客户匹配度.文献[11]采用二分图最大匹配算法求解外卖配送调度问题.文献[12]使用匈牙利算法求解以油耗最小为目标的车辆调度模型.

在物流末端的派件调度中,假设可分配的快递人员为Ri(i=1,2,…,k),待配送区域为Cj(j=1,2,…,k),分别计算每一组分配的代价得分,找出全局最优的“快递人员-配送区域”分配组合,使总代价最低.问题可以转化为传统的完备匹配下的最大权匹配问题:在一个二分图内,左边的快递人员节点集合R,右边的配送区域节点集合C,对于每组左右连接RiCj有权重Wij,即派送代价,求一种匹配使得所有Wij的和最大.常见的二分图权值为1(有边)或0(无边)[12],文中改进权值定义,根据快递人员对配送区域及路况的熟悉程度,定义Wij为

(4)

KM算法通过给每一个顶点一个顶标来将最大权匹配问题求解转换为求二分图完备匹配问题.算法流程如下:① 初始化可行顶标的值;② 用匈牙利算法在相等子图寻找完备匹配;③ 若未找到完备匹配,则修改可行顶标的值,扩充相等子图;④ 重复②、③直到找到相等子图的完备匹配为止.

基于KM算法的派件人员调度分配过程如下:

输入:

k,快递人员/配送区域的个数;

R，快递人员集合(k个);

C，配送区域集合(k个);

Wij，派送代价权重.

输出:快递人员-配送区域最大权二分匹配M.

操作方法如下:

fori← 1 tokdo∥初始化顶标

LCi=0;

forj← 1 tokdo

LRi=max(LRi,Wij);

fori← 1 tokdo

while TRUE do用匈牙利算法寻找完备匹配;

if 找到一个完备匹配then该匹配即为最大权二分匹配,算法结束;

forj← 1 tokdo∥更新顶标

if visRjthenLRj=LRj-INF;

if visCjthenLCj=LCj+INF.

其中:visRj,visCj分别为顶点Rj,Cj被访问过;INF为无穷大.

4 试验及讨论

4.1 试验区域概况

顺丰速运汉北街营业点为客户提供自寄自取和送件、收件等上门服务.网点配送范围为湛江路、龙园南路、凤凰东街、汉中门大街、莫愁湖西路、水西门大街构成的五边形区域,区域面积大约2.56 km2,服务苏城苑、华阳佳园、教工新村、西城岚湾、凤凰熙岸、莫愁新寓等众多居民小区,服务人口约9.5 万人.区域内住宅小区多,人口密度大,对物流服务质量要求高,通过对网点实际配送情况的调研,将设计的“先分区,后排班”派件调度方法应用于该区域,取得了较为成功的效果.

4.2 电子地图制作

城市道路网在电子地图中的表现形式为数字化的矢量地图,GIS中矢量地图按照图层组织,每个图层存放一类专题或一类信息.本次试验所需的电子地图制作步骤如下:① 以高德地图南京市鼓楼区地图为基础,使用ArcMAP建立配送区域的BaseMap;② 制作道路图层,用于描述道路的静态地理信息(如车辆通行限制、路口平交/立交、道路双行/单行),为NAServer模块计算最短路径提供准确数据;③ 制作网点和客户图层,标注网点和主要客户的经纬度数据,经纬度数据可以通过导航定位仪实地勘测或高德地图抓取(如网点门店地理坐标为32°04′07″N,118°75′58″E;苏城南苑西南门坐标为32°04′72″N,118°74′40″E).

4.3 试验结果分析

网点共有12名快递服务人员,根据业务繁忙情况,一般有8～10人进行上门服务.1次快递人员的派件调度指令在移动端APP上推送.

2019年4月1日的实际派件调度情况如表1所示.根据当日在岗快递员数量(k=8),选择西城岚湾、凤凰熙岸、教工新村、华阳佳园等8个包裹量较大或人口较多的小区作为初始簇中心;采用实际道路最短路径计算对象距离(调用ArcGIS NA模块);并设置ε=15%,k-medoids配送区域聚类算法将网点覆盖范围划分为8个配送责任区,并保证派件量大致相等.派件调度KM算法根据快递员对区域和路况的熟悉程度,将8个配送责任区分配给8位快递员.

表1 4月1日的实际派件调度情况

2019年3月22日至4月10日网点整体的派件情况如表2所示,其中从4月1日起网点启用了“先分区,后排班”派件调度方法,派件量差异有明显下降.

表2 网点整体派件情况

为了衡量新方法的有效性和优越性,将提出的“先分区,后排班”2阶段调度算法与基于距离聚类的遗传算法[4]、模糊聚类线路划分算法[6]进行了对比试验.基于距离聚类的遗传算法使用欧拉距离进行k-means聚类,将派送包裹分成k个区域,再使用遗传算法规划k个快递人员的配送路线;模糊聚类线路划分算法基于GIS实际路径通过模糊聚类方法对配送线路进行划分.对以上2种算法的路线结果在智能物流信息系统中统计总配送距离,与2阶段调度算法的实际应用情况进行比较,如表3所示.

分析数据可知,在行驶距离方面,基于距离聚类的遗传算法按直线距离最小原则将客户分类,不可避免地增加了行驶距离,2阶段调度算法在派件调度时考虑了快递人员的路况经验,以保证总体最优的分配组合,因此,快递人员的实际行驶距离并不比算法规划的差;在工作量方面,由于划分配送区域时进行了工作量均衡的约束,2阶段调度算法要远好于其他2种算法,5日平均派件量差异各低13.3%,16.4%.综上可知,相比传统算法,设计的2阶段调度算法,有效缩短了配送路径距离,并对快递人员的经济平衡优化效果显著.

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

5 结 论

现代物流系统已经进入了信息化、网络化、智能化的发展阶段.基于ArcGIS,Web和Android等关键技术构建了支撑物流末端配送的智能物流信息系统.在该系统中改进k-medoids聚类算法和二分图最大权匹配KM算法,提出“点面聚合,区域聚类”配送区域划分方法和“先分区,后排班”派件调度策略.通过试验验证了模型和算法的正确性和优越性,有效提高了物流信息的管理效率.在智能系统下改进传统VRP模型进行派件路径规划是进一步研究的重点,揽送混合业务下的人员调度也是一个较好的研究方向.