CVRP问题的启发式算法

CVRP问题的启发式算法

一、CVRP问题的一种启发式算法(论文文献综述)

饶舜[1](2021)在《基于启发式算法的带约束的车辆路径问题模型求解》文中研究表明车辆路径问题(Vehicle Routing Problem,VRP)是一种传统的组合优化问题,其广泛运用于物流、交通控制等领域。随着科技的发展以及交通、通信手段的日益丰富,该问题再度成为研究热点,焕发了新的生命力。一方面,人们不断尝试丰富各类约束条件,模拟现实中各种因素对模型的影响,使其更好的描述实际情况;另一方面,人们不断改进算法,以期能以更高的效率规划出最佳路径。车辆路径问题的求解涉及到较为复杂的组合优化,被证实为属于NP-Hard问题。随着客户数的增加,精确算法因计算量大幅增加而无法实现问题的求解。因此,由问题知识或搜索结果作为启发信息而形成的启发式算法成为求解VRP的主流方法。在此背景下,主要工作如下:一是提出了一种有效求解大规模带容量约束的车辆路径问题(Large Scale Capacitated Vehicle Routing Problem,LSCVRP)的新算法。大规模带容量约束车辆路径问题是基本车辆路径问题(Vehicle Routing Problem,VRP)在客户数上升至一定程度后形成的具有实际意义的热点问题,其难点在于如何在巨大的解空间中进行有效的搜索。本文将一种层次分解策略引入大规模带容量约束的车辆路径问题的求解,并使用变邻域搜索对解进行局部搜索,以进一步提高解的质量。为了验证所设计算法的有效性,在Golden和Li两个标准测试集上进行了计算,并和现有优秀算法进行对比。结果表明本文所设计的算法在较多算例上更新了问题的最优解,尤其在大规模测试集Li上,表现出色。二是模拟实际路况条件对基本带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem,CVRP)模型进行修改,考虑了车流量周期性变化及突发事件对路况条件的影响,提出了不确定路况条件下的CVRP问题。而后,分别在确定路况条件及不确定路况条件下规划路径,并使用修正后的VRP国际标准数据集中的十组不同规模、不同客户需求、不同最大载重约束的算例作为测试集对两种情况下规划的路径进行了测试,对其中三组算例进行了统计分析,证明了不确定路况条件下规划的路径在实际路况测试中表现更优。

汪洋广[2](2021)在《元启发式算法在带二维装箱约束的车辆路径问题中的应用研究》文中研究表明随着5G网络的进一步普及,现代物流技术使得物流配送体系更趋智能化和一体化。在这一背景下,合理的借助信息化技术,实现对现有物流体系在运营层面上进行优化和调整,将是应对日益攀升的物流服务需求的关键举措。本文运用线性规划、算法分析与设计、智能优化算法等相关理论,重点研究了在真实物流运输场景下,通过对车辆的配送路线、车厢装载率、装卸效率等方面的合理优化,实现物流企业在配送效率和经济效益上的提升。我们基于城市物流中的几种真实运输场景,提出了如下四个具有现实应用意义的车辆路径问题:首先,考虑到运输车队需要在顾客点处提供揽货服务以及运输车队中含有多车型等情况,我们提出了带有二维装箱和回程顾客约束的车辆路径问题,并同时提出了带有二维装箱、多车型和回程顾客约束的车辆路径问题;其次,在自然灾害突发时,基于顾客对应急物资的配送的真实需求,我们提出了带有二维装箱约束和最小等待时间的车辆路径问题;最后,考虑到城市物流中往往需要对不同类别的货物进行分类运输这一情况,我们提出了带有二维装箱的多隔间车辆路径问题。为了进一步求解本文所提出的四个问题,我们采用了一个统一的元启发式搜索框架。同文献中用于求解车辆路径问题的元启发式算法相比,该搜索框架在解的生成方式、解空间、个体评价方式、种群管理方式上的特点使得它在求解本文所提出的问题时更具有优势。具体而言,在该搜索框架中,约束条件的松弛配合Split算法的调用使得初始解的生成变得更为高效;独特的适应度评价方式和动态的惩罚系数可促使非可行解及时向可行解转化;非可行解种群的存在使得新个体在生成和变异时能有更大的概率向更优的方向移动。此外,本文还在前人的研究基础上,基于多种策略设计出了新的二维装箱算法,新算法能在可接受的时间范围内设计出较优的货物装载方案。最后,本文基于该搜索框架成功解决了带有二维装箱和顺程顾客约束的车辆路径问题,实验结果验证了该算法框架在求解带二维装箱约束的相关车辆路径问题时的有效性。综上,本文基于对真实的物流场景及客户需求的分析,提出了多种带有二维装箱约束的车辆路径问题,并给出了一个能高效求解此类问题的统一的元启发式搜索框架。这类实际的研究问题和能高效求解此类问题的算法的提出,对于提升城市物流系统的配送效率有着积极的应用价值和现实意义。

张云东[3](2020)在《中小学校车成本分摊方法研究》文中指出据统计,仅在2011年3月到9月的7个月之间,国内不同省市由于校车不够规范、校车司机不合规、没有配备校车监管人员等各种不规范不合理情况的发生,导致校车安全事故频频发生,因此国家立法要求中小学生采用符合安全规范校车入学。同样地,政府提倡发展公平而有质量的教育。当前在校车成本分摊问题由于没有考虑到接送点学生位置差异和接送点学生数量不同,导致由于校车不公平不合理分摊校车费用情况,使得中小学生家长存在普遍不满意的今天,研究校车的成本分摊问题可以保证校车的公平运营,提高学生家长对使用校车接送中小学生的满意度,促进校车的普及率,保障中小学生的人身安全。在国内外采用校车接送中小学生入学的100多年里,校车问题得到了各方广泛关注和大力研究。关于校车问题的研究,当前主要集中在校车路径问题(School Bus Routing Problem,SBRP)的优化,最近十几年,有部分学者对校车成本优化研究,特别地,自2019年校车的公平运营问题得到国内国外学者的关注与研究。因此本文从协作配送以及合作博弈视角,研究校车成本分摊问题,首先,对校车成本问题进行分析,明确校车成本由固定成本和变动成本构成;再利用CVRP模型,创新性地将CVRP模型目前函数改成更加适合实际的最小化校车总成本,同时利用现有算法对校车实现分区;再以TSP模型为基础,构造单辆校车的成本,采用Shapley值法分摊每辆校车成本;最后,结合实际调研数据和SBRP标准库数据,对比采用Shapley值法和按人均摊法以及人公里费用分摊法公平程度。通过本文研究发现:(1)校车成本分摊公平性主要由接送点位置以及不同接送点学生数量影响。(2)按人均摊法,没有考虑接送点位置和不同接送点学生数量对分摊方法的影响。(3)人公里费用分摊法,没有考虑接送点学生数量对分摊方法影响。(4)采用Shapley值法分摊校车成本是合理的。

杨敏[4](2020)在《带二维装箱约束的需求可分异构车辆路径问题研究》文中研究表明近年来,在经济增速放缓的影响下物流行业渐渐由增量市场转向存量市场,降本增效成为了物流企业的主要关注目标之一。与此同时,我国制造业也面临着转型升级的压力,而物流运输作为制造业供应链中的重要一环,把运筹优化技术运用其中将对提高整个供应链的效率起到重要作用。本文研究了汽车制造企业的物流部门在整车生产链路中,对上游供应商所提供的零部件进行集货运输所产生的车辆装载和运输问题。结合实际情况,将零部件的装载问题简化为二维矩形装箱问题,同时允许站点运输需求拆分,并考虑了站点车型限制及异构车队,从而提出了带二维装箱约束的需求可分异构车辆路径问题(2L-SDHFCVRP)。针对此问题,本文建立了数学模型,设计启发式优化算法,并在“2019上汽·未来汽车创想邀请赛”中取得冠军,证明了模型及算法的有效性和实用性。文章首先对二维装箱问题与车辆路径问题以及带二维装箱约束的车辆路径问题的相关研究做了文献梳理,通过对企业实际要求的合理假设与分析,构建了基于弧的数学模型。为了求解大规模真实算例,基于先路径再分割的思想,设计了基于旅行商问题解结构的变邻域搜索算法对路径进行优化,采用启发式路径装车算法对路径进行分割装车。在装箱部分,基于最大空间算法设计了背包组合和模式识别两个改进算法,并结合多种经典装箱算法构建了二维装箱算法集合。最后,通过赛事的预决赛算例测试、结果分析及与其他选手的启发式算法对比,验证了算法的效果。本文的工作对物流企业运营和学术研究均有一定意义,所提出的算法能够有效解决实际问题。

黄遥[5](2020)在《混合蛙跳算法及其在带容量约束的车辆路径问题中的应用研究》文中研究指明物流能够保证商品的流通,因此它是商品经济的动脉。车辆路径问题作为物流活动中的优化问题,更是具有深远的研究价值。群智能优化算法作为一类新兴的优化算法,虽然具有较好的寻优性能,但是面临复杂度不断升级的问题,求解性能也面临挑战。基于上述背景,本文对混合蛙跳算法及其在带容量约束的车辆路径问题中的应用进行研究,主要研究内容如下:(1)分析混合蛙跳算法的结构弊端,提出一种基于解空间跳跃和信息交互强化的混合蛙跳算法求解函数优化问题。算法在局部搜索中增加了子群次优解和次劣解的交互,强化内部信息交互;设计了反向跳跃机制,降低劣解生成概率,增强算法开发能力;对子群最优解进行变异,保证种群多样性;通过子群最优解交叉加深子群间交互,引入反向跳跃思想防止种群加速同化。选取23个不同类型的测试函数,验证策略的有效性和所提算法的性能,实验结果表明所提策略均能改善算法性能;与4种性能优越的算法对比,所提算法的整体性能优于对比算法,表现出了较好的求解精度和稳定性。(2)根据旅行商问题的特点,提出了一种基于启发信息的混合蛙跳算法求解旅行商问题。该算法设计了基于启发信息的个体生成算子,能够同时从优解和劣解中提取有效信息;采用反向轮盘赌策略,实现种群的多样性;设计了基于独立最优子群的算法框架,强化算法开发能力,平衡各子群搜索能力;变异并优化局部最优解,有助于跳出局部最优;强化局部搜索,提升求解精度和速度。共用31个标准测试实例,分别验证个体生成算子和改进策略的有效性以及所提算法的性能,实验结果表明个体生成算子和改进策略是有效的;与8种对比算法相比,本文所提算法在求解旅行商问题时具有更好的精度和稳定性。(3)分析带容量约束的车辆路径问题和旅行商问题的异同点,以上述基于启发信息的混合蛙跳算法为框架,修改了个体解码方式,将约束条件从车辆的容量转化为使用车辆的数量;设计与违反约束程度成正相关的惩罚函数,在算法迭代中淘汰不可行解;删除原有的强化局部搜索策略,在个体解码环节中,对每个车辆的路径分别进行局部搜索。采用45个不同规模的实例作为测试集,与近期具有代表性的4种算法进行对比实验,实验结果表明所提算法在带容量约束的车辆路径问题上具有更高的求解精度。

何国强[6](2020)在《物流配送车辆路径问题双种群混合遗传算法》文中研究表明相比于发达西方国家,我国物流业起步相对较晚。虽然近些年取得了长足发展,但是物流业整体运行效率偏低。据相关资料统计发现,在运输、配送、仓储、装卸搬运、流通加工和信息处理等这些物流作业活动中,配送作业成本占物流作业总成本的比例超过了50%,且一直高居不下。因此,如何进行配送线路和配送车辆的合理优化配置,实现配送作业在物流系统中的高效率、低成本运行一直是物流行业关注的重点。配送作业问题可以抽象成为容量约束的车辆路径问题,该问题是典型的NP-hard问题,也是一个组合优化问题,车辆路径问题求解的复杂程度会随着问题规模的增大呈指数级增长。对于车辆路径问题的求解方法,主要有精确算法、传统启发式算法及智能优化算法,本文采用遗传算法求解车辆路径问题。遗传算法由美国的J.H.Holland教授在1975年提出,该算法简单、易实现,具有并行、强鲁棒性等优点,是求解车辆路径这类问题的经典算法。在充分研究车辆路径特征及遗传算法优缺点后,本文设计三类改进遗传算法进行问题的求解,通过相关数据集的测试,证明了算法的有效性。主要工作如下:(1)传统遗传算法求解容量约束车辆路径时,染色体编码采用随机分割的策略,这种编码策略会产生大量的不可行解,缩小算法的搜索空间。因此,设计基于整数映射编码的遗传算法,使得每条染色体在解码后都产生可行解,保证算法解的空间在算法迭代过程始终保持多样性特征,提高算法求得最优解的概率。(2)验证可知,基于整数映射编码的遗传算法求解结果优于传统遗传算法,但该算法仍然存在早熟收敛、易陷入局部最优等问题,解严重依赖于初始化种群,特定的编码策略削弱了选择算子和交叉算子的搜索能力。因此,考虑将禁忌搜索算法的局部搜索能力同遗传算法的全局搜索能力相结合,设计遗传禁忌搜索混合算法求解容量约束车辆路径问题,通过全局搜索和局部搜索相结合的方式来提高算法搜索性能,提高算法求得最优解的概率。(3)验证可知,遗传禁忌搜索混合算法求解结果优于传统遗传算法和基于整数映射编码的遗传算法,但需要多次试算才可以得到比较满意的解,算法性能不稳定,解比较依赖于初始种群。为进一步提高算法求解稳定性及求解精度,设计了双种群混合遗传算法。种群I作为精英群体,采用扫描算法思想生产初始种群,使得种群I在迭代之初就处于一个较优状态。利用变邻域搜索策略进行局部搜索,提高算法搜索到最优解的概率。种群II作为劣势群体,进行全局开发,判断种群达到早熟收敛状态时,植入外部新个体,保证种群II的多样性。种群I和种群II通过移民算子进行种群间的协同优化,整体上提升算法稳定性和可行性。研究发现,双种群混合遗传算法在稳定性、求解精度等方面均优于传统遗传算法、基于映射编码的遗传算法及遗传禁忌搜索混合算法,这为容量约束车辆路径问题的求解提供一种新的思路。

于建芳[7](2020)在《基于演化算法的城市物流车辆路径问题的应用研究》文中认为物流产业作为现代国家经济发展的“加速器”和企业收入的“第三利润源泉”在改善发展中国家的国民经济、促进产业结构改革、提高世界国际竞争力等方面扮演着举足轻重的角色。在我国,降低1%的物流运输成本,相应地会增加4000多亿元的直接经济效益,因此提高物流管理水平,降低物流成本是目前物流工作的重中之重。而降低物流成本的关键在于缩短运输路程,所以利用有限的资源构建有效配送模型,找到配送路程最短的最佳车辆配送方案具有十分重要的现实意义。演化算法在车辆路径的优化方法中扮演着重要角色,相比传统求解方法具有求解规模大、时间短、效果好等优点。本文首先对车辆路径问题的国内外文献进行相关研究,分析VRP问题所面临的研究瓶颈;其次在VRP标准模型的基础上加入相应约束,构建CVRP和多物流公司协同配送模型,使其更加符合实际配送问题;再其次提出了基于黄金正弦的模拟退火算法,以CVRP模型验证了改进SA算法的搜索竞争优势,但同时存在一定的自身搜索缺陷,无法达到CVRP最优的搜索精度;然后提出了融合莱维飞行与黄金正弦的蚁狮优化算法,以12个标准函数验证了改进蚁狮优化算法的搜索精度优势,为模拟退火算法的优化提供研究思路;最后把新型蚁狮优化算法和经典模拟退火算法设计成新型混合优化算法LGSALO-SA,以VRP标准算例进行精度预测分析,证明了混合算法的极强搜索竞争力,并将其应用到三个物流企业协同配送的物流配送模型的实际案例中,验证了LGSALO-SA算法的可行性和优化能力。研究结果表明改进蚁狮优化算法和模拟退火的混合优化算法具有良好的搜索竞争力,也表明了物流车辆路径问题与演化算法结合求解,相比传统求解方式可以迅速规划出最佳配送路线,有效降低车辆配送里程和运输成本,对于城市物流车辆路径问题具有明显的求解优势,是降低配送成本的的有效手段。

吴俊斌[8](2020)在《电商包裹与O2O包裹联合配送的路径优化问题及算法研究》文中研究指明本文主要讨论的是电商包裹与O2O(Online To Offline)包裹联合配送的路径规划问题和算法改进。本文改进了随机最佳插入烟花算法(Randomized Best Insertion Fireworks Algorithm,RBIFWA),并使用标准数据集和天池大赛数据集来验证算法的有效性。对电商包裹与O2O包裹的联合配送的路径规划进行了分析和建模,得出了电商包裹配送的路径规划类似CVRP(Capacitated Vehicle Routing Problem)问题和O2O包裹配送的路径规划类似PDPTW问题的结论。为简化模型,结合实际生活情况对联合配送模式做出了相关假设,考虑到电商包裹的配送存在上下班时间的约束,因此为每个电商包裹配送订单也加入了时间窗约束,使得电商包裹配送的路径规划也转化为PDPTW(Pickup and Delivery Problem with Time Windows)问题。对转化后的问题进行分析和建模,得出了相关的目标函数和约束条件,为下文的算法提供改进方向。针对电商包裹与O2O包裹联合配送的路径规划模型,首先改进了随机最佳插入算法(Randomized Best Insertion,RBI)来构造初始解,不仅具有算法简单易于理解,并有效增加了解的多样性,然后改进了烟花算法(Fireworks Algorithm,FWA),重新设计了爆炸资源的分配方式、爆炸算子和变异算子,使算法能够与联合配送的路径规划模型有效结合。最后采用标准数据集TSPLIB对算法进行测试,与其他改进的亚启发式智能算法相对比,结果显示改进的RBIFWA具有更优的收敛能力,并能得到更精确的解。采用天池大赛《最后一公里极速配送》共计11270笔订单的数据作为数据集进行验证实验,首先对数据集按照配送中心的服务范围进行拆分,使问题规模缩小,然后采用改进RBIFWA对问题进行求解,结果显示改进RBIFWA算法在搜索时前期表现出较强的局部搜索能力,能够快速收敛,后期表现出一定的全局搜索能力,使得算法不易陷入局部最优解,同时改进RBIFWA算法在订单数量低于100的区域,表现出优秀的求解能力,使得每个订单的平均成本在40到50之间,随着订单量的提升,算法面临更大的解空间,搜索容易陷入局部最优解,使得每单的平均成本增加。本文改进的RBIFWA算法对电商包裹和O2O包裹联合配送的路径规划问题提供了一种解决方案。

王克[9](2020)在《电商订单与同城O2O订单共同配送路径优化》文中指出电商的迅速崛起,使得物流业的发展又迈入了一个新的高峰,目前,网购产生的物流包裹占据了中国物流运量的60%。如何更高效便捷的将快递送到消费者手中,这是物流末端配送的重要环节,目前这一环节的包裹配送模式主要分为两类,一类是快递员直接将电商包裹从网点送到客户家里,另一类则是由于互联网线下渗透产生的同城O2O包裹的配送。这两类包裹的配送是我国物流最后一公里配送的典型模式。本文的研究就是希望通过数据分析给物流最后一公里提供智能的配送方案,通过全局优化来提升配送效率及降低配送成本。电商订单配送和同城O2O订单配送相结合可以带来更大的经济效益,本文就是通过分析两者结合过程中所产生的问题,根据约束条件,构建配送模型,优化配送路径,挖掘优化算法,以期实现经济效益的最大化,主要内容如下:(1)文章起初对两种车辆路径优化模型CVRP、VRPPDTW相关理论研究做简单介绍,分析了“最后一公里”极速配送的研究现状,接着对车辆路径问题算法进行了概述,为后续的路径规划算法设计提供理论支撑。本文根据“最后一公里”配送问题的特点,以最小化配送距离为目标分别构建电商订单与同城O2O订单的配送模型。(2)以同城O2O包裹的路径规划为背景,构建带时间窗和同时取送货车辆路径规划模型。然后用双段法处理,先对配送区域用K-Means++聚类算法进行划分,接着用最小费用最大流算法(MCMF)构建网络,求解产生配送路径段,对得到的路径段动态规划合并得到同城O2O订单的配送方案。(3)以电商包裹的路径规划为背景,构建以最大载重量为约束的车辆路径规划模型。然后以最小化配送距离为目标函数,用C.W法生成初始可行解,再对其解用禁忌搜索算法处理得到电商订单的配送方案。(4)以同城O2O包裹与电商包裹共同配送的路径规划为背景,在路径段的组合上使用0/1背包合并算法,接着优化了配送O2O包裹时的等待时间。最后为验证算法的有效性和实用性,与传统启发式算法计算的共同配送结果做对比。

徐廷政[10](2019)在《应急物资配送问题建模与优化研究》文中进行了进一步梳理容量受限车辆路径问题(Capacitated Vehicle Routing Problem,CVRP)模型在交通领域有着广泛应用,以应急救灾物资配送为例,在应急救灾场景下,对物资配送的及时性有着非常高的要求,既要顾全大局,保证灾区整体物资配送的快速及时,也不能牺牲少数受灾点和灾民的利益,以某一个安置点的严重延误换取其他安置点的及时配送。这就需要审慎地进行物资配送调度,尽最大可能减少任何延误的发生,且尽量减少物资总配送时间。为了更好地实现以上目标,引入安置点紧急度属性,建立考虑紧急程度的CVRP模型,分别对紧急度确定和紧急度不确定两种情况进行研究,并设计了结合问题特性的遗传算法进行求解。第一步研究了紧急度确定性的应急救灾CVRP问题,优化目标为降低救灾物资配送的延误时间和救灾车辆的总运输时间。建立了基于紧急度的救灾物资车辆路径问题模型,并设计了一种改进遗传算法对该模型进行求解。首先,提出了一种基于紧急度的任务再分配算法作为局部搜索算子,该算子依据紧急度,为延误安置点重新安排配送车辆或调整配送顺序,从而降低延误时间。对无延误的车辆优化其路线以降低总运输时间,以达到延误时间、总运输时间两个目标最优。其次,采用多种策略生成初始种群;在17个数据集上与先来先服务(First Come First Served,FCFS)算法、按紧急度排序(Sorted by Urgency,URGS)算法,遗传算法(Genetic Algorithm,GA)三种经典算法对比,结果表明,具有基于紧急度的任务再分配策略的遗传算法(Genetic Algorithm with Task Redistribution Strategy Based on Urgency Degree,TRUD-GA)相较于GA,平均延误时间减少25.0%,平均运输时间减少1.9%,与FCFS、URGS算法相比改进更加明显。第二步研究了紧急度不确定的应急救灾CVRP问题。以总延误时间和总运输时间为优化目标,建立紧急程度不确定的应急物流规划模型,以Beta分布模拟灾区紧急度变化情况,同时进行预测。在遗传算法的局部搜索阶段设计了一种紧急度依赖的路径调整算法,根据物资需求点的紧急度不同的特性,对存在延误的配送路径进行有针对性的优化。12组数据的测试结果表明,所提模型和求解算法(Genetic Algorithm with Urgency-Dependent Path Adjustment),简记为UDGA。有效降低了延误和运输时间,与一些经典算法相比改进明显,相较于URGS算法延误时间降低89.7%,运输时间降低38.0%。UDGA算法在实验的多组算例中效果稳定,表现出良好的鲁棒性。

二、CVRP问题的一种启发式算法(论文开题报告)

(1)论文研究背景及目的

此处内容要求:

首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。

写法范例:

本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。

(2)本文研究方法

调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。

实证研究法:依据现有的科学理论和实践的需要提出设计。

定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。

定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。

跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。

模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

三、CVRP问题的一种启发式算法(论文提纲范文)

(1)基于启发式算法的带约束的车辆路径问题模型求解(论文提纲范文)

摘要
abstract
1 绪论
    1.1 车辆路径问题的研究背景及意义
    1.2 车辆路径问题的研究现状
        1.2.1 求解车辆路径问题的经典算法
        1.2.2 不同车辆路径问题的研究现状
    1.3 本文主要研究思路
2 CVRP模型与启发式算法
    2.1 标准CVRP模型
    2.2 启发式算法在求解CVRP中的应用
        2.2.1 邻域搜索算法概述
        2.2.2 遗传算法概述
    2.3 本章小结
3 一种求解大规模CVRP的启发式算法
    3.1 大规模车辆路径问题的描述与模型建立
        3.1.1 问题描述
        3.1.2 数学模型
    3.2 算法设计
        3.2.1 HD-VNS算法简介
        3.2.2 算法步骤
        3.2.3 分解策略
        3.2.4 变邻域搜索
    3.3 实验及分析
        3.3.1 实验参数
        3.3.2 实验结果及分析
    3.4 本章小结
4 不确定路况条件下的CVRP研究
    4.1 问题描述及模型建立
        4.1.1 问题描述
        4.1.2 不确定路况的描述
        4.1.3 随机路况条件下的CVRP模型
    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.2 创新点
    5.3 展望
参考文献
附录 符号表
作者简介
作者在攻读硕士学位期间获得的学术成果
致谢

(2)元启发式算法在带二维装箱约束的车辆路径问题中的应用研究(论文提纲范文)

摘要
ABSTRACT
第1章 绪论
    1.1 研究背景及意义
    1.2 研究内容及方法
    1.3 主要创新点
    1.4 论文研究框架
第2章 国内外研究现状介绍
    2.1 VRP相关问题引入
    2.2 带有装箱约束的VRP问题的研究综述
        2.2.1 带有二维装箱约束的VRP问题的研究综述
        2.2.2 带有三维装箱约束的VRP问题的研究综述
    2.3 本章小结
第3章 带二维装箱约束的车辆路径相关问题的描述及建模
    3.1 带有二维装箱和回程顾客约束的车辆路径问题
    3.2 带有二维装箱和最少等待时间的车辆路径问题
    3.3 带有二维装箱和回程顾客约束的异构车辆路径问题
    3.4 带有二维装箱的多隔间车辆路径问题
    3.5 本章小结
第4章 求解带二维装箱约束的车辆路径相关问题的统一算法框架
    4.1 最优路径的求解算法设计
        4.1.1 种群个体表示
        4.1.2 新个体的产生
        4.1.3 本地搜索
        4.1.4 种群管理机制
    4.2 二维装箱算法的设计
        4.2.1 基本装箱启发式算法
        4.2.2 “偏好”全局化策略
        4.2.3 有偏随机化策略
        4.2.4 组合策略
        4.2.5 启发式搜索策略
    4.3 本章小结
第5章 实验结果及分析
    5.1 实验设计和基准测试算例
    5.2 实验结果对比和分析
        5.2.1 VRPB实验结果与分析
        5.2.2 2L-VRPB实验结果与分析
    5.3 本章小结
第6章 总结和展望
参考文献
致谢
在读期间发表的学术论文与取得的其他研究成果

(3)中小学校车成本分摊方法研究(论文提纲范文)

摘要
abstract
变量注释表
1 绪论
    1.1 研究背景
    1.2 研究目的与意义
    1.3 国内外研究现状
    1.4 主要研究方法与技术路线
    1.5 主要研究内容
    1.6 论文创新点
2 校车成本分摊问题的理论基础
    2.1 成本分摊方法理论
    2.2 按人均摊法理论
    2.3 人公里费用分摊法理论
3 校车成本分摊问题定义和分析
    3.1 校车成本分摊问题定义
    3.2 校车成本分摊问题分析
4 校车成本分摊问题模型构建与实施
    4.1 数学符号
    4.2 模型构建
    4.3 模型实施
5 数据实验与结果分析
    5.1 青岛开发区小学实例计算展示
    5.2 SBRP标准算例库算例参数设置
    5.3 按人均摊法与Shapley值法偏差实验
    5.4 人公里费用分摊法与Shapley值法偏差实验
6 研究结论与展望
    6.1 研究结论
    6.2 研究展望
参考文献
作者简历
致谢
学位论文数据集

(4)带二维装箱约束的需求可分异构车辆路径问题研究(论文提纲范文)

摘要
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.2.3 车辆路径问题的求解算法
    2.3 总结
3 带二维装箱约束的需求可分异构车辆路径问题
    3.1 问题描述
    3.2 问题条件与假设
        3.2.1 二维装箱与载重约束
        3.2.2 需求可分
        3.2.3 异构车辆及站点车型限制
        3.2.4 总时间限制
        3.2.5 开放式
        3.2.6 成本计算
    3.3 数学模型建立
        3.3.1 模型参数
        3.3.2 2L-HFSDVRP的数学模型
    3.4 本章小结
4 算法设计
    4.1 算法主要流程框架设计
    4.2 二维装箱算法组合
        4.2.1 基于最大空间的构造启发式算法
        4.2.2 背包组合改进MS算法
        4.2.3 模式识别改进MS算法
        4.2.4 竞争装箱与Pickup装箱
        4.2.5 后优化装箱
    4.3 基于TSP解结构的变邻域搜索路径装车算法
        4.3.1 变邻域搜索算法流程框架
        4.3.2 变邻域下降过程
        4.3.3 邻域结构
        4.3.4 扰动操作
        4.3.5 路径装车算法
        4.3.6 异构车队处理
        4.3.7 终止条件
    4.4 本章小结
5 算例分析
    5.1 案例背景
    5.2 问题描述
    5.3 数据展示
    5.4 结果分析与对比
        5.4.1 赛事结果
        5.4.2 结果方案分析
        5.4.3 模式识别展示
        5.4.4 算法对比
    5.5 本章小结
6 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢
作者简历及攻读硕士学位期间的科研成果

(5)混合蛙跳算法及其在带容量约束的车辆路径问题中的应用研究(论文提纲范文)

摘要
Abstract
第一章 绪论
    1.1 选题背景与意义
    1.2 混合蛙跳算法研究现状
    1.3 旅行商问题研究现状
    1.4 带容量约束的车辆路径问题的研究现状
    1.5 本文工作内容和创新点
    1.6 本文结构安排
第二章 相关知识和理论
    2.1 优化问题和方法
        2.1.1 优化问题
        2.1.2 优化方法
    2.2 混合蛙跳算法
        2.2.1 混合蛙跳算法的基本思想
        2.2.2 混合蛙跳算法的具体实现
    2.3 本章小结
第三章 基于解空间反向跳跃和信息交互强化的混合蛙跳算法求解函数优化问题
    3.1 引言
    3.2 函数优化问题
    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 所提改进算法性能测试
    3.5 本章小结
第四章 基于启发信息的新型混合蛙跳算法求解TSP
    4.1 引言
    4.2 旅行商问题的概述
    4.3 基于启发信息求解TSP的新型混合蛙跳算法
        4.3.1 基于贪婪交叉的个体生成算子
        4.3.2 反向轮盘赌策略
        4.3.3 建立独立最优子群
        4.3.4 局部最优解变异策略
        4.3.5 增强局部搜索
        4.3.6 算法实现
    4.4 实验仿真与结果分析
        4.4.1 个体生成算子的有效性验证
        4.4.2 改进策略的有效性验证
        4.4.3 所提算法的性能验证
    4.5 本章小结
第五章 基于启发信息的混合蛙跳算法求解CVRP
    5.1 引言
    5.2 带容量约束的车辆路径问题概述
    5.3 基于启发信息求解CVRP的混合蛙跳算法
        5.3.1 编码与解码方式
        5.3.2 适应度函数
        5.3.3 强化局部搜索的改进策略
        5.3.4 算法实现
    5.4 实验仿真与结果分析
    5.5 本章小结
第六章 总结与展望
    6.1 论文总结
    6.2 工作展望
参考文献
致谢
作者简介

(6)物流配送车辆路径问题双种群混合遗传算法(论文提纲范文)

摘要
Abstract
1 研究背景及意义
    1.1 研究现状及总结
        1.1.1 国内外研究现状
        1.1.2 研究现状总结
    1.2 研究内容与组织结构
        1.2.1 研究内容
        1.2.2 组织结构
2 车辆路径问题及求解方法
    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 Metropolis抽样准则
        2.5.5 模拟退火算法过程
    2.6 禁忌搜索算法
        2.6.1 算法介绍
        2.6.2 禁忌搜索算法特点
        2.6.3 禁忌算法流程
3 两类改进遗传算法求解CVRP
    3.1 CVRP问题描述
    3.2 CVRP数学模型
    3.3 整数映射编码遗传算法
    3.4 遗传禁忌混合搜索算法
    3.5 仿真实验与分析
        3.5.1 参数设置
        3.5.2 算例求解
4 双种群混合遗传算法求解CVRP
    4.1 种群初始化
        4.1.1 种群I初始化
        4.1.2 种群II初始化
    4.2 遗传算子
        4.2.1 选择算子
        4.2.2 交叉算子
        4.2.3 变异算子
    4.3 种群I变邻域搜索
        4.3.1 抖动过程
        4.3.2 Metropolis准则
    4.4 种群II移民策略
    4.5 种群信息交换
    4.6 子路径再优化
    4.7 算法复杂度分析
5 仿真实验与分析
    5.1 参数设置
    5.2 算例求解
        5.2.1 实验1
        5.2.2 实验2
        5.2.3 实验3
        5.2.4 实验4
        5.2.5 实验5
    5.3 结果分析
6 总结与展望
    6.1 总结
    6.2 展望
致谢
参考文献

(7)基于演化算法的城市物流车辆路径问题的应用研究(论文提纲范文)

摘要
abstract
第一章 绪论
    1.1 研究背景
    1.2 研究目的及意义
    1.3 国内外相关研究综述
        1.3.1 车辆路径问题国内研究综述
        1.3.2 车辆路径问题国外研究综述
        1.3.3 文献评述
    1.4 研究内容
        1.4.1 本文的研究内容
        1.4.2 本文的结构安排
    1.5 本章小结
第二章 相关理论基础
    2.1 引言
    2.2 车辆路径问题
        2.2.1 车辆路径问题的描述
        2.2.2 车辆路径问题的分类
    2.3 车辆路径问题的求解算法
        2.3.1 传统算法
        2.3.2 经典启发式算法
        2.3.3 现代启发式算法
    2.4 本章小结
第三章 物流配送车辆路径优化数学模型
    3.1 有能力约束的车辆路径问题(CVRP)
        3.1.1 问题描述
        3.1.2 CVRP数学模型
    3.2 带取送货物车辆路径优化问题(VRPPD)
        3.2.1 问题描述
        3.2.2 VRPPD数学模型
    3.3 协同配送物流车辆路径优化问题
        3.3.1 问题描述
        3.3.2 协同配送车辆路径问题数学模型
        3.3.3 协同配送各配送中心的配送范围调整方法
    3.4 本章小结
第四章 改进模拟退火算法在CVRP车辆路径问题中的应用
    4.1 引言
    4.2 基本模拟退火算法
    4.3 基于黄金正弦的模拟退火算法(GSSA)
        4.3.1 编码与解码
        4.3.2 算法设计
        4.3.3 基于黄金正弦的模拟退火算法的流程
    4.4 改进模拟退火算法在车辆路径问题中的应用
        4.4.1 案例问题描述
        4.4.2 车辆路径问题的假设
        4.4.3 参数设置及结果分析
    4.5 本章小结
第五章 融合莱维飞行与黄金正弦的蚁狮优化算法
    5.1 引言
    5.2 基本蚁狮优化算法
    5.3 融合莱维飞行与黄金正弦的蚁狮优化算法(LGSALO)
        5.3.1 Levy变异机制
        5.3.2 黄金正弦算法
        5.3.3 融合莱维飞行与黄金正弦的蚁狮优化算法(LGSALO)
    5.4 测试仿真与结果分析
        5.4.1 测试函数
        5.4.2 参数设置
        5.4.3 结果分析
    5.5 本章小结
第六章 混合模拟退火算法在协同配送车辆路径问题中的应用
    6.1 引言
    6.2 新型混合演化算法
        6.2.1 算法设计
        6.2.2 基于黄金正弦蚁狮的模拟退火优化算法(LGSALO-SA)
    6.3 标准算例问题求解
        6.3.1 标准算例一
        6.3.2 算例仿真结果分析
        6.3.3 标准算例二
        6.3.4 算例仿真结果分析
    6.4 新型混合算法在协同配送VRP问题中的应用
        6.4.1 案例问题描述
        6.4.2 实验环境及参数设置
        6.4.3 协同配送快递物流配送车辆路径算例结果分析
    6.5 本章小结
第七章 总结与展望
    7.1 文章结论及贡献
    7.2 研究不足及展望
参考文献
攻读硕士学位期间发表的学术论文及取得的相关科研成果
致谢

(8)电商包裹与O2O包裹联合配送的路径优化问题及算法研究(论文提纲范文)

摘要
Abstract
第一章 绪论
    1.1 研究背景
    1.2 国内外研究现状
        1.2.1 VRP研究现状
        1.2.2 O2O模式物流配送研究现状
    1.3 研究意义
    1.4 研究思路及结构安排
第二章 部分相关理论
    2.1 配送模式
        2.1.1 电商配送模式
        2.1.2 O2O配送模式
        2.1.3 共享配送服务
        2.1.4 联盟模式
    2.2 车辆路径规划问题理论基础
        2.2.1 TSP问题模型
        2.2.2 VRP问题模型
        2.2.3 CVRP问题模型
        2.2.4 VRPTW模型
        2.2.5 PDPTW模型
    2.3 启发式算法
        2.3.1 传统启发式算法
        2.3.2 亚启发式算法
        2.3.3 两阶段启发式算法
    2.4 本章小结
第三章 联合配送的路径规划模型
    3.1 联合配送模式
    3.2 问题描述
    3.3 问题分析
    3.4 配送模型
    3.5 本章小结
第四章 随机最佳插入烟花算法
    4.1 基于插入的启发式算法
        4.1.1 贪心插入法
        4.1.2 改进的随机最佳插入法
    4.2 改进型烟花算法
        4.2.1 适应度评估函数
        4.2.2 爆炸资源分配
        4.2.3 爆炸算子
        4.2.4 变异算子
        4.2.5 选择策略
        4.2.6 算法过程描述
    4.3 算法实践及分析
    4.4 本章小结
第五章 改进算法验证及分析
    5.1 算例描述
    5.2 数据预处理
    5.3 求解步骤
    5.4 实验结果及分析
        5.4.1 总成本进化分析
        5.4.2 各地区平均成本比较分析
        5.4.3 配送员数量进化分析
        5.4.4 总体分析
    5.5 本章小结
第六章 总结与展望
致谢
参考文献
附录(攻读学位期间发表论文与专利)

(9)电商订单与同城O2O订单共同配送路径优化(论文提纲范文)

致谢
摘要
Abstract
1 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
        1.2.1 VRP问题研究及分类
        1.2.2 CVRP问题研究综述
        1.2.3 VRPPDTW问题研究综述
        1.2.4 “最后一公里”配送研究综述
    1.3 研究内容与技术路线图
    1.4 研究目标和创新
2 相关理论研究及算法概述
    2.1 节约法概述
    2.2 禁忌搜索算法概述
    2.3 最小费用最大流算法概述
    2.4 K-Means++聚类算法
    2.5 本章小结
3 同城O2O包裹的最后一公里配送路径优化
    3.1 同城O2O包裹配送模型
        3.1.1 问题描述
        3.1.2 数学模型
    3.2 算法设计
        3.2.1 数据集简介
        3.2.2 K-Means++划分同城O2O订单的配送区域
        3.2.3 同城O2O订单的费用流
        3.2.4 同城O2O订单的动态规划合并
    3.3 结果分析
    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.4 本章小结
5 电商包裹与同城O2O包裹共同配送路径优化
    5.1 电商订单与O2O订单的背包合并
    5.2 等待时间的优化
    5.3 结果分析
    5.4 本章小结
6 总结与展望
    6.1 总结
    6.2 展望
参考文献
个人简历

(10)应急物资配送问题建模与优化研究(论文提纲范文)

摘要
abstract
第一章 绪论
    1.1 车辆路径问题的研究背景及意义
    1.2 车辆路径问题的国内外研究现状
        1.2.1 救灾车辆路径问题研究现状
        1.2.2 求解车辆路径问题的启发式算法
    1.3 论文所做工作及结构介绍
第二章 VRP模型和遗传算法
    2.1 基本CVRP问题模型
        2.1.1 问题描述和模型约束
        2.1.2 数学模型
    2.2 扩展CVRP问题研究内容
    2.3 遗传算法在VRP中的应用
        2.3.1 遗传算法概述
        2.3.2 遗传算法求解VRP的一般流程
    2.4 本章小结
第三章 考虑紧急度的应急CVRP问题
    3.1 考虑紧急程度的CVRP模型
        3.1.1 问题描述
        3.1.2 模型设计与约定
        3.1.3 参数与变量
        3.1.4 数学模型
    3.2 基于紧急度的遗传算法设计
        3.2.1 染色体编码
        3.2.2 初始化种群
        3.2.3 适应度函数
        3.2.4 选择
        3.2.5 染色体交叉
        3.2.6 局部搜索算子TRUD
    3.3 实验结果及分析
        3.3.1 算例描述与实验设置
        3.3.2 结果分析
    3.4 本章小结
第四章 紧急度不确定的应急CVRP模型
    4.1 紧急程度变化的CVRP模型
        4.1.1 问题描述
        4.1.2 基于Beta分布的紧急度变化模型
        4.1.3 紧急度不确定救灾CVRP模型约束
        4.1.4 数学模型
    4.2 紧急度依赖的路径调整算法(UDPA)
    4.3 实验结果分析
        4.3.1 算例描述与实验设置
        4.3.2 实验结果及对比
        4.3.3 相关性分析探索延误时间与安置点数的关系
    4.4 本章小结
第五章 总结与展望
    5.1 研究总结
    5.2 展望
致谢
符号表
参考文献
附录:读研期间科研情况

四、CVRP问题的一种启发式算法(论文参考文献)

  • [1]基于启发式算法的带约束的车辆路径问题模型求解[D]. 饶舜. 安庆师范大学, 2021(12)
  • [2]元启发式算法在带二维装箱约束的车辆路径问题中的应用研究[D]. 汪洋广. 中国科学技术大学, 2021(09)
  • [3]中小学校车成本分摊方法研究[D]. 张云东. 山东科技大学, 2020(06)
  • [4]带二维装箱约束的需求可分异构车辆路径问题研究[D]. 杨敏. 大连海事大学, 2020(01)
  • [5]混合蛙跳算法及其在带容量约束的车辆路径问题中的应用研究[D]. 黄遥. 南京信息工程大学, 2020(02)
  • [6]物流配送车辆路径问题双种群混合遗传算法[D]. 何国强. 兰州交通大学, 2020(01)
  • [7]基于演化算法的城市物流车辆路径问题的应用研究[D]. 于建芳. 上海工程技术大学, 2020(05)
  • [8]电商包裹与O2O包裹联合配送的路径优化问题及算法研究[D]. 吴俊斌. 昆明理工大学, 2020(04)
  • [9]电商订单与同城O2O订单共同配送路径优化[D]. 王克. 杭州师范大学, 2020(04)
  • [10]应急物资配送问题建模与优化研究[D]. 徐廷政. 安庆师范大学, 2019(01)

标签:;  ;  ;  ;  ;  

CVRP问题的启发式算法
下载Doc文档

猜你喜欢