面向复杂物流配送场景的车辆路径规划多任务辅助进化算法

在现代社会中,复杂物流配送场景的车辆路径规划问题(Vehicle routing problem,VRP)一般带有时间窗约束且需要提供同时取送货的服务.这种复杂物流配送场景的车辆路径规划问题是NP-难问题.当其规模逐渐增大时,一般的数学规划方法难以求解,通常使用启发式方法在限定时间内求得较优解.然而,传统的启发式方法从原大规模问题直接开始搜索,无法利用先前相关的优化知识,导致收敛速度较慢.因此,提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm,MBEA),通过使用迁移优化方法加快算法收敛速度,其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题.首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务,然后使用进化多任务(Evolutional multitasking,EMT)方法用于生成原大规模问题和优化子任务的候选解.由于优化子任务相对简单且与原大规模问题相似,其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题,从而加快其求解速度.最后,提出的算法在京东物流公司快递取送货数据集上进行验证,其路径规划效果优于当前最新提出的路径规划算法.

改进蚁群算法的送餐机器人路径规划

蚁群算法拥有良好的全局性、自组织性、鲁棒性,但传统蚁群算法存在许多不足之处。为此,针对算法在路径规划问题中的缺陷,在传统蚁群算法的状态转移公式中,引入目标点距离因素和引导素,加快算法收敛性和改善局部最优缺陷。在带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)上,融合蚁群算法和遗传算法,并将顾客时间窗宽度以及机器人等待时间加入蚁群算法状态转移公式中,以及将蚁群算法的解作为遗传算法的初始种群,提高遗传算法的初始解质量,然后进行编码,设置违反时间窗约束和载重量的惩罚函数和适应度函数,在传统遗传算法的交叉、变异操作后加入了破坏-修复基因的操作来优化每一代新解的质量,在Solomon Benchmark算例上进行仿真,对比算法改进前后的最优解,验证算法可行性。最后在餐厅送餐问题中把带有障碍物的仿真环境路径规划问题和VRPTW问题结合,使用改进后的算法解决餐厅环境下送餐机器人对顾客服务配送问题。

时间窗约束下农产品物流配送路径优化研究

农产品需求量增加对物流配送提出较高挑战,基于此提出时间窗约束下农产品物流配送路径优化方法研究。依客户预期服务时间需求,取混合时间窗约束函数确定时间窗、物流配送车辆最大载重、配送路径长度与物流配送车辆约束条件,构建农产品物流配送路径优化模型;基于农产品物流配送需求改进传统遗传算法,求解构建模型,即获农产品物流配送路径优化结果。实验结果显示:相较生鲜农产品多车型冷链物流车辆路径优化,所提方法最优农产品物流配送路径获取迭代次数更少、配送路径长度更短、总成本更低,应用性能更佳。

基于紧致子序列的航班着陆调度问题研究

航班着陆调度问题已被证明是NP难问题,综合考虑多种实际情况,建立了时间窗约束的航班着陆优化模型,定义了紧致子序列概念,论述了其性质及左移、分割和合并的条件。在此基础上,提出一种基于紧致子序列的算法(CSA)求解固定顺序下航班着陆调度问题。按照航班的最优着陆时间排序,运用CSA计算出该顺序下各航班着陆时间;采用循环线性交换和循环线性插空策略微调该固定顺序,不断迭代逼近模型的最优解;采用OR-Library数据集进行验证。实验结果表明,CSA结合启发式微调策略求解结果明显优于位移决策算法DALP和仿生算法(BA),与CPLEX、混合粒子群优化-局部搜索算法RH-HPSO-LS、细胞自动机优化(CAO)算法相近,在时间效率上明显优于对比算法;在小规模数据集上,计算精度与速度优势更加明显。CSA是一种确定性算法,不依赖于先验参数,具有更高的鲁棒性,保证了启发式微调策略不断逼近最优解。

基于电子商务竞标结构的分布式作战资源调度

针对现代战争作战任务规划问题,提出一种基于电子商务多轮竞标结构的作战资源调度方法,以异步、分散的方式让多个供应商协调来自多个消费者的任务资源请求。每个任务关联一个时间窗口,有些任务需要不同类的多个资源同步服务。招标由消费者发起,供应商对各资源请求发起投标,消费者根据投标结果中任务的3种状态,采取不同策略,并向供应商发送中标信息以执行任务或启动下一轮竞标。建立供应商和消费者调度问题数学模型,针对供应商资源调度非确定性多项式(nondeterministic polynomial,NP)完全问题特点,提出基于改进节约算法和自适应大邻域搜索算法的两阶段启发式求解方法;消费者模型使用混合整数线性规划来选择成本最低的投标组合,以满足任务需求。算例分析验证了所提方法的有效性。

突发事件下的空地联运协同调度问题综述

突发性灾害事件背景下,充分发挥地面和航空运输领域各自的优势,建立空地联运协同调度应急救援体系,可以提升应急救援工作的质量和效率。对空地联运协同调度问题的研究现状进行系统梳理,探讨与协同调度相关的优化目标、物资分配、时间窗约束以及求解算法等关键问题,并展望空地联运协同调度研究趋势,对应急调度的研究具有重要意义。

基于LNS-NSGA2的多目标冷链运输优化

针对冷链物流配送系统配送成本较高以及车辆有效利用率低的问题,构建以运输成本最小化和用户满意度最大化为目标的多车型冷链物流路径优化模型,同时考虑配送时间窗和生鲜商品新鲜度对用户满意度的影响,不再对不满足时间窗配送的生鲜商品增加额外成本。以带精英策略的非支配排序遗传算法(Elitist Non-dominated Sorting Genetic Algorithm,NSGA2)为基础,设计聚类初始化种群方法,针对路径编码特点设计有序交叉方法;设计一种修复策略修改约束条件导致的不可行解,引导其在约束边缘搜索;结合大规模邻域搜索(Large Neighborhood Search,LNS)算法思想,引导个体在邻域搜索,增加局部搜索能力,丰富种群多样性。仿真实验结果表明,本文算法在多目标多车型路径优化问题中,得到的Pareto前沿明显优于传统的NSGA2算法。

带服务时间窗的绿色多式联运路径和速度多目标优化

在货物运输中,除考虑传统的成本目标外,最小化其对环境的影响具有重要的意义。本文研究了一类新的带服务时间窗的绿色公海多式联运多目标优化问题,旨在多式联运网络中决策货物运输路径和速度以满足货物运输需求,目的是同时最小化货物运输总成本和碳排放总量,并建立该问题的多目标混合整数非线性规划模型。为有效求解该问题,将上述非线性模型转化为线性模型,并提出了一种基于ε-约束法和模糊逻辑相结合的算法。最后以我国典型的绿色多式联运问题为例对模型和算法的有效性进行验证。计算结果表明,所提出的模型和算法能够有效求解所提出的带服务时间窗的绿色多式联运多目标优化问题,为决策者在进行绿色多式联运的路径和速度决策时提供参考。

时间窗约束下的无人集群分布式任务分配算法

综合考虑任务时间窗以及无人机能力约束,以任务的平均时间成本最小为优化目标,提出一种无人集群分布式协同任务分配算法。首先,定义任务对于无人机的增益和边际增益,用以描述无人机执行任务的时间成本的变化情况。然后,建立包括任务添加、冲突消解和任务再分配三个阶段的分布式分配算法。最后,仿真实验结果表明:第三个阶段将任务完全分配率提高了13.76%,相比现有算法,所提算法将任务完全分配率提高了21.94%,任务平均完成时间降低了24.25 s。

考虑时空特征的机器人VRP问题求解方法

针对多台变电站巡检机器人在同时调度分配过程中的转移运用车辆路径问题(Vehicle Routing Problem,VRP),提出了基于时空特征的机器人群体路径规划算法,有助于提高机器人在电力生产中的应用效能。首先建立基于变电站位置的纵横坐标构建平面二维坐标的宏观路网;其次梳理变电站之间的距离、机器人的能耗等约束条件,并构建考虑变电站巡检时间窗的时空三维坐标系;最后遍历搜索各台机器人完成区域内变电站巡检任务的可选路径,并在组合优化后提出解决机器人转移运用VRP问题的调配方案。实际应用效果表明,该方法能够在满足变电站多时间窗边界的基础上得到最优路径。

基于CNDLS的空中多编组时限约束任务分配方法

针对空中多编组任务分配具有整体任务完成时间限制和个体任务完成时窗限制的特点,以最高任务执行效率为目标,建立了包含时限约束的多编组任务分配数学模型。分析编组在作战过程中的资源损耗,构建了编组资源能力动态更新模型,使所建模型更为符合实际作战。在动态列表规划选择任务、量子遗传算法分配编组的基础上,设计了用于求解该模型的循环嵌套动态列表规划(CNDLS)的任务分配方法。针对作战想定进行仿真计算,仿真结果表明所建模型和所提方法能通过多次迭代可实现一定资源和时限约束下的最佳多编组任务分配。

随机时间依赖路网中危险品运输路径多准则优化

为实现动态路网中的危险品运输路径优化,以期为运输商的路径选择提供决策支持,分析了运输网络的随机时间依赖(STD)特征,对分段连续时间区间内各路段的行程时间和受影响人数进行曲线拟合.考虑到达时间窗的约束,以行程时间和运输风险的随机属性值为优化准则,建立0-1整数规划模型.结合STD网络的FIFO性质设计了两阶段多维标号修正算法,得到不同出发时刻以给定置信水平满足时间窗约束的非支配路径集合,并提出准则权重和阈值支配方法,实现计算效率和求解质量的均衡.研究结果表明:危险品在STD路网中的行程时间和运输风险与到达时间窗的设置和出发时刻的选取有关;生成的非支配路径取决于出发时刻和运输商的选择偏好,非支配路径的数量取决于支配阈值的大小;不同类型运输商可根据准时到达置信水平来选择出发时刻与运输路径的最优组合.

基于吱呀轮优化的多卫星数传调度问题求解方法

研究多卫星数传调度技术对提高对地观测系统的综合应用效益具有重要意义。通过分析卫星数传调度问题,建立一种考虑时间窗调整的约束优化模型。利用吱呀轮优化(Squeaky-Wheel Optimization,SWO)的大邻域导向式搜索特点,提出了一种基于SWO的多卫星数传调度算法。该算法可以在短时间内获得优化解。实验结果表明,该算法在时间性、优化度等方面取得满意的结果。

一种复杂项目调度问题的混合智能算法

针对有资源约束的项目调度问题模型的不足,调研了企业需求,提出了带有预约时间窗口约束的项目调度模型,并针对该类模型的特点分析了原有算法存在的问题,将分枝定界算法与启发式算法相结合,提出了一种解决该类问题的混合智能算法。仿真结果表明,该算法的优化效果明显优于其他算法。

基于自适应多态蚁群算法的多约束车辆路径问题

建立了在有客户优先级、路况影响、多车型、时间窗和容量等多约束条件下车辆路径问题(VRPMC)的数学模型.由于该模型是一个NP-hard问题,目前还没有多项式算法求解,又提出了采用自适应的多态蚁群算法(APACA)来对其进行求解的策略.首先,算法中侦察蚁完成满足约束条件的路径侦察并设置侦察信息素;其次,搜索蚁利用侦察蚁提供的辅助信息进一步搜索可行路径,通过多态蚂蚁间的协作和自适应调整挥发系数,能更快地搜索到问题的优化解;最后通过一个实例与节约算法、遗传算法、禁忌搜索算法和基本蚁群算法进行了对比,结果表明:对VR-PMC问题,APACA算法比前述算法在算法稳定性、运行距离、计算速度方面更具有优势.

带时间窗约束的船体分段空间调度问题

研究了将空间资源作为关键资源的生产调度问题——空间调度问题,分析了空间调度问题和三维装箱问题的异同,以具有时间窗约束的空间调度三维模型为基础,提出改进的基于极点的启发式定位规则,给出结合禁忌搜索和基于极点的定位规则的优化算法,并通过仿真验证了算法的有效性。

军用飞机智能起降调度技术研究

为了削弱军用飞机实际起降时刻与计划起降时刻之间的偏差对作战带来的不利影响,探讨了智能化的军机起降调度方法。分析了军机起降过程中的时间窗口约束和尾流间隔约束,建立了军机起降调度的数学模型。设计了针对模型解的混合编码策略,并针对自然数编码部分提出了一种离散粒子群算法进行更新。通过仿真实验确定了算法的最大迭代次数,并通过与其他调度算法的对比分析,说明了模型和算法的有效性。

弱硬实时系统任意窗口约束调度研究

弱硬实时应用中的QoS在过载情况下会不同程度地退化.本文针对因仅考虑无限区间或者某一固定有限区间上的任务丢失率而导致重度过载情况下服务不公平的情况,基于可变区间,提出(p,k)约束,给出任意窗口约束调度(Any Window Constraint Schedule,AWCS)算法及其简化算法K窗口约束调度(-KWindow Constraint Schedule,KWCS),实验表明KWCS与AWCS的性能相当,且开销大幅降低.通过分析算法特性,给出具有QoS保证的时延上界通用表示方法.实验结果表明在重度过载情况下,AWCS(KWCS)优于其它弱硬实时算法.

时间窗限制下泊位分配问题的约束规划模型

针对集装箱港口中船舶服务及作业时间在时间窗约束下的泊位分配问题,考虑船舶载重不同而产生的优先级,并把这种优先级反映到在港时间上,分别以最小化卸船完工时间为目标建立了约束规划模型和混合整数规划模型.研究结果表明:约束规划技术在求解时收敛速度快.通过数据试验证实了约束规划在港口调度如泊位分配问题中的可行性和有效性.

一种带时间窗和容量约束的车辆路线问题及其TabuSearch算法

本文提出一种带时间窗和容量约束的车辆路线问题 (CVRPTW ) ,并利用TabuSearch快速启式算法 ,针对Solomon提出的几个标准问题 ,快捷地得到了优良的数值结果。