需求不确定的车辆路径鲁棒优化模型与算法研究

发布时间：2021-08-13 11:04

　　物流配送是一个耗费大量人力物力的领域,有较大的优化空间。本文研究的是最后一公里配送中的不确定性车辆路径问题。实际情况中企业的配送需求是随机的,其随机因素包括订单位置、服务时间等。另一方面,配送员对配送路径的熟悉程度会直接影响其配送效率,配送员在配送区域的服务时间会影响客户的体验。因此,企业需要规划出多天随机需求下的鲁棒车辆路径。本文则提供了一个描述多场景下车辆路径鲁棒性问题的通用框架。首先,本文在考虑随机因素下车辆路径的鲁棒性时,引入各场景计划一致性的概念,提出了带主计划一致性的车辆路径模型。模型旨在给出一个主计划和每一天的日常计划。模型的目标函数是最小化所有计划的加权总成本。除了确定性模型会包含的许多约束外,本文提出的模型还包括主计划一致性约束以确保每天的日常计划与主计划中同一车辆时空路径的偏离程度较小。本文将区域质心作为需求点的单位。区域质心汇总了此区域内的需求。模型的随机因素是区域在不同场景下的随机总需服务时间、时间窗和总重量。其次,车辆路径问题本身就是一个NP难题,引入不确定性因素后问题变得更为复杂。不确定性问题的约束既包含确定性问题中的整数约束及大量边际约束,也包含主计划与子... 

【文章来源】：北京交通大学北京市 211工程院校 教育部直属院校

【文章页数】：97 页

【学位级别】：硕士

【部分图文】：

图１车辆路径问题的车辆路径方案示例??Ｆｉｇ．?１?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ａ?ｓｏｌｕｔｉｏｎ?ｔｏ?ｔｈｅ?ｖｅｈｉｃｌｅ?ｒｏｕｔｉｎｇ?ｐｒｏｂｌｅｍ??

态网将车辆路径问题的大量边际约束（包括车辆能力约束、服务时间约束、时间??窗约束等）内嵌。最后，本文采用前向动态规划法求解分解后的单车车辆路径子??问题。详细的问题分解过程见图２。??多场景的带主计划一致性约束??的鲁棒车辆路径问题??原问题??、．．?＿???＿一／??子计划对比主计划的?＼??一致性约束?＼??拉格朗日松弛法?＼??各场景?边际约束??主计划?子计划?（车辆能力约束、??——ｊ?１?：?ｙ?ｉ?时间窗约束等）??区域访问约束?区域访问约束?＼??★?觯???１??顯Ｍ?……［２１?１??Ｉ?问题分解?＼??多个?多个?＼??单车车辆路径子问题单车车辆路径子问题?１??（．圭蝴—?｜?（各场录子计划〉??＊???－?时空状态网??前向动态规划法求解??图２问题分解过程示意图??Ｆｉｇ．?２?Ｓｋｅｔｃｈ?ｍａｐ?ｏｆ?ｐｒｏｂｌｅｍ?ｄｅｃｏｍｐｏｓｉｔｉｏｎ?ｐｒｏｃｅｄｕｒｅ??本研宄所采用的技术路线借鉴了大量相关研宄，有着扎实的研宄基础。下文??对比说明了其他相关研宂所采用的研究方法，验证了本文研究方法的适宜性。??首先，文章通过主计划和子计划之间的一致性约束描述车辆路径的鲁棒性。??此建模方法借鉴了跨领域的研宄方法。在铁路时刻表领域中，学者们通过引入主??计划，并将其用做每一个日常计划的参考，确保主计划和日常计划的一致性。Ｌｕ??等人在２０１７年求解铁路时刻表问题时应用了主计划和子计划的概念。他通过制定??一个主计划并根据每天的实际情况调整当天的子计划使得变化幅度较小

此实例主要是用来描述不同程度的一致性约束是如何影响车辆路径方案的。??３．２多场景车辆路径鲁棒性问题描述??本文模型所用的网络如图３所示。图３左半部分表示一个带２个区域的物理??网络，节点〇和ｓ分别代表车辆的起终点。图３的右半部分将左半部分的区域节点??拆分成区域的服务开始节点和区域的服务结束节点。现考虑两个场景，每个区域??有两种不同的总需服务时间。因此，每个区域有一个区域服务开始节点和两个不??同的区域服务结束节点。如区域１拆分为１Ａ、１丨和Ｉ，２。其中６是ｂｅｇｉｎ的缩写，表??示车辆到达区域并开始服务，／是ｌｅａｖｉｎｇ的缩写表示即车辆服务结束并离开此区??域，右上角的数字１和２是一个区域不同服务结束节点的编号。连接区域服务开??始节点和区域服务结束节点的虚线是服务路段。虚线上的数字表示车辆经过此路??段时在区域的实际服务时长，单位是分钟。实线表示的是物理路段。实线上数字??表示车辆在此路段的旅行时间

【参考文献】：
期刊论文
[1]行驶时间和服务时间随机的集配货一体的分批配送车辆路径优化[J]. 石建力,张锦.  控制与决策. 2018(04)
[2]随机旅行时间的外卖O2O配送车辆路径问题[J]. 王帅,赵来军,胡青蜜.  物流科技. 2017(01)
[3]考虑交通拥堵及工作量平衡性的一致性车辆路径问题[J]. 刘恒宇,汝宜红.  西南交通大学学报. 2016(05)
[4]基于模糊时间窗的多中心开放式车辆路径问题[J]. 杨翔,范厚明,张晓楠,李阳.  计算机集成制造系统. 2016(07)
[5]求解多维背包问题的蚁群-拉格朗日松弛混合优化算法[J]. 任志刚,赵松云,黄姗姗,梁永胜.  控制与决策. 2016(07)
[6]需求不确定的车辆路径鲁棒优化模型[J]. 管峰,钟铭,韦达.  上海海事大学学报. 2015(04)
[7]求解随机旅行时间的C-VRP问题的混合遗传算法[J]. 李锋,魏莹.  系统管理学报. 2014(06)
[8]一种新的求解多目标随机需求车辆路径问题的算法[J]. 赵燕伟,李川,张景玲,陆游,王万良.  计算机集成制造系统. 2012(03)
[9]基于模糊聚类与车辆协作策略的随机车辆路径问题[J]. 刘长石,赖明勇.  管理工程学报. 2010(02)
[10]带时间窗和随机时间车辆路径问题:模型和算法[J]. 李相勇,田澎.  系统工程理论与实践. 2009(08)

博士论文
[1]随机车辆路径问题研究[D]. 谢秉磊.西南交通大学 2003

硕士论文
[1]基于蚁群算法的一致性车辆路径问题的研究[D]. 卞晨.安徽理工大学 2017
[2]随机行驶时间车辆调度问题研究[D]. 周柏松.大连海事大学 2005



本文编号：3340311