一、最短路径问题的求解（论文文献综述）
储胜[1]（2021）在《强制垃圾分类背景下城市生活垃圾回收网络规划研究》文中研究说明城市生活垃圾量在快速增长,带来的环境压力逐步增大,回收工作量也随之增加,强制推行城市生活垃圾回收的源头分类工作势在必行,发达国家的实践也证明了这一点。中国决心打破以往垃圾分类难以落实的局面,计划全面落实城市生活垃圾分类工作,“强制垃圾分类时代”已经到来。在此背景下,城市生活垃圾的回收工作将发生变动。面对新工作的不确定性,开展对强制垃圾分类背景下城市生活垃圾回收网络规划的研究具有重要的意义。论文通过文献法回顾了国内外典型城市生活垃圾分类情况,梳理了垃圾回收网络规划研究的现状,在对这两方面内容进行简要分析和总结后,确定了论文的研究方向是从设施选址、路径规划两个方面着手回收网络的构建,着重于目标模型的建立;确定了模型求解的发展趋势是混合或改进已有的智能算法。以运输成本最小化为研究目标,考虑城市生活垃圾在回收过程中分类运输以及在中转站后的分类处置情况,构建了城市生活垃圾回收网络中的垃圾中转站选址模型。以运输路径最短为目标,考虑运输车辆的能力限制,按垃圾类别、垃圾中转站位置构建了路径规划模型,用于设计不同的回收路径。以城市生活垃圾分类回收网络中设施选址模型和路径规划模型为基础,对比不同智能算法的特点,针对性的设计了基于双层变量的粒子群算法用于解决垃圾中转站选址模型的求解,采用了蚁群算法对路径规划模型求解。最后,以北京市昌平区地理环境为原型,模拟数据代入模型求解,验证了强制垃圾分类背景下城市生活垃圾回收网络模型的可操作性和实用性。研究结果表明,城市生活垃圾的强制分类时代对回收物流的主要影响有垃圾分类功能向源头转移、垃圾回收的运输和处置工作需要分类开展、垃圾回收工作不同环节责任自负三个方面。论文建立的强制垃圾分类背景下城市生活垃圾回收网络规划模型具有实用性;且可以根据模型应用区域的规模,自适应调整,有着较好的泛化性。论文中创新提出的基于双层变量的粒子群算法,能够有效地求解强制垃圾分类背景下城市生活垃圾回收网络中的垃圾中转站选址模型,解决了兼顾离散型变量和连续型变量的混合整数规划问题,补足了传统粒子群算法仅适用于连续型变量求解的短板。此外,蚁群算法也很好地求解论文中建立的垃圾回收路径优化模型,便于模型在实际中更好地应用。
高如虎[2]（2021）在《柔性列车运行图优化及交替方向乘子法》文中指出作为铁路运营组织过程中最重要的环节,列车运行图是协调铁路不同部门、不同工种进行运输生产活动的基础,同时也是连接铁路运营者与出行者的桥梁。列车运行图优化问题受多种因素制约,一直以来是交通运输领域公认的难题。为了降低列车运行图优化问题的求解难度,常常对列车附加一些人为的、并且相对狭窄的约束。这种强加的约束限制了铁路能力的有效利用,同时对于拥挤的铁路线路难以找到满意的优化方案。此外,列车运行图问题常常被独立优化,即仅对列车的到发时刻决策,而不考虑其他运营规划过程与列车运行图的互相影响。本文基于系统优化的思想,提出柔性列车运行图优化架构,构建集成多种因素的一体化数学模型,期望生成系统最优且满足各类实际需求的铁路运营组织方案。主要研究内容如下:（1）基于优化求解器的精确求解方法。考虑列车越行、列车发车时间范围、安全间隔等实际约束,引入列车发车顺序0-1变量,构建列车运行图的一般混合整数规划模型。在分析模型复杂度的基础上,利用通用优化求解器对列车运行图优化问题精确求解。实验表明,这种优化方法仅适合中小规模优化问题,对于大规模问题,需设计更加有效的求解方法。（2）基于拉格朗日松弛方法的列车运行图优化。针对现有的列车运行图优化结构,通过构建时空网络描述列车的时空转移。将列车运行图的各种约束转换为时空弧段的制约关系,将优化目标转化为列车的弧段费用,将安全间隔约束描述为列车占用网络弧段的不相容关系。利用拉格朗日松弛将原问题分解为关于单列车的最短路径子问题。算例表明,现有的优化结构限制了列车的路径选择,需要设计更加实际和灵活的运行图优化框架。（3）基于ADMM方法的柔性列车运行图优化。针对柔性列车运行图优化问题,利用时空网络将列车运行图优化问题描述为网络优化问题,将列车的安全间隔、越行以及均匀性约束刻画为列车占用弧段的不相容关系。利用交替方向乘子法对模型进行松弛、增广、线性化、分解,提出了一种优先权迭代策略对列车子问题交替迭代求解。通过实例验证了模型的正确性和算法的有效性,并比较了交替方向乘子法与拉格朗日松弛方法的求解效率。（4）考虑到发线运用的柔性列车运行图优化。在柔性列车运行图框架下,综合考虑了车站到发线运用的影响。构建了时空扩展网络描述列车的时空转换及到发线占用。利用不相容弧约束描述列车对时空资源以及车站资源的占用耦合关系。利用交替方向乘子法对原问题进行分解,并提出了一种更加可靠的可行化启发式算法。通过算例验证了所提出方法的有效性。（5）考虑动车组运用的柔性列车运行图优化。在柔性列车运行图优化架构下,综合考虑了动车组运用的影响。以列车运行区段为状态维,构建时空状态网络描述动车组的时空路径和状态选择。为提高求解效率,提出了网络弧段和节点压缩技术缩减网络,并设计了专门的带有限制条件的最短路径算法。利用交替方向乘子法对模型松弛、增广和分解,通过算例验证了所提方法的有效性。
贺俊源[3]（2021）在《高速铁路网径路搜索研究与系统研发》文中进行了进一步梳理根据高速铁路列车开行方案的起讫点,为列车选择可行且合理的列车运行径路,是编制高速铁路列车运行图的必要环节,也是保障高速铁路列车运行图编制质量的重要因素。科学的制定列车开行径路,可有效联动高速铁路列车开行方案制定与高速铁路列车运行图编制过程,对提升高速铁路运输组织管理水平具有十分重要的意义。本文对国内外路网建模与路径搜索有关研究成果进行总结分析,深入研究高速铁路物理网络构建方法与高速铁路列车运行径路的搜索技术,设计求解高速铁路合理径路集的方法,并开发高速铁路列车运行径路管理信息系统。论文的主要工作如下:（1）梳理并总结高速铁路成网条件下枢纽地区布置特点,分析高速铁路网络的组成元素,对各组成元素进行简化抽象,构建由节点、边及其连接关系组成的无负权的多重边有向图,作为高速铁路物理网模型,对高速铁路物理网络模型特征的进行评价。（2）归纳并总结高速铁路列车运行径路的概念与定义,阐述高速铁路列车运行径路在列车开行方案制定、列车运行图编制等过程中的作用,分析高速铁路列车运行径路的影响因素,从车站与区间两方面,论述高速铁路列车运行径路的可行性,在可行径路基础上,基于不同运用场景,分析不同径路的合理性,总结合理径路的特点。（3）基于构建的高速铁路物理网络和径路搜索算法,设计开发高速铁路列车运行径路管理信息系统,以京沪高铁为实证案列,搜索京沪高铁北京南*高速场至上海虹桥*高速场之间合理径路集,并从中选取最优径路,与京沪高铁北京南*高速场至上海虹桥*高速场之间的实际径路对比,验证系统的实际可行性。
徐志磊[4]（2021）在《资源受限的时变网络最短路径问题研究》文中研究表明资源受限的时变网络最短路径问题是网络优化领域中的一类关键问题。已有的算法在求解该类问题时存在着误差较大、效率偏低的缺点。为了克服这些缺陷,本文提出三种神经网络模型来求解不同情形下的资源受限时变最短路径问题,且能够得到精确解。主要创新点如下:1.提出跳数约束时变神经网络（HTNN）模型和算法,能够求得跳数约束时变最短路径问题的最优解。HTNN是一种以自动波驱动的神经网络,其特点是并行计算和不需要训练。HTNN所基于的跳数约束时变神经元具有七层结构,所求解的问题是一种单一权值时变网络上的资源受限时变最短路径问题。在国际标准数据集上的实验仿真结果表明了HTNN的优越性。2.提出代价约束时变神经网络（CTNN）模型和算法,能够求得代价约束时变最短路径问题的最优解。CTNN是一种并行计算且不需要训练的时间波神经网络。CTNN所基于的代价约束时变神经元具有六层结构,所求解的问题是一种双权值时变网络上的资源受限时变最短路径问题。国际标准数据集上的实验仿真结果表明了CTNN的优越性。3.提出时延约束时变神经网络（DTNN）模型和算法,能够求得时延约束时变最短路径问题的最优解。时延约束时变最短路径问题是双权值时变网络上的另一种资源受限时变最短路径问题,其包含三种变体问题:零等待时延约束时变最短路径问题、任意等待时延约束时变最短路径问题和限制等待时延约束时变最短路径问题。提出的DTNN基于一种具有七层结构的时延约束时变神经元,与传统算法只能求解一种变体问题不同的是,DTNN能够在不做任何修改的情况下同时求解三种时延约束时变最短路径的变体问题。在国际标准数据集上的实验结果表明,DTNN相比存在的算法具有鲜明的优越性。
孙秀巧[5]（2020）在《高速公路网巡逻车路径选择与车辆配置协同优化研究》文中认为随着我国经济的高速增长,人民生活水平的日益提高,人均车辆保有量也日益增加,高速公路交通事故屡见不鲜。交通事故导致高速公路交通拥堵、人员伤亡以及二次事故等问题给高速公路交通管理部门带来了巨大的压力,交通事故的增加以及交通警力资源缺乏等问题对传统粗放型交通勤务工作模式提出了巨大挑战。传统大多单独考虑巡逻车站点选择、路径选择及车辆配置问题的优化,较少看到三者的组合研究,且大多未考虑出警导致的巡逻车失效问题。如何在警力资源有限的条件下科学合理地设置巡逻设施选址点、优化巡逻路径及配置警力,以缩短事故响应时间、减少交通延误及人员伤亡是高速公路交通管理部门提升其管理水平和工作效率的主要目标,也是相关科研人员努力研究和探索的科研方向。本文针对高速公路路网内交通事故、尤其是多交通事故情景下的巡逻车辆路径及车辆配置协同优化问题进行深入研究,具体研究内容如下:（1）以高速公路网总事故平均响应时间为目标,将路径选择及车辆配置这两个最关键的问题整合到一个模型中,对高速公路巡逻车路径选择及车辆配置协同优化问题进行深入研究。在回顾车辆路径优化问题建模基础上,将高速公路网中的路段作为需求点,把高速公路巡逻路径问题转化为一种m TSP问题,基于m TSP问题中子路径消除约束对巡逻路径问题建模。并以Sioux Falls经典路网为例,采用有序整数编码方式对巡逻路径进行编码,采用改进遗传算法对模型进行求解,求解结果与情景假设、模拟退火算法、大规模邻域搜索算法及双基贪婪算法求解结果进行对比,分析本文编写的遗传算法性能。（2）研究了交叠巡逻情景高速公路巡逻车路径选择及车辆配置协同优化问题模型及方法。遵循公平性原则,以全路网事故平均响应时间为目标,提出了允许多条路径同时对某条或某些路段进行巡逻的非线性混合整数完全覆盖模型。采用序数编码与矩阵编码相结合的方式对遗传算法进行编码,实现了交叉、变异等遗传操作,采用拆分技术确保路径连通性,并通过调用LINGO实现了对车辆分配算法的求解。基于Sioux Falls经典有向路网对算法进行应用,并将结果与无交叠巡逻模式遗传算法及模拟退火算法求解结果进行比对分析。（3）高速公路多起突发交通事故情景下,针对巡逻车处于出警状态时,该巡逻车负责的其他路段发生事故时其需求将得不到响应这一问题,本文提出优化区域允许一部分巡逻车停在优化后的站点内随时待命、另外一部分巡逻车负责在路面上来回巡逻的组合巡逻模式,构建了多事故情景的高速公路巡逻车路径选择及车辆配置协同优化模型,以期在最优巡逻路径及最少人力物力下,达到高速公路交通事故总平均响应时间最短的目的。基于拉格朗日松弛算法、分枝定界算法、最短路算法、动态规划算法及遗传算法对模型进行求解。最后通过实例研究,讨论了模型及方法的可行性,并给出了分析结果。（4）以吉林省部分高速公路网为例,开展了基于高速公路交通事故响应速度的巡逻路径与车辆配置协同优化实例研究。通过结合现有路政科/交警部门管辖范围及车辆配置现状,对比分析了高速公路网总交通事故平均响应时间。针对现有警力对优化结果的影响分析,为高速公路相关管理部门的管理实践提供了政策建议。本文以国内外相关研究成果为基础,以调查统计及优化建模为研究手段,对高速公路网交通事故快速响应问题进行深入挖掘与研究。在理论层面上具有一定的创新和承接意义,在实践应用层面对于提高交通事故响应速度、提升高速公路管理实践的科学水平具有重要的现实意义。
张春苗[6]（2020）在《时间依赖绿色选址-车辆路径问题及算法研究》文中认为我国的物流费用一直居高不下,且在物流的运输活动中消耗大量的能源、排放大量的废气,因此有必要通过管理与优化各项物流活动,降低物流成本、减少物流运输过程中的能耗与排放。选址-路径问题（Location Routing Problem,LRP）是物流优化方向的一个重要分支问题,经典的选址-路径问题模型建立在高度概括的实验网络环境,节点之间的行程时间与车辆的速度是常数,多以配送距离为优化目标。而实际的路网中行程时间与车辆速度具有时变性与随机性,是时间依赖函数,因此时间依赖选址-路径问题对实际的物流配送活动更具有现实的指导意义。本文在经典的LRP问题基础之上,循序渐进、逐层深入的研究静态网络、时变网络以及随机时变路网环境下的绿色LRP问题,从数学模型及求解算法上展开研究,具体研究内容如下:（1）静态网络绿色选址-路径问题及算法静态网络是指网络节点（客户与配送中心）之间的距离是欧氏距离,车辆的速度认为是恒定的。基于静态网络假设,建立考虑油耗的选址-路径模型称为绿色选址-路径问题（Green Location-Routing Problem,GLRP）,该模型优化目标分为三个部分包括启用车辆成本,配送中心成本及油耗成本。由于静态网络中车辆的速度认为是1,所以静态网络油耗模型只考虑了车辆载重与行驶距离对油耗的影响。针对静态网络GLRP的特征,基于生物启发计算理论,设计改进型人工蜂群算法求解模型。并将改进型人工蜂群算法与三种经典LRP问题求解算法比较分析;通过案例比较改进型人工蜂群算法与生物启发计算中的粒子群算法、遗传算法在求解GLRP问题上的性能差别。本章的贡献是提出了绿色选址-路径问题建模的方法,深入挖掘配送中心选址规划、客户特征对车辆运行过程的能耗及总运营成本的影响,为时变网络绿色选址-路径问题的研究夯实基础。（2）时变网络绿色选址-路径问题及算法车辆速度是影响燃油消耗与排放的重要因素,网络的时变特性决定了车辆速度时变性,因此有必要合理路径规划以达到节约成本与降低能耗,减少排放的目标。本文第三章充分考虑车辆速度对油耗的影响,在时变网络下,模拟实时交通网络,将网络路段分为5类,每个路段的行程速度采用阶梯型的离散速度函数。在时变网络环境下基于经典的瞬时油耗计算模型CMEM,建立时变选址-路径模型（Time Dependent GLRP,TDGLRP）。针对TDGLRP问题的特征,基于生物群落演化理论设计多种群人工蜂群算法求解TDGLRP。对比分析单种群与多种群人工蜂群算法的差异,并研究了客户分布、客户时间窗对规划的影响。给出客户节点为1000个的大规模案例,为其他研究者提供对比的数据。本章的贡献是分析了时变网络TDGLRP与静态网络GLRP模型及求解方法上的差异,对比分析时变网路与静态网络规划路径的不同。为进一步深入研究路网环境下绿色选址-路径问题提供理论与方法基础。（3）随机时变路网绿色选址-路径问题及算法真实的交通路网具有动态随机的特性,因此论文第四章建立随机时变路网环境下的随机时变绿色选址-路径问题（Stochastic Time Dependent GLRP,STDGLRP）模型。为完全满足硬时间窗需求,根据最大最小优化模型将随机时变路网鲁棒为确定型的时变路网。与时变网络不同,随机时变路网中,从节点A到节点B具有不同的最短路径,还可能需要经过其它的节点,且两节点间的行程时间随车辆出发时间的不同而不同,具有随机时变性,因此在随机时变路网环境下,需要实时计算最短路径。同样,油耗也是随机时变的变量,需要实时计算。针对STDGLRP的特征设计高层策略为人工蜂群算法、动态接受机制的超启发算法求解模型,并设计9类底层算子。为对比分析,同时设计高层策略为蚁群算法、禁忌搜索算法的超启发算法,并与3种解的接受策略组合成9种超启发算法,进行对比分析。比较STDGLRP与TDGLRP模型下启用的车辆数量不同;时间窗的变化对各个函数值的影响;车辆容量的影响;针对路网的随机性,分析在不同波动水平的路网环境下规划路径的差异。（4）多目标时变绿色选址-路径问题及算法在时变路网环境下,建立以总成本、行程时间及启用车辆为优化目标的多目标时变绿色选址-路径问题,使用人工蜂群超启发算法进行求解。并将多目标人工蜂群算法与两种常用的多目标算法进行对比分析。
刘菲[7]（2020）在《基于历史样本数据的可靠路径问题研究》文中研究指明交通出行是人们日常生活中不可避免的基本需求,提前获取可靠且有效的出行路径信息不仅可以满足出行者的基本出行需求,还可以大大提高出行者的出行效率,因此交通网络中的路径规划问题应运而生。论文对交通网络中最短路径问题、可靠路径问题及其求解方法的国内外研究进行了回顾。静态交通网络中的最短路径问题一般考虑以路径行程时间最小为目标,未考虑出行时间的不确定性,因此存在较大的局限性。在最短路径问题基础上,以路径行程时间平均值和标准差线性组合的形式为目标函数,考虑了出行时间的不确定性和随机性,构造静态随机交通网络中的可靠路径问题。基于以上回顾和总结,确定了论文的主要研究内容。构建基于历史样本数据的可靠路径模型。考虑到出行时间的不确定性、随机性和路段行程时间之间的空间相关性是实际交通网络中不可忽视的特性,论文采用路径行程时间平均值和标准差线性组合的形式作为目标函数,使用大量的路段行程时间历史样本数据,并结合概率统计学中用样本方差估计随机变量总体方差的方法,直接计算路径行程时间的标准差,构建基于历史样本数据的可靠路径模型。该模型通过路径行程时间的标准差项考虑了出行时间的不确定性和随机性,同时大量的路段行程时间历史样本数据隐含了路段行程时间之间的空间相关性,使得模型更加贴合现实。提出基于拉格朗日松弛的可靠路径问题求解方法。由于历史样本数据的可靠路径模型具有非线性、不可加性等特性,违背了贝尔曼最优性原则,因此,论文考虑采用基于拉格朗日松弛的方法对模型进行求解。拉格朗日松弛方法的基本思想是通过引入非负的拉格朗日乘子,把难以处理的约束移动到目标函数中,使目标函数仍然保持线性,从而得到一个与原问题等价的拉格朗日松弛问题。拉格朗日松弛方法求得的最优解是原问题最优解的下界,最优下界是通过拉格朗日松弛问题关于拉格朗日乘子的最大化问题,即对偶问题求得的。基于拉格朗日松弛的可靠路径问题求解方法分为四个步骤:问题重构,构造并简化拉格朗日松弛问题,构造拉格朗日对偶问题,求解对偶问题。不同规模的交通网络算例分析。论文将提出的模型和求解方法应用于不同规模的交通网络。通过单OD对的小型交通网络算例,与基于方差-协方差矩阵的可靠路径模型进行对比,并验证模型和求解方法的正确性。通过多OD对的Sioux-Falls中型交通网络算例,分析其收敛速度、相对间隙和运行时间,验证模型和求解方法对中型交通网络的适用性。
邱钰峻[8]（2020）在《基于粒子群算法的铁路枢纽铺架方案优化研究》文中指出随着我国交通强国战略的推进和铁路网络规模的进一步扩大,枢纽新建和扩能改造工程的需求急剧增大,铁路枢纽的设计也愈发大型化和综合化,这对铁路枢纽的施工组织提出了更高的要求。而枢纽作为线路的控制性工程,铺架工程又作为枢纽施工中的重要环节,面对枢纽线路错综复杂、作业密度大、交叉干扰大、边界条件多的复杂状况,施工环节多、涉及面广、耗时长的枢纽铺架工程工期难以得到有效保障。因此,本文考虑枢纽线路交错情况和工程限制条件,探讨建立了同时求解最优铺架顺序、转场路径和运输路径的铁路枢纽铺架方案优化模型,并基于参数少、收敛快、适用于求解复杂工程优化问题的粒子群算法进行求解,保证了枢纽铺架施工的连续性和工期目标的实现。首先,分析归纳了我国铁路枢纽及铁路铺架工程的发展趋势及要求,从工期优化、铁路枢纽施工、铺架方案优化三方面总结了国内外研究现状,从而明晰了本文研究内容和技术路线。其次,通过探讨分析枢纽铺架工程的特点及影响因素,明确了枢纽铺架工程适宜选择的铺架方案。针对枢纽铺架工程特性,探讨了以组合优化问题求解铺架顺序,以最短路径问题求解转场路径及运输路径的铺架方案优化模型建立思路。然后,研究建立了同时求解最优铺架顺序、最优转场路径和最优运输路径的枢纽铺架方案优化模型。该模型基于图论建立铁路枢纽线路网络,将工程限制转变为施工限制时段和通行限制时段,作为线路边属性,并根据边属性、边和交叉节点通行情况标定边权值和节点权值,从而以工期为优化目标,基于铺架段的施工工期、架桥机转场调头时间、资源调配时间进行铺架方案优化。再次,研究优化算法求解铺架方案按模型。尝试利用离散粒子群算法求解最优铺架顺序,并结合Dijkstra算法求解转场路径和运输路径。探讨改进离散粒子群算法,提高算法适用性;基于弧标号改进了Dijkstra算法,以考虑交叉节点的延误和限制。最后,将基于改进离散粒子群—弧标号Dijkstra算法的枢纽铺架方案优化模型应用于实际枢纽铺架工程,验证了模型的适用性、可行性和可靠性。
唐芳[9]（2020）在《时间—空间—状态网络中车辆最小期望费用路径选择问题研究》文中研究表明近年来,移动支付的快速发展以及城市规模的不断扩大,使得网约车迅速兴起,以其预约便捷、支付方便、可达性较强、服务多样和营业时间长等特性在城市交通系统中发挥着重要作用。其中拼车服务以其多人共乘、成本分摊、优惠共享等特性颇受大众喜爱,并以其缓解交通拥堵、减轻能源消耗等优点受到政府大力倡导。然而,在网约拼车场景中,由于诸多复杂因素的影响（如恶劣天气、汽车抛锚、道路修建、交通事故等）,路段的通行时间具有高度不确定性,此时的路段通行时间不能精确测量。一方面,对于同一路段,车辆进入该路段时刻的差异可能导致通行时间的不同,如高峰时期和非高峰时期的路段通行时间就有明显差异,即随着道路拥堵程度的不同,路段通行时间也随之动态变化。另一方面,在不同的历史日期中,即使进入路段的时刻相同,该路段的旅行时间也可能不同。如果车辆路径规划是以单天数据为基础而不考虑多天的综合情况,必然会导致规划最短路径偏离实际最短路,增加车辆绕行和空车出行的现象,从而造成车辆载客空间的浪费,加大企业成本并影响调度系统的稳定性,甚至加剧交通拥堵。因此,在现有的交通条件下,如何提供优化路径以提高驾驶员接送乘客的效率和质量,已成为拼车服务信息系统的关键功能部分,也已然成为交通运输领域关注的一个重要科学问题。从企业角度,有效提高企业的服务质量和运营效率的同时最小化运营成本是其核心诉求。基于此,本文开展了在网约拼车场景中,对车辆路径选择的优化研究。基于大量历史出行数据,构建了0-1规划模型,目标函数为最小期望费用,同时对复杂模型进行重构,随后用拉格朗日松弛方法松弛模型,然后用改进动态规划算法求解模型,最后利用不同场景的算例分别对模型和算法的有效性进行评估。旨在给车辆提供高鲁棒性的路径选择引导,以保证能够在多位乘客的指定上车时间窗内接上乘客,并且在乘客指定的下车时间窗内分别将乘客送达目的地,最后车辆在行驶时间窗内返回仓库。该研究对提高用户满意度和网约拼车系统运营效率及供需匹配能力具有一定的理论意义和现实价值。本文具体内容详述如下:描述随机时间-空间-状态网络。本文构建了随机时间-空间-状态网络,其中,每一天对应一个时间-空间-状态网络。本文会详细阐述本文研究的网约拼车场景中最小期望车辆路径选择问题。随后本文将用一个简单的算例来对建立的随机时间-空间-状态网络模型进行详细的阐述,然后进一步描述车辆在服务过程中携带乘客的状态以及转换,车辆携带状态的数量。构建随机时间-空间-状态网络车辆最小期望费用路径选择模型。为了更加精确的构建所研究问题的模型,本文在构建的时间-空间-状态网络基础上,增加了相应的虚拟节点和虚拟路段。然后构建了以目标函数为最小期望费用的数学模型。模型约束包括各节点流量守恒约束;每位乘客的乘车请求都要被满足,且仅有一辆车服务的约束;跨不同日期的同一物理路径约束;还有二元变量约束。重构模型。由于本研究考虑了大量的历史出行数据,因此在上述模型中构建了一个跨不同日期的同一物理路经约束,这个约束是基于多个等式的约束,需要对该多等式约束重新构造,使新的约束便于用拉格朗日松弛方法吸收到目标函数中。拉格朗日松弛方法松弛原模型。根据本文所建模型的复杂性,在处理大规模数据集时面临着计算上的挑战。因此,本文引入拉格朗日乘子将复杂的约束松弛到目标函数中,随后将松弛模型分解为一系列单车时变最短路子问题。松弛模型求解算法。本文由于考虑了历史不同日期的数据,因此针对分解后的子问题求解时,需要改进动态规划算法,使其适用于本文模型求解。算例分析。本文对简单网络和现实网络分别构造几种不同场景进行求解,证明所建模型的正确性和算法的有效性。
袁冲[10]（2020）在《B公司某装配车间物料配送路径优化研究》文中进行了进一步梳理随着制造业的快速发展,车间物流体系是否合理对提高企业的经济效益具有重大的影响。而物料配送车辆路径问题作为物流体系的重要一个环节,低效的物料配送会约束生产线高速有效的生产,所以如何规划物料配送路径不仅能带来生产线的稳定运作,而且能提高车间生产的效率。本文以B公司某装配车间物料配送现状为背景进行研究,通过对B公司装配车间物料配送现状进行总结分析,结合车辆路径问题理论明确研究意义。提出了基于车间网络道路约束下的双目标车辆路径问题数学模型,并结合模型特点设计遗传禁忌搜索混合算法进行求解,最后通过B公司某装配车间实例验证了本文模型及算法的有效性,并为企业制定了合理有效的物料配送方案。本文主要研究内容如下:（1）对于经典车辆路径问题数学模型存在的问题,本文从车间实际情况出发,通过在经典车辆路径问题中考虑车间网络通道约束,提出基于车间网络通道约束下以配送车辆数最少和配送总距离最短为双目标的车辆路径问题数学模型,并在模型中同时考虑车辆配送容量约束。（2）考虑到基于车间网络通道约束下双目标车辆路径问题数学模型的特点,对经典遗传算法的基础上进行改进,采用能更直观的看出各车辆配送路径的自然数编码方式,选择算子首先采用最大保留策略,后采用轮盘赌选择个体,交叉算子设计部分匹配交叉方式,变异算子设计逆转变异法,这样操作使得种群多样性增加,不仅能改善算法局部搜索的能力,而且能防止算法过早收敛,最后结合禁忌搜索算法易跳出局部最优解的优点,设计了遗传禁忌搜索混合算法作为本文模型的求解方法。（3）结合B公司某装配车间实例,利用MATLAB软件进行仿真,对B1生产线装配车间10个工位点的物料配送路径进行优化,遗传禁忌搜索混合算法求解结果与车间现配送方案相比,不仅配送总距离减少了170米,配送车辆也减少了1辆,而且车辆平均装载率提升了22.92%。再使用传统遗传算法对相同模型进行求解,对改进前后算法性能对比,使用遗传禁忌搜索混合算法求解配送总距离得到进一步降低,算法收敛速度也更快,算法求解性能也更稳定。最后利用模拟退火算法对直线配送下的经典车辆路径问题进行了求解,分析了两者产生的差异是由于经典车辆路径问题得出的是理想解,而在车间通道约束下的车辆路径问题得出的是最优实际解。经过实例分析验证了基于车间网络通道约束下车辆路径问题数学模型和改进遗传禁忌搜索混合算法的有效性,为企业制定合理配送方案和提升经济效益提供了有效指导。
二、最短路径问题的求解（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、最短路径问题的求解（论文提纲范文）
（1）强制垃圾分类背景下城市生活垃圾回收网络规划研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 选题背景及意义 |
| 1.1.1 选题背景 |
| 1.1.2 选题意义 |
| 1.2 国内外研究现状 |
| 1.2.1 城市生活垃圾分类 |
| 1.2.2 垃圾回收网络规划研究 |
| 1.2.3 研究现状评述 |
| 1.3 研究内容与研究方法 |
| 1.3.1 研究内容 |
| 1.3.2 研究方法及技术路线 |
| 第2章 相关理论基础 |
| 2.1 设施选址理论 |
| 2.1.1 设施选址问题 |
| 2.1.2 设施选址常用模型 |
| 2.2 路径优化理论 |
| 2.2.1 路径优化问题 |
| 2.2.2 路径优化基础模型 |
| 2.3 本章小结 |
| 第3章 强制垃圾分类对回收网络影响研究 |
| 3.1 分类前城市生活垃圾回收物流研究 |
| 3.1.1 概述 |
| 3.1.2 特点分析 |
| 3.1.3 不足之处 |
| 3.2 垃圾分类及立法研究 |
| 3.2.1 国内外垃圾分类情况研究 |
| 3.2.2 垃圾分类立法相关内容 |
| 3.3 分类后城市生活垃圾回收物流网络研究 |
| 3.3.1 分类后城市生活垃圾回收物流系统变动 |
| 3.3.2 分类后垃圾中转站选址问题 |
| 3.3.3 分类后城市生活垃圾回收路径问题 |
| 3.4 本章小结 |
| 第4章 城市生活垃圾回收网络规划模型研究 |
| 4.1 城市生活垃圾回收网络规划问题的提出 |
| 4.1.1 城市生活垃圾回收网络概述 |
| 4.1.2 城市生活垃圾回收网络规划目标 |
| 4.1.3 城市生活垃圾回收网络规划原则 |
| 4.2 城市生活垃圾回收网络规划模型构建 |
| 4.2.1 垃圾中转站选址模型 |
| 4.2.2 垃圾回收路径规划模型 |
| 4.2.3 垃圾回收网络规划模型 |
| 4.2.4 模型泛化性研究 |
| 4.3 本章小结 |
| 第5章 城市生活垃圾回收网络规划模型求解算法 |
| 5.1 网络规划求解算法研究 |
| 5.1.1 精确算法 |
| 5.1.2 启发式算法 |
| 5.2 模型求解算法选择 |
| 5.3 基于双层变量的粒子群算法的模型求解 |
| 5.3.1 变量分层 |
| 5.3.2 整数变量处理 |
| 5.3.3 连续型变量处理 |
| 5.3.4 基于双层变量的粒子群算法 |
| 5.4 基于蚁群算法的模型求解 |
| 5.5 本章小结 |
| 第6章 算例 |
| 6.1 模拟数值设置 |
| 6.1.1 位置数据 |
| 6.1.2 垃圾产生量及各级能力限制数据 |
| 6.2 网络规划模型求解 |
| 6.2.1 设施选址求解 |
| 6.2.2 路径规划求解 |
| 6.3 本章小结 |
| 第7章 研究成果和结论 |
| 参考文献 |
| 附录一 基于双层变量的粒子群算法 |
| 附录二 蚁群算法 |
| 攻读硕士学位期间发表的论文及其他成果 |
| 致谢 |
（2）柔性列车运行图优化及交替方向乘子法（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 选题背景和意义 |
| 1.2 文献综述 |
| 1.2.1 列车运行图问题 |
| 1.2.2 列车运行图建模 |
| 1.2.3 列车运行图求解 |
| 1.3 论文创新点 |
| 1.4 研究内容 |
| 2 列车运行图优化及精确求解 |
| 2.1 问题分析 |
| 2.1.1 问题描述 |
| 2.1.2 符号定义 |
| 2.2 模型构建 |
| 2.2.1 优化目标 |
| 2.2.2 约束条件 |
| 2.3 模型复杂度 |
| 2.4 数值算例 |
| 2.4.1 算例设置 |
| 2.4.2 计算结果 |
| 3 基于拉格朗日松弛的列车运行图优化 |
| 3.1 问题分析 |
| 3.1.1 问题描述 |
| 3.1.2 符号说明 |
| 3.2 时空网络优化模型 |
| 3.2.1 时空网络构建 |
| 3.2.2 0-1 整数规划模型 |
| 3.3 基于拉格朗日松弛的求解方法 |
| 3.3.1 拉格朗日松弛方法 |
| 3.3.2 问题分解 |
| 3.3.3 算法框架 |
| 3.3.4 时变最短路径算法 |
| 3.3.5 上界生成算法 |
| 3.4 数值算例 |
| 3.4.1 算例设置 |
| 3.4.2 计算结果 |
| 3.4.3 比较分析 |
| 4 基于ADMM方法的柔性列车运行图优化 |
| 4.1 问题分析 |
| 4.1.1 柔性列车运行图优化架构 |
| 4.1.2 问题说明 |
| 4.1.3 符号定义 |
| 4.2 模型构建 |
| 4.2.1 时空网络 |
| 4.2.2 0-1 整数规划模型 |
| 4.3 对称性分析 |
| 4.4 求解算法 |
| 4.4.1 ADMM方法 |
| 4.4.2 增广、线性化及分解 |
| 4.4.3 基于优先权的迭代策略 |
| 4.4.4 算法框架 |
| 4.5 数值算例 |
| 4.5.1 实际算例 |
| 4.5.2 比较算例 |
| 5 考虑到发线运用的柔性列车运行图优化 |
| 5.1 问题分析 |
| 5.1.1 列车运行图与到发线运用 |
| 5.1.2 问题描述 |
| 5.1.3 符号说明 |
| 5.2 扩展时空网络 |
| 5.3 0-1 整数规划模型 |
| 5.3.1 优化目标 |
| 5.3.2 约束条件 |
| 5.4 基于ADMM的求解方法 |
| 5.4.1 求解框架 |
| 5.4.2 最短路径算法 |
| 5.4.3 上界生成算法 |
| 5.5 数值算例 |
| 5.5.1 算例设置 |
| 5.5.2 计算结果 |
| 6 考虑动车组运用的柔性列车运行图优化 |
| 6.1 问题分析 |
| 6.1.1 列车运行图与动车组运用 |
| 6.1.2 问题描述 |
| 6.1.3 优化框架 |
| 6.1.4 符号说明 |
| 6.2 时空状态网络 |
| 6.2.1 网络构建过程 |
| 6.2.2 节点和弧段压缩 |
| 6.3 模型构建 |
| 6.3.1 优化目标 |
| 6.3.2 约束条件 |
| 6.4 基于ADMM的求解方法 |
| 6.4.1 分解子问题 |
| 6.4.2 带限制的多最短路径算法 |
| 6.4.3 可行化启发式算法 |
| 6.5 数值算例 |
| 6.5.1 算例设置 |
| 6.5.2 计算结果 |
| 7 结论及展望 |
| 致谢 |
| 参考文献 |
| 附录A |
| 攻读学位期间的研究成果 |
（3）高速铁路网径路搜索研究与系统研发（论文提纲范文）
| 致谢 |
| 摘要 |
| ABSTRACT |
| 1 绪论 |
| 1.1 研究背景及意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 国内外研究现状 |
| 1.2.1 国外研究现状 |
| 1.2.2 国内研究现状 |
| 1.2.3 国内外研究总结 |
| 1.3 研究内容及技术路线 |
| 2 高速铁路物理网络分析 |
| 2.1 高速铁路物理网络 |
| 2.1.1 高速铁路网 |
| 2.1.2 高速铁路枢纽 |
| 2.2 高速铁路物理网络组成要素 |
| 2.3 高速铁路物理网络模型构建与抽象 |
| 2.3.1 高速铁路物理网络模型的构建 |
| 2.3.2 高速铁路物理网络模型抽象 |
| 2.4 高速铁路物理网络模型特点分析 |
| 2.5 本章小结 |
| 3 高速铁路列车运行径路分析 |
| 3.1 高速铁路列车运行径路 |
| 3.1.1 高速铁路列车运行径路的概念 |
| 3.1.2 高速铁路列车运行径路的作用 |
| 3.1.3 高速铁路列车运行径路的影响因素 |
| 3.2 高速铁路列车运行径路可行性分析 |
| 3.2.1 区间径路可行性分析 |
| 3.2.2 站点径路可行性分析 |
| 3.3 高速铁路列车运行径路合理性分析 |
| 3.3.1 径路里程最短的径路 |
| 3.3.2 运行时间最少的径路 |
| 3.3.3 线车速度匹配的径路 |
| 3.3.4 对能力影响最小的径路 |
| 3.3.5 特定径路 |
| 3.4 本章小结 |
| 4 高速铁路物理网合理径路集求解 |
| 4.1 合理径路集 |
| 4.1.1 合理径路集的定义 |
| 4.1.2 合理径路集的求解过程 |
| 4.2 高速铁路网络径路搜索优化 |
| 4.2.1 限制搜索范围 |
| 4.2.2 分层搜索 |
| 4.2.3 分块搜索 |
| 4.3 高速铁路网络径路搜索模型求解 |
| 4.3.1 算法思路 |
| 4.3.2 算法步骤 |
| 4.4 本章小结 |
| 5 高速铁路径路管理系统开发与实证研究 |
| 5.1 系统开发关键技术 |
| 5.1.1 数据处理关键技术 |
| 5.1.2 路网图形化关键技术 |
| 5.1.3 并行计算关键技术 |
| 5.2 系统展示 |
| 5.2.1 高速铁路网基础数据编辑模块 |
| 5.2.2 高速铁路网图形化展示模块 |
| 5.3 径路搜索实证研究 |
| 5.4 本章小结 |
| 6 结论与展望 |
| 6.1 主要研究结论与创新点 |
| 6.2 有待进一步研究的问题 |
| 参考文献 |
| 作者简历及攻读硕士学位期间取得的科研成果 |
| 学位论文数据集 |
（4）资源受限的时变网络最短路径问题研究（论文提纲范文）
| 摘要 |
| abstract |
| 第一章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 经典最短路径问题 |
| 1.2.2 时变最短路径问题 |
| 1.2.3 资源受限的时变最短路径问题 |
| 1.3 本文的创新点 |
| 1.4 本文的组织结构 |
| 第二章 最短路径问题定义与算法 |
| 2.1 最短路径问题定义 |
| 2.1.1 经典最短路径问题定义 |
| 2.1.2 时变最短路径问题定义 |
| 2.2 经典最短路径问题求解算法 |
| 2.3 时变最短路径问题求解算法 |
| 2.3.1 后向标签求解算法 |
| 2.3.2 前向标签求解算法 |
| 第三章 跳数约束时变最短路径问题 |
| 3.1 跳数约束时变最短路径问题定义 |
| 3.2 跳数约束时变神经网络 |
| 3.2.1 跳数约束时变神经网络模型 |
| 3.2.2 跳数约束时变神经网络算法 |
| 3.3 HTNN算法的时间复杂度与正确性分析 |
| 3.3.1 HTNN算法时间复杂度分析 |
| 3.3.2 HTNN算法正确性分析 |
| 3.4 数值算例 |
| 3.5 实验及结果分析 |
| 第四章 代价约束时变最短路径问题 |
| 4.1 代价约束时变最短路径问题定义 |
| 4.2 代价约束时变神经网络 |
| 4.2.1 代价约束时变神经网络模型 |
| 4.2.2 代价约束时变神经网络算法 |
| 4.3 CTNN算法的时间复杂度与正确性分析 |
| 4.3.1 CTNN算法时间复杂度分析 |
| 4.3.2 CTNN算法正确性分析 |
| 4.4 数值算例 |
| 4.5 实验及结果分析 |
| 第五章 时延约束时变最短路径问题 |
| 5.1 时延约束时变最短路径问题定义 |
| 5.2 时延约束时变神经网络 |
| 5.2.1 时延约束时变神经网络模型 |
| 5.2.2 时延约束时变神经网络算法 |
| 5.3 DTNN算法的时间复杂度与正确性分析 |
| 5.3.1 DTNN算法时间复杂度分析 |
| 5.3.2 DTNN算法正确性分析 |
| 5.4 数值算例 |
| 5.5 实验及结果分析 |
| 第六章 总结与展望 |
| 6.1 总结 |
| 6.2 展望 |
| 参考文献 |
| 在学期间取得的科研成果和科研情况说明 |
| 致谢 |
（5）高速公路网巡逻车路径选择与车辆配置协同优化研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 研究背景及目的和意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究目的和意义 |
| 1.2 国内外研究现状及分析 |
| 1.2.1 国外研究现状 |
| 1.2.2 国内研究现状 |
| 1.2.3 国内外研究现状综述 |
| 1.3 研究内容与方法 |
| 1.3.1 研究内容 |
| 1.3.2 研究方法 |
| 1.4 技术路线 |
| 第2章 传统巡逻情景巡逻车路径选择及车辆配置协同优化研究 |
| 2.1 FSP系统描述 |
| 2.2 问题描述 |
| 2.3 建模思路 |
| 2.3.1 旅行商问题 |
| 2.3.2 多旅行商问题 |
| 2.3.3 问题转化 |
| 2.4 模型构建 |
| 2.5 模型求解 |
| 2.5.1 模型转化 |
| 2.5.2 改进遗传算法 |
| 2.6 案例分析 |
| 2.7 本章小结 |
| 第3章 交叠巡逻情景巡逻车路径选择及车辆配置协同优化研究 |
| 3.1 交叠巡逻情景巡逻车路径选择及车辆配置协同优化模型 |
| 3.1.1 交叠巡逻情景巡逻车路径选择及车辆配置协同优化模型构建 |
| 3.1.2 基于遗传算法对交叠巡逻情景巡逻车路径选择及车辆配置协同优化模型求解 |
| 3.2 无交叠巡逻情景巡逻车路径选择及车辆配置协同优化模型 |
| 3.2.1 无交叠巡逻情景巡逻车路径选择及车辆配置协同优化模型构建 |
| 3.2.2 无交叠巡逻情景高速公路巡逻车路径选择及车辆配置协同优化模型求解 |
| 3.3 案例分析 |
| 3.4 本章小结 |
| 第4章 多事故情景巡逻车路径选择及车辆配置协同优化研究 |
| 4.1 问题描述 |
| 4.2 模型构建过程 |
| 4.2.1 基于位置集合覆盖模型对停车待命巡逻方式建模过程 |
| 4.2.2 多事故情景巡逻车路径选择及车辆配置协同优化建模过程 |
| 4.3 模型构建 |
| 4.4 模型求解 |
| 4.4.1 模型求解过程 |
| 4.4.2 求解算法 |
| 4.5 案例分析 |
| 4.6 本章小结 |
| 第5章 吉林省高速公路巡逻车路径选择及车辆配置协同优化研究 |
| 5.1 吉林省高速公路巡逻车巡逻服务现状 |
| 5.2 高速公路路网抽象及数据准备 |
| 5.2.1 高速公路路网抽象 |
| 5.2.2 数据准备 |
| 5.3 案例分析 |
| 5.4 吉林省高速公路巡逻车巡逻服务政策建议 |
| 5.5 本章小结 |
| 结论 |
| 参考文献 |
| 附录 |
| 攻读博士学位期间发表的论文 |
| 致谢 |
| 个人简历 |
（6）时间依赖绿色选址-车辆路径问题及算法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 符号说明 |
| 第一章 绪论 |
| 1.1 研究的背景 |
| 1.2 国内外研究现状 |
| 1.2.1 选址问题 |
| 1.2.2 最短路径问题 |
| 1.2.3 时变车辆路径问题 |
| 1.2.4 LRP及绿色LRP问题 |
| 1.2.5 LRP算法 |
| 1.2.6 生物启发式算法 |
| 1.2.7 超启发算法 |
| 1.3 研究的内容 |
| 1.3.1 时间依赖网络绿色选址-路径问题模型研究 |
| 1.3.2 算法研究 |
| 1.4 研究方法及技术路线 |
| 1.4.1 研究方法 |
| 1.4.2 技术路线 |
| 1.4.3 论文章节安排 |
| 第二章 静态网络绿色选址-路径问题与算法 |
| 2.1 问题描述 |
| 2.2 静态网络车辆油耗计算 |
| 2.3 绿色选址-路径问题建模 |
| 2.4 改进型人工蜂群算法 |
| 2.4.1 人工蜂群算法 |
| 2.4.2 相关定义 |
| 2.4.3 算法改进 |
| 2.4.4 算法流程 |
| 2.5 算法性能测试 |
| 2.5.1 仿真实验环境 |
| 2.5.2 参数设置 |
| 2.5.3 改进型人工蜂群与经典选址-路径算法对比分析 |
| 2.5.4 改进型人工蜂群与粒子群算法、遗传算法对比分析 |
| 2.6 优化目标对比分析 |
| 2.6.1 GLRP与传统选址-路径优化目标对比分析 |
| 2.6.2 单纯油耗目标与选址-路径总成本目标对比分析 |
| 2.7 小结 |
| 第三章 时变网络绿色选址-路径问题与算法 |
| 3.1 时变网络描述及其特征 |
| 3.2 时变网络两节点行程时间计算 |
| 3.3 时变网络绿色选址-路径问题建模 |
| 3.3.1 时变网络选址-路径问题描述 |
| 3.3.2 时变网络车辆油耗计算 |
| 3.3.3 时变绿色选址-路径问题建模 |
| 3.4 多种群人工蜂群算法 |
| 3.4.1 多种群人工蜂群算法统一模型 |
| 3.4.2 多种群人工蜂群算法流程 |
| 3.4.3 多种群人工蜂群算法伪代码与流程图 |
| 3.5 初始种群的生成方法 |
| 3.5.1 NNC算法 |
| 3.5.2 IMTT算法步骤 |
| 3.5.3 IMTT算法流程图 |
| 3.6 实验与分析 |
| 3.6.1 测试案例与设置 |
| 3.6.2 初始种群的影响 |
| 3.6.3 对比分析 |
| 3.6.4 客户特征的影响 |
| 3.6.5 解结果 |
| 3.7 小结 |
| 第四章 随机时变路网绿色选址-路径问题与算法 |
| 4.1 随机时变路网绿色选址-路径模型 |
| 4.1.1 假设条件与约束条件 |
| 4.1.2 目标函数 |
| 4.1.3 随机时变路网行程时间的鲁棒优化 |
| 4.2 人工蜂群超启发算法设计 |
| 4.2.1 底层算子设计 |
| 4.2.2 基于人工蜂群算法的高层策略设计 |
| 4.2.3 蚁群超启发算法 |
| 4.2.4 禁忌搜索超启发算法 |
| 4.2.5 接受策略设计 |
| 4.2.6 超启发算法运算过程 |
| 4.3 随机时变路网最短路径问题 |
| 4.3.1 随机时变行程车速函数鲁棒优化 |
| 4.3.2 时变路网最短路径算法 |
| 4.4 实验数据 |
| 4.4.1 随机时变路网 |
| 4.4.2 客户生成方法 |
| 4.4.3 配送中心生成方法 |
| 4.4.4 车辆数据 |
| 4.5 求解与分析 |
| 4.5.1 小规模案例 |
| 4.5.2 9种组合超启发算法对比分析 |
| 4.5.3 人工蜂群超启发算法求解STDGLRP |
| 4.5.4 波动水平的影响 |
| 4.6 小结 |
| 第五章 多目标时变路网绿色选址-路径问题 |
| 5.1 多目标优化问题 |
| 5.1.1 多目标转单目标问题方法 |
| 5.1.2 Pareto支配机制 |
| 5.2 时变路网多目标绿色选址-路径问题 |
| 5.2.1 问题描述 |
| 5.2.2 时变路网多目标绿色选址-路径问题模型 |
| 5.3 MOTDGLRP问题的求解算法 |
| 5.3.1 多目标人工蜂群超启发算法 |
| 5.3.2 带精英策略的非支配排序遗传算法 |
| 5.3.3 基于分解框架的多目标离散人工蜂群算法 |
| 5.4 三种算法Pareto解集的对比分析 |
| 5.4.1 仿真案例与初始设置 |
| 5.4.2 三种算法得到的最优解集比较 |
| 5.4.3 三种算法收敛速率 |
| 5.4.4 ABCHH算法Pareto面进化分析 |
| 5.4.5 所有算例的结果与分析 |
| 5.5 小结 |
| 第六章 结论 |
| 6.1 总结 |
| 6.2 创新点 |
| 6.3 工作展望 |
| 参考文献 |
| 致谢 |
| 作者简介 |
| 1 作者简历 |
| 2 攻读博士/硕士学位期间发表的学术论文 |
| 3 参与的科研项目及获奖情况 |
| 学位论文数据集 |
（7）基于历史样本数据的可靠路径问题研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 研究背景及意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 国内外研究现状 |
| 1.3 论文研究内容 |
| 1.4 论文技术线路 |
| 1.5 论文章节安排 |
| 1.6 本章小结 |
| 第二章 基于历史样本数据的可靠路径模型 |
| 2.1 问题描述与模型假设 |
| 2.2 基于历史样本数据的可靠路径模型 |
| 2.2.1 基于历史样本数据的可靠路径模型 |
| 2.2.2 基于历史样本数据的可靠路径模型特性 |
| 2.3 历史样本数据类型 |
| 2.4 本章小结 |
| 第三章 基于拉格朗日松弛的可靠路径问题求解方法 |
| 3.1 问题重构 |
| 3.2 构造并简化拉格朗日松弛问题 |
| 3.3 构造拉格朗日对偶问题 |
| 3.4 求解对偶问题 |
| 3.5 负循环与对偶间隙 |
| 3.5.1 负循环 |
| 3.5.2 对偶间隙 |
| 3.6 本章小结 |
| 第四章 算例分析 |
| 4.1 单OD对的小型交通网络算例分析 |
| 4.1.1 路网属性设置及模型对比 |
| 4.1.2 运行结果分析 |
| 4.2 Sioux-Falls中型交通网络算例分析 |
| 4.2.1 路网属性设置及历史样本数据来源 |
| 4.2.2 运行结果分析 |
| 4.3 本章小结 |
| 第五章 结论与展望 |
| 5.1 主要研究成果 |
| 5.2 主要创新点 |
| 5.3 研究展望 |
| 参考文献 |
| 致谢 |
（8）基于粒子群算法的铁路枢纽铺架方案优化研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 选题的背景和意义 |
| 1.2 国内外研究现状 |
| 1.2.1 工期优化研究现状 |
| 1.2.2 铁路枢纽施工研究现状 |
| 1.2.3 铺架方案优化研究现状 |
| 1.2.4 研究现状总体评述 |
| 1.3 本文主要研究内容及技术路线 |
| 1.3.1 研究内容 |
| 1.3.2 技术路线 |
| 第2章 铁路枢纽铺架方案优化问题分析 |
| 2.1 铁路枢纽铺架工程特性 |
| 2.1.1 铁路枢纽铺架影响因素 |
| 2.1.2 枢纽铺架工程特点 |
| 2.2 铁路枢纽铺架方案优化思路 |
| 2.2.1 求解铺架顺序 |
| 2.2.2 求解转场路径和运输路径 |
| 2.3 本章小结 |
| 第3章 铁路枢纽铺架方案优化模型研究 |
| 3.1 线路网络构建的理论基础 |
| 3.1.1 图的相关概念 |
| 3.1.2 图与最短路径问题 |
| 3.2 枢纽线路网络与铺架方案优化模型的构建 |
| 3.2.1 枢纽线路抽象为有向图 |
| 3.2.2 边属性及权值的标定 |
| 3.2.3 交叉节点的转线延误问题 |
| 3.2.4 构建铁路枢纽线路网络 |
| 3.2.5 构建铁路枢纽铺架方案优化模型 |
| 3.3 本章小结 |
| 第4章 铁路枢纽铺架方案优化算法研究 |
| 4.1 组合优化算法 |
| 4.1.1 优化算法概述 |
| 4.1.2 遗传算法 |
| 4.1.3 蚁群算法 |
| 4.1.4 粒子群算法 |
| 4.1.5 组合优化算法比较及选取 |
| 4.1.6 离散粒子群算法的改进 |
| 4.2 最短路径算法 |
| 4.2.1 Dijkstra算法 |
| 4.2.2 Floyd算法 |
| 4.2.3 SPFA算法 |
| 4.2.4 A~*算法 |
| 4.2.5 最短路径算法比较及选取 |
| 4.2.6 基于弧标号的Dijkstra算法 |
| 4.3 基于改进离散粒子群—弧标号Dijkstra算法的模型求解 |
| 4.4 本章小结 |
| 第5章 案例分析 |
| 5.1 案例背景 |
| 5.2 重庆枢纽线路网络 |
| 5.2.2 重庆枢纽线路网络弧权值 |
| 5.2.3 重庆枢纽线路网络节点权值 |
| 5.3 模型求解 |
| 5.4 结果分析 |
| 5.5 本章小结 |
| 结论与展望 |
| 致谢 |
| 参考文献 |
| 攻读硕士学位期间发表的论文及科研成果 |
（9）时间—空间—状态网络中车辆最小期望费用路径选择问题研究（论文提纲范文）
| 摘要 |
| Abstract |
| 符号、略缩词注释表 |
| 第一章 绪论 |
| 1.1 研究背景及意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 国内外研究现状 |
| 1.2.1 最短路问题研究 |
| 1.2.2 车辆路径选择问题研究 |
| 1.2.3 最短路问题和VRP问题求解算法研究 |
| 1.3 研究内容与技术路线 |
| 1.3.1 研究内容 |
| 1.3.2 技术路线 |
| 1.4 研究创新点 |
| 1.5 本章小结 |
| 第二章 最小期望费用VRPPDTW问题分析 |
| 2.1 物理交通网络与时间-空间交通网络 |
| 2.1.1 物理交通网络表示 |
| 2.1.2 随机时间-空间交通网络表示 |
| 2.1.3 物理路径与时间-空间路径的映射关系 |
| 2.2 随机时间-空间-状态交通网络构建 |
| 2.2.1 VRPPDTW问题在时间-空间-状态网络中的表示 |
| 2.2.2 时间-空间-状态网络中状态的表示与转换 |
| 2.2.3 物理路径与时间-空间-状态路径的映射关系 |
| 2.3 最小期望费用VRPPDTW问题阐述 |
| 2.4 本章小结 |
| 第三章 最小期望费用VRPPDTW问题模型建立与重构 |
| 3.1 最小期望费用VRPPDTW问题模型建立 |
| 3.1.1 目标函数 |
| 3.1.2 约束条件 |
| 3.2 最小期望费用VRPPDTW问题模型重构 |
| 3.3 本章小结 |
| 第四章 最小期望费用VRPPDTW问题的求解方法 |
| 4.1 最小期望费用VRPPDTW问题模型松弛与分解 |
| 4.1.1 拉格朗日松弛基本理论 |
| 4.1.2 松弛最小期望费用VRPPDTW问题模型 |
| 4.1.3 分解最小期望费用VRPPDTW问题的松弛模型 |
| 4.2 动态规划算法求解时变单车最短路径问题 |
| 4.2.1 动态规划算法基本理论 |
| 4.2.2 动态规划算法求解单车时变最短路问题 |
| 4.3 拉格朗日算法求解最小期望费用VRPPDTW问题 |
| 4.4 本章小结 |
| 第五章 案例求解结果分析 |
| 5.1 六节点网络案例 |
| 5.2 现实网络案例 |
| 5.3 本章小结 |
| 第六章 结论与展望 |
| 6.1 结论 |
| 6.2 展望 |
| 致谢 |
| 参考文献 |
| 攻读硕士学位期间发表论文及参与科研情况 |
（10）B公司某装配车间物料配送路径优化研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 研究背景与研究意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 国内外研究现状 |
| 1.2.1 国外研究现状 |
| 1.2.2 国内研究现状 |
| 1.2.3 文献综述 |
| 1.3 本文研究方法 |
| 1.4 本文创新点 |
| 1.5 主要内容和本文结构 |
| 1.5.1 本文主要内容 |
| 1.5.2 全文研究结构 |
| 第2章 物料配送车辆路径问题概述 |
| 2.1 物流 |
| 2.2 车间物料配送 |
| 2.3 车辆路径问题概述 |
| 2.4 车辆路径问题组成要素 |
| 2.5 车辆路径问题优化目标 |
| 2.6 车辆路径问题分类 |
| 2.7 车辆路径问题求解算法 |
| 2.7.1 精确算法 |
| 2.7.2 启发式算法 |
| 2.7.3 元启发式算法 |
| 2.8 本章小结 |
| 第3章 车间网络道路约束下车辆路径优化模型建立 |
| 3.1 B公司概况 |
| 3.1.1 B公司信息简介 |
| 3.1.2 B公司装配车间物料配送流程 |
| 3.1.3 B公司B1生产线装配车间物料配送存在的问题 |
| 3.2 经典车辆路径问题数学模型 |
| 3.2.1 经典车辆路径问题建模 |
| 3.2.2 经典车辆路径问题数学模型存在的问题 |
| 3.3 基于车间网络通道约束下车辆路径问题建模 |
| 3.3.1 数学模型建立思路 |
| 3.3.2 问题描述 |
| 3.3.3 参数定义 |
| 3.3.4 模型建立 |
| 3.4 本章小结 |
| 第4章 遗传禁忌搜索混合算法设计 |
| 4.1 Flody算法 |
| 4.1.1 flody算法原理 |
| 4.1.2 flody算法内容 |
| 4.1.3 flody算法引入的作用 |
| 4.2 改进遗传算法设计 |
| 4.2.1 编码 |
| 4.2.2 种群初始化 |
| 4.2.3 适应度函数 |
| 4.2.4 选择 |
| 4.2.5 交叉 |
| 4.2.6 变异 |
| 4.2.7 终止条件判断 |
| 4.3 遗传禁忌搜索混合算法 |
| 4.4 遗传禁忌搜索混合算法流程图 |
| 4.5 本章小结 |
| 第5章 实例分析 |
| 5.1 实验数据 |
| 5.2 实验结果 |
| 5.3 优化前后方案对比 |
| 5.4 改进前后遗传算法性能对比 |
| 5.5 直线配送与考虑车间通道约束求解数据对比 |
| 5.6 本章小结 |
| 总结与展望 |
| 全文总结 |
| 工作展望 |
| 参考文献 |
| 致谢 |
| 附录A 攻读学位期间发表的学术论文目录 |
四、最短路径问题的求解（论文参考文献）
- [1]强制垃圾分类背景下城市生活垃圾回收网络规划研究[D]. 储胜. 华北电力大学(北京), 2021(01)
- [2]柔性列车运行图优化及交替方向乘子法[D]. 高如虎. 兰州交通大学, 2021(01)
- [3]高速铁路网径路搜索研究与系统研发[D]. 贺俊源. 中国铁道科学研究院, 2021(01)
- [4]资源受限的时变网络最短路径问题研究[D]. 徐志磊. 天津理工大学, 2021(08)
- [5]高速公路网巡逻车路径选择与车辆配置协同优化研究[D]. 孙秀巧. 哈尔滨工业大学, 2020(01)
- [6]时间依赖绿色选址-车辆路径问题及算法研究[D]. 张春苗. 浙江工业大学, 2020(02)
- [7]基于历史样本数据的可靠路径问题研究[D]. 刘菲. 东南大学, 2020(01)
- [8]基于粒子群算法的铁路枢纽铺架方案优化研究[D]. 邱钰峻. 西南交通大学, 2020(07)
- [9]时间—空间—状态网络中车辆最小期望费用路径选择问题研究[D]. 唐芳. 东南大学, 2020(01)
- [10]B公司某装配车间物料配送路径优化研究[D]. 袁冲. 兰州理工大学, 2020(01)