A GRASP with evolutionary path relinking for the truck and trailer routing problem

In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.     

A hybrid particle swarm optimization algorithm for the vehicle routing problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for successfully solving one of the most popular supply chain management problems, the vehicle routing problem. The vehicle routing problem is considered one of the most well studied problems in operations research. The proposed algorithm for the solution of the vehicle routing problem, the hybrid particle swarm optimization (HybPSO), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search–greedy randomized adaptive search procedure (MPNS–GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is suitable for solving very large-scale vehicle routing problems as well as other, more difficult combinatorial optimization problems, within short computational time. It is tested on a set of benchmark instances and produced very satisfactory results. The algorithm is ranked in the fifth place among the 39 most known and effective algorithms in the literature and in the first place among all nature inspired methods that have ever been used for this set of instances.     

基于MPH的时延约束Steiner树算法

为了在时延约束务件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.     

混合分散搜索算法求解带容量约束车辆路径问题

设计一种解决带容量约束车辆路径问题的混合分散搜索算法. 在基本分散搜索的基础上, 保留参考集更新策略和组合策略的全局搜索能力. 采用随机插入法作为解的多样性产生方法, 以扩大搜索空间, 避免陷入局部最优.应用简化的变邻域搜索作为改进策略进行局部开发, 引入邻域半径减少策略提高开发效率. 对改进后的新种群实施精英保留策略, 保证算法收敛. 实验结果分析表明, 混合分散搜索算法优于所对比的算法, 寻优能力可靠.

     

A hybrid column generation with GRASP and path relinking for the network load balancing problem

In this paper, a hybrid meta-heuristic is proposed which combines the GRASP with path relinking method and Column Generation. The key idea of this method is to run a GRASP with path relinking search on a restricted search space, defined by Column Generation, instead of running the search on the complete search space of the problem. Moreover, column generation is used not only to compute the initial restricted search space but also to modify it during the whole algorithm. The proposed heuristic is used to solve the network load balancing problem: given a capacitated telecommunications network with single path routing and an estimated traffic demand matrix, the network load balancing problem is the determination of a routing path for each traffic commodity such that the network load balancing is optimized, i.e., the worst link load is minimized, among all such solutions, the second worst link load is minimized, and continuing in this way until all link loads are minimized. The computational results presented in this paper show that, for the network load balancing problem, the proposed heuristic is effective in obtaining better quality solutions in shorter running times.     

A GES/TS algorithm for the job shop scheduling

The job shop scheduling problem is a difficult combinatorial optimization problem. This paper presents a hybrid algorithm which combines global equilibrium search, path relinking and tabu search to solve the job shop scheduling problem. The proposed algorithm used biased random sampling to have a better covering of the solution space. In addition, a new version of N6 neighborhood is applied in a tabu search framework. In order to evaluate the algorithm, comprehensive tests are applied to it using various standard benchmark sets. Computational results confirm the effectiveness of the algorithm and its high speed. Besides, 19 new upper bounds among the unsolved problems are found.     

Scatter search with path relinking for the job shop with time lags and setup times

This paper addresses the job shop scheduling problem with time lags and sequence-dependent setup times. This is an extension of the job shop scheduling problem with many applications in real production environments. We propose a scatter search algorithm which uses path relinking and tabu search in its core. We consider both feasible and unfeasible schedules in the execution, and we propose effective neighborhood structures with the objectives of reducing the makespan and regain feasibility. We also define new procedures for estimating the quality of the neighbors. We conducted an experimental study to compare the proposed algorithm with the state-of-the-art, in benchmarks both with and without setups. In this study, our algorithm has obtained very competitive results in a reduced run time.     

Hybrid ensemble selection algorithm incorporating GRASP with path relinking

The greedy randomized adaptive search procedure (GRASP) is an iterative two-phase multi-start metaheuristic procedure for a combination optimization problem, while path relinking is an intensification procedure applied to the solutions generated by GRASP. In this paper, a hybrid ensemble selection algorithm incorporating GRASP with path relinking (PRelinkGraspEnS) is proposed for credit scoring. The base learner of the proposed method is an extreme learning machine (ELM). Bootstrap aggregation (bagging) is used to produce multiple diversified ELMs, while GRASP with path relinking is the approach for ensemble selection. The advantages of the ELM are inherited by the new algorithm, including fast learning speed, good generalization performance, and easy implementation. The PRelinkGraspEnS algorithm is able to escape from local optima and realizes a multi-start search. By incorporating path relinking into GRASP and using it as the ensemble selection method for the PRelinkGraspEnS the proposed algorithm becomes a procedure with a memory and high convergence speed. Three credit datasets are used to verify the efficiency of our proposed PRelinkGraspEnS algorithm. Experimental results demonstrate that PRelinkGraspEnS achieves significantly better generalization performance than the classical directed hill climbing ensemble pruning algorithm, support vector machines, multi-layer perceptrons, and a baseline method, the best single model. The experimental results further illustrate that by decreasing the average time needed to find a good-quality subensemble for the credit scoring problem, GRASP with path relinking outperforms pure GRASP (i.e., without path relinking).     

带模糊需求的开放式选址路径问题的混合离散蘑菇繁殖算法

针对带限制的开放性选址路径问题的研究,考虑模糊需求的条件下,以仓库选址成本、车辆行驶距离成本、机会损失成本、额外距离等目标之和最小化的要求建立数学模型。通过对蘑菇繁殖算法的改进,使用部分映射交叉和路径重连算法代替原算法中父代更新方式;在邻域搜索部分使用概率法进行邻域选择;使用随机模拟程序对设计好的路径进行模拟,计算因服务失败而产生的额外行驶距离与机会损失成本。在保留算法原有特性的情况下使其成功应用于组合优化问题;通过一系列算例测试与对比,验证了模型的正确性与有效性以及混合离散蘑菇繁殖算法的计算效率和优化能力。     

利用分散搜索算法实现受时延约束的多播路由

提出一种新的基于分散搜索算法 （Scatter Search,SS） 来解决受时延约束的多播路由的方法。作为进化算法的一种,分散搜索算法不但继承了进化算法中通过杂交和变异算子来增强性能的机制,还独创性地运用了“分散 - 收敛集聚”的迭代机制。通过在受时延约束多播路由算法上应用 SS 算法,寻找包含所有组播节点在内的最小代价树。实验表明,本算法具有较好的收敛性和分布性。     

多中心联合配送模式下集货需求随机的VRPSDP问题

针对多中心联合配送模式下集货需求随机的同时配集货车辆路径问题(MDVRPSDDSPJD), 构建了两阶段MDVRPSDDSPJD模型. 预优化阶段基于随机机会约束机制以及车载量约束为客户分配车辆, 生成预优化方案; 重优化阶段采用失败点重优化策略对服务失败点重新规划路径. 根据问题特征, 设计了自适应变邻域文化基因算法(Adaptive memetic algorithm and variable neighborhood search, AMAVNS), 针对文化基因算法易早熟、局部搜索能力弱等缺陷, 将变邻域搜索算法的深度搜索能力运用到文化基因算法的局部搜索策略中, 增强算法的局部搜索能力; 提出自适应邻域搜索次数策略和自适应劣解接受机制平衡种群进化所需的广度和深度. 通过多组算例验证了提出模型及算法的有效性. 研究成果不仅深化和拓展了VRP (Vehicle routing problem)相关理论研究, 也为物流企业制定车辆调度计划提供一种科学合理的方法.     

一种基于禁忌搜索的时延约束组播路由算法

提出了一种使用禁忌搜索方法构造组播树的时延约束最小代价组播路由算法（TSBDMA)。该算法充分利用禁忌搜索方法中灵活的记忆功能和禁忌规则等特点,以最小时延树为初始解,并使用换边操作构造邻域集,最终求得满足条件的组播树。仿真实验结果表明本算法具有代价性能良好、可靠性高、收敛速度快、时延低的特点。     

A scatter search approach for the minimum sum-of-squares clustering problem

A metaheuristic procedure based on the scatter search approach is proposed for the non-hierarchical clustering problem under the criterion of minimum sum-of-squares clustering. This algorithm incorporates procedures based on different strategies, such as local search, GRASP, tabu search or path relinking. The aim is to obtain quality solutions with short computation times. A series of computational experiments has been performed. The proposed algorithm obtains better results than previously reported methods, especially with small numbers of clusters.     

求解两级定位-路径问题的粒子群算法

为求解配送网络中的两级定位-路径问题,提出一种在粒子更新过程中融入路径重连启发式搜索策略的粒子群算法。其中,根据两级定位-路径问题中解的属性,提出以中转站、路径、边为对象的三个路径重连搜索模块;同时基于搜索模块的不同组合,提出四种路径重连策略。应用不同规模算例测试结果表明,该粒子群算法能有效求解两级定位-路径问题,且路径重连策略一的求解效率较高,策略二求解的稳定性较好,策略三求解时各方面均无突出表现,策略四求解时解的质量较高。     

一种新的求解MMKP问题的ACO&PR算法

针对多选择多维背包问题(MMKP)的特点,设计一种新型混合算法(ACO＆PR).该算法将线路重连算法(PR)嵌入蚁群算法(ACO),在搜索过程中既考虑解的质量,又考虑解的分散性.线路重连算法在重连过程中,向导解的属性逐步引入起始解属性中,可快速获得该线路上的最优解.实验结果表明,该算法优于其他现有较好的方法,获得了较好的结果.     

电力巡检中的无人机群路径规划算法

随着无人机技术的飞速发展, 无人机被广泛用于各种领域的巡检任务. 近年来, 电力网络的规模和长度都在快速增长, 无人机因其独特的性能和优势成为了电力巡检的首选, 无人机巡检不仅能保证安全性, 还能有效地提高巡检效率, 而路径规划是其在实际应用中的关键一步. 本文提出了一种新的混合元启发式方法, 用于解决电力巡检中带有多...     

混合算法的邻域结构变更研究及在排样问题上的应用

本文研究了全局搜索算法和局部搜索算法的混合机制,设计了基于邻域搜索和遗传算法的混合搜索算法。该算法结合了遗传算法的全局搜索特性和邻域局部贪婪搜索特性;在分析排样问题碰靠过程特征的基础上,构建了排样问题邻域假设,当邻域假设满足时,遗传算法+邻域搜索能很好发挥作用;当不能判断邻域结构是否满足邻域假设时,提出了建立遗传算法+匹配变邻域的搜索算法,该算法兼顾了组合优化中邻域搜索的局部搜索无效的情况,实现了匹配的变邻域混合算法在排样优化问题中的应用。实例结果标明,排样图形不一样,其求解难度不一样,该算法均搜索到了更好的排样模式,验证了算法的有效性。     

基于量子遗传退火策略的多播路由优化模型及其算法

针对网络通信中带时延约束的多播路由问题,提出了一种基于量子遗传退火策略的路由算法。文中对路由选择问题的优化模型进行了描述,并深入研究了量子遗传退火及其在多播路由选择优化问题中的应用。仿真实验表明,与基于遗传算法的多播路由算法相比,该算法具有更快的收敛速度和更好的全局寻优能力。     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。     

Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem

This paper introduces a new algorithmic nature-inspired approach that uses particle swarm optimization (PSO) with different neighborhood topologies, for successfully solving one of the most computationally complex problems, the permutation flowshop scheduling problem (PFSP). The PFSP belongs to the class of combinatorial optimization problems characterized as NP-hard and, thus, heuristic and metaheuristic techniques have been used in order to find high quality solutions in reasonable computational time. The proposed algorithm for the solution of the PFSP, the PSO with expanding neighborhood topology, combines a PSO algorithm, the variable neighborhood search strategy and a path relinking strategy. As, in general, the structure of the social network affects strongly a PSO algorithm, the proposed method using an expanding neighborhood topology manages to increase the performance of the algorithm. As the algorithm starts from a small size neighborhood and by increasing (expanding) in each iteration the size of the neighborhood, it ends to a neighborhood that includes all the swarm, and it manages to take advantage of the exploration abilities of a global neighborhood structure and of the exploitation abilities of a local neighborhood structure. In order to test the effectiveness and the efficiency of the proposed method, we use a set of benchmark instances of different sizes and compare the proposed method with a number of other PSO algorithms and other algorithms from the literature.