不确定环境下多品类共同配送路径优化
发布时间：2021-06-09 03:18
针对动态事件对配送过程的干扰问题,提出多品类共同配送车辆路径优化问题。基于对不确定环境下动态客户时空特性的分析,提出利用时空泊松分布生成动态客户的方法;并从整体运营成本及车辆固定成本入手,建立不确定环境下多品类共同配送模型;鉴于考虑模型的特殊性,设计遗传-禁忌搜索组合优化算法,结合具体算例对模型和算法性能进行验证。结果表明,提出的多品类共同配送方法优于单品类配送方法,且改进后的遗传-禁忌搜索算法具有更强的寻优能力。
【文章来源】：计算机工程与应用. 2019,55(09)北大核心CSCD
【文章页数】：7 页
【部分图文】：
服务区域及静态客户略图
PS和PT同时取1时，表示动态客户发生率同时在时间和空间两个维度进行变化；PS和PT同时取0时，表示配送场景动态度仅维持在ε水平，特别地；当ε=0时，算例GEN-D等价于传统静态车辆配送路径问题。PS和PT一个取0另一个取1时表示动态客户发生率仅在空间或时间维度变动。5.2优化结果及算法性能评估采用设计的遗传-禁忌搜索算法，以表2中规定的参数配置方式，在各前摄性调度单元中生成相应数目的动态客户，得到4个配送实例。依据表3配置遗传-禁忌搜索算法参数，对4个算例进行路径优化，结果见图3。由图3可知，不同的动态度场景下，生成的动态客户数目存在明显差异；特别地，对于GEN-DE，由于规定的基础动态度较小，整个服务区域无动态客户产生，等同于静态配送路径问题，配送成本为273.83。作为参照，GEN-AE增加了27个动态客户，配送成本增加了134；GEN-BE增加了6个动态客户，配送成本增加了11.9；GEN-CE增加了12个动态客户，配送成本增加了66.13。基于上述算例，将本文设计遗传-禁忌搜索算法与配送中心图2服务区域及静态客户略图算例GEN-AEGEN-BEGEN-CEGEN-DEPS1.01.00.00.0PT1.00.01.00.0down0.1up0.3ε0.05M2S16τ4表1仿真算例集合及其参数说明算例GEN-AE：(PS=1,PT=1)GEN-BE：(PS=1,PT=0)GEN-CE：(PS=0,PT=1)GEN-DE：(PS=0,PT=0)12341234123412341100100000110000020111000000000000300010010010100004010010000000000050112000000
2019，55（9）遗传算法的运行20次，对算法改进效果进行验证，结果见表4。由表4可知，改进后的遗传禁忌搜索算法，较原始遗传算法寻优能力更强，测试算例的平均改善率均达到5%以上；运行算法时发现禁忌搜索算法对初始解的依赖性较强，优良的初始解是禁忌搜索获得高质量调度方案的前提；经过多次运行遗传-禁忌搜索算法，总是优于遗传算法的解，证明使用禁忌搜索算法来改进遗传算法的局部搜索能力是非常有效的。同时，使用蚁群算法对本文设计算例进行路径优化，优化结果如图4所示。对上述4个算例，蚁群算法最优解为439.47、315.09、349.75和290.16，与遗传算法性能大致相当。由此可知，本文设计遗传禁忌搜索算法求解能力优于蚁群算法和遗传算法。5.3数学模型性能评估为验证多品类共同配送模型的有效性，将其与单品类配送方案的配送成本进行对比分析，结果见表5。单品类分别配送方案是指每个车辆负责一种货物的配送，如果某一客户同时需要两个货物品类，则调度两辆不同车辆配送相应的货物。由表5可知，使用多品类共同配送方案可以显著降低配送成本，且使用车辆更少。单品类分别配送方案需要调度更多的配送车辆，一定程度上增加了配送中心车辆调度工作量。此外，考虑到多品类共同配送可能对车辆有特殊要求，假定单品类配送车辆固定成本为5，单位距离运营成本为1；并以此为基准，规定多品类共同配送车辆的运营成本和固定成本均为单品类配送车辆的1.2倍，此时两方案成本对比见表6。表6可以看出，即使多品类共同配送使用了成本更高的配送车辆，其配送成本仍低于单品类分别配送。6结论针对不确定环境下多品类共同配送问题，提出多品类共同配送的数学模型，并设计遗传-禁忌搜索算法进行车辆路径优化。得到以下结论：（1）改进后?
【参考文献】：
期刊论文
[1]成品油配送多车舱车辆指派及路径优化问题研究[J]. 张源凯,孙丽君,胡祥培. 运筹与管理. 2017(07)
本文编号：3219807
【文章来源】：计算机工程与应用. 2019,55(09)北大核心CSCD
【文章页数】：7 页
【部分图文】：
服务区域及静态客户略图
PS和PT同时取1时，表示动态客户发生率同时在时间和空间两个维度进行变化；PS和PT同时取0时，表示配送场景动态度仅维持在ε水平，特别地；当ε=0时，算例GEN-D等价于传统静态车辆配送路径问题。PS和PT一个取0另一个取1时表示动态客户发生率仅在空间或时间维度变动。5.2优化结果及算法性能评估采用设计的遗传-禁忌搜索算法，以表2中规定的参数配置方式，在各前摄性调度单元中生成相应数目的动态客户，得到4个配送实例。依据表3配置遗传-禁忌搜索算法参数，对4个算例进行路径优化，结果见图3。由图3可知，不同的动态度场景下，生成的动态客户数目存在明显差异；特别地，对于GEN-DE，由于规定的基础动态度较小，整个服务区域无动态客户产生，等同于静态配送路径问题，配送成本为273.83。作为参照，GEN-AE增加了27个动态客户，配送成本增加了134；GEN-BE增加了6个动态客户，配送成本增加了11.9；GEN-CE增加了12个动态客户，配送成本增加了66.13。基于上述算例，将本文设计遗传-禁忌搜索算法与配送中心图2服务区域及静态客户略图算例GEN-AEGEN-BEGEN-CEGEN-DEPS1.01.00.00.0PT1.00.01.00.0down0.1up0.3ε0.05M2S16τ4表1仿真算例集合及其参数说明算例GEN-AE：(PS=1,PT=1)GEN-BE：(PS=1,PT=0)GEN-CE：(PS=0,PT=1)GEN-DE：(PS=0,PT=0)12341234123412341100100000110000020111000000000000300010010010100004010010000000000050112000000
2019，55（9）遗传算法的运行20次，对算法改进效果进行验证，结果见表4。由表4可知，改进后的遗传禁忌搜索算法，较原始遗传算法寻优能力更强，测试算例的平均改善率均达到5%以上；运行算法时发现禁忌搜索算法对初始解的依赖性较强，优良的初始解是禁忌搜索获得高质量调度方案的前提；经过多次运行遗传-禁忌搜索算法，总是优于遗传算法的解，证明使用禁忌搜索算法来改进遗传算法的局部搜索能力是非常有效的。同时，使用蚁群算法对本文设计算例进行路径优化，优化结果如图4所示。对上述4个算例，蚁群算法最优解为439.47、315.09、349.75和290.16，与遗传算法性能大致相当。由此可知，本文设计遗传禁忌搜索算法求解能力优于蚁群算法和遗传算法。5.3数学模型性能评估为验证多品类共同配送模型的有效性，将其与单品类配送方案的配送成本进行对比分析，结果见表5。单品类分别配送方案是指每个车辆负责一种货物的配送，如果某一客户同时需要两个货物品类，则调度两辆不同车辆配送相应的货物。由表5可知，使用多品类共同配送方案可以显著降低配送成本，且使用车辆更少。单品类分别配送方案需要调度更多的配送车辆，一定程度上增加了配送中心车辆调度工作量。此外，考虑到多品类共同配送可能对车辆有特殊要求，假定单品类配送车辆固定成本为5，单位距离运营成本为1；并以此为基准，规定多品类共同配送车辆的运营成本和固定成本均为单品类配送车辆的1.2倍，此时两方案成本对比见表6。表6可以看出，即使多品类共同配送使用了成本更高的配送车辆，其配送成本仍低于单品类分别配送。6结论针对不确定环境下多品类共同配送问题，提出多品类共同配送的数学模型，并设计遗传-禁忌搜索算法进行车辆路径优化。得到以下结论：（1）改进后?
【参考文献】：
期刊论文
[1]成品油配送多车舱车辆指派及路径优化问题研究[J]. 张源凯,孙丽君,胡祥培. 运筹与管理. 2017(07)
本文编号：3219807
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3219807.html
