Honey Bees Mating Optimization algorithm for large scale vehicle routing problems

Honey Bees Mating Optimization algorithm is a relatively new nature inspired algorithm. In this paper, this nature inspired algorithm is used in a hybrid scheme with other metaheuristic algorithms for successfully solving the Vehicle Routing Problem. More precisely, the proposed algorithm for the solution of the Vehicle Routing Problem, the Honey Bees Mating Optimization (HBMOVRP), combines a Honey Bees Mating Optimization (HBMO) algorithm with the Multiple Phase Neighborhood Search–Greedy Randomized Adaptive Search Procedure (MPNS–GRASP) and the Expanding Neighborhood Search (ENS) algorithm. Besides these two procedures, the proposed algorithm has, also, two additional main innovative features compared to other Honey Bees Mating Optimization algorithms concerning the crossover operator and the workers. Two sets of benchmark instances are used in order to test the proposed algorithm. The results obtained for both sets are very satisfactory. More specifically, in the fourteen classic instances proposed by Christofides, the average quality is 0.029% and in the second set with the twenty large scale vehicle routing problems the average quality is 0.40%.     

Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.     

A Hybrid Multi-Swarm Particle Swarm Optimization algorithm for the Probabilistic Traveling Salesman Problem

The Probabilistic Traveling Salesman Problem (PTSP) is a variation of the classic Traveling Salesman Problem (TSP) and one of the most significant stochastic routing problems. In the PTSP, only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a new hybrid algorithmic nature inspired approach based on Particle Swarm Optimization (PSO), Greedy Randomized Adaptive Search Procedure (GRASP) and Expanding Neighborhood Search (ENS) Strategy is proposed for the solution of the PTSP. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm, the classic PSO and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in 13 out of 20 cases the proposed algorithm gives a new best solution.     

Honey bees mating optimization algorithm for the Euclidean traveling salesman problem

This paper introduces a new hybrid algorithmic nature inspired approach based on Honey Bees Mating Optimization for successfully solving the Euclidean Traveling Salesman Problem. The proposed algorithm for the solution of the Traveling Salesman Problem, the Honey Bees Mating Optimization (HBMOTSP), combines a Honey Bees Mating Optimization (HBMO) algorithm, the Multiple Phase Neighborhood Search-Greedy Randomized Adaptive Search Procedure (MPNS-GRASP) algorithm and the Expanding Neighborhood Search Strategy. Besides these two procedures, the proposed algorithm has, also, two additional main innovative features compared to other Honey Bees Mating Optimization algorithms concerning the crossover operator and the workers. The main contribution of this paper is that it shows that the HBMO can be used in hybrid synthesis with other metaheuristics for the solution of the TSP with remarkable results both to quality and computational efficiency. The proposed algorithm was tested on a set of 74 benchmark instances from the TSPLIB and in all but eleven instances the best known solution has been found. For the rest instances the quality of the produced solution deviates less than 0.1% from the optimum.     

求解CARPSD问题的自适应局部搜索算法

针对带有随机需求的弧路径规划问题,提出一种自适应局部搜索算法。采用随机路径扫描算法产生初始种群,选出最优者作为初始解,以自适应的方式进行局部搜索,并设计2种局部搜索机制。实验结果表明,与自适应大邻域搜索算法相比,该算法的最优解得到改进,运行时间平均缩短60%。     

求解0-1二次规划问题的迭代禁忌搜索算法

提出迭代禁忌算法求解0-1二次规划问题。在局部搜索过程中,使用禁忌搜索贪心跳坑策略,能够使算法有效跳出局部最优值的陷阱。采用国际上公认的30个算例作为算法测试实验集,与传统的禁忌搜索、模拟退火算法以及混合算法进行比较。实验结果表明,该算法在所有算例上都能够得到文献中报告的最优解,且计算效率明显优于其他算法。     

Solving project scheduling problems with resource constraints via an event list-based evolutionary algorithm

There are various scheduling problems with resource limitations and constraints in the literature that can be modeled as variations of the Resource Constrained Project Scheduling Problem (RCPSP). This paper proposes a new solution representation and an evolutionary algorithm for solving the RCPSP. The representation scheme is based on an ordered list of events, that are sets of activities that start (or finish) at the same time. The proposed solution methodology, namely SAILS, operates on the event list and relies on a scatter search framework. The latter incorporates an Adaptive Iterated Local Search (AILS), as an improvement method, and integrates an event-list based solution combination method. AILS utilizes new enriched neighborhoods, guides the search via a long term memory and applies an efficient perturbation strategy. Computational results on benchmark instances of the literature indicate that both AILS and SAILS produce consistently high quality solutions, while the best results are derived for most problem data sets.     

A Glowworm Swarm Optimization algorithm for the Vehicle Routing Problem with Stochastic Demands

The Glowworm Swarm Optimization (GSO) algorithm is a relatively new swarm intelligence algorithm that simulates the movement of the glowworms in a swarm based on the distance between them and on a luminescent quantity called luciferin. This algorithm has been proven very efficient in the problems that has been applied. However, there is no application of this algorithm, at least to our knowledge, in routing type problems. In this paper, this nature inspired algorithm is used in a hybrid scheme (denoted as Combinatorial Neighborhood Topology Glowworm Swarm Optimization (CNTGSO)) with other metaheuristic algorithms (Variable Neighborhood Search (VNS) algorithm and Path Relinking (PR) algorithm) for successfully solving the Vehicle Routing Problem with Stochastic Demands. The major challenge is to prove that the proposed algorithm could efficiently be applied in a difficult combinatorial optimization problem as most of the applications of the GSO algorithm concern solutions of continuous optimization problems. Thus, two different solution vectors are used, the one in the continuous space (which is updated as in the classic GSO algorithm) and the other in the discrete space and it represents the path representation of the route and is updated using Combinatorial Neighborhood Topology technique. A migration (restart) phase is, also, applied in order to replace not promising solutions and to exchange information between solutions that are in different places in the solution space. Finally, a VNS strategy is used in order to improve each glowworm separately. The algorithm is tested in two problems, the Capacitated Vehicle Routing Problem and the Vehicle Routing Problem with Stochastic Demands in a number of sets of benchmark instances giving competitive and in some instances better results compared to other algorithms from the literature.     

Variable Neighborhood Search based algorithms for high school timetabling

This work presents the application of Variable Neighborhood Search (VNS) based algorithms to the High School Timetabling Problem. The addressed model of the problem was proposed by the Third International Timetabling Competition (ITC 2011), which released many instances from educational institutions around the world and attracted 17 competitors. Some of the VNS algorithm variants were able to outperform the winner of Third ITC solver, which proposed a Simulated Annealing – Iterated local Search approach. This result coupled with another reports in the literature points that VNS based algorithms are a practical solution method for providing high quality solutions for some hard timetabling problems. Moreover they are easy to implement with few parameters to adjust.     

A hybrid clonal selection algorithm for the location routing problem with stochastic demands

In this paper, a new formulation of the Location Routing Problem with Stochastic Demands is presented. The problem is treated as a two phase problem where in the first phase it is determined which depots will be opened and which customers will be assigned to them while in the second phase, for each of the open depots a Vehicle Routing Problem with Stochastic Demands is solved. For the solution of the problem a Hybrid Clonal Selection Algorithm is applied, where, in the two basic phases of the Clonal Selection Algorithm, a Variable Neighborhood Search algorithm and an Iterated Local Search algorithm respectively have been utilized. As there are no benchmark instances in the literature for this form of the problem, a number of new test instances have been created based on instances of the Capacitated Location Routing Problem. The algorithm is compared with both other variants of the Clonal Selection Algorithm and other evolutionary algorithms.     

求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法

针对单一机制的自适应大邻域搜索算法存在早熟收敛、易陷入局部最优的问题,提出了一种混合自适应大邻域搜索算法来求解冷链物流时间依赖型车辆路径问题（TDVRP）。首先,根据连续型行驶时间依赖函数来刻画时变车速,采用综合油耗模型来评估实时燃油消耗量,并建立了以总成本最小化为目标的路径优化模型;然后,根据问题的NP-hard性质和时间依赖特性设计了多种破坏和修复解的大邻域搜索算子,并将破坏-修复大邻域搜索算子融入到人工蜂群（ABC）算法之中,以提高算法的全局搜索能力。仿真实验结果表明,与自适应可变邻域搜索精英蚁群（AVNS_EAC）算法、自适应大邻域搜索精英蚁群（ALNS_EAC）算法、自适应大邻域搜索精英遗传（ALNS_EG）算法和自适应大邻域搜索模拟退火（ALNS_SA）算法相比,所提出的自适应大邻域搜索人工蜂群（ALNS_ABC）算法在多组测试数据上的最优适应度值分别平均提高了46.3%、5.3%、36.8%和6%。可见所提算法计算性能更高、稳定性更强,能够为冷链物流企业兼顾经济效益和环境效益提供更为合理的决策依据。     

Reactive Search strategies using Reinforcement Learning,local search algorithms and Variable Neighborhood Search

Optimization techniques known as metaheuristics have been applied successfully to solve different problems, in which their development is characterized by the appropriate selection of parameters (values) for its execution. Where the adjustment of a parameter is required, this parameter will be tested until viable results are obtained. Normally, such adjustments are made by the developer deploying the metaheuristic. The quality of the results of a test instance [The term instance is used to refer to the assignment of values to the input variables of a problem.] will not be transferred to the instances that were not tested yet and its feedback may require a slow process of “trial and error” where the algorithm has to be adjusted for a specific application. Within this context of metaheuristics the Reactive Search emerged defending the integration of machine learning within heuristic searches for solving complex optimization problems. Based in the integration that the Reactive Search proposes between machine learning and metaheuristics, emerged the idea of putting Reinforcement Learning, more specifically the Q-learning algorithm with a reactive behavior, to select which local search is the most appropriate in a given time of a search, to succeed another local search that can not improve the current solution in the VNS metaheuristic. In this work we propose a reactive implementation using Reinforcement Learning for the self-tuning of the implemented algorithm, applied to the Symmetric Travelling Salesman Problem.     

Multi-objective genetic local search algorithm using Kohonen’s neural map

Genetic Algorithms (GAs) are population based global search methods that can escape from local optima traps and find the global optima regions. However, near the optimum set their intensification process is often inaccurate. This is because the search strategy of GAs is completely probabilistic. With a random search near the optimum sets, there is a small probability to improve current solution. Another drawback of the GAs is genetic drift. The GAs search process is a black box process and no one knows that which region is being searched by the algorithm and it is possible that GAs search only a small region in the feasible space. On the other hand, GAs usually do not use the existing information about the optimality regions in past iterations.In this paper, a new method called SOM-Based Multi-Objective GA (SBMOGA) is proposed to improve the genetic diversity. In SBMOGA, a grid of neurons use the concept of learning rule of Self-Organizing Map (SOM) supporting by Variable Neighborhood Search (VNS) learn from genetic algorithm improving both local and global search. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm is developed to enhance the local search efficiency in the Evolutionary Algorithms (EAs). The SOM uses a multi-objective learning rule based-on Pareto dominance to train its neurons. The neurons gradually move toward better fitness areas in some trajectories in feasible space. The knowledge of optimum front in past generations is saved in form of trajectories. The final state of the neurons determines a set of new solutions that can be regarded as the probability density distribution function of the high fitness areas in the multi-objective space. The new set of solutions potentially can improve the GAs overall efficiency. In the last section of this paper, the applicability of the proposed algorithm is examined in developing optimal policies for a real world multi-objective multi-reservoir system which is a non-linear, non-convex, multi-objective optimization problem.     

Hybrid metaheuristics for the Clustered Vehicle Routing Problem

The Clustered Vehicle Routing Problem (CluVRP) is a variant of the Capacitated Vehicle Routing Problem in which customers are grouped into clusters. Each cluster has to be visited once, and a vehicle entering a cluster cannot leave it until all customers have been visited. This paper presents two alternative hybrid metaheuristic algorithms for the CluVRP. The first algorithm is based on an Iterated Local Search algorithm, in which only feasible solutions are explored and problem-specific local search moves are utilized. The second algorithm is a hybrid genetic search, for which the shortest Hamiltonian path between each pair of vertices within each cluster should be precomputed. Using this information, a sequence of clusters can be used as a solution representation and large neighborhoods can be efficiently explored, by means of bi-directional dynamic programming, sequence concatenation, and appropriate data structures. Extensive computational experiments are performed on benchmark instances from the literature, as well as new large scale instances. Recommendations on the choice of algorithm are provided, based on average cluster size.     

Effective local search algorithms for high school timetabling problems

This paper addresses the high school timetabling problem. The problem consists in building weekly timetables for meetings between classes and teachers with the goal of minimizing violations of specific requirements. In the last decades, several mixed-integer programs have been proposed and tested for this family of problems. However, medium and large size instances are still not effectively solved by these programs using state-of-the-art solvers and the scientific community has given special attention to the devising of alternative soft computing algorithms. In this paper, we propose a soft computing approach based on Iterated Local Search and Variable Neighborhood Search metaheuristic frameworks. Our algorithms incorporate new neighborhood structures and local search routines to perform an effective search. We validated the proposed algorithms on variants of the problem using seven public instances and a new dataset with 34 real-world instances including large cases. The results demonstrate that the proposed algorithms outperform the state-of-the-art approaches in both cases, finding the best solutions in 38 out of the 41 tested instances.     

Solving a bus driver scheduling problem with randomized multistart heuristics

We proposed several hybridizations of Reactive GRASP (Greedy Randomized Adaptive Search Procedure) with Path‐Relinking (PR) and Variable Neighborhood Search to determine high‐quality solutions for a Bus Driver Scheduling Problem (BDSP) under special constraints imposed by Italian transportation rules and mathematical statement originated by our collaboration with PluService Srl, leading Italian group in software for transportation companies. Experimental results are reported for all different proposed techniques that have been tested both on Italian real‐world instances and random instances described and used by Huisman et al. (2005).     

一种求解旅行商问题的混合路径重连算法

提出一种求解旅行商问题的新型混合路径重连算法,将贪婪随机自适应搜索方法的构建机制引入到路径重连算法中,从而在搜索过程中同时考虑解的质量及分散性。在重连过程中,将向导解的属性逐步引入到起始解属性中,以快速获得该线路上的最优解,并采用动态更新参考集策略加快收敛速度。实验结果表明,该算法的解质量优于其他算法。     

自适应动态邻域布谷鸟混合算法求解TSP问题

针对离散布谷鸟算法求解旅行商问题时邻域搜索效率低和易陷入局部最优解等问题,提出了一种自适应动态邻域布谷鸟混合算法（Adaptive Dynamic Neighborhood Hybrid Cuckoo Search algorithm,ADNHCS）。为了提升邻域搜索效率,设计了一种圆限定突变的动态邻域结构来降低经典算法的随机性;此外,提出了可根据迭代过程进行自适应参数调整的策略,并结合禁忌搜索算法来提升全局寻优的能力。使用MATLAB和标准TSPLIB数据库中的若干经典算例对算法性能进行了实验仿真,结果表明与其他基于布谷鸟算法、经典和新型群智能优化算法相比,ADNHCS算法在全局寻优能力以及稳定性方面表现更优。     

新颖的阻塞流水车间调度量子差分进化算法

针对阻塞流水车间调度问题(BFSP),提出了一种新颖的量子差分进化(NQDE)算法,用于最小化最大完工时间。该算法将量子进化算法(QEA)与差分进化(DE)相结合,设计一种新颖的量子旋转机制控制种群进化方向,增强种群多样性;采用高效的基于变邻域搜索的量子进化算法(QEA-VNS)协同进化策略增强算法的全局搜索能力,进一步提高解的质量。基于Taillard's benchmark实例仿真,结果表明,所提算法在最优解数量上明显高于目前较好的启发式算法--INEH,改进了110个实例中64个实例的当前最优解;在性能上也优于目前有效的元启发式算法--新型蛙跳算法(NMSFLA)和混合量子差分进化(HQDE),产生最优解的平均百分比偏差(ARPD)均下降约6%。NQDE算法适合大规模阻塞流水车间调度问题。     

爆炸搜索算法及其收敛性证明

受烟花(炸弹)爆炸的启发,结合经典优化算法提出了一种新的智能优化算法—爆炸搜索算法(Explosion Search Algorithm, ESA) 。ESA引入部域搜索的思想,将智能优化算法与下降搜索算法进行有机结合,使得ESA具有强大的局部搜索能力和全局搜索能力以及好的收敛精度。对算法的收敛性进行了证明,最后通过对benchmark函数集进行仿真并同其他算法进行比较,验证了ESA的高效性。