一种基于蚁算法的带道路与时间窗车辆路径优化方法

阅读：评论：0

1.本发明涉及本发明属于车辆路径优化领域，尤其涉及一种基于蚁算法的带道路与时间窗车辆路径优化方法。

背景技术：

2.随着科技的快速发展，企业智能化、数字化程度的不断提高，对物流配送提出了更高的要求。企业越来越重视车间实际道路环境与客户的服务水平，因此，研究带车间道路与时间窗的车辆路径问题具有非常重要的实际意义。
3.车辆路径问题(vehicle routing problem，vrp)，由dantzig等学者于1959年首次提出。该问题一般是指给定配送中心、客户的位置以及各个客户的需求量，车辆从配送中心出发，完成配送任务后回到配送中心，确定合理的配送方案，在满足车辆装载能力和行程限制等约束条件下使得某些目标达到最优(如总行程最短、使用车辆数量最少、成本最小等)。solomon将带有时间窗的车辆路径问题定义为：车辆从配送中心出发，在满足各个客户的服务时间约束下，将货物运送到客户手中，最后返回配送中心，使行驶的总行程最短。带车间道路的车辆路径问题是指：满足车间实际道路环境约束的车辆路径调度规划，而不是简单的求两个点之间的欧式距离。
4.目前主要求解vrp问题的方法有精确算法和启发式算法。只有小规模问题才能用精确算法在较短的时间内寻求其精确解。因此，设计有效的启发式算法来寻求大规模车辆路径问题的近似解是一个重要的研究方向。经典启发式算法采用局部搜索寻求满意解，算法易实现但容易陷入局部最优。智能启发式算法采用全局搜索来寻求满意解，能避免陷入局部最优，但算法设计较为复杂，参数设置对算法影响较大。如近年来发展起来的遗传算法、粒子算法、蝙蝠算法、蚁算法等越来越多地应用于vrp领域。然而在实际应用中，粒子优化算法和人工神经网络在迭代后期易陷入局部最优，遗传算法初始种敏感易早熟，蚁算法虽然寻优能力较强却依赖于参数设置，故启发式优化算法的实用性、寻优效率及应用价值均有待提高。
5.虽然国内外学者已经对带时间窗的车辆路径问题开展了诸多研究，但是大多数研究仅考虑时间窗约束，对于涉及车间实际道路和时间窗约束的车辆路径问题较少，而实际企业中是包含着车间通道环境约束的，故需要对此问题进行深入研究。

技术实现要素：

6.为了解决目前带车间道路和时间窗约束的车辆路径优化方法收敛速度慢、通用性低、无法跳出局部最优解、稳定性差、解的质量不高等问题，本发明提供一种求解速度快、通用性强、搜索效率高、能跳出局部最优解、提高最优解质量的改进蚁算法。
7.本发明的目的是通过以下技术方案来实现的：一种基于蚁算法的带道路与时间窗车辆路径优化方法，包括以下步骤：
8.s1、以包括车辆可变距离运输成本、固定车辆运输成本和车辆等待时间成本在内
的总物流配送成本最小化为目标，建立了带软时间窗约束的车辆路径优化模型；
9.s2、根据车间实际布局的物流路线构建了各工位需求点的距离关系，调用floyd算法求解得到最短距离矩阵；
10.s3、在蚁算法状态转移规则中增加了赌法选择下一目标点从而跳出局部最优解；在状态转移概率中增加了工位配送时间窗宽度和车辆等待时间长度两个影响选择下一目标点的因素；
11.在蚁算法信息素更新中，使用自适应挥发因子加快前期收敛速度，将当前迭代过程中走过最佳路线的总成本代替路径长度作为影响信息素更新的因素，得到改进的蚁算法；
12.采用改进的蚁算法对步骤s2求得的距离矩阵进行多次状态转移和信息素更新操作，通过多次迭代逐渐使可行解向最优解靠近，从而得到所有车辆的最优路径。
13.进一步地，步骤(1)车辆路径优化模型如下所示：
14.所述车辆路径优化模型包括总物流运输成本最小化的目标函数和设定约束条件；
15.配送中心o拥有m辆载重为q的物流配送车辆，物流配送车辆集合为k＝{k1，k2，
…
，km}，配送车辆负责对n个需求点进行配送，需求点集合为i，其中每个需求点i的货物需求质量为qi；c
ij
表示配送车辆从需求点i到需求点j的可变成本，其中c
ij
＝c1d
ij
，c1为车辆行驶距离单位成本，d
ij
为需求点i到需求点j的距离，t
ij
为需求点i到需求点j点的时间，c2为车辆固定成本；满足需求点i的软时间窗为[ei，li]，ei是需求点i最早服务时间窗，li是需求点i最晚服务时间窗，需求点i服务时间为si，为第k辆配送车辆在到达需求点i的时刻，t
i’k
为配送车辆在需求点i离开的时刻，为在需求点i处等待的时间，π1为提前时间惩罚单位成本，为服务时间成本函数；其中服务时间成本函数如公式(1)所示；
[0016][0017]
在满足车辆最大装载量和时间窗约束的前提下使行驶距离成本车辆数量成本和等待时间惩罚成本在内的总物流运输成本最小化是该问题的目标；x
ijk
是第k辆车从需求点i到需求点j的数值，取值为0或1；x
ojk
是第k辆车从配送中心o到需求点j的数值，取值为0或1；建立如下目标函数：
[0018][0019]
所述车辆路径优化模型的设定约束条件如下：
[0020][0021]
[0022][0023]
t
i'k
＝t
ik
+wt
ik
+si,i∈i，k∈k
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)
[0024]
wt
ik
＝max[0,(e
i-t
ik
)],i∈i
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(7)
[0025][0026]
t
ik
≤li,i∈i
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(9)
[0027]
x
ijk
∈{0,1},i,j∈i,i≠j,k∈k
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(10)
[0028]
约束(3)表示每个需求点i必须被一辆配送汽车配送一次，x
ik
是第k辆车经过需求点i的数值，取值为0或1；约束(4)表示到达和离开任意一个点的车辆数相等，从而保证了路由的连续性，x
ijk
是第k辆车从需求点i到需求点j的数值，取值为0或1，x
jik
是第k辆车从需求点j到需求点i的数值，取值为0或1；约束(5)表示配送车辆的装载质量不得超过车辆最大装载量；约束(6)表示离开需求点i处的时间为到达需求点i处的时间、等待时间和服务时间之和；约束(7)表示在需求点i处的等待时间；约束(8)表示到达需求点j处的时间t
jk
是从需求点i处出发时间与路径(i，j)的行驶时间之和；约束(9)表示车辆在需求点i处的到达时间不能超过需求点i的最晚时间窗范围；约束条件(10)表示决策变量为二进制。
[0029]
进一步地，所述步骤(2)采用floyd算法生成符合车间实际道路环境的最短距离矩阵，车间实际道路环境含义是结合车间实际布局的物流路线代替任意两需求点间直线相连的思想，基于车间通道节点约束求解最短距离矩阵；包括以下步骤：
[0030]
步骤2.1，初始化矩阵；根据需求点数量初始化距离矩阵；
[0031]
步骤2.2，记录已知节点之间最短距离信息，更新距离矩阵；
[0032]
步骤2.3，判断并更新距离矩阵；如果路径距离d(i,h)+d(h,j)《d(i,j)，则更新最短距离矩阵d(i,j)＝d(i,h)+d(h,j)；d(i,h)表示需求点i到需求点h的距离，d(h,j)表示需求点h到需求点j的距离，d(i,j)表示需求点i到需求点j的距离；
[0033]
步骤2.4，判断是否历经了所有节点；
[0034]
步骤2.5，输出结果；求解得到带道路的最短距离矩阵。
[0035]
进一步地，所述步骤(3)具体步骤如下：
[0036]
步骤3.1，初始化参数；
[0037]
步骤3.2，令迭代次数nc＝1，将m辆车随机放在调度中心，设置k＝1；
[0038]
步骤3.3，重置第k辆车的访问节点集合ni；根据状态转移概率选择下一个要访问的需求点判断需求点j的需求量和目前车辆装载量的和是否超过第k辆车的最大装载量，超过第k辆车的最大装载量则转到步骤3.4，若没有超过第k辆车的最大装载量，则更新第k辆车的访问节点集合ni和禁忌表；
[0039]
状态转移概率包含以下内容：构建一个0到1之间的随机数r，制定一个控制状态转移规则的参数r0；如果r≤r0，则选择状态转移概率最大的点作为前进的下一点；如果r＞r0，则根据各点的状态转移概率利用赌的方法挑选前进的下一点；
[0040]
当r≤r0时，通过计算状态转移概率选择下一目标点，状态转移概率公式如下：
[0041][0042]
其中，p
ijk
(t)表示选择下一节点的转移概率，τ
ij
为路段d
ij
上释放的信息素浓度，α和β分别表示信息素和启发函数的影响程度因子，w
1j
是需求点j配送时间窗宽度，w
2j
是车辆到达需求点j的等待时间长度，γ和δ分别表示时间窗跨度和等待时间的重要程度因子,η
ij
为路段d
ij
的启发函数；启发函数计算公式为：
[0043][0044]
当r＞r0时，利用赌法随机挑选下一点；对于需求点j的需求量和目前车辆装载量的和没有超过第k辆车的最大装载量的点，根据状态转移概率的大小进行排序，构建一个0到1之间的随机数r，如果r≥pp(i-1)并且r≤pp(i)，则挑选需求点i作为路径的下一点；pp(i)代表排序在需求点i之前所有点的状态转移概率之和；
[0045]
步骤3.4，如果进入步骤3.5；否则，k＝k+1，转到步骤3.3；
[0046]
步骤3.5，一次循环停止标准：如果k》m，则停止，记录进全局可行解集m并进入步骤3.6；否则，k＝k+1转到步骤3.3；
[0047]
步骤3.6，算法停止：如果迭代次数小于等于预先设定的最大迭代次数nc
max
，记录全局可行解集m里的所有解并进入步骤3.7；否则，算法终止并输出m作为所有车辆的最优路径；
[0048]
步骤3.7，解的评估：根据适应度函数f(x)＝1/z判断本次迭代产生的最优路径s是否较之前所得的最优路径s*更优、若并没有之前所得的解更优，则不更新s*，并且返回步骤3.3，重新进行寻优；若s比s*更优，则将s*更新为s；
[0049]
步骤3.8，更新信息素；
[0050]
步骤3.8.1，设置挥发因子ρ的值；为平衡算法的局部和全局搜索能力，避免陷入早熟，本文将挥发因子ρ设置为如式(13)的自适应调整方式：
[0051][0052]
步骤3.8.2，当蚂蚁在每次迭代中到该次迭代的最优路径时，通过式(14)执行全局信息素更新：
[0053][0054]
在这个等式中，δτ
ijk
(t)表示在t时刻，路径(i，j)上的信息素的值，由第k辆车来释放；ρ为信息素挥发系数；
[0055][0056]
在式(15)中，q代表更新信息素浓度的常数，cost
best
代表第k辆车在当前迭代过程中走过最优路径的总成本；
[0057]
步骤3.9，设置nc＝nc+1，重置禁忌表，进入步骤3.3。
[0058]
本发明的有益效果：
[0059]
建立了带时间窗约束的车辆路径优化模型，以行驶距离成本、使用车辆数量成本和车辆等待时间惩罚成本在内的总物流运输成本最小化为目标；利用floyd算法根据已知信息求解得到了更符合车间实际道路情况的配送路径，最终得到的距离矩阵作为调用改进蚁算法求解车辆路径问题的输入；提出了一种改进蚁算法来求解该车辆路径问题，通过改进状态转移规则、自适应信息素挥发因子和改进信息素更新相关参数来平衡算法的局部和全局搜索能力，提高了算法求解速度和搜索效率、跳出局部最优解、提高最优解质量。
附图说明
[0060]
图1是本发明实施例提供的一种基于蚁算法的带道路与时间窗车辆路径优化方法流程图；
[0061]
图2是本发明实施例提供的车辆等待时间惩罚成本函数示意图；
[0062]
图3是本发明实施例提供的floyd算法的流程示意图；
[0063]
图4是本发明实施例提供的蚁算法的流程示意图；
[0064]
图5是本发明实施例提供的车间实际道路约束示意图；
[0065]
图6是本发明实施例提供的各代最小成本变化趋势示意图；
[0066]
图7是本发明实施例提供的最优方案路径图。
具体实施方式
[0067]
以下结合附图对本发明具体实施方式作进一步详细说明。
[0068]
本发明提供的一种参照图1，一种基于蚁算法的带道路与时间窗车辆路径优化方法，所述优化方法步骤如下：
[0069]
步骤1：以最小化总物流配送成本为目标，构建带时间窗约束的车辆路径优化模型。
[0070]
配送中心o拥有m辆载重为q的物流配送车辆，物流配送车辆集合为k＝{k1，k2，
…
，km}，配送车辆负责对n个需求点进行配送，需求点集合为i，其中每个需求点i的货物需求质量为qi；c
ij
表示配送车辆从需求点i到需求点j的可变成本，其中c
ij
＝c1d
ij
，c1为车辆行驶距离单位成本，d
ij
为需求点i到需求点j的距离，t
ij
为需求点i到需求点j点的时间，c2为车辆固定成本；满足需求点i的软时间窗为[ei，li]，ei是需求点i最早服务时间窗，li是需求点i最晚服务时间窗，需求点i服务时间为si，为第k辆配送车辆在到达需求点i的时刻，t
i’k
为配送车辆在需求点i离开的时刻，为在需求点i处等待的时间，π1为提前时间惩罚单位成
本，为服务时间成本函数。其中服务时间成本函数如图2所示，车辆在需求点最早服务时间前到达会付出提前时间惩罚成本，在服务时间窗内到达不付出任何成本，不允许超过需求点最晚服务时间到达。
[0071][0072]
在满足车辆最大装载量和时间窗约束的前提下使行驶距离成本车辆数量成本和等待时间惩罚成本在内的总物流运输成本最小化是该问题的目标；x
ijk
是第k辆车从需求点i到需求点j的数值，取值为0或1；x
ojk
是第k辆车从配送中心o到需求点j的数值，取值为0或1；建立如下目标函数：
[0073][0074]
所述车辆路径优化模型的设定约束条件如下：
[0075][0076][0077][0078]
t
i'k
＝t
ik
+wt
ik
+si,i∈i，k∈k
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)
[0079]
wt
ik
＝max[0,(e
i-t
ik
)],i∈i
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(7)
[0080][0081]
t
ik
≤li,i∈i
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(9)
[0082]
x
ijk
∈{0,1},i,j∈i,i≠j,k∈k
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(10)
[0083]
约束(3)表示每个需求点i必须被一辆配送汽车配送一次，x
ik
是第k辆车经过需求点i的数值，取值为0或1；约束(4)表示到达和离开任意一个点的车辆数相等，从而保证了路由的连续性，x
ijk
是第k辆车从需求点i到需求点j的数值，取值为0或1，x
jik
是第k辆车从需求点j到需求点i的数值，取值为0或1；约束(5)表示配送车辆的装载质量不得超过车辆最大装载量；约束(6)表示离开需求点i处的时间为到达需求点i处的时间、等待时间和服务时间之和；约束(7)表示在需求点i处的等待时间；约束(8)表示到达需求点j处的时间t
jk
是从需求点i处出发时间与路径(i，j)的行驶时间之和；约束(9)表示车辆在需求点i处的到达时间不能超过需求点i的最晚时间窗范围；约束条件(10)表示决策变量为二进制。
[0084]
步骤2：根据车间实际通道环境约束构建了各工位需求点的距离关系代替任意两工位需求点间直线相连的思想，调用floyd算法求解得到距离矩阵；流程如图3所示，所述步骤如下：
[0085]
步骤2.1，初始化矩阵；根据需求点数量初始化距离矩阵；
[0086]
步骤2.2，记录已知节点之间最短距离信息，更新距离矩阵；
[0087]
步骤2.3，判断并更新距离矩阵；如果路径距离d(i,h)+d(h,j)《d(i,j)，则更新最短距离矩阵d(i,j)＝d(i,h)+d(h,j)，d(i,h)表示需求点i到需求点h的距离，d(h,j)表示需求点h到需求点j的距离，d(i,j)表示需求点i到需求点j的距离；
[0088]
步骤2.4，判断是否历经了所有节点；
[0089]
步骤2.5，输出结果；求解得到带道路的最短距离矩阵。
[0090]
步骤3：采用改进的蚁算法对该距离矩阵进行多次状态转移和信息素更新操作，通过多次迭代逐渐使可行解向最优解靠近，从而得到最优路径，如图4所示。包括以下步骤：
[0091]
步骤3.1，初始化参数；
[0092]
步骤3.2，令迭代次数nc＝1，将m辆车随机放在调度中心，设置k＝1；
[0093]
步骤3.3，重置第k辆车的访问节点集合ni；根据状态转移概率选择下一个要访问的需求点判断需求点j的需求量和目前车辆装载量的和是否超过第k辆车的最大装载量，超过第k辆车的最大装载量则转到步骤3.4，若没有超过第k辆车的最大装载量，则更新第k辆车的访问节点集合ni和禁忌表；
[0094]
状态转移概率包含以下内容：构建一个0到1之间的随机数r，制定一个控制状态转移规则的参数r0；如果r≤r0，则选择状态转移概率最大的点作为前进的下一点；如果r＞r0，则根据各点的状态转移概率利用赌的方法挑选前进的下一点；
[0095]
当r≤r0时，通过计算状态转移概率选择下一目标点，状态转移概率公式如下：
[0096][0097]
其中，p
ijk
(t)表示选择下一节点的转移概率，τ
ij
为路段d
ij
上释放的信息素浓度，α和β分别表示信息素和启发函数的影响程度因子，w
1j
是需求点j配送时间窗宽度，w
2j
是车辆到达需求点j的等待时间长度，γ和δ分别表示时间窗跨度和等待时间的重要程度因子,η
ij
为路段d
ij
的启发函数；启发函数计算公式为：
[0098][0099]
当r＞r0时，利用赌法随机挑选下一点；对于需求点j的需求量和目前车辆装载量的和没有超过第k辆车的最大装载量的点，根据状态转移概率的大小进行排序，构建一个0到1之间的随机数r，如果r≥pp(i-1)并且r≤pp(i)，则挑选需求点i作为路径的下一点；pp(i)代表排序在需求点i之前所有点的状态转移概率之和；
[0100]
步骤3.4，如果进入步骤3.5；否则，k＝k+1转到步骤3.3；
[0101]
步骤3.5，一次循环停止标准：如果k》m，则停止，记录进全局可行解集m并进入步骤3.6；否则，k＝k+1转到步骤3.3；
[0102]
步骤3.6，算法停止：如果迭代次数小于等于预先设定的最大迭代次数nc
max
，记录全局可行解集m里的所有解并进入步骤3.7；否则，算法终止并输出m作为所有车辆的最优路径；
[0103]
步骤3.7，解的评估：根据适应度函数f(x)＝1/z判断本次迭代产生的最优路径s是否较之前所得的最优路径s*更优、若并没有之前所得的解更优，则不更新s*，并且返回步骤3.3，重新进行寻优；若s比s*更优，则将s*更新为s；
[0104]
步骤3.8，更新信息素；
[0105]
步骤3.8.1，设置挥发因子ρ的值；为平衡算法的局部和全局搜索能力，避免陷入早熟，本文将挥发因子ρ设置为如式(13)的自适应调整方式：
[0106][0107]
步骤3.8.2，当蚂蚁在每次迭代中到该次迭代的最优路径时，通过式(14)执行全局信息素更新：
[0108][0109]
在这个等式中，δτ
ijk
(t)表示在t时刻，边(i，j)上的信息素的值，由第k辆车来释放；ρ为信息素挥发系数；
[0110][0111]
在式(15)中，q代表更新信息素浓度的常数，cost
best
代表第k辆车在当前迭代过程中走过最优路径的总成本；
[0112]
步骤3.9，设置nc＝nc+1，重置禁忌表，进入步骤3.3。
[0113]
实施例：某浴霸公司的自动车间有4条产线，共24个工位需要进行物料配送，车辆共有8辆。车间实际道路环境如图5所示，序号1为配送起点；序号2～9为转弯节点，共8个转弯节点；序号10～33为工位需求点，共24个工位需求点。其具体信息如表1所示，agv的运行速度为1m/s，承载量为8，行驶距离可变成本为1，车辆固定成本为1000，时间惩罚成本为1。要求合理安排车辆及其配送的行驶路线，使所有车辆的总成本最少。
[0114]
表1各点位的坐标、需求量和服务时间窗
[0115][0116][0117]
参数在多次调试后最终设置为：种蚂蚁规模m＝50，信息素重要程度因子α＝1，启发函数重要程度因子β＝3，时间窗跨度重要程度因子γ＝2，等待时间重要程度因子δ＝0.5，全局信息素常量q＝5，控制状态转移规则的参数r0＝0.5。实施以最小化总物流配送成本为目标，执行基于改进蚁算法的带车间道路与时间窗的车辆路径优化方法后，得到了如图6所示的各代最小成本变化趋势，在迭代次数达到56次时最小成本不再变化，得到最优解；最优配送方案的路径如图7所示。具体调度方案如表2所示。
[0118]
表2改进蚁算法的车辆调度方案
[0119][0120]
调用基本蚁算法求解该车辆路径问题，具体调度方案如表3所示。
[0121]
表3基本蚁算法的车辆调度方案
[0122][0123]
改进蚁算法与基本蚁算法性能对比，见表4所示。
[0124]
表4改进蚁算法与基本蚁算法性能对比
[0125][0126][0127]
通过对比分析可知，改进蚁算法在算法收敛速度和运行时间上的性能比基本蚁算法更优，得到的最佳配送方案在车辆使用数量、物流总成本和车辆平均装载率上的结果更佳。采用本发明所述方法在解决带车间道路与时间窗车辆路径调度问题方面，模型通用性强，方法搜索效率高、搜索空间广，收敛速度快，而且所求解的质量和稳定性明显提高。
[0128]
上述实施例用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。

技术特征：

1.一种基于蚁算法的带道路与时间窗车辆路径优化方法，其特征在于，包括以下步骤：s1、以包括车辆可变距离运输成本、固定车辆运输成本和车辆等待时间成本在内的总物流配送成本最小化为目标，建立带软时间窗约束的车辆路径优化模型；s2、根据车间实际布局的物流路线构建了各工位需求点的距离关系，调用floyd算法求解得到最短距离矩阵；s3、在蚁算法状态转移规则中增加了赌法选择下一目标点从而跳出局部最优解；在状态转移概率中增加了工位配送时间窗宽度和车辆等待时间长度两个影响选择下一目标点的因素；在蚁算法信息素更新中，使用自适应挥发因子加快前期收敛速度，将当前迭代过程中走过最佳路线的总成本代替路径长度作为影响信息素更新的因素，得到改进的蚁算法；采用改进的蚁算法对步骤s2求得的距离矩阵进行多次状态转移和信息素更新操作，通过多次迭代逐渐使可行解向最优解靠近，从而得到所有车辆的最优路径。2.根据权利要求1所述的一种基于蚁算法的带道路与时间窗车辆路径优化方法，其特征在于，步骤(1)车辆路径优化模型如下所示：所述车辆路径优化模型包括总物流运输成本最小化的目标函数和设定约束条件；配送中心o拥有m辆载重为q的物流配送车辆，物流配送车辆集合为k＝{k1，k2，
…
，k
m
}，配送车辆负责对n个需求点进行配送，需求点集合为i，其中每个需求点i的货物需求质量为q
i
；c
ij
表示配送车辆从需求点i到需求点j的可变成本，其中c
ij
＝c1d
ij
，c1为车辆行驶距离单位成本，d
ij
为需求点i到需求点j的距离，t
ij
为需求点i到需求点j点的时间，c2为车辆固定成本；满足需求点i的软时间窗为[e
i
，l
i
]，e
i
是需求点i最早服务时间窗，l
i
是需求点i最晚服务时间窗，需求点i服务时间为s
i
，t
ik
为第k辆配送车辆在到达需求点i的时刻，t
i’k
为配送车辆在需求点i离开的时刻，wt
ik
为在需求点i处等待的时间，π1为提前时间惩罚单位成本，s(t
ik
)为服务时间成本函数；其中服务时间成本函数如公式(1)所示；在满足车辆最大装载量和时间窗约束的前提下使行驶距离成本车辆数量成本和等待时间惩罚成本在内的总物流运输成本最小化是该问题的目标；x
ijk
是第k辆车从需求点i到需求点j的数值，取值为0或1；x
ojk
是第k辆车从配送中心o到需求点j的数值，取值为0或1；建立如下目标函数：所述车辆路径优化模型的约束条件如下：
t
i
'
k
＝t
ik
+wt
ik
+s
i
,i∈i，k∈k
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)wt
ik
＝max[0,(e
i-t
ik
)],i∈i
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(7)t
ik
≤l
i
,i∈i
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(9)x
ijk
∈{0,1},i,j∈i,i≠j,k∈k
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(10)约束(3)表示每个需求点i必须被一辆配送汽车配送一次，x
ik
是第k辆车经过需求点i的数值，取值为0或1；约束(4)表示到达和离开任意一个点的车辆数相等，从而保证了路由的连续性，x
ijk
是第k辆车从需求点i到需求点j的数值，取值为0或1，x
jik
是第k辆车从需求点j到需求点i的数值，取值为0或1；约束(5)表示配送车辆的装载质量不得超过车辆最大装载量；约束(6)表示离开需求点i处的时间为到达需求点i处的时间、等待时间和服务时间之和；约束(7)表示在需求点i处的等待时间；约束(8)表示到达需求点j处的时间t
jk
是从需求点i处出发时间与路径(i，j)的行驶时间之和；约束(9)表示车辆在需求点i处的到达时间不能超过需求点i的最晚时间窗范围；约束条件(10)表示决策变量为二进制。3.根据权利要求2所述的一种基于蚁算法的带道路与时间窗车辆路径优化方法，其特征在于，所述步骤(2)采用floyd算法生成符合车间实际道路环境的最短距离矩阵，车间实际道路环境含义是结合车间实际布局的物流路线代替任意两需求点间直线相连的思想，基于车间通道节点约束求解最短距离矩阵；包括以下步骤：步骤2.1，初始化矩阵；根据需求点数量初始化距离矩阵；步骤2.2，记录已知节点之间最短距离信息，更新距离矩阵；步骤2.3，判断并更新距离矩阵；如果路径距离d(i,h)+d(h,j)<d(i,j)，则更新最短距离矩阵d(i,j)＝d(i,h)+d(h,j)；d(i,h)表示需求点i到需求点h的距离，d(h,j)表示需求点h到需求点j的距离，d(i,j)表示需求点i到需求点j的距离；步骤2.4，判断是否历经了所有节点；步骤2.5，输出结果；求解得到带道路的最短距离矩阵。4.根据权利要求3所述的一种基于蚁算法的带道路与时间窗车辆路径优化方法，其特征在于，所述步骤(3)具体步骤如下：步骤3.1，初始化参数；步骤3.2，令迭代次数nc＝1，将m辆车随机放在调度中心，设置k＝1；步骤3.3，重置第k辆车的访问节点集合n
i
；根据状态转移概率选择下一个要访问的需求点判断需求点j的需求量和目前车辆装载量的和是否超过第k辆车的最大装载量，超过第k辆车的最大装载量则转到步骤3.4，若没有超过第k辆车的最大装载量，则更新第k辆车的访问节点集合n
i
和禁忌表；
状态转移概率包含以下内容：构建一个0到1之间的随机数r，制定一个控制状态转移规则的参数r0；如果r≤r0，则选择状态转移概率最大的点作为前进的下一点；如果r＞r0，则根据各点的状态转移概率利用赌的方法挑选前进的下一点；当r≤r0时，通过计算状态转移概率选择下一目标点，状态转移概率公式如下：其中，p
ijk
(t)表示选择下一节点的转移概率，τ
ij
为路段d
ij
上释放的信息素浓度，α和β分别表示信息素和启发函数的影响程度因子，w
1j
是需求点j配送时间窗宽度，w
2j
是车辆到达需求点j的等待时间长度，γ和δ分别表示时间窗跨度和等待时间的重要程度因子,η
ij
为路段d
ij
的启发函数；启发函数计算公式为：当r＞r0时，利用赌法随机挑选下一点；对于需求点j的需求量和目前车辆装载量的和没有超过第k辆车的最大装载量的点，根据状态转移概率的大小进行排序，构建一个0到1之间的随机数r，如果r≥pp(i-1)并且r≤pp(i)，则挑选需求点i作为路径的下一点；pp(i)代表排序在需求点i之前所有点的状态转移概率之和；步骤3.4，如果进入步骤3.5；否则，k＝k+1，转到步骤3.3；步骤3.5，一次循环停止标准：如果k>m，则停止，记录进全局可行解集m并进入步骤3.6；否则，k＝k+1转到步骤3.3；步骤3.6，算法停止：如果迭代次数小于等于预先设定的最大迭代次数nc
max
，记录全局可行解集m里的所有解并进入步骤3.7；否则，算法终止并输出m作为所有车辆的最优路径；步骤3.7，解的评估：根据适应度函数f(x)＝1/z判断本次迭代产生的最优路径s是否较之前所得的最优路径s*更优、若并没有之前所得的解更优，则不更新s*；若s比s*更优，则将s*更新为s；步骤3.8，更新信息素；步骤3.8.1，设置挥发因子ρ的值；为平衡算法的局部和全局搜索能力，避免陷入早熟，将挥发因子ρ设置为如式(13)的自适应调整方式：步骤3.8.2，当蚂蚁在每次迭代中到该次迭代的最优路径时，通过式(14)执行全局信息素更新：
在这个等式中，δτ
ijk
(t)表示在t时刻，路径(i，j)上的信息素的值，由第k辆车来释放；ρ为信息素挥发系数；在式(15)中，q代表更新信息素浓度的常数，cost
best
代表第k辆车在当前迭代过程中走过最优路径的总成本；步骤3.9，设置nc＝nc+1，重置禁忌表，进入步骤3.3。

技术总结

本发明公开了一种基于蚁算法的带道路与时间窗车辆路径优化方法，该方法包括：以总物流配送成本最低为目标建立目标函数，构建带时间窗约束车辆路径问题优化模型，并设定约束条件；根据已知的车间各工位需求点距离信息，采用Floyd算法生成符合车间实际道路环境的最短距离矩阵；设计蚁算法的状态转移规则和信息素更新相关参数，采用改进的蚁算法对求得的距离矩阵进行多次状态转移和信息素更新操作，通过多次迭代逐渐使可行解向最优解靠近，从而得到最优路径。本发明旨在有效求得优良的车辆行驶路线，降低物流配送成本；提高算法的搜索效率与收敛速度，跳出局部最优解，增加最优解的数量。优解的数量。优解的数量。