GNN Representation Learning and Multi-Objective Variable Neighborhood Search Algorithm for Wind Farm Layout Optimization

With the increasing demand for electrical services,wind farm layout optimization has been one of the biggest challenges that we have to deal with.Despite the promising performance of the heuristic algorithm on the route network design problem,the expressive capability and search performance of the algorithm on multi-objective problems remain unexplored.In this paper,the wind farm layout optimization problem is defined.Then,a multi-objective algorithm based on Graph Neural Network(GNN)and Variable Neighborhood Search(VNS)algorithm is proposed.GNN provides the basis representations for the following search algorithm so that the expressiveness and search accuracy of the algorithm can be improved.The multi-objective VNS algorithm is put forward by combining it with the multi-objective optimization algorithm to solve the problem with multiple objectives.The proposed algorithm is applied to the 18-node simulation example to evaluate the feasibility and practicality of the developed optimization strategy.The experiment on the simulation example shows that the proposed algorithm yields a reduction of 6.1% in Point of Common Coupling(PCC)over the current state-of-the-art algorithm,which means that the proposed algorithm designs a layout that improves the quality of the power supply by 6.1%at the same cost.The ablation experiments show that the proposed algorithm improves the power quality by more than 8.6% and 7.8% compared to both the original VNS algorithm and the multi-objective VNS algorithm.

Hybrid artificial bee colony algorithm with variable neighborhood search and memory mechanism

Artificial bee colony(ABC) is one of the most popular swarm intelligence optimization algorithms which have been widely used in numerical optimization and engineering applications. However, there are still deficiencies in ABC regarding its local search ability and global search efficiency. Aiming at these deficiencies,an ABC variant named hybrid ABC(HABC) algorithm is proposed.Firstly, the variable neighborhood search factor is added to the solution search equation, which can enhance the local search ability and increase the population diversity. Secondly, inspired by the neuroscience investigation of real honeybees, the memory mechanism is put forward, which assumes the artificial bees can remember their past successful experiences and further guide the subsequent foraging behavior. The proposed memory mechanism is used to improve the global search efficiency. Finally, the results of comparison on a set of ten benchmark functions demonstrate the superiority of HABC.

Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

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.

Particle Swarm Optimization Embedded in Variable Neighborhood Search for Task Scheduling in Cloud Computing

In cloud computing system,it is a hot and hard issue to find the optimal task scheduling method that makes the processing cost and the running time minimum. In order to deal with the task assignment,a task interaction graph was used to analyze the task scheduling; a modeling for task assignment was formulated and a particle swarm optimization (PSO)algorithm embedded in the variable neighborhood search (VNS) to optimize the task scheduling was proposed. The experimental results show that the method is more effective than the PSO in processing cost,transferring cost, and running time. When the task is more complex,the effect is much better. So,the algorithm can resolve the task scheduling in cloud computing and it is feasible,valid,and efficient.

An adaptive large neighborhood search for the multi-point dynamic aggregation problem

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.

Particle swarm optimization with variable neighborhood search for multiobjective flexible job shop scheduling problem

The simulation on benchmarks is a very simple and efficient method to evaluate the performance of the algorithm for solving flexible job shop scheduling model.Due to the assignment and scheduling decisions,flexible job shop scheduling problem(FJSP)becomes extremely hard to solve for production management.A discrete multi-objective particle swarm optimization(PSO)and simulated annealing(SA)algorithm with variable neighborhood search is developed for FJSP with three criteria:the makespan,the total workload and the critical machine workload.Firstly,a discrete PSO is designed and then SA algorithm performs variable neighborhood search integrating two neighborhoods on public critical block to enhance the search ability.Finally,the selection strategy of the personal-best individual and global-best individual from the external archive is developed in multi-objective optimization.Through the experimental simulation on matlab,the tests on Kacem instances,Brdata instances and BCdata instances show that the modified discrete multi-objective PSO algorithm is a promising and valid method for optimizing FJSP with three criteria.

General Pattern and Neighborhood Search Algorithms for Non-Convex Unit Commitment

This paper presents a new approach to solve mixed-variable unit commitment(UC) problems with non-smooth cost functions based on a generalized pattern search filter(GPS-filter) algorithm. A GPS-filter algorithm does not require any information about the gradient of the objective function while searching for an optimum solution. At the same time, it is available for solving mixed-variable optimization problems, which is very suitable for UC. A new suitable discrete neighborhood structure with UC characteristics is proposed to improve GPS-filter efficiently. A lot of multiple units' states are fixed before search; hence, the polling search of discrete variable is efficient for a few uncertain units. Numerical experiments are included to demonstrate the proposed approach's ability to handle the highly nonlinear, discontinuous, non-smooth cost functions and mixed variables of the UC problem.

A Multiple-Neighborhood-Based Parallel Composite Local Search Algorithm for Timetable Problem

This paper presents a parallel composite local search algorithm based on multiple search neighborhoods to solve a special kind of timetable problem. The new algorithm can also effectively solve those problems that can be solved by general local search algorithms. Experimental results show that the new algorithm can generate better solutions than general local search algorithms.

Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem

A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson (ie., FT6 and FT20)is made. The experiment results show the better optimal performance of the proposed algorithm.

多舱共配绿色车辆路径问题的改进变邻域搜索算法

针对社区团购前置仓配送场景中“多中心、高时效、多品类、高排放”难题,本文提出多车场带时间窗的绿色多舱车车辆路径问题(MDMCG-VRPTW),构建混合整数线性规划模型,并设计改进的变邻域搜索算法(IVNS)实现求解.采用两阶段混合算法构造高质量初始解.提出均衡抖动策略以充分探索解空间,引入粒度机制以提升局部搜索阶段的寻优效率.标准算例测试结果验证了两阶段初始解构造算法和IVNS算法的有效性.仿真实验结果表明,模型与算法能够有效求解MDMCGVRPTW,且改进策略提高了算法的求解效率和全局搜索能力.最后,基于对配送策略和时效性的敏感性分析,为相关配送企业降本增效提供更多决策依据.

基于改进蚁群算法的外卖配送路径规划研究

从外卖配送员角度出发提出一种改进蚁群算法(Improved Ant Colony Optimization,IACO),在此基础上进行外卖配送路径规划研究.首先通过蚁群算法(Ant Colony Optimization,ACO)求解得到初始规划路径,然后通过大规模邻域搜索算法(Large Neighborhood Search,LNS)优化初始规划路径,通过将ACO和LNS算法结合,提高求解质量.为了验证方法的有效性,对外卖配送过程进行仿真,并且选用不同订单数量场景进行对照分析.根据最优配送方案路线图和目标罚函数的最优值可以得出,IACO算法是有效的,且可以提高外卖配送员外卖配送的效率.IACO算法不但能够提升配送的智能化水平,还从外卖配送员的角度提出一种更为人性化的配送方法,支持网络互联外卖平台派送系统的可持续化发展.

混合白鲸优化算法求解柔性作业车间调度问题

针对柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP),提出一种混合白鲸优化算法(hybrid beluga whale optimization,HBWO)对其求解,旨在最小最大化完工时间。采用既定策略改进标准白鲸优化算法(beluga whale optimization,BWO),加快其收敛速度;基于机器选择和工序排序问题设计双层编码方案,解决FJSP离散化问题;采用主动编码及种群初始化策略,提高求解质量;基于工序的开始和结束时间确定关键路径和关键块,注重各工序时间维度;引入贪心思想至基于关键路径的混合变邻域搜索策略中,加大勘测搜索空间及减少无效搜索;此外,引入遗传算子防止算法陷入局部最优;通过35个标准算例的仿真实验与分析,证明了算法在求解FJSP问题中具有有效性。

考虑机会充电与行程时间可靠性的区域多车型电动公交调度优化

为提高电动公交系统运营效率,降低运营成本,本文提出一种考虑机会充电和行程时间可靠性的电动公交调度优化方法。首先,基于区域调度场景,提出在线路始末站配备快速充电桩,利用车次接续时间进行机会充电的策略;然后,考虑行程时间的随机波动,以表征特定可靠性的预留行程时间作为模型输入生成调度方案,同时,将发车延误成本纳入目标函数中,综合考虑公交企业从规划到运营阶段的整体效益,构建以总成本最小为目标的区域多车型电动公交调度优化模型,针对模型特点,设计自适应大邻域搜索算法进行求解;最后,以北京市大兴区4条公交线路为例,验证模型和算法的有效性。结果表明:基于本文方法得到的最优调度方案相较于传统单线路单车型调度方案,能使企业日均总成本下降37.93%,平均每辆车的发车延误时长减少5.63 min,说明本文所提方法能有效降低企业成本,提升公交系统可靠性。相较于不考虑机会充电和行程时间可靠性的区域多车型运营模式,本文最优方案能使总成本下降28.67%。此外,通过灵敏度分析,建议公交企业以240 kW的充电功率进行快速充电资源的配置,以90%的行程时间可靠性进行电动公交调度方案的编制。

基于多元信息引导的人工蜂群算法

利用优秀个体增强解搜索方程的开采能力是改进人工蜂群算法的一种主流思路.然而,现有相关工作往往仅以适应度信息作为评价个体的唯一标准,易导致算法出现早熟收敛等问题.本文提出一种多元信息引导的人工蜂群算法,分别设计了基于适应度、位置以及相似度信息的3种解搜索方程,并在雇佣蜂阶段和观察蜂阶段采用了不同的使用方式.同时,为保存侦察蜂阶段的搜索经验,采用一种微调后的邻域搜索机制用于处理被放弃蜜源.在CEC2013测试集和一个实际优化问题上进行了大量实验验证,与6种衍生算法和5种知名的相关改进人工蜂群算法进行了对比,结果表明本文算法性能竞争优势明显,在结果精度和收敛速度上均有更好表现.

改进文化基因算法求解双资源约束柔性作业车间调度问题

针对具有机器和工人的双资源约束柔性作业车间调度问题,以最小化最大完工时间为目标构建调度模型,并设计一种改进文化基因算法对其进行求解。由于该调度问题需要同时考虑工序排序、机器选择及工人选择3个子问题,故采用三层序列编码。考虑传统解码方式存在收敛速度慢、收敛不完全的弊端,设计一种扩展型插入式主动解码方式,以提高算法的收敛速度;针对进化算法易陷入局部最优的缺陷,设计一种基于负载平衡的机器和工人再分配算子,增强算法的全局搜索能力,对种群中的优秀个体采用改进变邻域搜索以提高算法的局部寻优能力。最后,利用仿真算例及航空设备生产实例进行实验,验证所提算法求解双资源约束调度问题的有效性。

混合遗传变邻域搜索算法求解柔性车间调度问题

针对考虑生产成本的柔性作业车间调度问题(flow job shop scheduling problem, FJSP),以完工时间与加工成本为优化指标,提出一种求解FJSP的混合遗传变邻域搜索算法。根据个体适应度对种群分割,结合自适应交叉概率改进子代种群产生方式;设计两种邻域结构增强算法的局部搜索能力;提出一种基于动态交叉变异概率的优化算法流程提高求解效率。运用提出的算法求解基准实例与实际问题测试,验证了算法的有效性。

求解燃气轮机制造车间调度的混合和声搜索算法

燃气轮机生产属于典型的离散型制造,其多品种小批量的生产特点给车间作业调度带来挑战,导致企业生产效率低下,不能满足产品交货期。因和声搜索算法结构简单易操作,常用于解决此类作业车间调度问题。然而传统和声搜索算法收敛速度较慢,易陷入局部最优。本文构建以最小化最大完工时间为目标的燃气轮机制造车间调度数学模型,提出一种离散型改进多种群混合和声搜索算法进行求解。结合和声搜索算法与变邻域搜索算法的优点,采用基于工序的编码方式进行编码,在种群更新部分引入模拟退火的Metropolis接受准则,提高种群多样性;提出自适应的记忆库保留概率和音调调节率来调节参数,以提高算法的全局寻优能力;加入变邻域搜索以提高算法的收敛速度。通过性能测试及实例验证表明,相较于已有算法,所提算法具有更好的性能。

基于混合算法的飞机部件装配静态调度方法研究

飞机部件装配生产工艺流程复杂、生产周期长,如何制定高效的生产调度计划是急需解决的问题。分析了飞机部件装配的工艺流程,建立了飞机部件装配调度的约束条件,包括装配工序的先后约束和装配工装占用的约束,建立了飞机部件装配调度的目标函数,包括最小化拖期惩罚和最小化最大完工周期,对飞机部件装配调度问题进行了合理的假设和抽象,并建立了飞机部件装配调度模型。针对飞机部件装配静态调度问题,将粒子群算法和变邻域搜索算法进行了有效结合,设计了粒子群-变邻域搜索混合算法,并采用实例验证了该算法的有效性。

改进文化基因算法求解带午休时间的多级别家庭护理路径和调度问题

针对护理员的技能等级以及午休时间等约束,以总运营成本最小为目标建立模型,设计混合初始化策略以及自适应邻域搜索结构改进文化基因算法,并采用田口方法调整算法参数。算例测试结果验证了算法的有效性;对比随机的邻域搜索方式,结果证明自适应邻域搜索提升了算法的收敛性;Friedman及后续检验结果则表明该算法优于遗传算法和禁忌搜索算法。针对午休时长和多级别护理员结构的灵敏度分析则分别证明合适的午休时长对降低成本的作用以及多级别护理员的引入对问题的重要性。

Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management

Technological advancements in unmanned aerial vehicles(UAVs)have revolutionized various industries,enabling the widespread adoption of UAV-based solutions.In engineering management,UAV-based inspection has emerged as a highly efficient method for identifying hidden risks in high-risk construction environments,surpassing traditional inspection techniques.Building on this foundation,this paper delves into the optimization of UAV inspection routing and scheduling,addressing the complexity introduced by factors such as no-fly zones,monitoring-interval time windows,and multiple monitoring rounds.To tackle this challenging problem,we propose a mixed-integer linear programming(MILP)model that optimizes inspection task assignments,monitoring sequence schedules,and charging decisions.The comprehensive consideration of these factors differentiates our problem from conventional vehicle routing problem(VRP),leading to a mathematically intractable model for commercial solvers in the case of large-scale instances.To overcome this limitation,we design a tailored variable neighborhood search(VNS)metaheuristic,customizing the algorithm to efficiently solve our model.Extensive numerical experiments are conducted to validate the efficacy of our proposed algorithm,demonstrating its scalability for both large-scale and real-scale instances.Sensitivity experiments and a case study based on an actual engineering project are also conducted,providing valuable insights for engineering managers to enhance inspection work efficiency.