基于实时交通的城市冷链物流路径优化研究

河北大学电子信息工程学院 郑敏静 宗晓萍 郭 会

基于实时交通的城市冷链物流路径优化研究

河北大学电子信息工程学院 郑敏静 宗晓萍 郭 会

针对城市冷链物流路径优化问题，提出与实时交通状况结合，并分步求解的方法。首先利用改进的Dijkstra算法构建动态路网，然后构建城市冷链物流路径优化模型，并运用遗传算法求解，与企业实际物流配送情况相比，成本降低了4．1%，配送效率提高了19．1%。

冷链物流；路径优化；实时交通；迪杰特斯拉算法；遗传算法

1 引言

随着科学技术的发展和人们现代生活水平的提高，人们对入口食物的品质有了更高的要求，从而对冷链物流的配送也有了更高的要求。冷链物流是指易腐易变质产品在从产品生产、加工、贮藏、运输、销售最终至消费者的各个环节始终处于符合产品属性要求的温度、湿度环境以有利于保证产品质量，减少产品损耗，防止污染的特殊供应链系统。冷链物流配送的产品具有易腐性，对运输温度要求比较高，并且要保证运送的时效性。

冷链物流配送路径问题是多目标最优解问题，受车载重量、配送产品数量、产品种类等诸多因素影响。目前我国对于冷链物流配送问题的研究主要集中在对静态车辆路径问题的优化，但是在城市实际路网中影响车辆行驶的因素有很多，例如：天气因素、交通流量、高峰期、交通事故、路段限行等。如果冷链配送不考虑实时交通状况，车辆很有可能会陷入交通拥堵使配送时间延长，配送成本增加。显然需要考虑交通状况对配送的影响，避免单纯考虑速度与距离而带来的偏差，降低冷链物流的配送成本。

传统物流配送道路是静态的，配送车辆从配送中心出发，经过各配送点后返回到配送中心，通常两点距离都是欧式距离，未考虑真实路网和交通状况。城市路网复杂，有成百上千路段和交叉口构成，对路径规划影响较大的是交通流和交叉路口延误时间。城市冷链物流配送最优路径规划与交通因素结合起来，才比较贴近实际，将交通路网抽象成带权图，用图论方法进行分析。本文将一天中交通流量变化的情况分为H个时段，假设每个时段内，路段交通流量大致相同，则配送车辆在该时间段通过某路段的行驶时间保持不变。

其中，交叉路口延误时间可以从城市信息系统中实时获取。城市路网的流畅性受交通流的影响[9]交通流量决定速度。基于此本文对基于交通的城市冷链物流路径进行了优化研究。

2 动态路网构建

2.1 D i j k s t r a算法

Dijkstra算法[7]是经典的最短路算法，用于计算一个节点到其他所有节点的最短路径。缺点是计算速度慢。在普通dijkstra算法中，弧以距离为权重，节点没有权重。在城市冷链物流配送中要求行驶时间最短，存在交叉口延误。因此针对dijkstra作了两方面改进：一方面以路段行驶时间作为权重，并给节点赋予权重，当作新增路段权重弧来处理；另一方面是设立评价函数h(n)=t(n)+b(n),其中t(n)是由任意节点n到固定节点的时间换算而来，b(n)是任意节点n到顾客需求点距离换算而来。评价函数最小的节点为固定节点，通过比较评价节点，找到最短的路径。

其中，节点之间行驶时间取决于所经过的路段和交叉口数。配送节点时间=各路段行驶时间和+经过的路口延误时间和。

每一路段行驶速度根据式(1)计算得出，行驶时间根据式(2)计算。

Lab为相邻节点之间的长度，a1、a2、a3为回归参数，取值为1.55、1.88、7.00。v0为路段零流量时的行驶车速取值为40km/h，q为实时交通流量，c为路段的基本通行能力，取值为900pcu/h。

算法步骤如下：

（1）标记客户需求点i为固定节点，j为目标节点，剩余节点为未标号节点。

（2）沿着i，j之间连线搜索未标号节点，按照评价函数计算值从大到小的顺序排列。

（3）选取评价值最小的节点，判定是否为目标节点j，若为目标节点则结束算法，若不是则转步骤（2）继续搜索，直到寻找出目标节点j。

2.2 路网构建

简单城市路网如图1所示，圆圈表示交叉口，圆圈内的数字表示交叉口延误时间（min），弧的权重为路段行驶时间（min）。不同的时间段，交通流不同，行驶时间也不同。

图1 简单城市路网

路网构建过程如图2所示。O为配送中心，ABC为配送点，运用上述算法，求出任意两点之间时间最短路径，构成物流配送网络。

图2 动态路网构建过程

3 模型构建与求解

3.1 模型构建

在物流配送中，车辆从配送中心装载一定量的货物对客户进行服务，完成后返回配送中心[5]。配送须保证每个客户被服务一次，车辆载重不能超过额定载重，不考虑时间窗问题，依赖于行驶时间构建以总成本为目标函数的模型（总成本包括运输成本、能耗成本、货损成本）。假设企业车辆集合K={1,2,3,…,m}，客户集合N={1,……,n}，车辆额定装载量为Q，客户点i的需求量为qi，从客户i到j的行驶时间为tij，单位时间耗油量为c1，单位时间货损系数为λ1，运送单位时间制冷能耗为l1，则配送总成本目标函数为：

其中xij为决策变量，若为1，则配送车辆经过客户点（Ni，Nj），若为0，则不经过。

约束条件为：

(3)式表示每辆车装的货物不能超过额定装载量；(4)式表示每个客户只能由一辆车服务；(5)式表示每个客户点都有车辆配送；(6)表示所用车辆数不能超过配送中心车辆数。

3.2 模型求解

遗传算法是一种求解组合优化问题的强大搜索方法，标准遗传算法包括种群初始化，个体适应度计算，选择操作，交叉操作，变异操作，终止条件判断操作等。

针对上述动态冷链物流路径模型，本文选用遗传算法进行求解[4-6]。具体算法步骤如下：

（1）随机生成初始化种群，设置种群规模为100，染色体长度为8；

（2）计算每个染色体适应度（目标函数的倒数）并标记；

（3）采用Monte-Carlo选择策略选择N个适应度高的染色体。

（4）采用部分匹配交叉法，以交叉概率0.7选择染色体进行交叉操作生成新个体。

（5）以变异概率0.03进行变异操作。

（6）产生新代种群，达到收敛代数则终止算法，否则重新进入达到步骤2。

4 实例分析

本文结合某企业城市配送的真实路网情况进行了简化处理，选取86个路网节点，经过118条路段。该企业有一个配送中心，八个需求点。在matlab中用坐标图模拟真实配送节点位置。对早高峰时段（6∶30-9∶30）配送进行了优化仿真。

表1 需求点坐标及需求量

表2 配送节点时间矩阵（单位：mi n）

4.1 参数设置

参数设置：单位油耗成本1元/min，每辆车使用一次固定成本50元，l1、c1，λ1，k，n,Q,取值分别为1元/min，1.5元/min，0.003，l2为0.5元/min。

（1）各需求点位置坐标、需求量见表1，其中0为配送中心位置，坐标为（0,25）。

（2）配送节点实际配送时间见表2。时间矩阵经过改进的dijkstra算法在MATLAB中进行计算得到。

4.2 结果分析

对所建模型，利用上述遗传算法进行求解，实验结果表明对需求点的配送需要两辆车，配送路线如图3、图4所示，本文基于实时交通的配送情况和企业实际配送情况见表3、表4。

图3 基于实时交通的最优配送路线

图4 企业传统配送路线

表3 基于实时交通的配送情况

表4 企业传统配送情况

由实验结果可以看出，基于实时交通配送路径与企业实际配送路线不同，行驶距离、总配送成本、配送时间都不相同，企业时间配送距离为144km、配送时间为164min，总成本为502.5元，基于实时交通信息配送距离为153.8km、配送时间132.6min、总配送成本为482.7元，优化后，虽然配送距离增加，但配送成本降低了4.1%，配送效率提高了19.1%。

5 结论

本文提出将冷链物流配送与实时交通将结合的模型，实验证明，基于实时交通的配送，更贴近实际具有可行性，并且有效的规避了拥堵，减少了配送成本，提高了配送效率。今后将进一步研究实时交通状况下同时送取货物的配送路径。

[1]兰辉,何琴飞,边展,靳志宏．考虑道路通行状况的冷链物流配送路径优化[J]．大连海事大学学报,2015：67-74．

[2]王一松,王直杰．基于实时交通信息的路径规划算法研究[J]．计算机与现代化,2013：52-55．

[3]李亚南．基于车联网的冷链物流配送路径优化研究[D]．长安大学,2016．

[4]唐坤．车辆路径问题中的遗传算法设计[J]．东华大学学报(自然科学版),2002,28(1)：66-70．

[5]宗晓萍,刘森,王培光,路瑞宽．基于企业冷链物流MAS的车辆调度问题研究[J]．物流技术,2014,33(12)：253-255．

[6]周咏．冷链物流同时送取货车辆路径优化[J]．数学实践与认识,2016,46(20)：18-26．

[7]袁彬,刘建胜,钱丹．一种基于改进Dijkstra的物流网络路径优化算法分析[J]．制造业自动化,2014：86-89．

[8]邓丽君．基于客户满意度的物流配送车辆调度优化模型与算法研究[D]．北京：北京交通大学,2012．

郑敏静（1992—），女，河北石家庄人，研究生，研究方向：智能物流。