卫田[1]2007年在《物流配送中车辆路径问题的多目标优化算法研究》文中研究指明物流配送车辆路径优化问题(Vehicle Routing Problem, VRP)已经被证明属于NP-Hard问题。传统的研究在模型建立上比较单一,没有对求解模型的算法进行深入探索并且在算法选择方面也没有进行细致的比较研究。因此,本文针对这叁个方面对VRP数学建模,算法研究以及算法性能比较进行探讨,取得了以下研究成果:1.针对目前没有公认的多目标优化算法比较标准以及算法选择流程,本文提出了精度、时间、解决问题个数相结合的叁维算法比较方法。首次,将精度作为算法比较的一个重要方面,得到了算法比较叁维模型,同时,给出了可行的算法选择流程,并开发了算法选择软件。2.建立了静态多目标VRP模型,利用算法选择软件选出了合适的算法—NSGAⅡ。收集整理了美国密西根州的配送中心的数据,用NSGAⅡ求解已建立的静态多目标VRP模型,从收敛速率、Pareto面和Pareto投影叁个方面分析了算法的有效性和可行性。3.为了克服NSGAⅡ算法早熟收敛和对初始群体依赖性的缺点,按照算法融合的思想,将经典算法与现代NSGAⅡ算法进行融合,提出了贪心NSGAⅡ、分支定界NSGAⅡ和Or-opt NSGAⅡ叁种改进算法,以美国密西根州配送中心为实例,验证了叁种算法的有效性和可行性。4.以经典遗传算法为参照,以美国密西根州配送中心的大规模(498个配送点)和小规模(30个配送点)VRP为实例,从收敛速率、收敛时间、最优值和非支配个体百分比四个方面对NSGAⅡ及其叁种改进算法的性能进行了比较研究,得到了静态多目标VRP模型算法分析简表。5.利用仿真方法研究了交通拥挤对配送网络的影响,得到路口拥挤与准时到达折线图并基于此折线图提出了多目标VRP两阶段模型。同样,在动态多目标VRP模型上对NSGAⅡ及其叁种算法的性能进行了研究探讨,得到了动态多目标VRP模型算法分析简表,与静态多目标VRP模型算法分析简表一起,成为多目标VRP两阶段模型的算法分析简表。
刘昌生[2]2014年在《随机配送时间车辆路径优化模型及算法研究》文中认为物流配送中的车辆路径优化问题(Vehicle Routing Problem,VRP)是当今物流配送优化的关键环节，一直是现代物流领域研究的热点问题。有效地安排车辆行驶路径，不仅可以加快对客户需求的响应速度，提高服务质量，还可以降低物流服务商运作成本。目前对于VRP的研究多把VRP的约束条件如行驶时间、服务时间等都看成是固定不变的静态VRP，且对模型的目标函数的设定多从配送企业出发，设定为车辆行驶距离最短、配送成本最低等单目标函数，对于综合考虑客户满意度、配送成本多目标的VRP优化研究还不多见。事实上，实际的物流配送系统中由于交通、车辆和自然条件等因素的影响，使得物流配送系统具有一定的随机性和复杂性，因此对带有随机性VRP的研究更能贴近实际的配送情况。本论文研究的重点是围绕随机配送时间车辆路径问题进行的。通过分析了国内外VRP研究现状，指出了国内在VRP模型上研究还不够深入的问题，确定了本文所要解决的问题。设计了新的适合实际情况的物流配送路径优化模型，并进行了实例验证。首先，在分析了目前VRP模型的基础上，本文在综合考虑了企业运输成本的最小化以及顾客满意度约束等多方面因素，通过对物流配送时间的随机性和顾客的满意度进行相关的研究；采用随机机会约束规划理论构建了VRP的随机机会约束规划模型，并将顾客满意度函数作为首要的约束条件体现在模型当中，在模型寻优的过程中直接起作用，从而将配送中心以往不能量化的信誉损失间接的予以量化，这在很大程度上强化了配送中心的长远利益，也提高了顾客服务水平，即准时化、高效率化等。其次，在对模型的求解过程中采用了遗传算法，由于标准遗传算法在求解车辆路径问题时易早熟收敛。本文根据求解VRP模型的特点，对标准的遗传算法的遗传操作进行了改进，设计了新的自适应遗传算法，算法的运行参数交叉率和变异率不是固定的数值，而是能够根据适应度值在进化的不同阶段进行自适应调节。最后，通过算例验证了模型和算法的可行性及有效性，对选用的算例建立了随机VRP模型，采用改进的遗传算法对建立的模型进行了求解，讨论了不同的置信度和满意度取值对于模型解的影响。研究的结果不仅对于车辆路径问题的实际应用具有指导意义，而且还能为物流配送调度系统提供决策支持。
李阳[3]2018年在《需求不确定的车辆路径问题模型与算法研究》文中进行了进一步梳理交通与物流是支撑社会经济发展的重要行业,车辆路径问题(Vehicle Routing Problem,VRP)作为组合优化和运筹学领域研究的经典和热点问题,主要研究在满足一定约束条件下合理安排车辆的路径方案和调度计划,使得总体的配送服务成本达到优化,其在物资调运、电子商务以及铁路民航、公交线路等交通和物流领域具有极为广阔的应用背景,而在现实生活中,经常出现某些信息无法提前获知的情况,属于不确定问题,因此对贴近实际生产作业环节中的不确定型车辆路径问题进行研究和优化具有较强的理论和现实意义。本文以模糊需求车辆路径问题(Capacitated Vehicle Routing Problem with Fuzzy Demand,CVRPFD)、随机需求车辆路径问题(Capacitated Vehicle Routing Problem with Stochastic Demand,CVRPSD)、动态需求车辆路径问题(Capacitated Vehicle Routing Problem with Dynamic Requests,CVRPDR)为例,对需求不确定型车辆路径问题展开研究。在对不确定规划理论、VRP研究进展以及启发式算法进行综述的基础上,首先分析了经典的CVRP,设计结合变邻域搜索和生物共栖搜索的混合启发式算法求解,算法采取有序编码方式,通过文献算例对比验证和分析表明了混合算法以及模型的有效性。针对CVRPFD,基于先预优化后重调度的两阶段求解思路,本文首先分析和处理了 CVRPFD的客户点模糊需求变量,通过引入模糊可信性理论,结合预设的决策者风险偏好水平,该模糊变量可以通过模糊机会约束参与后续优化环节。依据所构建的CVRPFD模糊机会规划模型,本文设计了两阶段求解混合变邻域禁忌搜索算法,提出了新客户点重调度策略,该策略能解决以往失败点返回先天不足以及适当返回点选取困难的问题,在出现路径失败时依据重调度策略对全部未完全服务子路径展开整体优化,降低额外配送成本,保证所有客户点能接受服务。针对CVRPSD,本文首先对客户点处随机需求变量进行了分析和处理,构建随机机会约束使其可以参与模型优化,随后依据中心极限定理对该约束进行了确定型等价处理,使后续失败路径的调整得以进行。由于随机需求变量的影响,CVRPSD在求解时也有两阶段优化的特点,预优化阶段首先借助随机机会约束规划模型求得路径方案,在出现路径失败时依据所提出的失败点重调度策略重新调整方案,减少额外配送成本。文章设计了结合变邻域搜索和分散搜索的混合算法对CVRPSD展开两阶段优化求解,通过时间复杂性分析和相应确定型CVRP算例、CVRPSD随机问题算例和文献对比分析表明了所构建随机机会约束规划模型以及混合算法的有效性,算例结果表明新的失败点重调度策略能有效减少整体的配送成本。在对模糊和随机因素影响下UVRP进行研究基础上,本文对CVRPDR展开了相关研究,不同于前两个问题两阶段优化的特征,客户点动态需求的特点使得CVRPDR必须通过周期性的多阶段优化来实现求解,其优化策略对最终方案总成本影响较大。文章首先对其动态性进行了分析,随后提出了基于时间片划分的周期性实时重置策略来解决客户点连续出现的问题,其延迟服务机制能均衡新老客户点的服务需求,合理利用时间因素优化客户点服务顺序,减少车辆配送成本。依据上述策略,文章还设计了子路径动态转变的混合变邻域人工蜂群算法来求解CVRPDR,该算法中车辆子路径可在时间片间动态转变,客户点能实现与虚拟中心的转变,契合动态问题的求解特征。
娄山佐[4]2006年在《车辆路径问题的建模及优化算法研究》文中指出智能交通系统作为基于现代科学技术建立起来的，一种在大范围内全方位发挥作用的，准时、准确、高效的交通运输管理体系，受到各国的普遍重视。全球经济的一体化，也正推动着被称为是企业“第叁利润源”——现代物流业的快速发展。车辆路径问题作为智能交通系统中的重要内容，在现代物流中占据着很重要位置。虽然经过几十年研究，取得了不少的成果，但由于该问题的复杂性，目前还存在许多需要进一步加强研究的问题。随着计算技术和优化方法以及信息和通信技术的发展，过去解决不够完善的或没能解决的问题，可以借助现代科技的力量，将其进一步完善或解决。本文针对目前车辆路径问题的现状，利用系统工程理论和最新的优化方法，对存在的问题进行建模和优化算法研究，具有重要的理论意义和实用价值。论文主要做了以下几方面工作：1、针对带时间窗有限车辆路径问题，设计了一种混合遗传禁忌算法。在描述问题和建立模型的基础上，首先，因染色体中仅有部分基因起作用，为充分利用染色体包含的信息，提出采用Bellman-Ford最短路算法，找到它最佳的分割方法。其次，利用禁忌搜索法改善因遗传算法变异概率小，带来局部搜索能力低的问题。另外，对禁忌搜索法又进行设计，通过在目标函数中添加惩罚项，使搜索在可行和不可行交界区域间动态调整，既使搜索不偏离最优解太远，又丰富了搜索区域，提高获得更优解的概率。最后，将解与已知的最优解进行对比，并分析参数对解的影响。2、针对大规模单车型带软时间窗车辆路径问题，设计了一种基于大系统分解协调技术新的解决方法。在对问题进行了描述并给出它的模型后，首先，运用动态聚类法，基于每辆车的位置坐标对车辆聚类，得到分类车辆的中心坐标；再根据每个任务到分类车辆中心的距离，对任务进行分类。其次，针对采用传统分解协调法解决该问题，收敛性能比较差的问题，设计了有效的协调参数，并在主／子系统中，分别设计了不同的自适应遗传算法。通过仿真试验，证实了该算法的有效性。针对大规模多车型带软时间窗车辆路径问题，设计了一个有效的禁忌搜索算法。在给出了问题描述并建立了它的模型后，首先，提出采用候选表策略，通过它舍弃大部分没有希望的移动，且随着搜索过程的进展，动态地调整与搜索邻域有关候选表的大小，提供了一个简单的实施集中性搜索和分散性搜索的方法。其次，采用动态摆动策略，控制它集中在可行和不可行空间交界区域搜索。仿真试验结果证实了所设计禁忌搜索算法的有效性。3、对多库房带时间窗车辆路径问题，在分析几个经典的多库房位置模型后，对该问题进行了描述并构建了它的模型。针对目前解决多库房车辆路径问题，效率低且易陷于局部最优解的问题，提出一种采用分解协调技术解决该问题的新方法。首先，根据启发式方法，将用户分解为耦合和非耦合用户。其次，利用遗传算法设计了协调参数，并设计了禁忌搜索算法，有效地解决各库房的车辆路径问题。最后，通过仿真试验，对它的有效性进行了验证。对多库房随机需求车辆路径问题，在描述该问题以及分析了有关模型的基础上，建立了它的数学模型。基于分解协调技术，在协调层，利用自适应遗传算法确定耦合用户的最佳分解方式；在执行层，对解决子系统的随机需求车辆路径问题，基于预防性补救措施，设计了自适应交叉熵法。最后，通过对不同算法仿真结果比较，验证了所设计方法的有效性。4、在分析了几种解决随机需求车辆路径问题典型方法后，提出了一种基于交叉熵，结合重要抽样、Monte-Carlo及Markov状态转移技术，解决更复杂的随机用户和需求车辆路径问题新方法。在对该问题进行了描述，并建立模型后，首先，针对路径期望费用函数的复杂性，设计了基于Monte-Carlo抽样求解的有效方法。其次，为提高标准交叉熵法性能，根据迭代过程中分位值改变大小，对用于更新转移矩阵关键的路径，设计了自适应调整方法。最后，利用仿真试验，验证了所设计交叉熵法的鲁棒性和有效性。5、在分析了随机最短路问题的基础上，对动态随机需求车辆路径问题进行了描述，并建立它的最优策略模型。针对状态空间“维数灾”问题，基于增强学习函数近似原理，利用径向基函数网络逼近最优cost-to-go函数。首先，对径向基函数进行分析和设计，其次，在一给定的控制策略下，将最小平方瞬时差分法确定近似函数权系数与交叉熵法确定隐层节点基函数参数相结合，通过在线调整，使Bellman残差平方和性能指标达到最小，以实现对最优cost-to-go函数的逼近。通过仿真试验，证实了此算法的有效性。
杨雪敏[5]2016年在《随机时间车辆路径问题研究》文中认为在经济全球化以及互联网+时代环境下,企业之间的竞争愈演愈烈,资源消耗、人力成本上升等,企业可压缩的成本空间逐渐缩小,使得第叁利润源——物流越来越受到关注,它在社会经济中的地位也越来越重要。配送是物流过程的一个重要环节,而且配送成本占物流总成本比例也相对较高。合理安排配送活动、选择高效配送路线,可以降低企业物流成本、提高服务质量,进一步增加企业竞争力。物流配送的核心问题是配送路线优化问题即车辆路径问题。本文以Z电子商务企业南京物流中心配送活动为研究对象,依据公司实际情况,在传统车辆路径问题基础上加入车辆每次最长行驶时间与时间窗约束,在送货途中还要同时考虑取货(退货)问题,并且在实际生活中,车辆行驶时间受天气、事故等不可控因素影响呈现随机状态,所以本文研究带时间窗的同时送取货随机时间车辆路径问题,建立相应求解模型。为了更符合公司实际情况,对最长行驶时间与时间窗考虑满足一个概率约束,并利用统计学知识将这两个随机约束转化为确定性约束进行求解。针对所建模型,综合考虑各求解算法优缺点,选用遗传算法进行问题求解。以Matlab为运行环境,对优化结果进行比较分析。结果表明,不同概率水平下优化结果存在差异,且概率水平高(时间要求严格)的配送成本高于概率水平低的配送成本;与企业实际配送情况相比,优化后的配送路线明显降低配送成本、提高车辆利用率以及配送效率,使得企业利润空间增大、竞争优势增强。
滕耘[6]2008年在《逆向物流回收的车辆配置及路径优化研究》文中研究表明近年来,随着社会对资源、环境问题的日益重视,逆向物流因其强调废旧物品的循环利用和对环境污染的有效控制而成为学术界和企业界关注的焦点。运输是逆向物流活动的重要组成部分,而如何进行有效地配置回收物品的车辆和选择合理的路径,则是降低逆向物流运输成本的关键。由于逆向物流需求的分散性及其发生的时间、地点、体积、重量的不确定性等特点,使得逆向物流的车辆配置和路径优化与正向物流配送相比具有特殊性和更加复杂性,因此需要结合逆向物流自身的特点来探讨逆向物流车辆配置和路径优化的理论、模型和方法问题。论文在国内外相关研究基础上,分别探讨了需求确定和不确定情况下,逆向物流回收的车辆配置和路径优化研究问题。论文共分六章。第一章介绍了论文的选题背景、意义及国内外研究现状,并对论文的总体构思、结构框架和创新点进行了阐述;第二章介绍了逆向物流的概念及其分类,对逆向物流的需求特点及其网络结构类型进行了分析和描述。第叁章则主要对选题涉及到的相关的路径优化和车辆装载问题进行了概念性的介绍。第四章构建了需求确定情况下,以车辆使用、运行成本最小为目标,以车辆的允许载重范围、允许容量范围、最大行驶距离等为约束条件的车辆配置和路径优化模型,并采用遗传算法对模型进行了求解设计,最后通过算例的实现验证了算法的有效性。第五章则考虑到现实生产生活中需求往往不确定的情况,把客户点回流品的体积和重量作为随机变量,建立了逆向物流回收的车辆配置和路径优化的不确定型机会约束模型,并采用最大-最小蚁群算法对该模型进行了算法设计和算例的实现。第六章则对论文研究的成果进行了归纳总结,并对论文今后需要进一步研究的问题和发展方向进行的分析和展望。
蒋勇[7]2007年在《蚁群算法在车辆路径问题中的应用研究》文中研究表明配送是物流系统中很重要的环节。在物流的各项成本中,配送成本占了相当高的比例。车辆路径问题是配送系统的核心问题,也是研究热点之一。对车辆路径进行优化,可以提高物流经济效益,实现物流科学化。因此,研究物流配送车辆路径优化问题,不仅具有较大的理论意义,而且还有相当大的实用价值。本论文在综述国内外有关车辆路径问题研究现状的基础上,通过对几类车辆路径问题模型的分析,对解决此类问题的蚁群算法进行了研究。1.带时间窗的车辆路径问题是车辆路径问题的一个基本类型,也是目前研究最多的一类车辆路径问题。本文采用基本蚁群系统求解,并对蚁群系统的相关参数以及蚂蚁行为对算法性能的影响通过实验仿真进行了详细的研究。2.带时间窗的装卸货问题其模型相对带时间窗的车辆路径问题更具一般性。针对装卸货问题的约束条件,采用了一种解构造方式基于插入算法的蚁群算法予以求解。算法设计了两类信息素,分别引导解构造过程的两个关键步骤。仿真表明,该算法能获得满意的结果。3.研究了蚁群算法求解带软时间窗的随机需求车辆路径问题。分析了随机需求车辆路径问题的研究现状,给出了带软时间窗的随机需求车辆路径问题的数学模型。基于预优化策略,通过在蚁群算法目标函数中引入对违背时间窗路径的惩罚因子,将多目标问题转化为单目标问题。设计了带软时间窗的随机需求车辆路径问题的测试实例,并对各不同规模的实例进行了仿真。4.研究了基于可信性测度的带模糊旅行时间的车辆路径问题。在介绍基本模糊理论的基础上,给出了基于可信性测度的带模糊旅行时间的车辆路径问题的数学模型,然后采用双蚁群系统分别优化问题的两个目标。设计了测试实例并进行了仿真。5.最后,对全文进行总结,并对进一步的研究提出一些展望。
李相勇, 田澎[8]2009年在《带时间窗和随机时间车辆路径问题:模型和算法》文中认为研究带随机车辆旅行时间、服务时间以及时间窗的车辆路径问题.根据不同的优化目标,首先给出了问题的两种数学模型描述:机会约束规划和带修正的随机规划模型.为了有效地求解该问题,提出了基于禁忌搜索的启发式算法,该算法考虑了问题的随机特性.在实验部分,首先给出了产生测试问题的方法,然后基于产生的测试问题给出了算法的计算结果.
韩娟娟[9]2016年在《随机需求车辆路径问题的混合遗传算法研究》文中研究指明随机需求车辆路径问题(Vehicle Routing Problems with Stochastic Demands,VRPSD)是车辆路径问题(Vehicle Routing Problem,VRP)的一个重要分支,由于其具有很强的现实意义,所以成为物流管理领域研究的热点。如何在顾客需求随机的情况下,合理安排车辆行驶路径,以实现运输时间最短、成本最低等目标,这是多年来随机需求车辆路径问题研究的难点。本文通过引入决策者风险偏好改进了VRPSD模型并设计了混合遗传算法求解VRPSD,最后通过随机需求车辆路径问题算例进行了验证和对比,证明了本文算法的有效性并确定了使随机需求车辆路径问题目标值最优的决策者风险偏好值。本文的具体研究工作如下:(1)随机需求车辆路径问题的构建。在分析了目前VRPSD模型的基础上,本文在客户需求随机的情况下考虑了决策者风险偏好对VRPSD目标值的影响。本文采用机会约束策略建立了VRPSD模型,将决策者风险偏好引入到模型中,决策者风险偏好在模型寻优的过程中起到重要作用。(2基于混合遗传算法求解随机需求车辆路径问题研究。设计了混合遗传算法求解VRPSD,先用“最近邻域和插入混合”算法结合随机生成方法产生随机需求车辆路径问题的初始种群,提高了初始种群的质量,再利用遗传算法进行全局搜索,求得随机需求车辆路径问题的解。(3)混合遗传算法求解随机需求车辆路径问题的算例验证。通过C语言对本文提出的混合遗传算法算法编程,利用本文提出混合遗传算法求解随机需求车辆路径问题算例,确定了决策者的最佳风险偏好值,并通过对比实验证明了本文混合遗传算法求解VRPSD的有效性。本文研究了决策者风险偏好对随VRPSD求解的影响并确定了使优化目标最小的决策者风险偏好值,设计了高效的混合遗传算法对VRPSD进行求解,为求解VRPSD和发展遗传混合算法提供了有用的价值。其研究成果不仅对于车辆路径问题的实际应用具有指导意义,而且决策者风险偏好值的研究还能为物流配送调度系统提供决策支持。
李相勇[10]2007年在《车辆路径问题模型及算法研究》文中认为车辆路径问题(Vehicle Routing Problem,VRP)是组合优化和运筹学领域研究的热点问题之一,其主要研究满足约束条件的最优车辆使用方案以及最优的车辆路径方案。基于基本车辆路径问题的框架,研究满足生产经营和运作需要的各种车辆路径问题,并构建具有高质量和高鲁棒性(roubustness)的问题求解算法对于提高生产经营管理水平和降低运作成本具有重要的理论意义和现实价值。本文以车辆路径问题为研究对象,综合运用组合优化和现代启发式算法等工具,对几类重要的车辆路径问题模型及其优化算法进行了系统的研究,主要研究工作及成果总结如下:1.综述了车辆路径问题在定义车辆路径问题分类和扩展标准的基础上,给出了车辆路径问题的研究综述。基于不同的分类标准,首先讨论了主要的标准车辆路径问题扩展问题。在此基础上详细地综述了求解标准车辆路径问题的现代启发式算法,系统地描述了各种算法的实现机理以及各种算法的性能比较结果。2.综述了求解组合优化问题的现代启发式算法在给出组合优化问题和计算复杂性定义的基础上,综述了求解复杂组合优化问题的各种现代启发式算法。3.研究了开放式车辆路径问题通过松弛标准车辆路径问题中车辆路线为哈密尔顿巡回(Hamiltonian tour)的假设,研究了车辆路线为哈密尔顿路径(Hamiltonian path)的开放式车辆路径问题。该问题中车辆在服务完最后一个顾客点后不需要回到车场,若要求回到车场,则必须沿原路返回。在首先给出问题数学模型的基础上,提出了求解开放式车辆路径问题的蚁群优化算法。该算法主体是一个在超立方框架下执行的MAX-MIN蚂蚁系统,算法混合了禁忌搜索算法作为局部优化算法,同时集成了一个后优化过程来进一步优化最优解。基于基准测试问题,系统地研究了算法性能。同其它算法的性能比较结果表明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法。4.研究了带时间窗和带时间期限开放式车辆路径问题通过引入时间约束,研究了两类新的满足时效性要求的开放式车辆路径问题——带时间窗和带时间期限开放式车辆路径问题。首先构建了两类问题的数学模型,同时提出了求解两类问题的基于禁忌搜索的迭代局部搜索算法,该算法集成了不同的解接受标准以及一个基于阈值接受的后优化过程。基于随机产生的测试问题的实验结果表明:基于禁忌搜索的迭代局部搜索算法可以有效地求解带时间窗和带时间期限开放式车辆路径问题。5.研究了带时间窗和随机旅行时间车辆路径问题通过对标准车辆路径问题的拓展,引入新的边约束条件:时间窗、随机旅行时间和服务时间,研究了一类新的随机车辆路径问题——带时间窗和随机旅行时间车辆路径问题。根据不同的优化标准,分别构建了问题的机会约束规划模型以及带修正随机规划模型。机会约束规划模型是在随机约束以一定的置信水平成立的条件下最小化运输费用。带修正的随机规划模型是一个两阶段优化问题,其确定第一阶段的路线集以最小化第二阶段(随机变量实现后)的期望运输费用。鉴于问题的随机特性,为了有效求解该问题提出了基于随机模拟的禁忌搜索算法。同时基于随机产生的测试问题通过实验检验了算法有效性。6.研究了固定车辆数异型车辆路径问题在车辆路径问题经典文献中,一般均假设车辆同质且车辆数无限。然而在实际运作中,车辆集一般是由具有不同属性(装载能力、固定成本以及单位公里可变费用)的车辆组成,且受运作成本的约束车辆数也是固定的。通过对车辆同质及车辆数无限的假设条件的放松,研究了固定车辆数的异型车辆路径问题。在首先给出问题数学模型的基础上,提出了求解该问题的多起点自适应记忆规划算法。基于文献中的基准测试问题,系统地研究了算法在不同多样化策略下的性能。同文献中其它算法的比较结果表明:提出的多起点自适应记忆规划算法是较好的求解固定车辆数异型车辆路径问题的算法,对于其中五个测试问题,算法发现了新的最优解。7.研究了车辆路径问题的应用问题以城市日常报品配送问题为例,进行了车辆路径问题的应用研究。基于报品配送的实际数据,运用本文研究的几类车辆路径问题的框架,研究了不同类型的最优报品配送车辆路径方案的制定问题。执行本文提出的优化算法,给出了不同类型的报品配送的最优车辆路径方案。通过实验验证了论文提出的车辆路径问题优化算法的有效性,实验结果表明论文提出的算法可以用于生产管理中最优车辆路线方案的制定。本文创新性研究成果及贡献主要包括以下几方面:1.松弛了标准VRP中车辆路线为哈密尔顿巡回的假设,研究了车辆路线为哈密尔顿路径的开放式车辆路径问题。构建了求解问题的蚁群优化算法,该算法是一个集成了后优化过程的在超立方框架下执行的MAX-MIN蚂蚁系统。同文献中其它算法性能的比较结果证明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法,算法改进了文献中其它算法发现的最优解。2.引入时间约束,研究了两类新的满足时效性要求的车辆路径问题——带时间窗和带时间期限开放式车辆路径问题。提出了求解上述两类问题的迭代局部搜索算法,并基于随机产生的测试问系统研究了算法的求解性能。3.引入时间窗、随机旅行时间和服务时间约束,研究了带时间窗和随机旅行时间车辆路径问题。根据不同的优化标准,分别构建了问题的机会约束规划模型以及带修正随机规划模型。提出了基于随机模拟的禁忌搜索算法,基于随机机产生的测试问题的实验结果验证了算法的有效性。4.通过松弛标准VRP中车辆同质及车辆数无限的假设,研究了固定车辆数异型车辆路径问题。提出了求解问题的多起点自适应记忆规划算法,同文献中其它算法的比较结果表明:多起点自适应记忆规划算法是较好的求解固定车辆数异型车辆路径问题的算法,对于五个基准测试问题,算法发现了新的最优解。本文综合运用运筹学和组合优化的理论与方法,对几类车辆路径问题模型及算法进行了系统的研究。本文的研究工作拓展了车辆路径问题以及组合优化的研究空间,丰富了运筹学和管理科学的理论研究成果,同时为运输、物流和配送管理等领域中最优车辆路径方案的规划与设计提供了借鉴和参考。
参考文献：
[1]. 物流配送中车辆路径问题的多目标优化算法研究[D]. 卫田. 清华大学. 2007
[2]. 随机配送时间车辆路径优化模型及算法研究[D]. 刘昌生. 兰州交通大学. 2014
[3]. 需求不确定的车辆路径问题模型与算法研究[D]. 李阳. 大连海事大学. 2018
[4]. 车辆路径问题的建模及优化算法研究[D]. 娄山佐. 西北工业大学. 2006
[5]. 随机时间车辆路径问题研究[D]. 杨雪敏. 南京农业大学. 2016
[6]. 逆向物流回收的车辆配置及路径优化研究[D]. 滕耘. 北京交通大学. 2008
[7]. 蚁群算法在车辆路径问题中的应用研究[D]. 蒋勇. 浙江工业大学. 2007
[8]. 带时间窗和随机时间车辆路径问题:模型和算法[J]. 李相勇, 田澎. 系统工程理论与实践. 2009
[9]. 随机需求车辆路径问题的混合遗传算法研究[D]. 韩娟娟. 辽宁师范大学. 2016
[10]. 车辆路径问题模型及算法研究[D]. 李相勇. 上海交通大学. 2007
标签：公路与水路运输论文; 遗传算法论文; 随机算法论文; 时间窗论文; 混合策略论文; 优化策略论文; 路径分析论文; 动态模型论文; vrp论文; 算法论文;