һ�ද̬����·������ģ�ͺ����׶��㷨

针对一类动态车辆路径问题,分析4种主要类型动态信息对传统车辆路径问题的本质影响,将动态车辆路径问题(Dynamic Vehicle Routing Problem, DVRP)转化为多个静态的多车型开放式车辆路径问题(The Fleet Size and Mixed Open Vehicle Routing Problem, FSMOVRP),并进一步转化为多个带能力约束车辆路径问题(Capacitated Vehicle Routing Problem, CVRP),基于CVRP模型建立了DVRP模型;然后,在分析DVRP问题特点基础上,提出两阶段算法,第一阶段基于利用K-d trees对配送区域进行分割的策略,提出了复杂度仅为O(nlogn)的快速构建型算法,第二阶段通过分析算法搜索解空间结构原理,设计混合局部搜索算法;最后,基于现有12个大规模CVRP标准算例,设计并求解36个DVRP算例。求解结果表明了模型和两阶段算法的有效性。     

车辆路径问题的形式化及其知识表示方法研究

针对目前车辆路径问题(Vehicle Routing Problem,VRP)求解方法缺乏动态自适应能力这一缺陷,从面向问题的角度出发,研究车辆路径问题的形式化和知识表示。通过深入分析车辆路径问题及其特点,提出了基于知识的车辆路径问题的形式化方法及车辆路径问题的树状知识表示方法,并以此为基础,实现了车辆路径问题的知识表示支持系统,为模型自动生成和问题求解创造条件。     

考虑碳排放的两阶段选址-路径问题及其算法

为减少物流车辆的碳排放，基于以排放因子为主要参数的碳排放计算方法，建立以碳排放最小化为目标的两阶段选址-路线问题（2E-LRP）模型，并设计了一种可用于快速求解大规模问题的两阶段混合算法（TSHA）.算法第一阶段将2E-LRP转化成不考虑车辆路径的两阶段设施选址问题，调用Cplex直接求解得到配送中心选址和客户分配方案；在此基础上，算法第二阶段中，物流园区到被选用的配送中心以及配送中心到所分配客户的车辆路径问题被进一步转化成若干个独立的VRP (vehicle routing problem)问题，再运用改进的蚁群算法进行求解；最后，对Prodhon标准算例集中全部6个最大规模的算例进行测试.研究结果表明：与TSHA具有相同算法思想的TSHA-Ⅱ算法能够在求解质量下降2.3%的情况下将计算时长大大缩短至25 s左右；TSHA算法在求解考虑碳排放的2E-LRP算例时表现非常稳定，可以作为一种求解考虑碳排放2E-LRP的有效算法.     

城市轨道交通网络单程票卡调配模型

城市轨道交通单程票卡调配是票务组织中的重要组成部分.针对路网票务中心与线路票务中心间票卡调配问题,将其转化为载重能力约束条件下的车辆路径优化问题(Vehicle Routing Problem,VRP),构建以配送成本最小化为目标,以配送车辆路径为决策变量的优化模型,并采用遗传算法求解.以北京市轨道交通网络为对象进行实证分析,结果显示:所构建方法相比单次配送过程,成本平均降低约49.6%;相比既有装卸混合条件下的配送过程,成本降低约18.7%,验证了模型的准确性与有效性.所构建方法能够有效解决轨道交通路网层票卡调配问题,为票务组织提供理论和方法支持.     

时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。     

时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。     

应急车辆动态路径选择的两阶段优化模型

为研究突发事件情境下交通路网动态变化时的应急车辆路径选择问题，提出应急车辆动态路径选择的两阶段调度优化模型。通过结合路网动态状况和应急救援特征，建立基于最大路径可靠度和最短行程时间的两阶段优化模型；通过混沌搜索改进布谷鸟算法初始种群，并加入蛙跳算法改进局部搜索操作，设计混合布谷鸟算法，改善全局寻优能力；以某市某区部分区域路网为例，将该区域路网实时交通数据应用于模型和求解算法中。实验表明，利用两阶段优化模型和算法编码方案能成功获得出发点到救援点的动态可靠路径，相同行驶路径情况下模型与算法求解的最短行程时间与实地驾车获得的最短行程时间最大误差不超过8%，说明优化模型可行。3 种不同算法求解K最短路径的结果发现，混合布谷鸟算法得到的最短行程时间比粒子群算法和 经典布谷鸟算法得到的结果都要小，且计算时间最短，表明混合布谷鸟算法求解的结果最优，性能最好。     

����������·�Ż��ĸĽ��Ŵ��㷨�о�

物流配送线路优化问题，即车辆路线问题(VRP，Vehicle Routing Problem)是组合优化领域中的著名NP(Nonlinear Programming)难题。本文以VRP为基础，建立该问题的数学模型，设计了改进的遗传算法，通过大量计算机计算分析验证，此改进算法对VRP有良好的近似解和较高的收敛速度。     

时变条件下城市物流配送车辆路径优化

针对城市交通网络依时周期性变化的特点,建立了城市物流配送车辆路径优化问题的数学模型,并利用两阶段算法对该问题进行求解,第一阶段采用插入法,求解出初始路径;第二阶段通过减少路径数和邻域搜索改进初始配送路径。最后,给出一个应用算例,结果证明了模型和算法的有效性。     

定位-路径问题综述

研究了定位-路径问题(LRP), 总结了国内外LRP模型及其扩展模型, 比较了LRP模型求解算法的适用性, 分析了LRP测试算例的节点分布和数据规模, 提出了LRP研究的主要方向。研究结果表明: LRP模型从基于基础网络的最简化问题(带容量约束的LRP, CLRP) 向多方向模型进行扩展, 包括基于网络复杂化的LRP扩展, 如特定网络系统的多目标LRP (MOLRP)、同时取送货LRP (LRPSPD)、接驳转运中心LRP (CDCLRP)、两阶段LRP (2E-LRP)、选址-弧路径问题(LARP)、卡车和拖车路径问题(TTRP) 与设施地点为二维连续的LRP (PLRP), 基础网络参数不确定化的LRP, 包括带模糊数据的LRP与多计划周期LRP (MPLRP), 且正在向更切合实际的问题如高度集成、不确定与动态LRP发展; LRP算法方面, 精确算法仅可用于求解小规模LRP, 主要LRP求解算法由早期的智能算法逐渐转向元启发式算法、基于邻域搜索优化的算法与混合算法方向发展, 这些改进算法均基于特定LRP设计, 具有更好的求解性能, 尤其是采用基于多种破坏和修复因子的自适应大邻域搜索算法求解大规模LRP取得了较好的解, 且其改造性极强; 常用LRP测试算例的节点呈现均匀分布、堆分布及均匀与堆混合分布, 且逐渐产生了适用于2E-LRP与LRPSPD等扩展LRP的测试算例; 根据物流市场环境变化和需求, 提出LRP未来扩展研究的主要方向, 包括多阶段LRP的扩展(如2E-LRPSPD、考虑库存的2E-LRP等)、节点二维连续的LRP、客户含优先级的带竞争或盈利LRP、混合不确定LRP等切合实际的问题; 提出了LRP求解算法未来方向, 包括设计新型精确算法求解中、大规模LRP, 设计更准确更高效的组合启发式算法与应用近似算法求解LRP及扩展LRP的最优解。      

A Hybrid TCNN Optimization Approach for the Capacity Vehicle Routing Problem

Introduction The vehicle routing problem(VRP)is one ofthe well-known NP-hard optimization problems[1]occurring in many transport logistics and distribu-tion systems of considerable economic significance.The capacity vehicle routing problem(CVRP)likeVRP with the additional constraint that every vehi-cle must have a capacity,so it is also an NP-hardoptimization problems.It involves minimizing costvehicle schedules for a fleet of vehicles originatingand terminating from a central depot.The …     

全局搜索聚类的多车场多车型调度算法研究

针对物流配送中多车场多车型车辆调度问题的特征构造了一种以最短路径为代价的车辆调度的双多模型.为解决此类NP问题,本文提出了一种两阶段解决方案：第一阶段首先对全局隶属值的搜索训练找出最优隶属度,然后再利用任务相对紧急数组以K-Means算法为基础对用户进行聚类,把一个多车场多车型的车辆调度问题转化成多个单车场多车型的调度问题,大大降低了问题求解的复杂度;第二阶段对多个单车场多车型VSP问题利用遗传算法进行并行处理,为了保证染色体的多样性和尽可能地降低问题求解复杂度,提出了五类遗传交叉算子;最后对4车场32用户实例进行试验.结果表明,此算法对求解多车场多车型车辆调度问题很有效.     

An Effective Hybrid Optimization Algorithm for Capacitated Vehicle Routing Problem

IntroductionVehicle routing problem(VRP)is a well-known combinatorial optimization problem and isalso a focal problem of distribution managementwithin the area of service operations managementand logistics.Capacitated vehicle routing problem(CVRP)is a very hard vehicle routing problem.The problem is to simultaneously determine theroutes for several vehicles from a central depot to aset of customers,and then return to the depotwithout exceeding the capacity constraints of eachvehicle.In prac…     

动态行驶时间取送一体化车辆路径问题

为优化真实路网下的车辆配送路径,采用优化 + 调整的两阶段求解方法. 在优化阶段,根据常发拥堵信息,采用遗传算法求解时变取送一体化车辆路径,安排车辆初始配送路径. 在调整阶段,以路段行驶时间为时间间隔,采用滚动更新策略调整车辆配送路线躲避偶发拥堵. 在针对车辆路径调整问题构建了一系列混合整数规划模型的基础上,设计了2-opt + insertion启发式算法求解模型,并结合Dijkstra算法求解到的客户点间最短行驶路线,将车辆配送路径转化成了真实路网中的车辆配送路线. 数值实验测试结果表明:滚动更新策略中,以路段行驶时间为时间间隔比以客户间行驶时间为时间间隔减少车辆行驶时间0.24～11.95 min;以路段行驶时间为时间间隔比以24 min为时间间隔减少车辆行驶时间0.08～8.06 min,比以6 min为时间间隔减少更新次数10.02～34.59次,因此,固定时间滚动更新策略中的最优时间间隔难以确定,其实用性较差. 2-opt + insertion启发式算法求解速度是遗传算法的4倍.      

随机时变车辆路径问题的多目标鲁棒优化方法

车辆路径问题 （vehicle routing problem,VRP） 是物流配送的核心问题之一,为了提高物流配送的时效性,在传统VRP模型的基础上,同时考虑了路网交通状态的时变性和随机性,基于最小最大准则,提出了一种带硬时间窗的随机时变车辆路径问题 （stochastic time-dependent vehicle routing problem,STDVRP） 的多目标鲁棒优化模型. 设计了一种非支配排序蚁群算法 （non-dominated sorting ant colony optimisation,NSACO）,求解STDVRP多目标优化模型;通过测试算例,对比分析了NSACO算法与改进型非支配排序遗传算法 （non-dominated sorting genetic algorithm II,NSGA-II）. 研究结果表明:对于车辆数最小的Pareto边界解,NSACO算法的平均车辆数比NSGA-II算法小3.33%;对于最坏行程时间最小的Pareto边界解,NSACO算法的平均最坏行程时间比NSGA-II算法小17.49%.      

混合超启发式法求解大规模VRP的优化研究

车辆路径是一类NP(non-deteministic polynomial)完全问题,研究解决车辆路径问题的高质量启发式算法有着重要理论价值和现实意义.提出一种将最近邻搜索法和禁忌搜索法优势相结合的混合超启发式算法,用来解决带容量约束的车辆路径问题.先利用最近邻搜索法构建初步路线,再利用禁忌搜索法对内部线路和互跨线路进...     

随机行驶时间车辆路径问题的模型与算法

车辆路径问题是现有物流管理系统中非常重要的一个方面,许多专家学者对此进行了深入研究.到目前为止,所有这些研究都是针对确定环境下的车辆路径问题或不确定车辆路径问题中具有模糊或随机需求的问题,尚未发现有对随机行驶时间的多类型车辆路径问题进行研究.针对随机信息条件下的多类型车辆路径问题进行了分析,运用不确定规划理论建立了该问题的优化模型,并利用遗传算法对问题进行求解.通过实验证明,该模型及算法对于多类型车辆路径问题具有一定的实用价值.     

考虑随机需求和时间约束LIRP联合协同优化

针对多节点多层次多功能的供应链管理中整体效益亟待提高的问题，结合某连锁超市的单一供应商、多分销中心、多零售店所构成二级分销网络，建立以系统总成本和供货时间为目标的多目标选址-库存-路径问题（location-inventory-routing?problem，LIRP）集成规划模型. 利用线性加权法将其转化为单目标规划模型，提出遗传算法和节约里程法相结合的两阶段启发式算法并求解模型，第1阶段用遗传算法求解选址-库存问题，第2阶段用节约里程算法求解车辆路径规划问题. 并结合某连锁超市实例，对不同总成本权重下的不同决策方案的分销网络进行LIRP集成优化，优化后的系统方案比原文献的总里程减少了3 606.9 km，系统总成本减小了6 526.2 元，缺货成本降低了124.6 元，只有19.7元，验证了模型和算法的有效性.