基于改进蚁群算法的软硬时间窗车辆路径优化

杨婷 韩冬桂 燕怒 刘芳

摘要：文章针对客户對时间紧迫性要求不同的情形，建立软硬时间窗车辆路径优化模型，在车辆行驶距离和载重约束下，以行驶成本、惩罚成本和固定成本形成的总成本最低为目标，利用改进蚁群算法优化车辆路径。首先蚂蚁状态转移规则采用随机规则使蚂蚁优先选择时间窗较窄和到达时间较早的节点，接着采用伪随机规则决定蚂蚁倾向选择信息素浓度较大的路径或随机选择，并且探讨伪随机因子q。取值对解的影响并找到最优值，同时对不满足硬时间窗约束的节点做返回到配送中心的处理。最后通过实例验证，Matlab仿真计算，采用伪随机规则且使用最优的q。值，使配送成本降低且总优化率提高了17%，进一步论证改进蚁群算法有优于遗传算法的收敛效果。

关键词：软硬时间窗;蚁群算法;伪随机规则;伪随机因子

中图分类号：U116.2文献标识码：A

0引言

随着经济全球化，物流行业作为“第三方利润源泉”的学说被提出，配送是物流活动与消费者直接相连的重要环节，经调查，运输成本在整个物流成本中占相当大的比例。因此，有效降低运输成本对企业发展具有重要意义。

车辆路径设计直接影响到物流配送成本，现实生活中，不同客户对货物送达时间的要求不一致，于是存在混合时间窗的问题。（1）硬时间窗，若车辆早于该客户的约定时间，必须等待;若晚于约定时间，则拒绝服务。（2）软时间窗，若车辆早于或晚于该客户的约定时间，将按规定受到惩罚成本。目前，对单独研究硬时间窗或软时间窗或无时间窗车辆路径问题比较多，但对时间窗同时存在的情况研究比较少。周蓉等利用粒子群算法求解软硬时间窗共存装卸一体化车辆路径问题。史昊等探讨用于求解软硬时间窗共存情况下的车辆路径问题的改进遗传算法，设计改进的交叉和变异准则，以避免问题陷入局部最优解。彭鑫等构建带混合时间窗的车辆路径问题的数学模型，引入优良基因及最优个体保护策略改进遗传算法。

解决车辆路径问题VRP（Vehicle Routing Problem），使用较多的是遗传算法，但遗传算法存在早熟收敛问题，容易使算法陷入局部最优解。而蚁群算法具有正反馈机制和并行计算等优点，能够快速发现较好解并在各领域得到广泛应用。本文利用改进蚁群算法并采用伪随机规则求解带软硬时间窗的车辆路径问题，寻求最小成本路径。并探讨伪随机因子对解的影响，寻找最优伪随机因子。最后利用Matlab数值仿真论证该方法的有效性。

1问题描述和模型

1.1问题描述

本文研究的带混合时间窗的车辆路径问题VRPSHTW（vehicle Routing Problem with Soft and Hard Time Windows），可以描述为：某固定配送中心派发车辆，给已知的客户点进行配送，每个客户点只允许一辆车服务且每个客户点都有相应的配送时间、服务时间和货物需求量。车辆完成配送任务后，最后再返回到配送中心。车辆在配送过程中，需满足三个约束条件：（1）车辆不允许超载。（2）车辆的行驶距离不允许超过其最大行驶距离。（3）对于特定客户点，访问车辆必须在该时间窗口内服务，早到必须等待;对于一般客户点，访问车辆早于或晚于时间窗将受到惩罚。在满足所有约束条件下，求解最佳配送方案，以达到降低成本的目的。

1.2模型建立

2算法设计

2.1求解VRPSHTW的ACO算法执行流程

初始解构造的算法流程如图1所示：

初始化所有参数，设置当前迭代次数iter=l，最大迭代次数iter max，蚂蚁数目m，信息素挥发系数p，信息素重要程度因子α，启发函数重要程度因子β，信息素释放总量Q。且每只蚂蚁按照转移概率规则选择下一个将访问的节点，并判断访问的节点是否满足以下约束：（1）该节点未访问过;（2）满足车辆最大行驶距离;（3）满足车辆最大载重限制;（4）满足特殊节点的硬时间窗口限制。构建解空间。

2.2路径转移规则

当蚂蚁完全依赖随机概率规则访问下一个节点，仅由式（10）决定;当采用伪随机概率选择规则，蚂蚁从i移动到j节点的规则由式（9）和式（10）共同决定。

2.3信息素更新规则

信息素更新方式分为两种方式：局部更新信息素和全局更新信息素。这里采用全局更新信息素的方法，其更新规则如下：

2.4伪随机因子的改进

伪随机选择规则涉及参数伪随机因子q。，其参数取值仍处在探索阶段，直接影响运算结果和解的好坏。本文将对伪随机因子的取值进行探讨，选择最好的q。值，提高解质量。

3仿真分析

3.1数据集

为测试改进的蚁群算法求解VRPSHTW问题效果，应用文献中的实例进行分析比较，车辆最大载荷25，车辆最大行驶距离300，车辆固定发车成本150，单位运输成本为1，包括配送中心1节点共有15个节点。实例选取节点4、7和11作为硬时间窗约束，每个节点的数据如表1和表2所示，且不满硬时间窗约束的及节点将重新返回到配送中心。

3.2试验结果

（1）当算法采用随机概率规则（仅使用轮盘赌法访问下个节点），即此时伪随机因子值不存在。结果如图2和表4所示：

（2）当算法采用伪随机概率规则时，既可以利用关于问题的先验性知识，又可以进行倾向性的探索新路径。而在蚁群算法中，参数取值仍处在探索阶段，不具有普遍性，包括伪随机因子，q。取值大小调节蚂蚁“利用”和“探索”间的重要性，影响算法性能。由文献[13-18]可知，伪随机因子一般取值0.01、0.1、0.7、0.9。这里设伪随机因子取值分别为0.01、0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9。

结果如图3和表5所示：

从图2和表4可知，本文设计的蚁群算法求解带混合时间窗的车辆路径问题，使解的质量提高了14%。从图3和表5可知，伪随机因子取值既不能过大也不能过小。当q。值较大时，蚂蚁倾向于选择信息素浓度（先验值）较大的路径，有利于快速找到最优解。当q。值较小时，蚂蚁倾向于随机选择，有利于找到最新解。如何调节q。值大小，对运算结果有一定影响。根据仿真结果，当q。值为0.5时，取得最优解且平均解最优，对应最优成本1074.9元，解的质量在原改进基础上又提高了3%。总优化率17%。

4结论

本文根据客户对时间紧迫性要求不一致的情形，优化软硬时间窗下的车辆路径。构建VRPSHTW模型，利用改进蚁群算法，分别采用随机规则和伪随机规则，同时采用改进后的蚂蚁转移概率公式。并且该算法对晚于约定时间的硬时间窗客户做重新返回到配送中心的处理。再讨论伪随机因子对解的影响并找到最好q。值。通过Matlab数值仿真，与遗传算法计算结果比较，结果表明：改进蚁群算法可以得到更优的车辆配送方案。

（1）改进蚁群算法解决软硬时间窗车辆调度问题，可得到最优解。较参考文献中遗传算法，优化率提高了17%。

（2）采用伪随机规则比随机规则得到的解更优。当伪随机因子取值0.5时，解的质量最好。