基于遗传算法的相交圆弧逼近轮廓曲线的节点计算

在数控机床上对非圆轮廓曲线进行加工时,按等步长进行节点计算编写出的加工程序通常段数多,给程序的输入与调试带来困难,直接影响机床的使用效率.将遗传算法应用于用加工中心进行非圆轮廓曲线加工时的节点计算优化中,根据等拟合误差和插补圆弧段最长的原则,利用遗传算法自适应迭代寻优的概率搜索,获得全局最优解来进行节点计算,并用一个算例证明了该算法的可行性.     

结合概率搜索定界的入度统计最短路径算法

Dijkstra 经典最短路径算法包括大量的排序运算,且需要对图中所有顶点进行计算,效率较低.本文针对有向网络,提出了与概率搜索定界结合的入度统计最短路径算法.该算法通过按概率搜索得到一条较短路径,依据路径长度和有向网络结构特征确定和顶点序号相关的节点阻抗最大值;采用入度统计算法代替经典的标号算法,在计算过程中根据节点阻抗最大值,采取一定方式剔除无效顶点(不在最短路径内的顶点),简化网络结构.本文提出的算法不需要进行排序运算,简化了运算过程,并且可以剔除大量的无效顶点,降低了网络复杂度.算例分析表明,相对于Dijkstra算法,结合概率搜索定界的入度统计算法大幅度提高了运算效率,具有实用性.     

求解最短路问题的改进禁忌搜索算法

最短路问题(Short-Path Problem)以其广泛的应用场景一直是热点问题,目前已有Dijkstra等基本算法可以求得问题的最优解,但当网络节点较多时,表现出耗时较长、求解困难等问题。禁忌搜索算法是基于邻域搜索的智能优化算法,适合解决大型组合优化问题。在给出基于顶点优先权最短路径问题的基础上,建立数学优化模型,并设计禁忌搜索算法的步骤和算法关键技术,最后以顶点数为30的网络验证该算法的有效性。结果表明:该算法能求得本算例的最优解且计算时间比Dijkstra短。     

第Ⅰ类双边装配线平衡问题的改进蚁群算法

为克服传统算法求解大规模双边装配线平衡问题计算时间长、性能不稳定的缺陷,针对第Ⅰ类双边装配线平衡问题,应用综合信息素搜索规则与全局信息素更新规则,提出了一种先产生任务排列序列、后按启发式分配规则产生可行解的蚁群算法,可有效脱离陷入局部最优解.用改进蚁群算法对30个不同规模的问题进行求解,并与标准蚁群算法和禁忌搜索算法进行了对比.结果表明:改进蚁群算法求出29个最优解,比普通蚁群算法、禁忌搜索算法分别能多求得6个和3个最优解;应用于汽车双边装配线算例,在保持平衡效率的条件下,改进蚁群算法计算时间为21.01 s,比普通蚁群算法减少了9.14 s,计算效率提高了30.3%.      

基于和声搜索算法的公交线路规划方法研究

我国城市交通拥堵日益严重,公共交通越发重要。数据量较大时,传统的最短路径算法已无法满足计算要求。针对公交线路规划中服务人数最大问题、行程时间最短问题,通过引入智能和声搜索(HS)算法,分别结合约束条件和算例场景进行计算筛选,得出两种目标问题下的最优路径解。结果表明,和声算法收敛性良好,计算过程迅速准确。     

求解双目标带时间窗车辆路径问题的蚁群算法

针对运输网络为多重图的双目标带时间窗车辆路径问题设计了蚁群算法.首先,建立了多重图的双目标带时间窗车辆路径问题的数学模型,提出了针对该问题解的搜索空间构建方法,定义了一种综合考虑各优化目标、时间窗和信息素等启发信息的状态转移概率公式. 为了对比说明该算法的有效性,同时设计基于NSGA-II的多目标遗传算法.针对本文算例,对蚁群算法中的各参数进行了敏感性分析,根据分析结果设定算法参数,获得了算例的Pareto最优路径集,同时与NSGA-II算法及相关文献算法针对运行时间、收敛性和群体多样性进行比较.结果显示,本文设计的蚁群算法在这3个指标上均明显优于NSGA-II算法;在相同蚂蚁数量情况下,本文的算法在收敛性和群体多样性方面优于相关文献算法.     

基于混合修正策略的随机时间车辆路径优化方法

针对带有随机旅行时间、随机服务时间及时间窗约束的车辆路径问题,建立了带修正策略的随机规划模型,并给出了两阶段求解方法.第一阶段运用改进遗传算法获取先验路径,第二阶段采用两种混合修正策略(分别记为A、B)调整"失败"的先验路径.混合修正策略A(B)通过随机模拟实验判断对当前顾客的延迟服务(对下一顾客的服务)是否会对该路径后续顾客造成大规模延迟服务,并采取相应的调整措施.基于Solomon算例进行了仿真实验,对小规模算例将仿真结果同CPLEX求解结果作对比;对大规模算例将仿真结果同已知最优解作对比.结果 表明:所给算法可获得小规模算例的精确解,大规模算例的近似最优解.同时,对比不同策略下的仿真结果表明两种混合修正策略具有优越性,研究结果对随机车辆路径问题的求解具有一定的参考意义.     

带中转设施的垃圾收集VRP的改进蚁群算法

为减少城市垃圾的收运成本和各车辆路径之间的重叠区域,设计了一种具有聚类策略、改进全局信息素更新规则和交叉算子的多重蚁群算法.用该算法求解2个标准算例,一个达到目前已知的最优解,另一个偏离度为2.13%.此外,还对含有不同规则的蚁群算法进行了比较.结果表明:与不带聚类策略的蚁群算法相比,该算法求解的路径最佳,其长度缩短4.90%,紧凑度降低83.33%;不同转移更新规则的贡献程度从大到小依次是:带块可见度的聚类策略、全局信息素更新规则和交叉算子.     

带回程取货的逆向物流车辆路径建模及其蚁群算法

对逆向物流车辆路径问题进行了概述和分类,构建了以VRPPDTW为基础的带回程取货的逆向物流车辆路径数学模型,设计了求解该模型的最大-最小蚁群算法,对设计要素进行了详细介绍,包括初始蚁群分布,状态转移策略,以及信息素更新策略等,并给出了具体的算法步骤. 最后,以Solomon中的R101、R102、R103、R104和R105等5项示例为背景,分别取前25节点和50节点,以取货点的取货量比例分别占全部客户节点需求量的10％、30％、50％取货,得到30个算例的计算结果,并将其与Tangian和模拟退火等计算结果进行了比较,结果表明最大-最小蚁群算法在某种程度上优于其他算法     

双重不确定下应急物资多式联运可靠路径优化

为按时、可靠地将应急物资运达目的地，综合考虑需求和运输环境的双重不确定性、节点疫情感染风险、成本约束、班期限制和转运能力限制等，构建以可靠度最大为目标的应急物资多式联运可靠路径优化模型。同时针对所求问题的NP-难特点，设计蒙特卡洛自适应遗传算法和模拟退火遗传算法进行求解，并引入优劣解距离法对算例的运行结果进行分析。研究结果表明：蒙特卡洛自适应遗传算法较模拟退火遗传算法在求解质量和求解时间方面更优，在交叉概率为0.80，变异概率为0.08，种群大小为50的最佳参数组合下，得到的优化路径最大可靠度为85%，且求解出来的最优路线均未经过存在疫情感染风险的节点，求解结果较好。参数分析表明：在交叉概率相同的条件下，两种算法的平均运行时间均随着变异概率的降低而减少，随着变异概率的增加而增加；多式联运路径优化的决策会受水铁班期的影响。     

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

为优化真实路网下的车辆配送路径,采用优化 + 调整的两阶段求解方法. 在优化阶段,根据常发拥堵信息,采用遗传算法求解时变取送一体化车辆路径,安排车辆初始配送路径. 在调整阶段,以路段行驶时间为时间间隔,采用滚动更新策略调整车辆配送路线躲避偶发拥堵. 在针对车辆路径调整问题构建了一系列混合整数规划模型的基础上,设计了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倍.      

带软时间窗车辆路径问题及禁忌搜索算法

考虑不同容量和运输成本的多车型车辆,建立容量限制和软时间约束,并以最小化车辆在路段上的运输量和该路段的长度乘积为目标的数学模型,给出求解该问题的禁忌搜索算法。在算法中考虑使用车辆最少的插入算法生成初始解。最后,通过仿真算例,检验模型和算法的有效性。     

基于可信性测度的模糊车辆路径问题

车辆路径问题(VRP)主要用来寻找有效路径。车辆的起始点都是位于交通中心的仓库,通过车队运输来满足客户对商品的需求。文中介绍不确定条件下的车辆路径问题,即客户的服务时间窗是模糊的。设计一个基于可信性测度的模糊车辆路径模型,并通过模糊模拟和遗传算法的混合智能算法进行求解。最后,结合一个实例说明该模型的应用性和可行性。     

带时间窗的甩挂运输路径优化问题研究

针对带时间窗的甩挂运输路径优化问题,考虑整车和卡车2种运输方式,以及整车、卡车、混合3种行驶路径,以行驶时间为目标函数构建模型,设计基于A、B策略的两阶段混合启发式算法.算例分析结果表明：针对客户规模在100以内的小规模算例,均可在3s内求得结果,策略B的求解时间少于策略A,而策略A的目标函数优于策略B;当客户规模逐步增至900时,选择策略A可获得更高的求解效率.可见,本文所构建的模型与算法是可行和有效的,对实际配送过程中的车辆指派与路径优化具有一定的参考价值.     

客户配送要求变动下的VRPSDP干扰管理优化

为解决客户配送要求变动对VRPSDP方案造成的干扰问题，从成本和服务时间两个方面，就干扰事件对原物流配送车辆路径方案造成的影响进行了干扰辨识分析.构建了VRPSDP干扰管理模型，并设计基于禁忌搜索的调度算法.从Solomon标准测试算例中随机抽取6组算例对模型和算法的有效性进行验证.结果显示，本文的干扰管理方案与传统的增派车辆和全局重调度方案相比较，广义总费用偏离有明显地降低，且本文方法能够在较短的时间内生成满意的物流配送车辆调度调整方案.     

快递配送车辆路径优化研究

考虑到快递配送和物流配送的异同,在物流配送路径优化问题的基础上构建了符合快递配送路径优化问题的数学模型.设计了一种采用自然数编码,综合考虑快件数量、车辆载重、车辆容量等约束的解码方式的遗传算法.通过一个拥有20个配送点的快递配送案例,验证本文所构建模型和算法能够得到合理配送路径和各个配送点的服务时刻.最后通过灵敏度分析和四轮厢式货车算例验证表明:当前情况下,研究快递配送路径优化时,快件数量、快递员最长配送时间和各配送点的作业时间必须考虑;当前快递配送车辆的载重和容量满足当前需求,无需更换载重和容量更大的配送车辆.     

一种基于时空距离的带时间窗车辆路径问题算法

带时间窗的车辆路径问题是典型的NP难题,一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法. 传统算法在顾客分组时主要考虑顾客的空间位置关系,但是忽略了顾客对服务时间窗口的要求. 本文同时考虑顾客的时间和空间特性,提出了一种基于时空度量的顾客分组方法. 在路径优化阶段,本文提出了一种禁忌搜索算法来进行求解,该算法中禁忌的对象不是解,而是这些解的目标函数值的区间,以便于提高收敛效率. 作为验证,本文以Solomon标杆问题集为算例进行演算,结果表明,在窄时间窗约束下,基于时空距离的两阶段启发式算法明显优于基于空间距离的算法,且部分算例的解达到了国内外已发表的最好解.     

Research on the Best Routing Algorithm of Terminal Distribution Based on the Random Factor of Road Hustling Degree

Dijkstra algorithm is a basic algorithm to analyze the vehicle routing problem (VRP) in the terminal distribution of logistics center. According to the actual client demands of service speed and quality, the conceptions of economical distance of delivery and the best routing algorithm were given on the base of the Dijkstra algorithm with consideration of a coefficient of the road hustle degree. Economical distance of delivery is the shortest physical distance between two customers. It is the value of goods delivery in shortest distance when concerning factors such as the road length, the hustle degree, the driveway quantity, and the type of the road. The improved algorithm is being used in the development and application of a distribution path information system in the terminal distribution of logistics center. The simulation and practical case prove that the algorithm is effective and reasonable.     

基于VRP模型的两阶段物流网络路径优化模型

以基于VRP模型的两阶段三层次物流网络路径优化问题为研究对象,利用启发式算法中的分解法将问题分为选择物流中心与配送路径优化两个子问题,并与数理规划软件LINGO 8.0相结合给出了基于VRP模型的MSDL-RP问题——多供应商、多配送中心选址与路径优化问题的求解模型。利用所提出的模型可以求出商品从多供应商经过多物流中心到最终客户这一过程中能使费用最小的供应商的最佳位置与数量、物流中心的最佳位置与数量及从物流中心到客户的最佳配送路径,并通过实例进行了验证。对于小规模问题,运用所提出的方法能在很短的时间内求出问题的最优解,具有一定的实用价值。     

时间依赖型绿色车辆路径问题研究

城市配送系统中考虑交通拥堵和环境污染车辆路径问题的时间依赖性体现在：不同道路 拥堵程度下车辆运行速度不同,则不同出发时间对应的运输总时间也不同,导致运输成本和造成 的环境污染也有较大差异。因此,本文提出一个时间依赖型绿色车辆路径模型,通过优化运输路 径和出发时间降低运输成本、减少环境污染。模型的目标函数最小化包括油耗成本在内的运输 总成本,其中,车辆油耗的度量基于综合模式排放模型,其创新之处在于,定义了允许车辆在节点 处等待的情形,使车辆选择合适的时间出发以规避拥堵,即通过优化车辆路径以及路径上各节点 处的出发时间寻求成本最优的运输方案。本文提出嵌套遗传算法求解模型,外层遗传算法优化 路径,内层遗传算法优化路径上各节点处的车辆出发时间。并通过响应面分析法(RSM)调试算法 关键参数,得到适用于模型的最佳参数搭配,算法性能测试结果表明了本文算法的高效性。本文 基于污染-路径问题实验数据库进行数值实验,结果证明,允许车辆在客户处等待并选择合适时 间出发,可以在一定程度上降低燃油消耗和总成本。此外,目标函数中引入油耗要素,可以有效 降低决策方案的燃油消耗,减少环境污染。