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

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

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

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

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

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

客户分级优先的即时配送路径规划方法

为了使即时配送企业能以较低的成本提高配送准时性,从而维护并发展高价值客户,首先,针对即时配送客户的特点改进RFM模型,基于已有数据使用DBSCAN算法进行客户聚类,根据聚类结果使用GBDT算法构建客户分级预测模型对即时配送客户进行分级预测。在此基础上,以即时配送的固定成本、变动成本及客户超时点种类、数量为优化目标,构建基于客户分级优先的即时配送路径优化模型,再设计遗传算法对该模型进行求解。最后,以沈阳市某一站式冷链即时配送企业为对象进行实例分析。结果显示,相比该企业原配送方案,应用客户分级优先的即时配送路径规划方法规划后的方案在配送总成本仅提高4.8%的情况下,高价值、潜在高价值客户超时点数量由6减少为2,且超时点均为边缘客户,同时配送总时间减少了7.3%,验证了该方法的有效性。采用该配送路径规划方法,企业的配送成本虽然会小幅增加,但因配送准时性提升,可以更好地维护高价值客户,同时发展潜在高价值客户向高价值客户转变,进而保持或提高长期收益。

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

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

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

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

频繁时序模式挖掘方法综述

频繁时序模式挖掘是指从时间序列数据中发现频繁出现的模式或规律的过程,其目的是可以帮助理解时间序列数据中的重要特征,例如周期性、趋势和异常等,有助于预测未来的发展趋势和识别异常情况等。根据近年来的频繁时序模式挖掘方法的相关文献调研,按照关键技术和代表性算法将其分为三类,即基于结构约束的频繁时序模式挖掘方法、基于参数约束的频繁时序模式挖掘方法和基于窗口的频繁时序模式挖掘方法。陈述了频繁时序模式挖掘方法的背景以及各方法的特点;分别介绍了三类挖掘方法的发展以及分类,并从优缺点和性能等方面对各类改进方法进行了详细的对比分析;对频繁时序模式挖掘方法进行归纳和总结,并对频繁时序模式挖掘方法的未来研究方向进行了展望。

一种限界优化方法求解航班着陆调度问题

航空运输需求持续增长与枢纽终端区空域资源紧张的情况日益凸显,本文提出了一种限界优化的动态规划方法(Dynamic programming approach to limit optimization,DPALO)求解终端区航班着陆调度问题(Arrived landing problem,ALP)。首先建立了时间窗约束的航班着陆调度的离散化数学模型,推导了固定顺序下求解ALP的递推公式,并结合ALP问题特点,限界优化航班时间窗,并证明了所提方法不影响模型最优值的求解。其次,运用精英遗传算法、粒子群算法、线性循环交换和线性循环插空等方法调整航班序列,以期求得较优解。最后在OR‑Library数据集进行验证,实验结果表明,采用精英遗传算法调整航班着陆序列,DPALO的计算结果优于已知最优解(Best known values,BKV)、仿生算法(Bionic algorithm,BA)和位移决策算法(Displacement decision algorthm,DDA),与细胞自动机优化方法(Cellular automaton optimization,CAO)、紧致子序列算法(Compact subsequence algorithm,CSA)和滚动时域‑混合粒子群优化‑局部搜索算法(Rolling horizon framework hybrid particle swarm optimization local search algorithm,RH‑HPSO‑LS)的结果相近;DPALO的时间效率在小样本数据集上时间效率达到毫秒级,在大样本数据集上相较于CSA、CAO和RH‑HPSO‑LS分别提升了76.88%、89.11%和78.28%。

二态量子系统准确布居动力学的一类新型相空间表示及其与三角窗函数的关系

二态系统是最简单的且无经典对应的量子系统,对二态系统的同构表示的认识和研究能启发研究人员对其动力学与统计行为的更深刻理解.本文使用在[J.Chem.Phys.145,204105(2016);J.Chem.Phys.151,024105(2019);J.Phys.Chem.Lett.12,2496(2021)]等文章中发展的约束相空间严格理论、非协变相空间函数、含时权重函数与含时归一化因子来构建一类新型量子相空间表示.这类同构表示可以导出二态量子系统布居动力学的准确结果.约束相空间上的轨迹运动方程同构于含时薛定谔方程.每条相空间轨迹对于布居动力学所对应积分表达式的贡献严格半正定。进一步证明了在[J.Chem.Phys.145,144108(2016)]这篇文章中根据经验提出的三角窗函数方法在本质上可以对应于本文的这类新型相空间表示的一个特殊情况,因此同样是二态量子系统准确布居动力学的同构表示.

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

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

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

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

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

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

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

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

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

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

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

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

基于CSP的Job shop调度算法研究

针对一类典型的约束满足问题--Job shop调度问题,提出一种CSP调度算法框架,详细讨论CSP 调度算法中的工序开始时间窗、一致性预处理、搜索空间概率模型、工序排序启发、开工时间排序启发的求解 方法。仿真结果表明CSP调度算法在较小的计算时间代价下,获得了FT10标准调度问题的近优解。

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

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

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

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

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

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

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

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