速度波动影响下对带软时间窗快递配送车辆路径问题研究
发布时间：2021-11-20 19:14
对于车辆路径问题的研究,往往考虑速度恒定或者时变的情况,最终得到的都是一个确定的行驶时间。但根据以往经验,车辆行驶在某个路段的平均速度不会是恒定的,也无法提前准确掌握,一般会在某个范围内波动。车辆的行驶时间主要和速度相关,所以速度的波动又会影响旅行时间,造成车辆在节点间的旅行时间的不确定。为了研究车辆速度波动对车辆配送成本和路径的影响,本文引入了车辆平均行驶速度分布函数,通过计算得出车辆到达客户点的时间并与客户所期望的时间窗相比较,分析可能出现的情形并得到相应的时间成本表达式,最终构建了基于配送成本最低的目标函数,包括车辆固定成本、车辆行驶成本和时间成本。并考虑模型特点,设计改进遗传算法进行求解。本文基于实际配送情景,研究了城市快递配送车辆行驶速度波动的VRPSTW问题,研究方法及内容如下:（1）首先,针对配送车辆行驶过程中速度波动的问题,引入了车辆平均行驶速度分布函数,由此得到车辆到达客户点的时间段,建立了基于车辆固定成本、运输成本及时间成本总和最低的带软时间窗的车辆路径问题数学模型,并设计改进遗传算法求解。（2）通过算例分析,得到速度波动下配送车辆的行驶路径。然后,将运算结果与研究...
【文章来源】：大连海事大学辽宁省 211工程院校
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
图１．１?２０１５－２０２０城市配送市场规模及预测??Ｆｉｇ．?１．１?２０１５－２０２０?ｕｒｂａｎ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｍａｒｋｅｔ?ｓｃａｌｅ?ａｎｄ?ｆｏｒｅｃａｓｔ??
?大连海事大学专业学位硕士学位论文???２车辆路径问题的相关概念及理论基础??２．１车辆路径问题概述??车辆路径问题作为运筹学的一个经典模型，自１９５９年提出以来，就受到各个领域??的专家和学者的极大重视，并对此问题进行了更加深入的研究。该问题定义［３５］—般可描??述为对于一系列需要提供配送服务的客户点（装货点或卸货点），在满足一定约束条件??下，例如车辆的载货量包括载重和容量、客户的时间窗等，组织一定数量的车辆以及合??适的行车路线，从配送中心出发，使车辆按照预先设定好的路线依次服务路线上的每个??客户并最终回到终点，且达到一定的目标，主要包括配送成本最低、完成配送时间最短、??客户满意度最高等。车辆路径问题可由图２．１所示：??／?＇?Ｂ送中心＜一＾－一＾??图２．１车辆路径问题示意图??Ｆｉｇ．?２．１?Ｓｃｈｅｍａｔｉｃ?ｄｉａｇｒａｍ?ｏｆ?Ｖｅｈｉｃｌｅ?Ｒｏｕｔｉｎｇ?Ｐｒｏｂｌｅｍ??２．２?ＶＲＰ问题的构成要素??作为运筹学中的经典模型之一完整的ＶＲＰ系统主要由以下几类要素构成；??（１）配送中心??配送中心是配送业务的“中央处理器”，是处理物流和信息流集中的地方。对到达??配送中心的货物进行倒装、分拣，在根据客户的要求例如时间窗或其他方面，设计合理??运输路线，安排车辆为客户提供配送服务。属性有车辆的数量和类型、初始配送时间和??１３??
?大连海事大学专业学位硕士学位论文???１７％?１６％??２４％?Ｂ??图４．３轮盘赌选择法??Ｆｉｇ?４．２?Ｒｏｕｌｅｔｔｅ?ｓｅｌｅｃｔｉｏｎ?ｍｅｔｈｏｄ??轮盘赌选择法虽然可以保证种群多样性但同时随机性也较大，难以保证算法收敛。??本文结合模型分析，在轮盘赌算子的基础上引入最休保存策略，防止适应度高的个体因??为随机的原因不被选中，避免适应度高的个体被后续的遗传操作改变，使群体向最优化??方向进化，提高收敛能力。具体选择操作为：??（１）计算个体的适应度ｆｉ，将每一代具有最大适应度的个体直接进行复制；??（２）计算每个个体被遗传到下一代中的概率；??Ｐ丨＝各．?（４２）??Ｉ／；??１？１?，??（３）计算个体的累计概率；??？，■?＝?Ｙ，Ｐｊ?（４－３）??（４）在［０，１］之间随机产生一个数ｔ，若ｔ＜ａｉ，则选择个体１进入子代种群，若ａｋ－ｉ＜ｔ＜ａｋ，??选择个体ｋ进入子代总群。??（５）重复步骤（４），直到子代种群选择完毕生成新一代种群，并将适应度最低的个体??用父代适应度最高的染色体进行替换。??４．３．２交叉算子??交叉操作是指两个父代染色体上基因位进行交换生成新个体的操作。交叉操作改变??了父代个体中的基因，是产生新个体的主要来源。本文交叉算子采用适合自然数编码的??部分映射交叉法（Ｐａｒｔｉａｌ－Ｍａｐｐｅｄ?Ｃｒｏｓｓｏｖｅｒ，ＰＭＸ）［６２］，具体步骤为：??（１）随机选择一对染色体（父代）中几个基因的起止位置（两染色体被选位置相??３３??
【参考文献】：
期刊论文
[1]混合蚁群算法求解带软时间窗的车辆路径问题[J]. 李卓,李文霞,巨玉祥,陈晓明,何晓平. 武汉理工大学学报(交通科学与工程版). 2019(04)
[2]车辆路径优化问题及求解方法研究综述[J]. 庞燕,罗华丽,邢立宁,任腾. 控制理论与应用. 2019(10)
[3]带软时间窗的电动车辆路径优化问题[J]. 葛显龙,竹自强. 工业工程与管理. 2019(04)
[4]旅行时间不确定下的车辆路径问题研究[J]. 武小平,寇艺槟,樊相宇. 制造业自动化. 2019(04)
[5]实数编码遗传算法的改进及并行化实现[J]. 刘振鹏,王雪峰,薛雷,张彬,张寿华. 河北大学学报(自然科学版). 2019(01)
[6]带软时间窗的连锁超市配送车辆路径问题[J]. 夏扬坤,符卓. 信息与控制. 2018(05)
[7]行驶时间随机的分批配送车辆路径问题模型与算法[J]. 石建力,张锦. 计算机应用. 2018(02)
[8]求解软时间窗装卸一体车辆路径问题的布谷鸟算法[J]. 戚艳君,陈超,高杨军,刘正元. 空军工程大学学报(自然科学版). 2017(06)
[9]随机旅行时间的外卖O2O配送车辆路径问题[J]. 王帅,赵来军,胡青蜜. 物流科技. 2017(01)
[10]基于两阶段算法的需求可拆分多车型车辆路径问题[J]. 潘雯雯,郭海湘,周光勇,杜天松. 中国管理科学. 2016(S1)
博士论文
[1]不确定因素下路径规划问题研究[D]. 张梦颖.中国科学技术大学 2016
硕士论文
[1]城市快递配送车辆路径规划研究[D]. 宋汶轩.北京邮电大学 2019
[2]任务均衡下的快递末端配送区域划分及路径优化研究[D]. 张慧敏.北京交通大学 2019
[3]带模糊需求与时间窗的车辆路径优化研究[D]. 耿静.大连海事大学 2019
[4]基于遗传算法的实验室设备综合规划的研究与应用[D]. 陈锡生.上海交通大学 2017
[5]物流配送中车辆路径问题研究[D]. 闫凯.解放军信息工程大学 2017
[6]带货物权重的软时间窗开放式车辆路径问题研究[D]. 张琳琳.长安大学 2016
[7]乘用车公路运输路径优化问题研究[D]. 王维天.大连海事大学 2014
[8]基于近似动态规划的随机车辆路径问题研究[D]. 张晨.清华大学 2012
[9]基于鲁棒优化的应急管理下的车辆路线问题的研究[D]. 孙华.河南大学 2007
本文编号：3507951
【文章来源】：大连海事大学辽宁省 211工程院校
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
图１．１?２０１５－２０２０城市配送市场规模及预测??Ｆｉｇ．?１．１?２０１５－２０２０?ｕｒｂａｎ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｍａｒｋｅｔ?ｓｃａｌｅ?ａｎｄ?ｆｏｒｅｃａｓｔ??
?大连海事大学专业学位硕士学位论文???２车辆路径问题的相关概念及理论基础??２．１车辆路径问题概述??车辆路径问题作为运筹学的一个经典模型，自１９５９年提出以来，就受到各个领域??的专家和学者的极大重视，并对此问题进行了更加深入的研究。该问题定义［３５］—般可描??述为对于一系列需要提供配送服务的客户点（装货点或卸货点），在满足一定约束条件??下，例如车辆的载货量包括载重和容量、客户的时间窗等，组织一定数量的车辆以及合??适的行车路线，从配送中心出发，使车辆按照预先设定好的路线依次服务路线上的每个??客户并最终回到终点，且达到一定的目标，主要包括配送成本最低、完成配送时间最短、??客户满意度最高等。车辆路径问题可由图２．１所示：??／?＇?Ｂ送中心＜一＾－一＾??图２．１车辆路径问题示意图??Ｆｉｇ．?２．１?Ｓｃｈｅｍａｔｉｃ?ｄｉａｇｒａｍ?ｏｆ?Ｖｅｈｉｃｌｅ?Ｒｏｕｔｉｎｇ?Ｐｒｏｂｌｅｍ??２．２?ＶＲＰ问题的构成要素??作为运筹学中的经典模型之一完整的ＶＲＰ系统主要由以下几类要素构成；??（１）配送中心??配送中心是配送业务的“中央处理器”，是处理物流和信息流集中的地方。对到达??配送中心的货物进行倒装、分拣，在根据客户的要求例如时间窗或其他方面，设计合理??运输路线，安排车辆为客户提供配送服务。属性有车辆的数量和类型、初始配送时间和??１３??
?大连海事大学专业学位硕士学位论文???１７％?１６％??２４％?Ｂ??图４．３轮盘赌选择法??Ｆｉｇ?４．２?Ｒｏｕｌｅｔｔｅ?ｓｅｌｅｃｔｉｏｎ?ｍｅｔｈｏｄ??轮盘赌选择法虽然可以保证种群多样性但同时随机性也较大，难以保证算法收敛。??本文结合模型分析，在轮盘赌算子的基础上引入最休保存策略，防止适应度高的个体因??为随机的原因不被选中，避免适应度高的个体被后续的遗传操作改变，使群体向最优化??方向进化，提高收敛能力。具体选择操作为：??（１）计算个体的适应度ｆｉ，将每一代具有最大适应度的个体直接进行复制；??（２）计算每个个体被遗传到下一代中的概率；??Ｐ丨＝各．?（４２）??Ｉ／；??１？１?，??（３）计算个体的累计概率；??？，■?＝?Ｙ，Ｐｊ?（４－３）??（４）在［０，１］之间随机产生一个数ｔ，若ｔ＜ａｉ，则选择个体１进入子代种群，若ａｋ－ｉ＜ｔ＜ａｋ，??选择个体ｋ进入子代总群。??（５）重复步骤（４），直到子代种群选择完毕生成新一代种群，并将适应度最低的个体??用父代适应度最高的染色体进行替换。??４．３．２交叉算子??交叉操作是指两个父代染色体上基因位进行交换生成新个体的操作。交叉操作改变??了父代个体中的基因，是产生新个体的主要来源。本文交叉算子采用适合自然数编码的??部分映射交叉法（Ｐａｒｔｉａｌ－Ｍａｐｐｅｄ?Ｃｒｏｓｓｏｖｅｒ，ＰＭＸ）［６２］，具体步骤为：??（１）随机选择一对染色体（父代）中几个基因的起止位置（两染色体被选位置相??３３??
【参考文献】：
期刊论文
[1]混合蚁群算法求解带软时间窗的车辆路径问题[J]. 李卓,李文霞,巨玉祥,陈晓明,何晓平. 武汉理工大学学报(交通科学与工程版). 2019(04)
[2]车辆路径优化问题及求解方法研究综述[J]. 庞燕,罗华丽,邢立宁,任腾. 控制理论与应用. 2019(10)
[3]带软时间窗的电动车辆路径优化问题[J]. 葛显龙,竹自强. 工业工程与管理. 2019(04)
[4]旅行时间不确定下的车辆路径问题研究[J]. 武小平,寇艺槟,樊相宇. 制造业自动化. 2019(04)
[5]实数编码遗传算法的改进及并行化实现[J]. 刘振鹏,王雪峰,薛雷,张彬,张寿华. 河北大学学报(自然科学版). 2019(01)
[6]带软时间窗的连锁超市配送车辆路径问题[J]. 夏扬坤,符卓. 信息与控制. 2018(05)
[7]行驶时间随机的分批配送车辆路径问题模型与算法[J]. 石建力,张锦. 计算机应用. 2018(02)
[8]求解软时间窗装卸一体车辆路径问题的布谷鸟算法[J]. 戚艳君,陈超,高杨军,刘正元. 空军工程大学学报(自然科学版). 2017(06)
[9]随机旅行时间的外卖O2O配送车辆路径问题[J]. 王帅,赵来军,胡青蜜. 物流科技. 2017(01)
[10]基于两阶段算法的需求可拆分多车型车辆路径问题[J]. 潘雯雯,郭海湘,周光勇,杜天松. 中国管理科学. 2016(S1)
博士论文
[1]不确定因素下路径规划问题研究[D]. 张梦颖.中国科学技术大学 2016
硕士论文
[1]城市快递配送车辆路径规划研究[D]. 宋汶轩.北京邮电大学 2019
[2]任务均衡下的快递末端配送区域划分及路径优化研究[D]. 张慧敏.北京交通大学 2019
[3]带模糊需求与时间窗的车辆路径优化研究[D]. 耿静.大连海事大学 2019
[4]基于遗传算法的实验室设备综合规划的研究与应用[D]. 陈锡生.上海交通大学 2017
[5]物流配送中车辆路径问题研究[D]. 闫凯.解放军信息工程大学 2017
[6]带货物权重的软时间窗开放式车辆路径问题研究[D]. 张琳琳.长安大学 2016
[7]乘用车公路运输路径优化问题研究[D]. 王维天.大连海事大学 2014
[8]基于近似动态规划的随机车辆路径问题研究[D]. 张晨.清华大学 2012
[9]基于鲁棒优化的应急管理下的车辆路线问题的研究[D]. 孙华.河南大学 2007
本文编号：3507951
本文链接：https://www.wllwen.com/kejilunwen/daoluqiaoliang/3507951.html
