基于邮政网络的社区物流多中心m-TSP问题

钱小凤，林国龙

(上海海事大学 物流研究中心，上海 201306)

0 引言

21世纪物流在迅速发展，物联网这个新名词也慢慢深入人心.业内专家早在十年前就提出了社区物流的发展，但十年来，社区物流一直处于停滞不前的地步.社区物流的发展整体都存在较大问题，包括理论认识方面、政策支持方面、服务手段、配套设施等方面.

袁伯友谈到了物流企业应该合作来完成社区配送，但如果社区物流发展起来，并不是单单几个企业合作就能完成，而且不同企业之间总会存在竞争，从这一点来讲，邮政最适合来担任这个角色［1］.黄莺对开展社区服务的策略及措施等方面进行了研究［2］.

本文的思想是将邮政网络视作密集的、随处可取的配送中心，通过对有社区物流需求的区域进行分区规划来完成社区物流的配送，并且最终达到配送车辆的里程、车载量等的均衡.

1 邮政网络参与社区物流

1.1 社区物流

本文所提到的社区物流是指以某种方式集聚的社会人的物流需求的总称.该物流需求各式各样，包括以生活用品、快速消费品，家电设施等具备流通、加工、定制、存储、配送、回收等物流业态要素的物流需求.从物流起点和终端，物流服务者，物流服务对象，物流需求，物流配送来说明，社区物流的特点如下［3］：

(1)社区是以有一定的区域，有一定的数量人口，以社区为物流服务对象的社区物流可以实现共同配送，可以实现配送数量的规模经济;

(2)提供社区物流的企业或主体需具备资金充足、资源设备丰富、网点布置密集在社区居民和居委会中有一定的威信等特点才能担起这份责任;

(3)社区物流对象包括空巢老人，小家庭，外来打工人员，因其行动不便，或时间原因，对配送要求很高，可能需要拆零、保鲜、冷冻运输，但要求提供及时、可靠、准确的物流服务;

(4)社区物流配送需求数量比较稳定，需求品种变化不大，需求规律容易把握.

1.2 邮政参与社区物流的优势［4］

邮政与社区密不可分，邮政服务是构成社区服务内容的重要组成部分，邮政进入社区服务市场具有明显的优势.

(1)网络优势 中国邮政同时具备了实物流，资金流和信息流三大功能，是其他物流企业所无法替代的核心能力.

(2)品牌优势 自新中国建立以来，邮政的绿色几乎是信誉可靠的代名词，这种品牌号召力，成为中国邮政参与现代物流的巨大财富.

(3)政策优势 我国政府在1998年成立国家邮政总局，当前中国还处于社会主义初级阶段，邮政存在的意义很重要，政府会实行各种优惠政策来促进邮政的发展.

邮政发展至今，虽然在各类业务方面都有突破，但总体来讲，邮政资源多数还是处于闲置状态.物流已不新鲜，但是以人群集聚为特点并细化到生活中的各种需求的物流，即社区物流还是较新鲜的一个名词，它的发展显然涉及到一个社会和谐的问题，必定需要政府政策的扶持，同时重要的一点是它的发展必定要有配套的设施设备.邮政现有的密集网络，相对于其他任何物流企业而言，它为社区物流的发展提供必要的设施设备是最合适不过.所以本文将在邮政网络的基础上来对社区物流做分区规划.

2 社区物流多中心mTSP模型的建立

2.1 问题定义

经过对社区老年物流特点的总结可知，社区老年物流和其他各式物流存在较大的区别.所以作社区老年物流的分区规划时会存在以下各种问题：比如配送的资源在何处，准备如何安排;配送中心在哪里，并做怎样的安排;要给某个居民区的老年客户们服务，有些服务对物流设备要求很严格，该安排什么样的设备;物流需求量将如何计算;服务对象老年人，一般是一些文化程度低的人群，从其所需服务来看，对服务时间、质量要求很高，又该如何做才能满足老年人的物流需求.解决社区老年物流配送区域划分的同时，也必定要解决好这些问题.

针对社区老年物流配送区域划分问题，作如下前提假设：

(1)按照调查，有需求的各种资源已经采购完毕，并且各个邮政网点均有存货，所有邮政网点都是潜在的配送中转站;

(2)某个存在物流需求的公寓大楼、居民院、单位等即算作是一个需求节点;物品都是单流向的，即都是由中转站配送到各个需求节点;

(3)通过调研，各需求点数目、需求量、需求规律已知，需求单位按照物品的件数计算，为SKU;

(4)货物的装卸和交货时间忽略不计(货物送达某个需求点后，由该需求点的社区居委会负责分派到每个客户手中)，只计算车辆行走的时间;

(5)每个邮政网点配有各种车型，且每次派出的车辆能满足运输线路上所有客户的需求总量;

(6)模型中通过地图按一定比例得到需求点的位置，以两点之间欧式距离计算.

社区老年物流配送区域划分问题定义如下：为在某个给定的行政区域内，将一栋大楼、居民区、单位凡有某种意义上圈在一起的人群集体视作一个需求节点，统计每个需求节点的社区老年物流需求(按照文中社区老年物流需求定义来统计);通过改进的K均值聚类算法对该区域所有需求点按工作量平衡的原则进行划分聚类工作，使得划分后的各分区中散落的需求节点满足下面的要求：①每个需求节点只能被划分在一个小分区内;②同一小分区内的节点应相对集中;③每一小分区内的车辆工作量应该尽量平衡;④划分完成后，分别由距离每个小分区最近的邮政网点为其服务.

2.2 改进的K均值算法建立社区老年物流配送区域划分模型

2.2.1 K 均值算法原理

设有 N 个模式样本{X1，X2，…，Xn};

第一步：首先从N个模式样品中选择K个初始聚类中心，c1(1)，c2(1)，…，ck(1)，其中括号内的序号为聚类迭代运算的次序号.

第二步：逐个将需分类的其余模式样本{Xi}按最小距离(欧氏距离)准则分配到K个聚类中，初始聚类工作完成得到C1(1)，C2(1)，…，Ck(1)点集.

第三步：重新计算各个聚类域的质心，即聚类域中样本的均值向量，并确定为每个聚类域新的中心，c1(2)，c2(2)，…，ck(2).

第四步：重复二、三两步，直到聚类中心不再变化.聚类工作完毕.

2.2.2 改进的K均值法应用

(1)K值的确定

假设需要划分配送区域的客户节点集C为整体，n个客户有需求，总需求量为Wt，如果每辆车的载货量最大为Wm，则理想的配送车辆数大致为：k=Wt/Wm.即只考虑每个配送区域由中转站每天派一辆车来完成社区老年物流配送的情况下，应将整个配送区域划分为K个子区域为合理.

(2)初始聚类的确定

这里选择均匀选择法来确定K个聚类中心，即将整个区域划分为m行n列，K=m×n，K个聚类中心就定位在离每个小区域中心位置附近的需求点，需要注意的是当K是合数时，尽量选择K的比较接近的两个因数作为m和n的值.这种起始均匀状态下的聚类结果也会尽量接近均匀.

Weighted-K-means算法引入了一个新公式，在计算其余需求点Xi到每个聚类中心的距离时，不再使用式(1)，而是采用与权重有关的式(2)来计算，使得形成的初始聚类考虑需求点权重因素.

式中，(xj，yj)这K个聚类中心的横坐标与纵坐标;W(cj)表示聚类中心K的权重.对于剩余每个需求点 Xi，按照 Dik=min{dij}，判断 Xi∈ Ck.初始聚类形成.

(3)聚类迭代计算

根据式(3)、(4)分别计算每个聚类点集Ck的权重质心的(xj，yj)，即新的聚类中心ck;Wi表示各个区域中的各需求点的权重，据式(5)可得每个聚类点集的总权重W(Ck)：

根据式(6)分别重新计算所有节点到K个新聚类中心ck的权重距离，并对全部的点进行重新聚类.对于每个节点Xi，按照Dik=min{dij}，判断Xi∈Ck：

再次得到新的聚类结果，而且是考虑了每个需求点权重的聚类结果.

对聚类结果进行收敛判断，达到收敛准则停止计算，否则重复步骤3，直至聚类收敛.收敛的判断是通过观察聚类权重质心和总权重的变化波动是否保持在某个范围内来判断的，是则收敛，否则反之.

2.2.3 基于平衡工作量的K均值聚类结果的调整

(1)TSP引用

TSP数学描述：∃连通图H，其顶点集V，设起点为A，同时也为终点.顶点间的距离为

其中式(8)是目标函数，使得所得路径最短，式(9)、(10)分别保证每点的出度和入度均为1，(11)式为决策变量式，式(12)保证只形成一个闭环.

(2)平衡工作量的定义

通常普通的聚类方法不能合理地将所有的需求点均衡地划分开来，所以对聚类划分结果需要做进一步调整.

每个聚类的工作量Wk是指综合考虑聚类Ck中所有需求点的车辆行驶距离、网点数目、需求权重三个因素，且工作量的求解公式如(13)：

式中，Sk是指聚类划分确定以后的聚类Ck的TSP距离;Wi指Ck中每个需求点的需求权重;Nk表示Ck中需求点的数量;ρ1、ρ2、ρ3分别表示三个因素的权值，并且分别以所有聚类的车辆行驶距离均值倒数、网点数目均值倒数、需求权重均值倒数来表示.

工作量均衡是指事先设定一个初始值W0，若每个聚类Ck的工作量Wk满足式(14)，则称该次聚类工作满足工作量均衡的条件.

(3)基于工作量均衡的聚类结果的调整

计算每个聚类Ck的工作量Wk，并按照式(14)判断聚类Ck的工作量是否均衡：若均衡，则无需调整，说明此次聚类结果比较合理;若不均衡，对所有聚类结果按如下方式调整：

根据式(15)选取聚类Cf，并对Cf聚类进行调整.选取Cf聚类中权重距离最大的节点，将其弹出，并将此节点加入到其离K个聚类中心权重距离次小的聚类.这样操作就降低了Cf的整体工作量，接近工作量平衡的效果.

为了防止某个数据点被反复弹出，对被弹出点进行标记，当下次再次需要弹出该点时，对该点不做处理，而是选择次远点［8］.

在调整之后，重复步骤3再次对新得的聚类结果作工作量均衡检验，如此反复迭代，直至区域划分后每个小分区的工作量差异在可允许的范围内.

聚类及调整过程算法如图1，图2.

此种改进的两阶段算法添加了工作量均衡的思想，其优点总结为三点：

(a)选择初始点，没有采用随机选择方式，而采用均匀法.与传统随机方式相比，它能够使初始聚类中心分散开来，使得结果更易收敛;

图1 聚类算法流程图

(b)在第一阶段的K均值聚类迭代过程中，虽然添加了工作量均衡的思想，但K均值算法，研究至今，已经进入成熟阶段，不会因为距离计算方法的变化而有太大变化，故实现起来比较容易;

(c)在算法的第二阶段引入了外部约束工作量均衡的条件来判断各个聚类的工作量是否均衡，再利用弹出机制对已完成好的聚类进行调整，使得算法更贴近实际，配送工作也更人性化.

图2 聚类结果调整流程图

2.2.4 邮政网点的选取

聚类结果形成以后，关键是选择送货的中转站邮政网点，那么整个社区末端的老年物流配送才算真正完成.

图3 邮政网点选取的算法流程

将该行政区域内所有的具有配送能力的邮政网点位置在地图上表示出，并按地图比例确定它们的位置坐标.对于每个聚类分区，遍历每个邮政网点，计算包括一个邮政网点在内的该聚类分区的TSP距离，找出TSP距离最短的那个邮政网点为该聚类的末端配送中转站，而相应的TSP距离即为该聚类的车辆行驶路线.算法如图3.

3 实例分析

为了验证算法的有效性，本文设计了如下算例进行论证.假设邮政速递要利用现有网点对某区域内的42个居民小区进行配送.通过一定的比例换算，这些点集位置如图4.

各点的需求量(单位为SKU)表如表1所示.需求总量为6428SKU，假设一辆普通的车辆的最大载货量是800SKU，此时可得K=9，则当天用于配送的车辆为9辆.

图4 地理坐标信息模拟图(各需求点标号)

表1 各节点的需求量

利用matlab编程，对算例进行求解，结果如图5.图5显示了42个需求点经过上面算法的求解后得到的聚类图，共得到9类.如图所示，改进的算法充分考虑了工作量均衡的问题，每一类中所包含的需求点的数量大致相等，而且相对集中;将就近的邮政网点，每一类的配送中心考虑进去，从而得到每个聚类的最短路线图.

聚类结果中每个聚类包含的点集、及相应的车载量、里程数据如表2所示.从表中可以看到，车载量大致相同，车载率也相应比较高，Uk大致相等，符合算法中提出的工作量均衡的要求.改进的k均值算法使得配送区域划分更合理，车辆配送更合理.

图5 配送区域划分图(三角形表示邮政网点，虚线圈表示类别号)

表2 改进的K-means聚类分析数据显示

4 结论

本文基于一些合理化假设，对社区物流进行了研究，首先是对社区物流作了一些解读，并解释了利用邮政资源的目的。在此基础上，利用工作量均衡标准，通过聚类算法和TSP问题，研究了社区物流配送区域划分的问题，并用matlab对算法进行求解.该模型的建立可以同时解决在社区物流分区规划时，对配送车载量、车里程量等几个方面的提出的均衡要求.最后通过算例，验证算法的有效性.

社区物流是一块还未开垦的荒地，其各方面的研究还处于初级阶段，还没有形成完善的结构体系，需要对其进行更加深入的研究.随着电子商务和物联网的发展，社区物流也必将会迎来一个更快的发展阶段.

［1］袁伯友.基于社区物流的物流企业配送策略探讨［J］.物流技术，2009，28：2-4.

［2］黄莺.邮政参与社区服务市场的研究［J］.邮政研究，2003，19：17-19.

［3］姜燕宁.基于社会管理创新的社区物流发展对策研究［J］.商业时代，2011，28：4-6.

［4］薛君.中国邮政发展现代物流的可行性分析与策略建议［J］.西安邮电学院学报，2003，8：14-17.

［5］王勇，毛海军.带时间窗的物流配送区域划分模型及其算法［J］.东南大学学报，2010，40：1077-1083.

［6］谢可.物流配送系统中聚类算法的研究与应用［D］.浙江：浙江大学，2006.

［7］朱培芬，汉吉庆.基于改进K-means算法的烟草配送区域划分［J］.物流工程与管理，2009，31：84-85.

［8］谷伟，张群.基于改进K-means聚类的物流配送区域划分方法研究［J］.中国管理信息化，2010，13：60-63.