不确定因素下配送路径优化问题研究

发布时间：2020-11-03 04:35

　　 作为现代物流中的重要环节,物流配送路径优化是有效降低配送成本和提高配送效率的重要手段。本文研究配送路径优化中的两点配送路径选择问题和多点配送车辆路径优化问题,在综述了国内外路径优化研究现状的基础上,着重对路径优化的求解方法、考虑顾客需求随机性和负载变化的多点配送绿色车辆路径优化问题、不确定多因素下的两点配送路径选择问题进行了研究,并提出了相关的解决方法。本文研究工作包括以下三个方面:(1)针对带容量约束的多点配送车辆路径优化问题(Capacitated Vehicle Routing Problem,CVRP),提出了一种基于禁忌搜索的混合模拟退火算法(Hybrid Simulated Annealing Algorithm,HSAA)求解。相比于传统的模拟退火算法,本文提出的HSAA算法具有以下改进:不同于传统随机初始化方法,通过引入k-means聚类算法进行簇划分和使用插入法进行簇调整,得到能考虑顾客地理分布特性的初始可行解;借鉴禁忌搜索算法的思想,使用K-近邻算法生成禁忌表,通过4种邻域搜索方法遍历禁忌表的全局逐步寻优搜索方式,在扩展邻域搜索范围的同时,提升邻域搜索过程的有效性。为验证HSAA算法的性能,本文使用20个标准CVRP算例进行测试,并与文献中已有算法进行对比。实验结果表明,本文提出HSAA算法的寻优能力和同等温度衰减次数下的收敛速度均优于已有的具有重启策略的模拟退火算法。(2)针对绿色节能路径优化问题,提出了同时考虑随机需求和负载变化的多点配送车辆路径优化模型,并在本文提出的HSAA算法基础上给出了相应的求解方法。在实际配送场景中,车辆负载与其能耗率具有正比关系。传统的车辆路径优化模型仅考虑配送距离最短,忽略了车辆负载对能耗的影响,其所得最优路径在能耗上并不是最小的。同时,已有研究一般只考虑确定的顾客需求,而忽视了其随机性。本文以最小化配送运输能耗为目标,考虑随机需求对车辆负载的影响,并引入风险概率约束来描述因随机需求而导致车辆出现超载的概率,还提出了风险概率的简化策略,以降低算法求解复杂度。实验结果表明:相比于传统路径优化模型,考虑车辆负载变化和顾客需求随机性的路径优化方法可以有效避免车辆超载并且降低能耗,进而提升优化结果的实用性并降低配送成本。(3)针对不确定多因素下的两点配送路径选择问题,提出了基于证据推理的路径选择方法。目前,已有路径选择研究多集中于静态运输网络,不符合实际场景下运输网络的动态随机特性。另外,实际交通场景中车辆的配送路径选择结果往往受多种因素影响,其结果也往往是不确定的,因此仅考虑运输网络中的某一单个因素是难以得到合理满意的路径选择结果。本文考虑实际动态随机运输网络中的多条候选路径选择问题,提出了基于证据推理的不确定多因素路径选择方法。首先将影响候选路径的因素数据通过隶属度函数构建简单支持证据,再使用Dempster组合规则融合所有因素的证据体获取全局基本信度分配,最终选择具有最大信度的路径作为最优结果。通过北京市实际配送场景验证提出的方法的有效性,并给出了详细的运算结果。结果表明,相比于模糊层次分析法,本文提出的方法所得到的评估结果具有更高的区分度,因此能更有效地消除决策结果的不确定性。
【学位单位】：北京交通大学
【学位级别】：博士
【学位年份】：2019
【中图分类】：F252.1;TP18
【部分图文】：

１．３技术路线和论文结构??１．３．１技术路线??根据本文的研宄内容，本文的技术路线如图１－２所示。??（??１?ｉ?提出?｜??第丨章绪论??研宄背景和研究意义?ｉ问题：??１?Ｊ?Ｉ??ｊ?；阶段；??＼??ｙ?ｌ?；??路径优化问题国内外文献综述ｉ?理论基础?????Ｉ；?ｊ???ｉ！??Ｃ?第２章?Ｈ多点配送车辆路径优化问题１丨聚类算法??文献综述和理论基础?｜！?丨丨模拟退火?｜ｉ?＇：问题：??Ｖ?Ｊ?！??１丨林已油，去?层次分析丨丨：＇????！?两点配送路径选择问题?丨！禁忌搜索?｜｜丨阶段：??１１?！?！?１１??！??Ｉ??ｖ??模型构建?算法设计??Ｉ?Ｉ??广?第５章?｜?｜???１?｜??带容量约束的多点配送车辆ＣＶＲＰ问题模型?一？?ＨＳＡＡ算法??、?路径优化问题?」???ｊ；??Ｉ?Ｉ??Ｉ?Ｉ???ｊｒ??１?ｉ?ｊ?１??第４?章?１??考虑随机需求和负载变化的ＬＶＧＶＲＰＳＤ问题模型?—?ＨＳＡＡ算法?＾?Ｉ问题：??＾多点配送车辆路径优化问题＾）?Ｊ＼＼?ｊ阶段｜??ｌ?ｉ??Ｉ?Ｉ???ｙ?ｒ??ｊ?ｒ?｜?ｊ??Ｌ■占基于证据理论的不确定多?基于证据推理的不确定??卜点配，—－评估模型—．＾—多—径选择方法一；｜

综合上述冷却进度表的参数，ＳＡＡ算法一般的求解步骤如下：??Ｓｔｅｐｌ：初始化。设置初始温度，终止温度７＾及哀减函数７Ｘ／）的哀减因卞以，??Ｍａｒｋｏｖ链的长度；??Ｓｔｅｐ２：从可行解空间随机选取一初始解，作为当前解计算目??标函数八义）；??Ｓｔｅｐ３：从当前解的邻域中随机扰动产生一个新解Ｘ，计算新解的目标函数??／（Ｘ），并计算目标函数增量Ａ／?＝?／（义）－／（々）；??Ｓｔｅｐ４：若Ａ／＜０，则接受新解Ｘ作为当前解，令否则以概率??；？?＝?ｅｘｐ?接受欠作为新的当前解；??Ｖ?Ｔ?）??２３??

ｓ＝ｍ（２－１２）??所定义的函数：２ｅ?－＞［０，１］为框架Ｇ）上的似真度函数（Ｐｌａｕｓｉｂｉｌｉｔｙ?Ｆｕｎｃｔｉｏｎ）。??反映的是对所有不怀疑命题Ｊ的子集所对应的信度之和。??信度函数价／（七和似真度函数之间有如下的关系：??Ｐｌｓ（Ａ）?＝?＼－Ｂｅｌ（Ａ）?（２－１３）??Ｐｌｓ＾Ａ）?＞?Ｂｅｌ＾Ａ）?（２－１４）??其中，２为命题ｄ的补集，从式（２－１４）可知ＰｈＭ）是比价／（ｄ）更宽松的一种??估计。??证据理论就是通过价／（七和他（七这两个函数来描述不确定性，＆／（七和??分别表示假设ｄ所对应的信度的下界和上界，由二者组成的区间??称为命题ｄ的信度区间，表征假设Ｊ的不确定性程度的范围，也称为不确??定区间。而他（七－５？描述了假设Ｊ的无知程度的大小，外（七和价／（」）之??间的差值越大，假设Ｊ所对应的无知度越大，证据的可靠性越低。＆／ｐ）和??对不确定性的描述如图２－３所示：??
【参考文献】

相关期刊论文 前10条

1 李进;傅培华;李修琳;张江华;朱道立;;低碳环境下的车辆路径问题及禁忌搜索算法研究[J];中国管理科学;2015年10期

2 张晓楠;范厚明;;混合分散搜索算法求解带容量约束车辆路径问题[J];控制与决策;2015年11期

3 葛显龙;苗国庆;谭柏川;;开放式污染路径问题优化建模与算法研究[J];工业工程与管理;2015年04期

4 蔡延光;汤雅连;;关联运输调度问题带遗传算子的自适应蚁群算法[J];计算机应用研究;2015年08期

5 刘万峰;李霞;;车辆路径问题的快速多邻域迭代局部搜索算法[J];深圳大学学报(理工版);2015年02期

6 杨浩雄;王丹;张敬蕤;;基于蚁群算法的拥堵交通最短路径研究[J];计算机仿真;2015年03期

7 李进;张江华;;基于碳排放与速度优化的带时间窗车辆路径问题[J];系统工程理论与实践;2014年12期

8 李锋;魏莹;;求解随机旅行时间的C-VRP问题的混合遗传算法[J];系统管理学报;2014年06期

9 潘义勇;孙璐;;交通网络最优路径问题分类研究[J];交通运输工程与信息学报;2014年03期

10 郑建湖;伍雄斌;黄明芳;文子娟;;有偏好的多属性灰色关联路径选择模型[J];交通运输系统工程与信息;2014年04期

本文编号：2868101