基于蚁群算法的需求可拆分车辆路径问题研究
发布时间：2020-12-19 03:49
当今世界经济的迅猛发展大大促进了物流运输的发展,物流产业作为各国经济的重要组成部分,已经广泛的引起了人们的重视。目前物流的发展程度决定了一个国家的发展水平,它可以提高一个国家的国民生产总值,引导国家经济的发展方向。减少运输成本可以有效提高物流行业的效益,最常用的方法就是使运输路径最短。传统的车辆路径问题（Vehicle Routing Problem,VRP）就是研究运输路径最小化的问题。因为它要求每个顾客的需求必须由一辆运输车进行配送,所以当一些顾客的需求量大于车辆容量时,就会出现无法满足所有顾客需求的情况。为了解决这个问题,相关学者开始考虑对顾客的需求进行拆分,并提出了需求可拆分车辆路径问题（Split Delivery Vehicle Routing Problem,SDVRP）。本文在研究SDVRP问题的过程中发现它没有考虑到在运输途中消耗物资的情况,因此本文将路径消耗加入到SDVRP问题的约束条件中,提出了运输途中货物消耗的需求可拆分车辆路径问题（Split Delivery Vehicle Routing Problem with Goods Consumed during...
【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校
【文章页数】：61 页
【学位级别】：硕士
【部分图文】：
SDVRP和SDVRP-GCT示例图
第4章三种扩展蚁群算法的实现19第4章三种扩展蚁群算法的实现4.1蚁群算法概述蚁群算法是MarcoDorigo受到蚁群觅食行为的启发后，于1992年在博士论文中提出的一种智能仿生算法，它能在合理计算时间内得到组合优化问题的近似最优解。在大量的研究中人们发现蚁群之所以能很快的聚集在一条寻找食物的最短路径上，是因为蚁群中的蚂蚁在寻找路径时通过释放一种微量的化学物质-信息素进行交流。每只蚂蚁都会在途经过的路上释放信息素，其他蚂蚁在寻找食物的时候可以根据路径上信息素的残留程度选择出信息素浓度高的路径，这样一来该路径被选择的次数越多，信息素的浓度就越高，蚂蚁越有可能选择这条路径，因此在一段时间后所有的蚂蚁都会聚集在寻找食物的最短或者近似最短路径上。如果在最短路径上突然放置一个障碍物，蚁群也能很快的适应新的环境，迅速改变路径，找到食物的最优路径。下图4.1[39]展示了蚁群的搜索机制。图4.1蚁群觅食行为示意图[39]4.2求解SDVRP-GCT问题的蚁群算法提出背景起初相关学者们提出蚁群算法是为了解决旅行商（TSP）问题，后来大量研究都证明了蚁群算法在离散优化问题，组合优化问题上都有非常好的性能。由于SDVRP-GCT是一个首次被提出的问题，没有现成的算法可以直接使用，蚁群算
第5章实验设计与分析32图5.1三种扩展算法在不同h时的最短路径长度比较正如预期的那样，随着h的逐渐增加，车辆在运输的过程中消耗的货物量逐渐增加，此时用于装载顾客需求的容量逐渐减小，所以总的路径长度在增加。为了进一步评估三个扩展算法在新的SDVRP-GCT问题上的性能，本文以h=0.1为例进行实验然后详细的分析所得到的实验结果，并将结果展示在下表5.5中，最后从实验得到的最短路径长度，所需车辆数目，以及算法运行时间几个方面分别进行分析。表5.5三种扩展算法在14个转化后的SDVRP-GCT上的结果比较NameASGCTACGCTMMGCTMinAvg(std)MinAvg(std)MinAvg(std)S51D1490.21499.16(5.20)481.85487.98(4.61)473.34483.90(6.46)S51D2824.08847.30(8.39)806.78816.91(6.33)789.19811.26(12.52)S51D31065.511082.15(6.98)1036.601056.46(17.97)1043.191064.91(11.17)S51D41815.091830.01(8.92)1801.441819.24(7.67)1773.701805.31(15.31)S51D51502.251532.60(10.21)1479.221506.42(11.26)1485.071515.06(13.23)S51D62443.972479.82(14.47)2434.712450.68(7.92)2428.952474.72(13.99)S76D1705.44716.60(5.77)665.23681.37(8.79)655.56680.21(16.07)S76D21263.201278.18(7.89)1221.401260.07(13.66)1216.701243.99(17.10)S76D31661.411685.88(12.53)1643.981668.23(11.63)1620.521662.03(17.92)S76D42396.632421.87(12.43)2321.082361.50(16.82)2344.622377.14(18.50)S101D1813.45837.38(8.66)803.16820.23(9.38)793.60813.49(12.41)S101D21596.011629.53(11.26)1593.211613.29(11.81)1565.731598.78(21.42)S101D32109.012134.06(11.93)2086.622108.90(9.85)2088.622111.64(17.35)S101D53142.763204.34(30.51)3098.823121.55(11.31)3057.73
本文编号：2925200
【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校
【文章页数】：61 页
【学位级别】：硕士
【部分图文】：
SDVRP和SDVRP-GCT示例图
第4章三种扩展蚁群算法的实现19第4章三种扩展蚁群算法的实现4.1蚁群算法概述蚁群算法是MarcoDorigo受到蚁群觅食行为的启发后，于1992年在博士论文中提出的一种智能仿生算法，它能在合理计算时间内得到组合优化问题的近似最优解。在大量的研究中人们发现蚁群之所以能很快的聚集在一条寻找食物的最短路径上，是因为蚁群中的蚂蚁在寻找路径时通过释放一种微量的化学物质-信息素进行交流。每只蚂蚁都会在途经过的路上释放信息素，其他蚂蚁在寻找食物的时候可以根据路径上信息素的残留程度选择出信息素浓度高的路径，这样一来该路径被选择的次数越多，信息素的浓度就越高，蚂蚁越有可能选择这条路径，因此在一段时间后所有的蚂蚁都会聚集在寻找食物的最短或者近似最短路径上。如果在最短路径上突然放置一个障碍物，蚁群也能很快的适应新的环境，迅速改变路径，找到食物的最优路径。下图4.1[39]展示了蚁群的搜索机制。图4.1蚁群觅食行为示意图[39]4.2求解SDVRP-GCT问题的蚁群算法提出背景起初相关学者们提出蚁群算法是为了解决旅行商（TSP）问题，后来大量研究都证明了蚁群算法在离散优化问题，组合优化问题上都有非常好的性能。由于SDVRP-GCT是一个首次被提出的问题，没有现成的算法可以直接使用，蚁群算
第5章实验设计与分析32图5.1三种扩展算法在不同h时的最短路径长度比较正如预期的那样，随着h的逐渐增加，车辆在运输的过程中消耗的货物量逐渐增加，此时用于装载顾客需求的容量逐渐减小，所以总的路径长度在增加。为了进一步评估三个扩展算法在新的SDVRP-GCT问题上的性能，本文以h=0.1为例进行实验然后详细的分析所得到的实验结果，并将结果展示在下表5.5中，最后从实验得到的最短路径长度，所需车辆数目，以及算法运行时间几个方面分别进行分析。表5.5三种扩展算法在14个转化后的SDVRP-GCT上的结果比较NameASGCTACGCTMMGCTMinAvg(std)MinAvg(std)MinAvg(std)S51D1490.21499.16(5.20)481.85487.98(4.61)473.34483.90(6.46)S51D2824.08847.30(8.39)806.78816.91(6.33)789.19811.26(12.52)S51D31065.511082.15(6.98)1036.601056.46(17.97)1043.191064.91(11.17)S51D41815.091830.01(8.92)1801.441819.24(7.67)1773.701805.31(15.31)S51D51502.251532.60(10.21)1479.221506.42(11.26)1485.071515.06(13.23)S51D62443.972479.82(14.47)2434.712450.68(7.92)2428.952474.72(13.99)S76D1705.44716.60(5.77)665.23681.37(8.79)655.56680.21(16.07)S76D21263.201278.18(7.89)1221.401260.07(13.66)1216.701243.99(17.10)S76D31661.411685.88(12.53)1643.981668.23(11.63)1620.521662.03(17.92)S76D42396.632421.87(12.43)2321.082361.50(16.82)2344.622377.14(18.50)S101D1813.45837.38(8.66)803.16820.23(9.38)793.60813.49(12.41)S101D21596.011629.53(11.26)1593.211613.29(11.81)1565.731598.78(21.42)S101D32109.012134.06(11.93)2086.622108.90(9.85)2088.622111.64(17.35)S101D53142.763204.34(30.51)3098.823121.55(11.31)3057.73
本文编号：2925200
本文链接：https://www.wllwen.com/kejilunwen/daoluqiaoliang/2925200.html
