基于量子蚁群算法的随机需求的动态车辆路径问题

宁涛,焦璇,魏瑛琦,梁旭

(1.大连交通大学 软件学院，辽宁 大连 116054; 2.大连东软信息学院 会计学院,辽宁 大连 116023)*

0 引言

车辆路径问题(Vehicle Routing Problem，VRP)自1959年Dantzig和Ramser[1]提出以来，受到研究者们广泛关注.在物流配送中可能出现新增客户点、原客户点的需求发生改变、交通堵塞或天气状况等问题而重新调整配送路线，这类问题即为动态车辆路径问题(Dynamic Vehicle Routing Problem,DVRP).近年来国内外学者在该问题上进行了相关研究，Zhiwei Yang[2]等针对车辆配送过程中需求变更或时间窗变更的情况提出了一种多重蚁群算法，该算法具有强大的局部搜索能力.Briseida Sarasola[3]等研究了随机需求或需求动态变更的车辆路径问题，提出了可扩展的变邻域搜索算法.Yinan Guo[4]等针对带有硬时间窗口和随机需求的车辆路径问题，提出了局部优化策略的鲁棒动态车辆路径方案.Nicolas Zufferey[5]等研究了扩展环境下的动态车辆路径问题.宁涛[6]针对动态车辆问题提出了车辆链和货物链的双链量子编码方法和改进的多向量子粒群算法.Michalis Mavrovouniotis[7]针对用蚁群算法求解动态车辆路径问题提出了新的方案，该方案能够保证种群的多样性，避免过早收敛.Tao Ning 等[8]针对需求变更的动态车辆路径问题，提出了一种基于可变邻域搜索的元启发式来求解.M. Schyns[9]等提出一种基于蚁群系统的算法来处理动态时间窗口，分离交付和异构车队的车辆路径问题.Jalel Euchi[10]等提出了一种基于2_Opt本地搜索的人造蚁群来解决动态车辆路径问题.S. Masrom[11]等提出将动态参数化突变和交叉算子与粒子群算法相结合.

本文提出了用量子蚁群算法来求解随机需求的动态车辆路径问题，建立了两阶段模型，将DVRP转化成了静态VRP，考虑到客户对物流配送的满意程度，本文引入了模糊隶属度函数.

1 问题描述

随机需求的DVRP阶段的数学模型可被描述为由1个配送中心和L个已知客户点组成，派出K辆车对L个客户点进行服务，K辆车从配送中心出发，完成配送任务后再返回配送中心，K辆车均为同一车型，具有相同的车载量Q.

具体定义如下：

L:初始阶段客户总数，i={0，1，2，…，L} ；其中i=0表示配送中心，i=1，2，…，L表示客户点；K表示配送中心车辆数，K={1，2，…，K}；F表示派出一辆车的固定成本；Q表示车辆最大容载量；qi表示每个客户的需求；dij表示从i到j距离；cij表示从i到j的单位运输费用；ωijk表示车辆K从i到j的运输量.

决策变量定义如下：

目标函数如下：

(1)

其中,Z为衡量客户满意度的度量，取值范围为0～1，本文将最小化车辆费用与最小化客户不满意度相加求和，但Z的数量级与车辆配送成本的数量级相差甚远，所以本文采用公式α=F×β将客户满意度与车辆配送费用变为同一数量级别，本文β取0.5.

约束条件：

含义如下：式(1)为目标函数，式(2)为车辆能力约束，式(3)表示每个客户都被服务一次，式(4)、(5)表示客户被且仅被一辆车服务，式(6)表示车辆从i到j的运输量大于客户j的需求量.

2 改进量子蚁群算法

蚁群算法是一种具有较强寻优能力且鲁棒性强的算法，但当种群规模较大时，容易陷入局部最优，许多研究者将蚁群算法与其他算法结合，量子算法是近年来研究的热点，该算法因其优越的编码方式能够同时表达多个态的叠加，事实证明，该算法在求解组合优化问题上具有明显的优势，本文将量子算法与蚁群算法结合并，用改进的量子蚁群算法(QACO)来求解随机需求的DVRP.

2.1 状态转移规则

(7)

其中,l表示所有可能的取值;τij为边弧(i,j)的轨迹强度;α(α>0)为信息启发式因子，表示轨迹的相对重要性 ,其值越大,蚂蚁越倾向于选择有较多蚂蚁经过的路径;ηij为边弧(i,j)的能见度，其表达式为：

(8)

其中,dij为相邻两个客户间的距离;β(β>0)为期望的启发式因子, 表示能见度的相对重要性, 其值越大蚂蚁越倾向于选择路径较短的路径;μj为客户节点j的量子信息强度, 其表达式为：

(9)

2.2 信息素的更新

蚂蚁在进行路径搜索的过程中，之前路径上的信息素会不断的挥发，而蚂蚁在走过的路径上会释放新的信息素，信息素的更新方程为：

τij=(1-ρ)τij+Δτij

(10)

(11)

(12)

Q为信息素量，是一个常值，Lk为第k只蚂蚁已经构建路径的长度，本文把量子概率幅引入，在进行信息素更新时，蚂蚁经过的路径上量子信息素会越来越多，而蚂蚁未经过的路径随着量子信息素的挥发，该路径上所剩的量子信息素会越来越少，这将导致不同的边量子信息素相差越来越大，容易陷入局部最优.本文设计的量子信息素更新策略会随着蚂蚁构建的路径的增加，量子信息素所增加的量将逐渐减少，从而避免某条边上信息素积累过多导致陷入局部最优的问题.

2.3 算法步骤

(1)初始调度阶段：

步骤3：如果蚂蚁k=(k=1,2,…,n)走完全部客户点即所有客户点都在当前解集中，记下蚂蚁个数Nk；

步骤4：计算各目标函数Wk(k=1,2,…,m)，得到当前最优解；

步骤5：对各边信息素进行更新，用量子Hε门对量子蚁群进行更新；

步骤6：判断当前迭代次数是否达到最大迭代次数，否则转步骤2；

步骤7：输出当前得到的最优解.

(2)动态优化阶段：

步骤1：执行初始调度阶段的配送方案并更新客户信息；

步骤2：若有新的客户请求出现，判断新增客户点数量是否达到上限，若达到上限，转到步骤3，否则判断是否到达下一重调度时间点，若到达下一重调度时间点，执行步骤3，否则转到步骤1；

步骤3：根据模糊需求概率公式判断是否将该客户点插入到当前配送路径中，如果S大于下一客户点需求量的临界值，则将该点插入到当前路径中，用量子蚁群算法生成新路径，否则转到步骤4；

步骤4：新增车辆来完成新增客户点的配送任务.

3 仿真实验

仿真实验借助Matlab7.0软件来验证改进的量子蚁群算法的可行性和有效性，本文以一个配送中心坐标为(300，270)、14个静态客户点、4个动态客户点为例，配送区域为450 km×450 km的正方形区域，重调度周期为1 h，对随机需求的动态车辆路径问题进行仿真实验，不同客户的位置如表1和表2所示.

表1 14个静态客户的地理坐标

表2 4个动态客户的地理坐标

图1静态阶段配送路线图2动态阶段配送路线

(2)在某时间片内增加了a、b、c、d四个动态客户点，根据动态阶段重调度策略，将新增客户点插入到当前配送路径中，可得更新后的配送路径如图2所示.

(3)根据图2的路线图生成的动态阶段重调度表如表3所示.

表3 动态重调度表

4 结论

本文提出将量子计算与蚁群算法相结合并加以改进，求解随机需求的DVRP问题.对各路径上的信息素进行量子比特编码，采用Hε门对量子蚁群更新；为了避免搜索陷入局部最优，改进了信息素更新方程.采用重调度判断公式来处理新增客户点问题，最后进行Matlab仿真实验，验证了本算法在求解随机需求的动态车辆路径问题上的有效性.