变邻域模拟退火算法求解速度时变的VRPTW问题

本文在经典的带时间窗的车辆路径问题(VRPTW)的基础上,考虑不同时间段车辆行驶速度不同的情况,研究速度时变的带时间窗车辆路径问题(TDVRPTW),使问题更具实际意义。本文用分段函数表示不同时间段下的车辆行驶速度,并解决了速度时变条件下行驶时间计算的问题。针对模拟退火算法(SA)在求解VRPTW问题时易陷入局部最优解,变邻域搜索算法(VNS)在求解VRPTW问题时收敛速度慢的问题,本文将模拟退火算法以一定概率接受非最优解的思想和变邻域搜索算法系统地改变当前解的邻域结构以拓展搜索范围的思想结合起来,提出了一种改进的算法——变邻域模拟退火算法(SAVN),使算法在退火过程中一陷入局部最优解就改变邻域结构,更换搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。通过在仿真实验中将SAVN算法的求解结果与VNS算法、SA算法进行对比,验证了SAVN算法确实能显著提升算法跳出局部最优解的能力。     

两级定位-路径问题模型及变邻域粒子群算法

为满足B2C电子商务中高效率、低成本配送需求,建立了两级定位-路径问题的三下标车流模型,提出了一种求解该问题的变邻域粒子群算法。该算法引入路径重连思想,将粒子群算法中粒子动态更新设计为当前解的邻域搜索、当前解与个体历史最优解之间的路径重连、当前解与种群历史最优解之间的路径重连;在此基础上,提出变邻域搜索策略,动态改变邻域结构以拓展搜索空间。实验结果表明,该算法能有效求解两级定位-路径问题。     

改进的布谷鸟算法求解物流配送中心选址问题

针对基本布谷鸟算法求解物流配送中心选址问题时存在搜索精度低、易陷入局部最优值的缺陷,提出一种改进的布谷鸟算法.算法采用基于寄生巢适应度值排序的自适应方法改进基本布谷鸟算法的惯性权重,以平衡算法的全局开发能力和局部探索能力;利用NEH领域搜索以提高算法的搜索精度和收敛速度;引入停止阻止策略对全局最优寄生巢位置进行变异避免算法陷入局部最优值、增加种群的多样性.通过实验仿真表明,改进的布谷鸟算法在求解物流配送中心选址问题上要优与基本布谷鸟算法以及其它智群算法,是一种有效的算法.     

带时间窗偏好的同时配集货且需求可拆分车辆路径问题

针对带时间窗偏好的同时配集货且需求可拆分车辆路径问题,最小化派遣成本、理货成本、时间窗惩罚成本以及油耗成本之和,建立数学模型。设计混合遗传变邻域搜索算法求解问题,在算法中引入时空距离的理念,首先用最近邻插入法和Logistic映射方程生成初始种群;然后利用变邻域搜索算法的深度搜索能力优化算法;提出自适应搜索策略,平衡种群进化所需的广度和深度;设计拆分准则,为各客户设置不同的拆分服务量;提出确定车辆最优出发时间的时差推移法,减少车辆在客户处的等待时间;最后通过多组算例验证本文模型和算法的有效性。     

基于维数学习和二次插值的混沌飞蛾火焰优化算法

针对K-means算法对初始聚类中心敏感和容易陷入局部最优的问题,首先提出一种基于维数学习和二次插值的飞蛾火焰优化算法以提高基本算法的求解精度和收敛速度,即采用Tent混沌映射产生多样性较好的初始种群,增强算法的全局搜索能力;对火焰位置采用维数学习策略生成更优良的火焰来指导飞蛾寻优,以提高算法的搜索效率;把二次插值引入...     

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。     

一种自适应人工蜂群算法求解U型顺序相依拆卸线平衡问题

产品拆卸过程中零部件之间会相互干扰影响任务作业时间,基于该情形构建了多目标U型SDDLBP优化模型,并提出一种自适应ABC算法。所提算法设计了自适应动态邻域搜索方法,以提高局部开发能力;采用了轮盘赌与锦标赛法结合的分段选择法,以有效评价并选择蜜源进行深度开发;建立了基于当前最优解的变异操作,以提高全局探索能力快速跳出局部最优。最后,通过算例测试和实例分析验证算法的高效性。     

求解带时间窗车辆路径问题的改进离散花朵授粉算法

针对当前算法在求解带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)时存在精度、效率方面的不足,提出一种改进的离散花朵授粉算法.算法在基本花朵授粉算法的基础上进行离散化,使其适合求解带时间窗车辆路径问题,重新定义花朵授粉算子操作.为了提高求解精度和效率,设计了随机插入、路径内的2-opt、交换和逆序操作,为了增加种群间信息的交互,结合改进的遗传算子.通过11个测试算例表明,改进的离散花朵授粉算法在求解VRPTW是行之有效的,与文献中其他算法比较,算法在精度、效率和鲁棒性方面具有优势.     

函数优化的小生境蝙蝠算法

针对蝙蝠算法易陷入局部最优解的缺点,利用小生境技术对蝙蝠算法进行了改进,提出一种小生境蝙蝠优化算法.算法基于小生境技术的适应度共享来分隔种群,引入了小生境排挤机制来保持种群多样性,在延续蝙蝠算法原有并行搜索等优势的基础上,提高了算法的金局搜索能力和局部收敛速度,具有可在不同邻域内发现多个解的特点.通过对一系列经典函数测试,并与已有算法进行比较,结果表明该算法在函数优化问题的求解中具有较高的计算效率和精度,以及较好的全局寻优能力.     

一种改进灰狼优化算法研究及应用

针对灰狼算法易陷入局部最优、收敛精度不高、收敛速度慢等缺点,提出一种改进的灰狼算法.引入莱维飞行,扩大搜索范围,增强全局搜索能力,避免陷入局部最优;引入贪婪原理,提升种群优良性以提高算法收敛精度;引入自适应收敛因子,加快收敛速度;引入动态权重策略,制约全局搜索与局部搜索的相互影响.将改进算法与其他四种算法作对比,实验表明,改进算法在收敛速度与收敛精度上都有更好的性能.最后,应用于图像多阈值分割中,采用GWO-Otsu法可以克服传统Otsu法在多阈值分割时计算量大,实时性差的特点,不但能够取得最优解,且明显缩减计算时间.     

A hybrid iterated local search heuristic for the maximum weight independent set problem

This paper presents a hybrid iterated local search (ILS) algorithm for the maximum weight independent set (MWIS) problem, a generalization of the classical maximum independent set problem. Two efficient neighborhood structures are proposed and they are explored using the variable neighborhood descent procedure. Moreover, we devise a perturbation mechanism that dynamically adjusts the balance between intensification and diversification during the search. The proposed algorithm was tested on two well-known benchmarks (DIMACS-W and BHOSLIB-W) and the results obtained were compared with those found by state-of-the-art heuristics and exact methods. Our heuristic outperforms the best-known heuristic for the MWIS as well as the best heuristics for the maximum weight clique problem. The results also show that the hybrid ILS was capable of finding all known optimal solutions in milliseconds.     

Adaptive Tabu Search for course timetabling

This paper presents an Adaptive Tabu Search algorithm (denoted by ATS) for solving a problem of curriculum-based course timetabling. The proposed algorithm follows a general framework composed of three phases: initialization, intensification and diversification. The initialization phase constructs a feasible initial timetable using a fast greedy heuristic. Then an adaptively combined intensification and diversification phase is used to reduce the number of soft constraint violations while maintaining the satisfaction of hard constraints. The proposed ATS algorithm integrates several distinguished features such as an original double Kempe chains neighborhood structure, a penalty-guided perturbation operator and an adaptive search mechanism. Computational results show the high effectiveness of the proposed ATS algorithm, compared with five reference algorithms as well as the current best known results. This paper also shows an analysis to explain which are the essential ingredients of the ATS algorithm.     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

A new hybrid genetic algorithm for the capacitated vehicle routing problem

Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.     

A hybrid genetic local search algorithm for the permutation flowshop scheduling problem

Traditionally, the permutation flowshop scheduling problem (PFSP) was with the criterion of minimizing makespan. The permutation flowshop scheduling problem to minimize the total flowtime has attracted more attention from researchers in recent years. In this paper, a hybrid genetic local search algorithm is proposed to solve this problem with each of both criteria. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search and two local search methods to do the local search. Two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the GA’s capability of intensification. The experimental results show the advantage of combining the two local search methods. The performance of the proposed hybrid genetic algorithm is very competitive. For the PFSP with the total flowtime criterion, it improved 66 out of the 90 current best solutions reported in the literature in short-term search and it also improved all the 20 current best solutions reported in the literature in long-term search. For the PFSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature.     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows

We propose a new population-based hybrid meta-heuristic for the periodic vehicle routing problem with time windows. This meta-heuristic is a generational genetic algorithm that uses two neighborhood-based meta-heuristics to optimize offspring. Local search methods have previously been proposed to enhance the fitness of offspring generated by crossover operators. In the proposed method, neighborhood-based meta-heuristics are used for their capacity to escape local optima, and deliver optimized and diversified solutions to the population of the next generation. Furthermore, the search performed by the neighborhood-based meta-heuristics repairs most of the constraint violations that naturally occur after the application of the crossover operators. The genetic algorithm we propose introduces two new crossover operators addressing the periodic vehicle routing problem with time windows. The two crossover operators are seeking the diversification of the exploration in the solution space from solution recombination, while simultaneously aiming not to destroy information about routes in the population as computing routes is NP-hard. Extensive numerical experiments and comparisons with all methods proposed in the literature show that the proposed methodology is highly competitive, providing new best solutions for a number of large instances.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.