带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法

为了同时实现总配送成本最低、车辆数最少和车辆行驶距离最短等目标,考虑车辆指派成本及运输路径成本的相对重要性,建立了带时间窗装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种混合离散粒子群求解算法。算法基于客户排列的直观无分段大路径解表示法,采用改进深度优先搜索分割法对问题解进行解码与评价;嵌入一种变邻域下降搜索程序并在个体粒子每次迭代时以一定概率选择执行,利用混合粒子群算法在多邻域深度搜索和在全局空间广度搜索进行寻优,同时应用模拟退火思想和比例选择性变异最差个体来改善个体搜索停滞现象。采用两个不同目标算例进行寻优测试,验证了所提算法的可行性和有效性。

求解VRPSDP的变邻域混合遗传算法

针对卸装一体化车辆路径问题,提出一种结合变邻域下降搜索和遗传算法的混合启发式算法(GA_VND).利用随机生成的初始种群,通过遗传算法的交叉变异操作生成弱可行解种群,选择其中的最优值作为变邻域深度搜索的初始解.在变邻域深度搜索的过程中通过两种不同的局部搜索算子对解进行局部搜索和迭代优化.通过对54个算例的求解,仿真结果表明GA_VND更新了54个已知最好解中的8个,表明了该算法是解决卸装一体化车辆路径问题的一种有效方法.

求解卸装一体化的车辆路径问题的混合启发式算法

提出一种结合蚁群系统（Ant Colony System,ACS）和变邻域下降搜索（Variable Neighborhood Descent,VND）的混合启发式算法ACS_VND,求解卸装一体化车辆路径问题.利用基于插入的ACS解构造方法产生多个弱可行解,再逐个转换成强可行解,并选择其中最好的作为VND的初始解.在VND过程中使用三种不同的邻域结构：插入、交换和2-opt依次对解进行迭代优化.对55个规模为22~199的benchmark算例的求解结果表明,算法ACS_VND能在较短时间内获得52个算例的已知最好解,并且更新了其中44个算例的已知最好解,求解性能优于现有算法.

独立任务分配的贪婪随机自适应搜索过程

提出了一种贪婪随机自适应搜索过程求解异构环境下的独立任务分配问题。使用随机化的最小最小完成时间算法来产生问题的初始解,再通过变邻域下降算法来改进这个解,在变邻域下降算法中,为增强算法的空间勘探能力,外层局部搜索采用允许接收劣质解的策略,使用禁忌表来防止迂回搜索,使算法在多样性和集中性间取得了较好的平衡。与领域中的典型算法进行了仿真比较,结果表明提出的算法具有良好的性能。

两级车辆路径问题的多起始点变邻域下降算法

两级车辆路径问题是指货物必须首先由中心仓库配送至中转站(第一级),再转运至需求点(第二级)的一种新型车辆路径问题.针对该问题特性,提出一种多起始点变邻域下降求解算法.首先由改进的Split算法循环分割由所有需求点组成的随机排列,直至出现可行的第二级配送方案,然后求解第一级问题,获得完整的初始可行解,再通过变邻域下降算法进一步改进.当变邻域下降算法无法改进时,采用多起始点技术重复上述过程,直至算法终止.实验结果表明,所提出的算法易于实现,且性能优于已有最好的两种启发式算法.

开放式两级车辆路径问题建模与多起始点变邻域下降法求解

针对城市物流中普遍存在的物资开放式两级配送情形,构建了开放式两级车辆路径问题的数学模型,它要求物资必须先由远程的中心仓库配送至转运中心(第一级),再由转运中心配送至客户点(第二级),两级车辆在完成各自的配送任务后,均不必返回出发点,若要返回,则必须按照原路返回。为有效求解该NP难问题,设计了一种多起始点变邻域下降算法。扩展算例的测试结果表明,所设计的算法注重求解质量与求解效率的平衡,可有效求解提出的开放式两级车辆路径问题。

软硬时间窗共存装卸一体化车辆路径问题的混合离散粒子群优化算法

文章针对软硬时间窗共存装卸一体化车辆路径问题(vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows,VRPSDPCSHTW)建立了包含车辆固定出行成本、运输成本和惩罚成本的数学模型,提出了一种混合离散粒子群优化算法。针对基本离散粒子群算法容易早熟收敛而陷入局部最优等问题,内嵌一种变邻域下降局域搜索方法,并在一定概率下执行以加强种群搜索能力,最后通过3个算例的仿真分析进行了算法验证。

异构环境独立任务分配的导引式局部搜索算法

针对异构环境下的独立任务分配问题,结合变邻域下降算法,提出了一种导引式局部搜索算法.该算法通过不断动态修改原问题的目标函数和系统性地改变邻域结构,既保留了局部搜索算法的高效率,又能有效地避免陷入局部极小解,因而能够较快地得到满意解.与领域中的典型算法进行了仿真比较,结果表明提出的算法具有良好的性能.

一种求解带时间窗车辆路径问题的混合差分进化算法

对带时间窗的车辆路径问题进行研究,建立以最小化车辆数量和行驶路程为目标的多目标数学模型,提出一种结合改进差分进化算法和变邻域下降搜索的基于Pareto支配的混合差分进化算法。首先重新定义了个体的生成方式。其次,结合双种群策略和变邻域下降搜索技术来平衡算法的全局探索能力和局部开发能力,并在搜索过程中用随机个体替代种群中的重复个体,维持种群的多样性。然后引入Pareto支配的概念来评价个体的优劣性,并采用擂台法则构造非支配解集。最后对18个不同规模的Solomon算例的求解结果表明,算法在行驶路程和车辆数量上的求解质量比人工蜂群算法分别平均提高了2.04%和14.95%,且与已知最优解相比,在车辆数量的求解质量上平均提高了14.53%,验证了所提算法的有效性。

电力巡检中的无人机群路径规划算法

随着无人机技术的飞速发展,无人机被广泛用于各种领域的巡检任务.近年来,电力网络的规模和长度都在快速增长,无人机因其独特的性能和优势成为了电力巡检的首选,无人机巡检不仅能保证安全性,还能有效地提高巡检效率,而路径规划是其在实际应用中的关键一步.本文提出了一种新的混合元启发式方法,用于解决电力巡检中带有多个站点的无人机群路径规划问题.该算法在自适应大邻域搜索的框架下添加变邻域下降为下属策略,加强邻域搜索能力,增加找到更优解的可能.实验结果表明,本文提出的算法能够有效地解决该问题,并且具有较好的稳定性和鲁棒性.另外,通过实验对比了本算法和其他元启发式算法,验证了本算法能有效地减少巡检中使用的无人机数量和时间成本.

一种求解多校多车型校车路径问题的元启发算法

针对多种车型可用的多校校车路径问题(SBRP),建立数学模型,并提出了一种迭代局部搜索(ILS)元启发算法进行求解。该算法引入并改进了带时间窗的装卸一体化问题(PDPTW)求解中的点对邻域算子,并使用可变邻域下降搜索(VND)完成局部提升。局部提升过程中,设计一种基于路径段的车型调整策略,尽可能地调整车型,降低成本,并允许接受一定偏差范围内的邻域解以保证搜索的多样性。对于局部提升得到的最好解,使用多点移动方法对其进行扰动,以避免算法过早陷入局部最优。在国际基准测试案例上分别测试多校混载和不混载模式下算法的性能,实验结果验证了设计算法的有效性。进一步使用提出的算法求解单车型多校SBRP问题,并与后启发算法、模拟退火算法和记录更新法等算法进行比较,实验结果表明该算法仍然能够获得较好的优化效果。

混合启发式算法在汽车调度中的应用

将蚁群优化和变邻域下降搜索VND相结合,形成一种混合启发式算法ACS_VND,应用于客运公司的汽车调度,求解车辆需求数和最佳路径。该算法充分利用了2种不同算法的优点。实验结果表明,算法ACS_VND能在较短时间内获得比单个算法更好的车辆调度路径。

带机器人制造单元的作业车间调度仿真

针对带有机器人制造单元的作业车间调度优化问题,在若干加工机器上可以加工具有特定加工工序的若干工件,并且搬运机器人可以将工件在装卸载站与各加工机器间进行搬运.在实际生产过程中,由于不确定性,特别是带有存货的加工单元,要求工件的完工时间在一个时间窗内,而不是一个特定的时间点.因此针对此情况的作业车间,考虑到其在求解问题过程中的复杂性和约束性等特点,研究了在时间窗约束下,目标值为最小化工件完成时间提前量和延迟量的总权重.提出了一种将文化基因算法与邻域搜索技术(变邻域下降搜索)相结合的改进元启发式算法,在求得最优目标值的同时,可得到最优值的工件加工序列及机器人搬运序列.通过实验结果表明,所提出的算法有效且优于传统文化基因算法与遗传算法.

混合粒子群算法求解带软时间窗的VRPSPD问题

针对带软时间窗的同时集配货车辆路径问题(VRPSPD),建立了以车辆派遣成本、行驶成本和时间窗惩罚成本之和最小为目标的车辆路径优化模型;设计混合粒子群算法进行求解,该算法结合以变邻域下降搜索为主体的适应性扰动机制,采用适应性选择邻域策略,并在每个邻域搜索中应用可变的循环次数,以此提高对解空间的探测能力和搜索效率。数值实验结果表明了该算法的可行性和有效性。

基于随机森林与变邻域下降的车辆合乘求解

为了最大化用户满意度,长期车辆合乘问题(LTCPP)被建模为多目标优化问题。然后,根据历史合乘数据以及用户满意度信息,使用随机森林算法计算每个指标对用户满意度的重要性影响,并作为对应优化目标的权重,以避免人为设定权重因子对优化结果的影响。提出了一种求解LTCPP的变邻域下降(VND)算法,通过顺序地在多个邻域内搜索得到问题的最优解。实验结果表明,结合随机森林和VND算法能为LTCPP提供高质量的解决方案,且具有很高的时间效率。

基于改进遗传算法的多车场生鲜配送优化

针对生鲜产品易腐烂特性与对配送及时性的高要求,构建以制冷成本、燃油成本、损耗成本、时间惩罚成本、产品固定运输成本和车辆固定成本的总成本最小函数,并考虑顾客的位置、车辆载重及时间窗约束,建立多车场生鲜配送模型,使用K-means聚类对算例中的客户群进行车场划分后,采用变邻域下降搜索策略和模拟退火算法对遗传算法进行改进,利用改进后的遗传算法计算得出优化后的车辆配送路线。通过对改进后的遗传算法与传统的自适应遗传算法对比后,结果表明各项成本都有不同程度的减少,且总成本减少了14.6%,从而验证改进后算法的优势,达到减少配送成本、满足配送及时性和提升顾客满意度的目的。

基于变邻域下降的列车运行时刻调整算法

高速铁路区间失效可能严重影响列车正常运行,区间失效后调度员需要及时调整列车运行时刻.本文主要针对区间失效后不改变列车顺序下的时刻调整问题进行研究,建立了以所有列车在各站晚点时间之和为目标的列车运行调整模型,模型中各约束条件保证列车安全运行.针对目前常见的获取最优解或次优解需花费较长时间的问题,提出一种基于变邻域下降算法的多阶段变邻域下降算法.算法的第一、第二阶段使用变邻域下降算法结合禁忌表快速确定哪些列车经过调整后的时刻能与图定时刻相等,第三阶段则调整未恢复到图定时刻的列车.最后,以西成客运专线与某日的列车时刻数据为算例,求解多种区间失效场景下的列车运行时刻调整方案验证算法的有效性与实时性.

在线动态订单需求车辆路径规划

针对客户满意度和时间窗时域单一的问题,提出一种多时域分级方式衡量车辆配送进度,该设计细化普通时间窗时域,分成多个时域衡量车辆行进位置,算法方面,遗传算法(genetic algorithm,GA)与变邻域下降搜索算法(variable neighborhood descent,VND)的组合优化形式得到静态预优化路径最优车辆行进线路。动态调度周期中,现有贪婪订单插入算法(greedy order insertion algorithm,GOIA)搜索效率不高,提出一种改进后的贪婪订单插入算法(improved new greedy insertion algorithm,IGOIA),摒弃了GOIA随机插入路径的方式,最有原则的将订单插入到配送路径中去,将其与变邻域下降搜索算法组合优化(Genetic algorithm-Variable Neighborhood Descent,GAVND),对未服务的客户点进行局部优化。通过数学模型优化和求解算法改进,在统一平台上与IGOIA-GAVND、GOIA-GAVND与GOIA-GA2-opt的遗传算法改进形式进行对比试验,改进后的动态订单插入算法在不同规模的Solomon算例下,平均目标值降低了11%,算法平均计算时间降低了2.74 s,实例分析中,成本解分别节约了23%、31%、21%,研究结果证明了原则订单插入算法在滚动周期策略作用下可以获得较高质量的解。

基于迭代变邻域下降算法求解TTRP问题

为了求解卡车带挂车的车辆路径问题(truck and trailer routing problem, TTRP),提出迭代变邻域下降算法(iterated variable neighborhood descent, IVND).该算法首先使用T-cluster算法求得一个初始可行解.然后,设计了基于多邻域算子的变邻域下降搜索算法.在搜索过程中,借鉴"粒邻域"的思想定义了"受限邻域",同时设计了基于switch-vehicle-type算子的扰动策略.最后,选取国际上通用的Chao测试数据集(21个50~199个顾客规模的标准测试算例)对算法性能进行测试.通过与文献中其它4种算法比较,实验结果表明,提出的IVND算法可以在最短的计算时间内收敛到满意解,并且IVND算法结构简单、计算效率高、易实现,可以被灵活地扩展解决其它车辆路径问题和组合优化问题.

应急物流中的累计时间式多车场车辆路径问题

为提升应急救援的快速性和公平性,以最小化所有受灾点的累计等待时间为目标建立累计时间式多车场车辆路径问题(Cum-MDVRP)的模型.由于该问题具有NP-hard性质,设计了一种多起始点变邻域下降法对其进行快速求解.每次迭代中,多起始点方法通过改进的Split算法结合可行性修复程序生成随机的初始可行解,然后由变邻域下降法对其进一步改进.扩展的标准算例的测试结果验证了所提出模型和求解算法的有效性.