一种求解带软时间窗物流运输车辆路径问题的方法

摘要

本发明公开了一种求解带软时间窗物流运输车辆路径问题的方法，针对基于实时交通信息的带软时间窗物流运输车辆路径问题，采用时间窗惩罚机制，建立其数学模型；使用自适应混沌蚁群算法求解该模型，通过算法信息素的自适应更新和算法参数的混沌自适应调整来提高算法的寻优能力。本发明与现实生产生活中的物流配送更加吻合，运用自适应混沌蚁群算法求解该问题，因具有更好的优化搜索能力，有效避免搜索过程陷入局部最优，提高解的多样性和全局寻优能力，改进全局更新策略，引入精英策略，适当提高优质蚂蚁释放的信息素的正反馈；设置信息素及信息素增量的上下限以减小路径上信息素的过大差异，利用自适应混沌蚁群算法解决经典的车辆路径寻优问题。

主权项

一种求解带软时间窗物流运输车辆路径问题的方法，其特征在于，包括以下步骤：S1、获取基于实时交通信息的带软时间窗VRP问题基本参数：物流配送中心的位置，客户的地理位置，客户货物需求量，客户的时间窗约束以及车辆的信息；S2、在问题中，客户具有软时间窗要求：送货的时间窗为[et_i，lt_i]，配送车辆在配送点i的最早服务时间为et_i，最晚到达配送时间为lt_i，迟到或者早到都会产生惩罚费用；每小时等待费用为c₁，每小时延迟费用为c₂；车辆行驶速度由不同时间段决定，1个调度周期分为若干离散区间时段，车辆在各个时段的行驶速度是变化的，各区间内部行驶速度一定，调度中心只能知道当前时间行驶速度，未来时间行驶速度与当前速度相同处理；S3、定义如下变量：S4、根据如下约束条件建立基于实时交通信息的带软时间窗物流运输车辆路径问题的数学模型：(1)1个车场，N个客户，客户需求量确定；(2)同种车型，非满载；(3)每辆车有最大配送距离约束和载重约束；(4)闭合式车辆路径；(5)客户的时间窗已知，软时间窗限制，且每个客户的时间窗要求已知；(6)求解目标：在城市动态交通信息网中找到一组服务所有客户的最优物流配送路径，达到配送成本最低；S5、设计蚁群算法信息素的自适应更新来提高算法的寻优能力、抗噪性，进而避免算法陷入局部最优，具体表现为：S5‑1、改进全局更新策略，引入精英策略，在每次算法循环后会给全局度量函数值大于本次迭代平均全局度量函数值的路径进行信息素更新，而对小于本次迭代平均全局度量值的路径不进行信息素更新，全局更新规则只用于最优解路径上，规则如下：上式中，Q表示信息素强度，其值为常量，L_gb表示当前找到的全局最优路径长度；S5‑2、设置信息素及信息素增量的上下限以减小路径上信息素的过大差异，通过适当调整，将各条路径上的信息素强度限制在区间[τ_min,τ_max]内，同时在每次更新信息素时将信息素增量限制在区间[Δτ_min,Δτ_max]，根据上述改进和优化，信息素自适应更新的总表达式为：在(4)式中，信息素增量S6、设计蚁群算法计算参数的混沌自适应调整，提高算法对该数学模型的寻优能力和计算效率；蚁群算法每代次迭代寻优开始时α取初值为1到5之间的任意数，ρ取的初值为0.1‑0.5之间的任意数，而后按如下式对启发因子α和信息素挥发系数ρ进行混沌自适应调整：S7、利用自适应混沌蚁群算法寻求基于实时交通信息的带软时间窗物流运输车辆路径问题的最优配送路径，具体步骤如下：S7‑1、初始化自适应混沌蚁群算法参数：最大迭代次数NC_max，蚂蚁个数m，ρ₍₀₎，α₍₀₎，Q，τ，Δτ，迭代计数器NC＝0；S7‑2、蚂蚁从配送中心的位置出发；S7‑3、对蚂蚁k从1到m，重复S7‑4和S7‑6步骤，直到蚂蚁k遍历完所有的配送点。