A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely no...A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.展开更多
Adaptive optimization is one of the means that agile organization of command and control resource （AOC2R） adapts for the dynamic battlefield environment. A math model of the adaptive optimization of AOC2R is put for...Adaptive optimization is one of the means that agile organization of command and control resource （AOC2R） adapts for the dynamic battlefield environment. A math model of the adaptive optimization of AOC2R is put forward by analyzing the interrelating concept and research. The model takes the adaptive process as a multi-stage decision making problem. The 2-phases method is presented to calculate the model, which obtains the related parameters by running the colored Petri net （CPN） model of AOC2R and then searches for the result by ant colony optimization （ACO） algorithm integrated with genetic optimization techniques. The simulation results demonstrate that the proposed algorithm greatly improves the performance of AOC2R.展开更多
针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(ada...针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(adaptive brain storm optimization,ABSO)进行求解。全局搜索阶段,采用多项惩罚方式扩大搜索区域,并使用聚类及三种路径搜索策略进行全局搜索;局部搜索阶段,将六种破坏-修复算子作为备选集合,进而设计自适应动态选择邻域搜索机制,增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试,实验结果表明针对小规模标准算例,所提算法全部取得了当前已知最优解;对于大规模标准算例,通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比,所提算法实验计算结果有7.52%~12.03%的提升;对于实际案例,所提算法在收敛速度和寻优能力方面均展示出优越性,充分验证了所提算法对解决VRPSPDTW问题的有效性。展开更多
针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将...针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将自适应大邻域搜索算法与遗传算法相结合,称为ALNS-GA设计了3个移除算子和2个重插算子,以提高遗传算法的局部搜索能力,并优化了初始种群生成策略。同时,为了验证算法的有效性,分别对比了传统遗传算法和基于大规模邻域搜索的遗传算法(LNS-GA、LNS*-GA),并选取Solomon数据库上VRPTW测试算例,在Matlab R2016b上进行实验验证。实验结果表明,当终止条件为迭代100次时,ALNS-GA的求解质量高于传统遗传算法,大部分案例中,ALNS-GA所求的最好值优于LNS-GA和LNS*-GA,且ALNS-GA平均用时均小于LNS-GA和LNS*-GA,特别是当顾客规模为100时,ALNS-GA的平均用时更少,虽然小部分案例的平均值略高于LNS-GA和LNS*-GA,但从整体上看,ALNS-GA的寻优速度和质量均优于LNS-GA和LNS*-GA,说明经过改进后,遗传算法的局部搜索能力明显提高,可以有效改善遗传算法在带时间窗车辆路径问题上的应用。该研究具有一定的创新。展开更多
提出了一种基于块特性与自适应搜索窗口的运动估计算法(Motion estimation algorithm based on blockcharacteristic and adaptive search window,MBC-ASW),该算法在充分利用视频图像的时间、空间相关性的同时,根据运动向量的统计特性,...提出了一种基于块特性与自适应搜索窗口的运动估计算法(Motion estimation algorithm based on blockcharacteristic and adaptive search window,MBC-ASW),该算法在充分利用视频图像的时间、空间相关性的同时,根据运动向量的统计特性,分别在帧层和块层进行自适应搜索窗口的粗调与微调,并且针对不同的块进行相应的编码处理。在PC上利用C语言实验验证了该算法的可行性,评估了其性能,并与经典的全搜索算法(Fullsearch motion estimation,FS)、三步搜索算法(Three step search,TSS)、新三步搜索算法(New three stepsearch,NTSS)和钻石搜索算法(Diamond search,DS)进行了详细的比较,该算法在性能和效率上均有较大程度的提高,对不同的序列具有较强的自适应性。展开更多
基金supported by the National Natural Science Foundation of China (7060103570801062)
文摘A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.
文摘Adaptive optimization is one of the means that agile organization of command and control resource （AOC2R） adapts for the dynamic battlefield environment. A math model of the adaptive optimization of AOC2R is put forward by analyzing the interrelating concept and research. The model takes the adaptive process as a multi-stage decision making problem. The 2-phases method is presented to calculate the model, which obtains the related parameters by running the colored Petri net （CPN） model of AOC2R and then searches for the result by ant colony optimization （ACO） algorithm integrated with genetic optimization techniques. The simulation results demonstrate that the proposed algorithm greatly improves the performance of AOC2R.
文摘针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(adaptive brain storm optimization,ABSO)进行求解。全局搜索阶段,采用多项惩罚方式扩大搜索区域,并使用聚类及三种路径搜索策略进行全局搜索;局部搜索阶段,将六种破坏-修复算子作为备选集合,进而设计自适应动态选择邻域搜索机制,增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试,实验结果表明针对小规模标准算例,所提算法全部取得了当前已知最优解;对于大规模标准算例,通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比,所提算法实验计算结果有7.52%~12.03%的提升;对于实际案例,所提算法在收敛速度和寻优能力方面均展示出优越性,充分验证了所提算法对解决VRPSPDTW问题的有效性。
文摘针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将自适应大邻域搜索算法与遗传算法相结合,称为ALNS-GA设计了3个移除算子和2个重插算子,以提高遗传算法的局部搜索能力,并优化了初始种群生成策略。同时,为了验证算法的有效性,分别对比了传统遗传算法和基于大规模邻域搜索的遗传算法(LNS-GA、LNS*-GA),并选取Solomon数据库上VRPTW测试算例,在Matlab R2016b上进行实验验证。实验结果表明,当终止条件为迭代100次时,ALNS-GA的求解质量高于传统遗传算法,大部分案例中,ALNS-GA所求的最好值优于LNS-GA和LNS*-GA,且ALNS-GA平均用时均小于LNS-GA和LNS*-GA,特别是当顾客规模为100时,ALNS-GA的平均用时更少,虽然小部分案例的平均值略高于LNS-GA和LNS*-GA,但从整体上看,ALNS-GA的寻优速度和质量均优于LNS-GA和LNS*-GA,说明经过改进后,遗传算法的局部搜索能力明显提高,可以有效改善遗传算法在带时间窗车辆路径问题上的应用。该研究具有一定的创新。
文摘提出了一种基于块特性与自适应搜索窗口的运动估计算法(Motion estimation algorithm based on blockcharacteristic and adaptive search window,MBC-ASW),该算法在充分利用视频图像的时间、空间相关性的同时,根据运动向量的统计特性,分别在帧层和块层进行自适应搜索窗口的粗调与微调,并且针对不同的块进行相应的编码处理。在PC上利用C语言实验验证了该算法的可行性,评估了其性能,并与经典的全搜索算法(Fullsearch motion estimation,FS)、三步搜索算法(Three step search,TSS)、新三步搜索算法(New three stepsearch,NTSS)和钻石搜索算法(Diamond search,DS)进行了详细的比较,该算法在性能和效率上均有较大程度的提高,对不同的序列具有较强的自适应性。
文摘高速铁路夕发朝至列车开行与天窗设置存在动态影响关系,将两者进行协同优化有助于满足旅客夜间出行需求,提升铁路运力资源配置.以通道型高速铁路为对象,在分析高速铁路夕发朝至列车与天窗设置影响关系的基础上,以高速铁路夕发朝至列车总的旅行时间最少和高速铁路夕发朝至列车的开行对既有列车运行图的影响最小为目标,建立了列车开行模式未定情形下高速铁路夕发朝至列车与天窗协同优化的非线性混合整数规划模型.结合问题特性,提出了双目标转换和约束线性化处理等模型约简策略,设计了基于自适应大邻域搜索的启发式求解算法.最后,以京广高速铁路走廊为例,对模型算法的有效性进行了验证.结果表明:算法经过40次左右迭代便可收敛至最优解,耗时784 s.
