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.展开更多
The multi-point dynamic aggregation(MPDA)problem is a challenging real-world problem.In the MPDA problem,the demands of tasks keep changing with their inherent incremental rates,while a heterogeneous robot fleet is re...The multi-point dynamic aggregation(MPDA)problem is a challenging real-world problem.In the MPDA problem,the demands of tasks keep changing with their inherent incremental rates,while a heterogeneous robot fleet is required to travel between these tasks to change the time-varying state of each task.The robots are allowed to collaborate on the same task or work separately until all tasks are completed.It is challenging to generate an effective task execution plan due to the tight coupling between robots abilities and tasks'incremental rates,and the complexity of robot collaboration.For effectiveness consideration,we use the variable length encoding to avoid redundancy in the solution space.We creatively use the adaptive large neighborhood search(ALNS)framework to solve the MPDA problem.In the proposed algorithm,high-quality initial solutions are generated through multiple problem-specific solution construction heuristics.These heuristics are also used to fix the broken solution in the novel integrated decoding-construction repair process of the ALNS framework.The results of statistical analysis by the Wilcoxon rank-sum test demonstrate that the proposed ALNS can obtain better task execution plans than some state-of-the-art algorithms in most MPDA instances.展开更多
针对无人机路径规划求解计算量大、难收敛等问题,提出了一种基于全粒子推动野马算法的路径规划方法。建立三维环境模型与路径代价模型,将路径规划问题转化为多维函数优化问题;采用一种自适应邻域搜索策略,改善算法的开发能力;利用高斯...针对无人机路径规划求解计算量大、难收敛等问题,提出了一种基于全粒子推动野马算法的路径规划方法。建立三维环境模型与路径代价模型,将路径规划问题转化为多维函数优化问题;采用一种自适应邻域搜索策略,改善算法的开发能力;利用高斯随机游走策略对个体的历史最优位置进行回溯搜索,改善算法的探索能力;考虑到自适应策略对初始种群多样性敏感的问题,结合Tent混沌映射初始化种群,提高算法的鲁棒性以及全局寻优能力;将提出的改进算法在13个经典测试函数中进行性能验证,并移植于无人机三维路径规划问题中。在30峰、40峰、50峰的环境模型下进行测试,与遗传算法、粒子群算法、SRM-PSO(self-regulating and self-perception particle swarm optimization with mutation mechanism)算法以及野马算法对比,全粒子推动野马算法皆取得最短平均路径,且在所有测试中都找到满足约束、无碰的路径。仿真结果证明,在复杂环境下全粒子推动野马算法具有优秀的全局寻优能力以及较好的鲁棒性。展开更多
To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,...To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.展开更多
基金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.
基金supported in part by the National Outstanding Youth Talents Support Program(No.61822304)the Basic Science Center Program of the NSFC(No.62088101)+2 种基金the Project of Major International(Regional)Joint Research Program of NSFC(No.61720106011)the Shanghai Municipal Science and Technology Major Project(No.2021SHZDZX0100)the Shanghai Municipal Commission of Science and Technology Project(No.19511132101).
文摘The multi-point dynamic aggregation(MPDA)problem is a challenging real-world problem.In the MPDA problem,the demands of tasks keep changing with their inherent incremental rates,while a heterogeneous robot fleet is required to travel between these tasks to change the time-varying state of each task.The robots are allowed to collaborate on the same task or work separately until all tasks are completed.It is challenging to generate an effective task execution plan due to the tight coupling between robots abilities and tasks'incremental rates,and the complexity of robot collaboration.For effectiveness consideration,we use the variable length encoding to avoid redundancy in the solution space.We creatively use the adaptive large neighborhood search(ALNS)framework to solve the MPDA problem.In the proposed algorithm,high-quality initial solutions are generated through multiple problem-specific solution construction heuristics.These heuristics are also used to fix the broken solution in the novel integrated decoding-construction repair process of the ALNS framework.The results of statistical analysis by the Wilcoxon rank-sum test demonstrate that the proposed ALNS can obtain better task execution plans than some state-of-the-art algorithms in most MPDA instances.
文摘针对无人机路径规划求解计算量大、难收敛等问题,提出了一种基于全粒子推动野马算法的路径规划方法。建立三维环境模型与路径代价模型,将路径规划问题转化为多维函数优化问题;采用一种自适应邻域搜索策略,改善算法的开发能力;利用高斯随机游走策略对个体的历史最优位置进行回溯搜索,改善算法的探索能力;考虑到自适应策略对初始种群多样性敏感的问题,结合Tent混沌映射初始化种群,提高算法的鲁棒性以及全局寻优能力;将提出的改进算法在13个经典测试函数中进行性能验证,并移植于无人机三维路径规划问题中。在30峰、40峰、50峰的环境模型下进行测试,与遗传算法、粒子群算法、SRM-PSO(self-regulating and self-perception particle swarm optimization with mutation mechanism)算法以及野马算法对比,全粒子推动野马算法皆取得最短平均路径,且在所有测试中都找到满足约束、无碰的路径。仿真结果证明,在复杂环境下全粒子推动野马算法具有优秀的全局寻优能力以及较好的鲁棒性。
基金supported by Natural Science Foundation Project of Gansu Provincial Science and Technology Department(No.1506RJZA084)Gansu Provincial Education Department Scientific Research Fund Grant Project(No.1204-13).
文摘To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.
