基于复杂网络和实际交通数据的城市冷链物流末端配送规划

2022-07-11王正国熊一凡

武汉理工大学学报（交通科学与工程版） 2022年3期

王正国陈升* 熊一凡

(武汉理工大学交通与物流工程学院1) 武汉 430063) (武汉烽火国际技术有限责任公司2) 武汉 430074)

0 引言

冷链产品具有易腐败、难保存等特点，导致冷链物流末端配送对时效性要求更高，这也是我国冷链物流末端配送成本配送居高不下的主要原因．城市冷链末端配送通道为实际的路网，复杂的城市交通状况对配送造成了很大影响．因此，考虑交通路网的影响对配送区域进行合理规划对提高冷链配送效率，降低配送成本具有重要意义．

针对配送区域划分问题，何梦军等[1]考虑到配送点之间的关联因素，采用改进的吸引子传播聚类算法实现对配送区域的划分．房庆军等[2]构建生鲜冷链配送“区域划分+区域调整”两阶段模型，利用k均值算法以最短配送时间为聚类准则进行初始区域划分，引入均衡载货指标，调整初始划分区域．杨雯婷等[3]基于泰森多边形理论，以某一地区现役油库为例，对该地区现有油库的配送区域进行重新划分，缩短了配送距离，提高了配送效率．吴亮然等[4]通过配送区域间的拓扑关系生成区域协同配送网络，进而依据一次配送中的有货区域信息生成车辆初始配送线路，并对具有相邻关系的线路进行配送线路间调整，从而形成最终的车辆途径配送区域的配送线路．上述文献未能考虑到在城市末端配送过程中复杂的交通路况对配送造成的影响．李玉鹏等[5]考虑了路况条件、道路条件和停车难易等因素并对其进行了权重分析，构建了现实生活中物流配送的复杂网络模型，然后基于两阶段的LinkRank社区发现算法实现了物流配送区域的划分．周程等[6]考虑了车辆行驶速度与实时路况带来的影响，建立配送优化决策模型，更贴近现实．赵邦磊等[7]研究了不同天气状况、不同时间段道路拥堵情况等因素对行驶速度产生的影响，建立车速特征影响模型，构建冷链物流配送模型．

考虑到司机常根据地图软件导航路线行驶，文中利用高德地图获取客户点间双向实际通行时间来描述节点间物流联系，构建有向的城市配送复杂网络模型，利用社区发现法进行配送区域划分，提高冷链物流末端配送网络规划的合理性．

1 基于复杂网络的冷链配送区域划分

1.1 复杂网络

复杂网络实质上是由网络中所有的顶点V和所有顶点联系的边所构建成的图形．复杂网路可用邻接矩阵A=(aij)表示．其中aij的取值可以表示节点i与节点j之间是否存在连接关系，对于无权网络，节点间存在连接则取值为1，否则，取值为0．对于有权网络，可以将对节点间连接关系的评价值作为权重．

一个复杂网络可由若干个“社区”构成，社区内部的结点间的连接相对紧密，而社区之间的节点间连接相对稀疏．图1为一带有社区结构的复杂网络．

图1 带有社区结构的复杂网络

社区发现是指寻找网络中社区结构的过程，社区发现结果的好坏可用模块度衡量．对于有向带权网络图，模块度的计算公式为

(1)

1.2 带社区结构复杂网络模型的建立

构建合理的配送网络模型是进行冷链物流末端配送区域划分的前提．建立社区结构网络模型的需要明确网络中的节点、边以及边的方向和权重，针对社区结构网络模型的建立提出三点转化规则．

1) 将有冷链需求的社区转化为网络模型中的节点．

2) 将社区之间所具有的物流关系转化为社区结构网络之中有方向有权重的边，即A社区到B社区与B社区到A社区是两条方向相反的边．

3) 将社区间通行时间的倒数作为边的权重值．社区间的通行时间主要会受到道路等级、长度、交通状况、车辆行驶速度等主要因素的影响．

若网络模型中存在由社区i指向社区j的边，由于从社区i到社区j的通行路线中存在多个路段，通行时间的计算方法为

(2)

式中：tij为从i到j间的通行时间；dk为第k条路段的长度；ck为路段k的道路等级；vck为车辆在路段k畅通情况下的行驶速度；qk为路段k的拥堵情况对车辆行驶速度的影响系数；v为车辆最大行驶速度.

则边的权重Wij计算公式为

Wij=1/tij

(3)

考虑到地图软件工具拥有海量道路网络数据，能全面考虑到上述因素的影响来估测两节点间最短通行路径与通行时间，因此利用地图软件获取节点间的通行时间作为通行时间数据来源．

1.3 带社区结构复杂网络的划分

建立了社区结构网络模型之后，需要挖掘网络模型中所存在的社区结构．Louvain社区发现算法利用贪心策略将节点划入与其具有连接关系的节点所在的社区，从而使模块度增量最大，优化整体网络模块度[8]．

算法的流程可以分为两个阶段．首先假设存在一个加权网络，具有n个节点，每个节点作为一个独立社区．将节点i划入其相邻节点所在社区并计算此次移动产生的模块度增量ΔQ，如果最大的模块度增量ΔQ大于0，则将其加入对应社区，否则，不进行移动．重复该过程直到所有节点都不再发生移动．

在有权有向网络中，模块度增量ΔQ的计算公式为

(4)

算法第二阶段的主要任务是重构整个网络，将第一阶段发现的社区作为新的节点，新节点继承社区中所包含节点与外部节点的连接关系，出入度等于该社区中所有节点的出入度之和．网络重构结束后，重复第一阶段过程至得出最优的社区结构．步骤如下.

步骤1每个节点作为一个独立社区，二者编号相同．

步骤2对于节点i，计算将其划入至其相邻节点所在社区时的模块度增量ΔQ，记录ΔQ最大时所对应的社区编号，如果max(ΔQ)>0，则把节点i划入该社区，否则不进行移动．

步骤3重复步骤2，直到所有节点不再发生移动．

步骤4重构新图，将每个社区压缩为一个新的节点，新节点继承社区内部节点与外部节点间的连接关系，其属性值为内部节点属性值之和．

步骤5重复步骤2～步骤4,直到网络的模块度不再发生变化．

2 基于复杂网络的冷链配送路径模型建立

2.1 问题描述

冷链末端配送中的网络节点有两种属性：配送站点及社区．上一节利用社区发现法对网络模型进行了划分，解决了末端配送网络区域划分问题．在配送区域划分已经完成的情况下，现需从备选配送站点中选出与划分出的区域数量相等的配送站点，并确定每个区域对应的末端配送站点以及每个配送站点服务该区域所有社区时所应该安排的车辆与车辆的配送路径，验证所提区域划分方案的有效性．

2.2 模型假设

1) 已知各个配送站点的地理位置，从现有配送站点中选取备选配送站点，不另外新建配送站点．

2) 各个配送站点的订单处理能力相同．

3) 仅考虑单一冷链产品需求的配送．

4) 已知社区点地理坐标、需求量，以及配送时间窗．

5) 每个配送区域都由一个固定的配送站点进行服务，配送站点不进行跨区服务，社区的配送需求要一次完成，不能拆分．

6) 利用高德地图大数据获取网络中两点间的行驶路线，两点间路线可能因起始点不同而发生变化．

7) 车辆行驶路线是固定的，不能中途更改．

8) 配送时冷链产品的变质只与配送时间相关．

2.3 模型符号

2.4 优化目标

城市冷链物流末端配送成本主要包括固定成本，运输成本以及货损成本，各成本要素如下.

1) 固定成本C1主要包括车辆的折旧、配送员的工资以及与运输相关的固定损耗，配送过程产生的固定成本C1为

(5)

2) 运输成本C2车辆的运输成本与配送车辆运输时间成正比．车辆的运输成本C2为

(6)

3) 货损成本C3根据“3T”理论，同一冷链产品的变质率主要受温度和时间的影响，因此，假设在温度恒定时，同一冷链产品变质率只与配送时长有关，本文中冷链品的变质函数为

O(t)=λO0e-ρt

(7)

式中：O(t)为冷链产品在经过t时间后的品质；O0为冷链产品的初始品质；λ为冷链产品常数值，与保温箱中的温度有关；ρ为冷链产品对于时间的敏感系数．则货损成本为

(8)

4) 时间惩罚成本C4由于冷链产品具有易腐性，客户对收货时间要求更严格，配送车辆需在规定时间窗内到达，但是由于道路拥堵、调度失误等因素的影响，配送车辆难以在规定的时间段内送达，对此予以一定惩罚，冷藏车辆配送过程中时间窗惩罚成本为

(9)

2.5 模型构建

minC=C1+C2+C3+C4

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

式(10)为模型目标函数，使网络总成本最低；式(11)～式(12)为配送站点与配送区域是一一对应的；式(13)为车辆必须从站点出发，完成任务后返回该站点；式(14)为配送车辆只为固定站点服务；式(15)为一个社区只能被一辆车服务一次；式(16)万车辆必须从进入的节点离开；式(17)为车辆不能超载．

3 案例分析

文中以SF公司在M地区城市冷链物流末端配送网络为例展开研究．假设只考虑单一冷链商品的需求，针对M区有冷链配送需求的67个社区建立社区网络模型，运用louvain社区发现算法实现社区网络模型的划分，得到配送区域划分方案．为验证本文所提方案的有效性建立配送优化数学模型，分别基于SF公司原始配送区域划分方案和本文所求方案利用遗传算法求解，比较两种方案下配送成本．利用网络爬虫技术[9]对高德地图进行社区地理位置以及社区间通行时间等数据信息的获取．67个社区的实际位置分布见图2．

图2 社区分布图

3.1 相关数据

图2中各社区点经纬度数据可通过高德地图获取，相关数据见表1．

表1 社区点相关数据

3.2 相关参数含义及数值

f为车辆固定成本，80元/辆；c为车辆单位时间运输成本，0.5元/min；P为冷链产品单价，20元/件；λ为冷链品常数，0.95；ρ为冷链品对时间的敏感系数，0.01；Qk为车辆最大容量约束，30件；tc为时间惩罚，5元．

由高德地图大数据可得个节点间通行时间，节点间通行时间见表2．

表2 节点间通行时间单位：min

3.3 问题求解

3.3.1配送区域的划分

由高德地图大数据可获得各社区点间最短通行时间，根据式(3)计算各边所占权重构建网络模型，基于M地区的社区网络模型，运用Louvain社区发现算法对该网络模型进行社区发现．配送区域划分方案见表3．

表3 配送区域划分方案

在SF公司官网上可以查得该地区已有的配送站点及原始配送区域划分方案见表4．

表4 原始配送区域划分方案

由表4可知：SF公司原有配送站点中，站点1、2、4负责社区点最多且分别位于文中方法得出的三个配送区域中，因此选取这三个原有站点作为求解得到的配送区域的配送站点．

3.3.2模型求解

基于配送区域划分结果以及SF公司原始配送区域划分方案，利用遗传算法对模型进行求解，遗传算法参数设定为：种群规模为100，交叉概率为0.85，变异概率为0.2，最大迭代次数为150．实验结果见图3和表5～8．

图3 基于原始配送区域和社区发现的配送路线

表5 基于社区发现的站点任务分配情况

3.4 结果分析

通过数据分析可以发现，在满足客户需求的前提下，利用社区发现法进行配送区域划分可以将配送站点从原来的7个降低至现在的4个，配送车辆从13辆减少至11辆，车辆装载率提升了14.1%，固定成本减少了15.4%，而运输成本与货损成本仅增加了7.1%，时间惩罚成本减少了4.6%，总成本降低了5.4%．结果表明利用社区发现方法对客户进行聚类划分配送区域可以保证配送时效性并有效降低整体配送成本．