动态路网下物流配送中心选址-路径优化算法及实现分析

徐稳

（西北工业大学，陕西西安 710068)

0 引言

随着中国经济的快速发展，物流产业成为促进地区经济发展的重要因素。物流中心的布局规划、物流配送、车辆路径的综合优化是物流系统的三个重要环节，选址优化直接影响物流服务的整体效率和成本。同时，还能通过规模化运输、优化的库存控制以达到企业节约成本的目的。传统的LRP 问题算法无法处理的问题,是基于静态网络结构过程中，始终具有争议的时间问题，即在动态网络结构过程中的到达边权时间,与抵达边尾点的时间无关。

1 数学模型建立

1.1 动态路网的时间依赖函数

从车辆运输理论模型的具体和实际应用两个角度进行分析。探讨LRP 问题，提出基于时间依赖函数的假设和基本架构（如图1）。IKUGA 等人进行研究，并采用离散行进时间速度依赖时间函数。由于该离散运动依赖时间函数直接由动态行进依赖时间函数代替，所以该动态道路网络函数是比较先进的先出准则[1]。

图1 路网时间依赖函数

1.2 车辆行驶速度的分布

基于上述相关理论分析研究，为了更加全面、精确地获得车辆在中国城市实际道路路网结构形式上，所采用配送运输模式的实际使用情况。

在LRP 模型的假设和应用设计中，根据不同时段、不同路段的速度以及不同道路限速的情况，给出了假设条件。

当各个道路的交通密度差异很大时，也就是在城市的平均拥堵高峰时段，理论上，车速分布一定要遵循上述正态分布；在道路流量密度相对较高的路段，也就是通行高峰时段的平均车速分布，应当遵循两个对数的正常分配，如式（1）所示。

式（1）中:tn1为畅通时间段；tn2为一般时间段;tn3为高峰时间段；μ 为不同时期的期望车速值；σ 为不同时间范围内的标准速度差异。其中f[v(t)]为畅通时段、普通时段、高峰时段进行对比。

1.3 动态道路路网跨时段车辆行驶时间

给定路网G(V、A、T)。其中V 是非空结点集；A是有限边集；用ωi、ωj表示从结点ωi到结点ωj的有向边；Tn表示在tn时段结点ωi到结点ωj的行驶时间；设车辆从结点ωj由t0时刻出发到达结点ωin的过程中经过了N 个时段,其中第N 个时段的端点为MN,MN+1;设ωi1与ωin之间的距离为d；tk时段车辆的行驶速度为en；由旅行速度时间依赖函数可得车辆行驶的总旅行时间为式（2）：

到达结点ωin时间为式（3）：

经整理得到式（4）：

te为结点ωi1出发时刻t0的增函数，满足FIFO准则。

1.4 路网静态约束的影响

通过对近年来物流理论研究成果的分析，许多研究人员没有认真考虑物流配送与运输系统复杂的微观现实物流地理结构和整个物流网络的布局，以及优化规划方法对物流车辆整体配送、对运输计划的潜在经济影响。在未来的实施方式中，由于距离矩阵当前是欧几里得距离矩阵，所以在Cartesia 坐标中将配电网建模为各个点时，D=（dij）。因此，不能考虑交通管制的主要原因，如路面速度限制、转向延迟、单向限制等。实际道路网络中节点之间的实际距离比欧几里得距离复杂。如图2所示，实际距离1～2、2～5 是由于一个线路的限制。因此，OD 成本矩阵D=OD（i,j）被用作网络距离矩阵。在建立网络模型的连通策略之后，通过构建混叠单元，将混叠延迟转换成网络的边缘权重。此外，在定义一条线段的属性之后，Dijkstra 算法获得了富属性网络，其可以称为道路网络的源节点和目的节点之间的实际距离OD（i,j）。

图2 有向富属性网络

2 实例分析与应用

基于提出的算法，在杭州市实际路网数据上进行动态路网下LRP 问题的求解，建立的杭州市富属性网络模型(如图3所示)中,结点数为88164,边(edge)数为95883，其中主干道路段数为50193，支干道路段数为36969[2]。

图3 富属性网络

2.1 基于空间连通性的动态路网路段阻抗设置

通过内置的杭州富属性路网模型设定区间属性值，可以进一步计算节点之间的实际矢量距离，以及指定转向符号所需的交点。单线边界场的设定是在向量化方向与一条线的方向平行的情况下，设定为FT，否则设定为TF 属性。在[道路质量]（Road Quality）字段中指定3 个值：1、2、3，再利用Dijkstra 算法，求出源结点与目标结点间的最小时间传输费用为D(i，j，tn,ti)，并在t 周期的t 时刻从节点i 开始，由D(i,j,ti)到j。在优化过程中，由于对时间t 未知，所以D(i,j,tn,ti）会随着时间的推移而改变，而路网权值也不固定。基于此，为解决基于时间优化的动态网络模型的问题，引入一种在不同时期更新4OD 网络的方法，点计数协议是针对任意断点协议而构成的。

2.2 参数设置

在以上分析的基础上，提出一种基于该方法的协作式启发式方法，并在此基础上建立一种新的交通网络模型，并给出新的LRP 问题。针对杭州市问题，一家大型跨国物流公司至少有10 个以上的国际物流中心的问题，建立了一个动态的选址中心-配送运营中心问题模型，并给出相应的解决方案，要求必须在两大公司至少10 家物流车辆配送营运中心中随机选择一个最合适的位置，选择其中至少4 家公司为车辆配送运营中心，以便在动态交通条件下的车辆分配和运输路线，对总的固定费用和总费用进行比较。

快速路、主干路、支路3 种类型的道路，其中，高速公路设计速度为70km/h，主干路为50km/h，支路为30km/h；该条款列出了各地区配送中心的平均每天工作时间窗口，分别设计为平均每天早晨8∶00 至次日20∶00，不应仅考虑平均每个用户点每日的卸货工作时间。不需要单独考虑平均每个用户点日的平均工作时间窗，具体计算及参数设置形式均如表1所示；同时，50 家客户点平均每日的货物需求量，均如表1所示。在算法与参数的合理设置的基础上，遗传算法和种群规模大小各取前20；而染色体变异概率取0.5，精英个数取2。

表1 速度分布参数

2.3 试验结果及分析

配送中心每年自农历1月份至10月份以来拥有并运营的固定运输车辆数，每年平均每个月四辆车，发运每一辆的固定车次配送的运输车辆的固定成本每年为平均每天约300 元，F=平均每月约300 元/辆；每次运输车辆单位时间内，每天消耗的实际物流运输服务总成本大约为人民币20 元/m3。在物流配送转运中心，在每日上午8∶00 起开始进行对外物流营业输送服务运营时，每增加一辆物流配送运输车则每天的物流配送正常运营发车开始的具体时间点，都统一确定为每日早晨8∶00 左右；在这种情况下，用“星形”表示10 个待选择的配送中心；“方形”代表50 个顾客点。

3 结语

着重对基于动态网络模型的LRP 问题的设计进行深入而系统的研究，该设计是利用遗传算法和蚂蚁算法进行交互转化协作的启发式算法。通过分析试验得出，该算法是在通过设计中，引入另一个基于NNC 算法的初始化策略后，在一定收敛性基础上，进一步提高了算法本身的收敛率；同时，利用仿真退火的方法，对最大最小蚂蚁系统进行动态修正，提升了物流优化问题的简单性，使其实现路径优化。