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.

A hybrid algorithm based on tabu search and large neighbourhood search for car sequencing problem

The car sequencing problem(CSP)concerns a production sequence of different types of cars in the mixed-model assembly line.A hybrid algorithm is proposed to find an assembly sequence of CSP with minimum violations.Firstly,the hybrid algorithm is based on the tabu search and large neighborhood search(TLNS),servicing as the framework.Moreover,two components are incorporated into the hybrid algorithm.One is the parallel constructive heuristic(PCH)that is used to construct a set of initial solutions and find some high quality solutions,and the other is the small neighborhood search(SNS)which is designed to improve the new constructed solutions.The computational results show that the proposed hybrid algorithm(PCH+TLNS+SNS)obtains100best known values out of109public instances,among these89instances get their best known values with100%success rate.By comparing with the well-known related algorithms,computational results demonstrate the effectiveness,efficiency and robustness of the proposed algorithm.

具有最大总加权满意度的单机调度问题的dynasearch算法

研究了总加权满意程度最大化的单机调度问题.对最优解的性质进行分析和证明,提出该类问题的统治规则.提出该问题新的基于dynasearch邻域的迭代局域搜索算法(ILS).算法主要特点:1)dynasearch是基于多摄动的思想,即一次可以做多个相互独立的交换(或插入);2)用动态规划获得最优dynasearch移动;3)ILS采用随机kick策略对局部最优解进行摄动,然后继续迭代.实现了该问题的两种dynaearch算法;把两种dynasearch算法与统治规则相结合;在进行kick时引入误差限制.实验表明:嵌入统治规则的算法优于没有统治规则的算法;基于dynasearch交换的ILS优于基于dynasearch插入的ILS;dynaearch算法要优于以交换为邻域的多初始点改进算法.

强化Dynasearch & TS算法求解酸轧生产调度问题

酸轧生产调度的主要任务是在满足酸轧机组生产工艺和能力约束下,考虑下游机组的流向需求,为保证生产连续性和平滑过渡的要求,从给定候选池中选择适合的板卷构成一个酸轧调度单元.针对此问题,本文建立了以最小化过渡费用和调度单元剩余容量惩罚费用为目标的整数规划模型,提出了一种嵌入强化Dynasearch算法的禁忌搜索混合算法.该混合算法采用基于最小插入法的两阶段启发式产生初始解,根据采用邻域结构的不同设计双禁忌表,为了避免算法陷入局部最优,在禁忌搜索的每次迭代过程中嵌入Swap邻域和Inner-insert邻域相结合的多交换Dynasearch邻域,并设计了多项式动态规划算法搜索该邻域.针对问题的特征,提出了Block分区结构,基于此分析了多个可行解性质,有效降低了搜索空间.与一般禁忌搜索算法比较,结果表明所提出的强化Dynsearch & TS(Tabusearch)算法求解效果明显优于一般TS算法,平均改进量为3.62%,算法运行时间大大缩短.验证了该算法在解决此类问题的有效性.

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

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

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

针对社区团购前置仓配送场景中“多中心、高时效、多品类、高排放”难题,本文提出多车场带时间窗的绿色多舱车车辆路径问题(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问题中具有有效性。

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

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

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

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

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

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

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

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