秋雷带有时间窗的车辆路径问题的混合蚁群算法研究

《秋雷带有时间窗的车辆路径问题的混合蚁群算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、丁秋雷:带有时间窗的车辆路径问题的混合蚁群算法研究其中:I是从上次更新最优值开始到现在已经完成的搜索次数，c,d为常数，可分别取2和50,B;是从搜索开始到上一次发现最优值所经过的搜索次数，n是指问题的规模。3.2混合蚁群算法的求解步骤根据3.1节的基本原理，对解决VRPTW的混合蚁群算法求解步骤如下:step1:初始化各控制参数，读取客户资料，设找到全局最优解匀、。，迭代计数器nc=0，将。只蚂蚁置于配货中心(为扩大组合范围、增加可行解产生的条件，m可取较大值。若在搜索过程中，现有蚂蚁数量仍不能保证所有客户点都被访问，则增加蚂蚁数量)，分别以刀个客户点

2、为起点，建立候选节点列表(候选节点数凭多次实验而定)。step2:对于每一只蚂蚁j，在候选节点列表中找出所有未走过的节点，并在这些节点中按照公式3.5选择蚂蚁的下一个旅行节点工['lu(t)?[s]B[,U=]'，if、‘p,(3.5)j一{argmaxjfM,ahyAr[zjIy(ft)]0jotabu,，otherwisemax[0,LTL,}T-Am-aExT(EJT,,ET,)]，，:::二6max[O,LTL,T-Am-aExT(EAT,,LT,)]，else(3.6)E兀=ET,+T,十t,其中:tabu,(k=1,2,二、习为禁忌表，记录蚂

3、蚁k当前所走过的所有节点::俐4,分别表示信息素浓度和能见度(两点距离d,;的倒数);8;;)}考虑时间急迫度而引入的时间窗匹配程度因子，由公式3.6决定，其中【鱿，乙剐为客户j的时间窗口，界为车辆在客户j的卸货时间，右伪车辆从沂驶到角时间;N，一do+心-d。为吸收节约法引入的节约值;a、I4,9,Y为各变量的相对重要程度;9是一个随机数，qe[0,1]cpA1J始值取为pal，随进化的过程动态调整。step3:判断已搜索的蚂蚁总数是否等于m,若否，则还有蚂蚁未进行搜索，返回step2，直到所有蚂蚁都进行搜索为止;若是，执行step40大连理工大学硕士

4、研究生学位论文step4:计算每只蚂蚁的搜索路径LkI置本次路径L1_，为本次最优路径，Ll_.,=艺Lk，同时保存最优路径表。k.1step5:对本次最优路径分别实施n次2-opt与or-opt(为满足对解空间完全搜索，n开始较大;进化到一定代数后，n减小)，交换一次后若该路线满足装载量与时m]窗约束，则记录本次路径长度L},，与对应的路径表，若Lno,

5、满足时间窗约束条件，则保存灾变，更新乙、。，与最优路径表;否则取消该灾变。step7:对所有路径上的信息素按式(3.7)进行动态更新:叮‘=PT尸十AT;,(3.7)IQ，l)属于本次最优路径Orf=}L,lt0其中:Q为常数，即蚂蚁释放的总信息素;1-P为信息素挥发程度，P的初始值为11随进化的过程动态调整。信息素更新后，吸收最值蚂蚁算法与信息素平滑的思想，即当T,>:。时，用:~替换:、，当:;,<:。时，用(T.,ntr-)/2替换:。，便于蚂蚁产生新的搜索路线。step8:将本次最优路径L,x,.，与全局最优解LYI}，作比较，如果Llcrnl<

6、Lg1oy=1，则Lgloaa}Ll},nn1，同时更新全局最优路径表。step9:当进化到一定代数进化方向已经基本确定后，为更好的对解空Ol进行搜索，动态地调整确定性选择的概率Pt与信息素保留程度P.对于几，其调整规则如下:0.95p,-,护0.95p1-,>_pmin(3.8)Pminotherwise其中:P:。为进化过程中确定性选择概率P‘的最小值，用以确保当P，过小仍然保持一定的确定性选择机会。丁秋雷:带有时间窗的车辆路径问题的混合蚁群算法研究对于P，其调整规则如下:95P=_一if0.95P_,>_P.j}(3.9)P.,.，otherwis

7、e其中:P。为进化过程中P的最小值，用以防止P过小而降低算法的收敛速度。step10:判断nc是否等于最大迭代次数，若是，则流程结束:若否，则清空禁忌表，跳回step2，重复进行上述步骤。算法流程见图3.3.3.3算法的设计与实现3.3.1系统需求对于用于解决VRPTW的HACS算法演示程序，是要提供一个功能相对完整、用户界面友好的演示软件。另外要求该演示软件具有容易修改、扩充为真正实用的软件工具的能力。演示软件将首先提供初始参数输入界面，用于各车辆的行驶速度、各客户点的服务时间等初始参数及蚂蚁数量、信息素保留程度等控制参数的输入。对初始参数设置完毕后将

8、进入软件主页面，该页面提供给用户一个矩形区域，用户可以首先选择要解决的问题题号，