基于改进蚁群算法的多时间窗车辆路径问题
发布时间：2021-11-02 09:55
物流运输成本在物流总成本中占有很大比重,合理安排车辆路线,满足用户需求对企业有重要意义。车辆路径问题是运筹优化领域的热点研究问题,多时间窗车辆路径问题是对车辆路径问题的扩展。文中以总成本最小为目标,建立了多时间窗车辆路径问题的一般数学模型,针对蚁群算法在求解时容易陷入局部最优解和收敛速度慢的问题,改进转移概率公式,采用邻域搜索策略提高解的质量,借鉴模拟退火算法的思想对信息素进行更新,提高算法的寻优能力,加快收敛速度。实验结果表明,改进后的蚁群算法可以有效求得最优解,降低物流运输成本。相比其他算法,改进后的蚁群算法求解精确度高,收敛速度快,在求解多时间窗车辆路径问题上有着较好的性能。
【文章来源】：计算机技术与发展. 2019,29(01)
【文章页数】：4 页
【部分图文】：
路线图1
均已访问完毕，则k=k+1，转至步骤2;如果所有蚂蚁遍历完毕，找出当前最优解，按照邻域搜索策略进行可行解的优化，然后根据更新公式更新信息素;n=n+1，如果n＜N，转至步骤2;(6)输出结果，退出程序。3仿真实验多时间窗车辆路径问题尚无标准的测试数据，该算例数据取自文献［11］，不在此一一列举。改进蚁群算法的参数设置为:种群规模100，迭代次数200，初始信息素为1，α=1，β=2，ε=1，ρ=0．1，T=1000，r=0.9。改进蚁群算法求得的最优解为2156．8，共需要4辆车完成配送任务，路线如图1、2和表1所示。图1路线图1图2路线图2表1车辆路线表车辆路线装载率/%10→1→4→3→6→2→5→06020→7→9→10→8→11→072．53a0→20→19→15→18→0953b0→18→15→19→20→09540→17→16→13→14→12→095·401·计算机技术与发展第29卷
821616．69标准蚁群算法2168．9220624．58模拟退火算法2168．92470．1128．56禁忌搜索算法2168．92323．3146．86从表2中可以看出，在20次实验中，改进蚁群算法求得的最优解为2156．8，平均每次求得的最优解为2161，标准差为6．69，三项指标均优于其他三种算法。标准蚁群算、模拟退火算法和禁忌搜索算法均停留在某个局部最优解上，说明改进蚁群算法在跳出局部最优解方面具有良好的性能，而且算法求解的标准差较小，结果相对稳定，而未改进的标准蚁群算法、模拟退火算法和禁忌搜索算法在求解过程中的稳定性较差。从图3可以看出，模拟退火算法和禁忌搜索算法在迭代过程中变化幅度大，稳定性差，而且求解质量不高，而改进蚁群算法在求解问题时速度较快，稳定性好，求解质量高于其他三种算法。图3算法迭代对比图4结束语车辆路径问题属于NP难题，构造高质量的启发式算法是很多学者的研究方向。针对多时间窗车辆路径问题建立了一般数学模型，改进蚁群算法进行求解，和其他算法求得的结果进行比对分析。改进后的蚁群算法在求解多时间窗车辆路径问题上有着较好的性能，是求解多时间窗车辆路径问题的较好途径。参考文献:［1］DANTZIGG，ＲAMSEＲJ．Thetruckdispatchingproblem［J］．ManagementScience，1959，6(1):80－91．［2］杨宇栋，朗茂祥，胡思继．有时间窗车辆路径问题的模型及其改进模拟退火算法研究［J］．管理工程学报，2006，20(3):104－107．［3］刘志硕，柴跃廷，申金升．蚁群算法及其在有硬时间窗的车辆路径问题中的应用［J］．计算机集成制造系统，2006，12(4):596－602．［4］何小锋，马良．带时间窗车辆路径问题的量子蚁群算法［J］．系统工程理论与实践，2013，33(5):1255－1261．［5］BELHAIZAS，HANSENP，
【参考文献】：
期刊论文
[1]多模糊时间窗车辆路径问题的建模及求解[J]. 闫芳,王媛媛. 交通运输系统工程与信息. 2016(06)
[2]多时间窗车辆路径问题的智能水滴算法[J]. 李珍萍,赵菲,刘洪伟. 运筹与管理. 2015(06)
[3]基于蚁群模拟退火算法的云环境任务调度[J]. 张浩荣,陈平华,熊建斌. 广东工业大学学报. 2014(03)
[4]带时间窗车辆路径问题的量子蚁群算法[J]. 何小锋,马良. 系统工程理论与实践. 2013(05)
[5]基于协同自适应禁忌的多时窗VRP算法实现[J]. 朱玲玲,杨爱琴,吴宽仁. 计算机应用研究. 2012(12)
[6]允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解[J]. 马华伟,叶浩然,夏维. 中国管理科学. 2012(S1)
[7]多时间窗车辆路径问题的数学模型及算法[J]. 黄秋爱,李珍萍. 物流技术. 2012(13)
[8]求解有时间窗的车辆路径问题的混合蚁群算法[J]. 丁秋雷,胡祥培,李永先. 系统工程理论与实践. 2007(10)
[9]有时间窗车辆路径问题的模型及其改进模拟退火算法研究[J]. 杨宇栋,朗茂祥,胡思继. 管理工程学报. 2006(03)
[10]蚁群算法及其在有硬时间窗的车辆路径问题中的应用[J]. 刘志硕,柴跃廷,申金升. 计算机集成制造系统. 2006(04)
本文编号：3471825
【文章来源】：计算机技术与发展. 2019,29(01)
【文章页数】：4 页
【部分图文】：
路线图1
均已访问完毕，则k=k+1，转至步骤2;如果所有蚂蚁遍历完毕，找出当前最优解，按照邻域搜索策略进行可行解的优化，然后根据更新公式更新信息素;n=n+1，如果n＜N，转至步骤2;(6)输出结果，退出程序。3仿真实验多时间窗车辆路径问题尚无标准的测试数据，该算例数据取自文献［11］，不在此一一列举。改进蚁群算法的参数设置为:种群规模100，迭代次数200，初始信息素为1，α=1，β=2，ε=1，ρ=0．1，T=1000，r=0.9。改进蚁群算法求得的最优解为2156．8，共需要4辆车完成配送任务，路线如图1、2和表1所示。图1路线图1图2路线图2表1车辆路线表车辆路线装载率/%10→1→4→3→6→2→5→06020→7→9→10→8→11→072．53a0→20→19→15→18→0953b0→18→15→19→20→09540→17→16→13→14→12→095·401·计算机技术与发展第29卷
821616．69标准蚁群算法2168．9220624．58模拟退火算法2168．92470．1128．56禁忌搜索算法2168．92323．3146．86从表2中可以看出，在20次实验中，改进蚁群算法求得的最优解为2156．8，平均每次求得的最优解为2161，标准差为6．69，三项指标均优于其他三种算法。标准蚁群算、模拟退火算法和禁忌搜索算法均停留在某个局部最优解上，说明改进蚁群算法在跳出局部最优解方面具有良好的性能，而且算法求解的标准差较小，结果相对稳定，而未改进的标准蚁群算法、模拟退火算法和禁忌搜索算法在求解过程中的稳定性较差。从图3可以看出，模拟退火算法和禁忌搜索算法在迭代过程中变化幅度大，稳定性差，而且求解质量不高，而改进蚁群算法在求解问题时速度较快，稳定性好，求解质量高于其他三种算法。图3算法迭代对比图4结束语车辆路径问题属于NP难题，构造高质量的启发式算法是很多学者的研究方向。针对多时间窗车辆路径问题建立了一般数学模型，改进蚁群算法进行求解，和其他算法求得的结果进行比对分析。改进后的蚁群算法在求解多时间窗车辆路径问题上有着较好的性能，是求解多时间窗车辆路径问题的较好途径。参考文献:［1］DANTZIGG，ＲAMSEＲJ．Thetruckdispatchingproblem［J］．ManagementScience，1959，6(1):80－91．［2］杨宇栋，朗茂祥，胡思继．有时间窗车辆路径问题的模型及其改进模拟退火算法研究［J］．管理工程学报，2006，20(3):104－107．［3］刘志硕，柴跃廷，申金升．蚁群算法及其在有硬时间窗的车辆路径问题中的应用［J］．计算机集成制造系统，2006，12(4):596－602．［4］何小锋，马良．带时间窗车辆路径问题的量子蚁群算法［J］．系统工程理论与实践，2013，33(5):1255－1261．［5］BELHAIZAS，HANSENP，
【参考文献】：
期刊论文
[1]多模糊时间窗车辆路径问题的建模及求解[J]. 闫芳,王媛媛. 交通运输系统工程与信息. 2016(06)
[2]多时间窗车辆路径问题的智能水滴算法[J]. 李珍萍,赵菲,刘洪伟. 运筹与管理. 2015(06)
[3]基于蚁群模拟退火算法的云环境任务调度[J]. 张浩荣,陈平华,熊建斌. 广东工业大学学报. 2014(03)
[4]带时间窗车辆路径问题的量子蚁群算法[J]. 何小锋,马良. 系统工程理论与实践. 2013(05)
[5]基于协同自适应禁忌的多时窗VRP算法实现[J]. 朱玲玲,杨爱琴,吴宽仁. 计算机应用研究. 2012(12)
[6]允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解[J]. 马华伟,叶浩然,夏维. 中国管理科学. 2012(S1)
[7]多时间窗车辆路径问题的数学模型及算法[J]. 黄秋爱,李珍萍. 物流技术. 2012(13)
[8]求解有时间窗的车辆路径问题的混合蚁群算法[J]. 丁秋雷,胡祥培,李永先. 系统工程理论与实践. 2007(10)
[9]有时间窗车辆路径问题的模型及其改进模拟退火算法研究[J]. 杨宇栋,朗茂祥,胡思继. 管理工程学报. 2006(03)
[10]蚁群算法及其在有硬时间窗的车辆路径问题中的应用[J]. 刘志硕,柴跃廷,申金升. 计算机集成制造系统. 2006(04)
本文编号：3471825
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3471825.html
