A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming

The conventional unconstrained binary quadratic programming (UBQP) problem is known to be a unified modeling and solution framework for many combinatorial optimization problems. This paper extends the single-objective UBQP to the multiobjective case (mUBQP) where multiple objectives are to be optimized simultaneously. We propose a hybrid metaheuristic which combines an elitist evolutionary multiobjective optimization algorithm and a state-of-the-art single-objective tabu search procedure by using an achievement scalarizing function. Finally, we define a formal model to generate mUBQP instances and validate the performance of the proposed approach in obtaining competitive results on large-size mUBQP instances with two and three objectives.     

Pharmacy duty scheduling problem

In this study, we define the pharmacy duty scheduling problem, which requires a subset of pharmacies to be on duty on national holidays, at weekends, and at nights, in order to be able to satisfy the emergency medicine needs. We model the pharmacy duty scheduling problem as a multiperiod p‐median problem with special side constraints, and analyze the computational complexity. We propose a Tabu Search heuristic and develop lower bound (LB) algorithms. We test the performance of mathematical models, Tabu Search heuristic, and the LBs on randomly generated instances. We analyze the current system in ?zmir, the third largest city in Turkey, with a population of 3.5 million, and apply solution methods. Our results show that the proposed Tabu Search algorithm suggests improvements on the current system.     

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.     

Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem

Greedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used.     

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.     

极小化时间表长的无等待流水车间调度

针对以时间表长最小为目标函数的无等待流水车间（No-Wait Flow Shop,NWFS）调度问题,提出了一个混合禁忌搜索算法（Hybrid Taboo Search,HTS）,以启发式算法产生的解作为初始解,通过禁忌搜索进一步提高解的质量。大量随机产生实例的实验结果表明：提出的HTS算法在总体性能上优于经典的RAJ、VNS和GASA算法,因此该算法具有可行性和优越性。     

Designing bijective S-boxes using Algorithm Portfolios with limited time budgets

Substitution boxes (S-boxes) are essential parts of symmetric-key cryptosystems. Designing S-boxes with satisfactory nonlinearity and autocorrelation properties is a challenging task for both theoretical algebraic methods and computational optimization algorithms. Algorithm Portfolios (APs) are algorithmic schemes where multiple copies of the same algorithm or different algorithms share the available computational resources, running concurrently or interchangeably on a number of processors. Recently, APs have gained increasing attention due to their remarkable efficiency in multidisciplinary applications. The present work is a preliminary study of parallel APs on the bijective S-boxes design problem. The proposed APs comprise two state-of-the-art heuristic algorithms, namely Simulated Annealing and Tabu Search, and they are parallelized according to the master-slave model without exchange of information among the constituent algorithms. The proposed APs are experimentally assessed on typical problem instances under limited time budgets. Different aspects of their performance is analyzed, suggesting that the considered APs are competitive in terms of solution quality and running time against their constituent algorithms as well as different approaches.     

Multistart Iterated Tabu Search for Bandwidth Coloring Problem

This paper presents a Multistart Iterated Tabu Search (MITS) algorithm for solving Bandwidth Coloring Problem (BCP) and Bandwidth MultiColoring Problem (BMCP). The proposed MITS algorithm exhibits several distinguishing features, such as integrating an Iterated Tabu Search (ITS) algorithm with a multistart method and a problem specific perturbation operator. Tested on two sets of 66 public benchmark instances widely used in the literature, the MITS algorithm achieves highly competitive results compared with the best performing algorithms, improving the previous best known results for 22 instances while matching the previous best known results for 39 ones. Furthermore, two important features of the proposed algorithm are analyzed.     

An effective GRASP and tabu search for the 0–1 quadratic knapsack problem

As a generalization of the classical 0-1 knapsack problem, the 0-1 Quadratic Knapsack Problem (QKP) that maximizes a quadratic objective function subject to a linear capacity constraint is NP-hard in strong sense. In this paper, we propose a memory based Greedy Randomized Adaptive Search Procedures (GRASP) and a tabu search algorithm to find near optimal solution for the QKP. Computational experiments on benchmarks and on randomly generated instances demonstrate the effectiveness and the efficiency of the proposed algorithms, which outperforms the current state-of-the-art heuristic Mini-Swarm in computational time and in the probability to achieve optimal solutions. Numerical results on large-sized instances with up to 2000 binary variables have also been reported.     

Iterated Local Search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness

We present an Iterated Local Search (ILS) algorithm for solving the single-machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness. The proposed ILS algorithm exhibits several distinguishing features, including a new neighborhood structure called Block Move and a fast incremental evaluation technique, for evaluating neighborhood solutions. Applying the proposed algorithm to solve 120 public benchmark instances widely used in the literature, we achieve highly competitive results compared with a recently proposed exact algorithm and five sets of best solutions of state-of-the-art metaheuristic algorithms in the literature. Specifically, ILS obtains the optimal solutions for 113 instances within a reasonable time, and it outperforms the previous best-known results obtained by metaheuristic algorithms for 34 instances and matches the best results for 82 instances. In addition, ILS is able to obtain the optimal solutions for the remaining seven instances under a relaxed time limit, and its computational efficiency is comparable with the state-of-the-art exact algorithm by Tanaka and Araki (Comput Oper Res 40:344–352, 2013). Finally, on analyzing some important features that affect the performance of ILS, we ascertain the significance of the proposed Block Move neighborhood and the fast incremental evaluation technique.     

Lower and upper bounds for the two-echelon capacitated location-routing problem

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.     

Combining tabu Hopfield network and estimation of distribution for unconstrained binary quadratic programming problem

Unconstrained binary quadratic programming problem (UBQP) consists in maximizing a quadratic 0–1 function. It is a well known NP-hard problem and is considered as a unified model for a variety of combinatorial optimization problems. This paper combines a tabu Hopfield neural network (HNN) (THNN) with estimation of distribution algorithm (EDA), and thus a THNN–EDA is proposed for the UBQP. In the THNN, the tabu rule, instead of the original updating rule of the HNN, is used to govern the state transition or updating of neurons to search for the global minimum of the energy function. A probability vector in EDA model is built to characterize the distribution of promising solutions in the search space, and then the THNN is guided by the global search information in EDA model to search better solution in the promising region. Thus, the short term memory of the tabu mechanism in the THNN cooperates with the long term memory mechanism in the EDA to help the network escape from local minima. The THNN–EDA is tested on 21 UBQP benchmark problems with the size ranging from 3000 to 7000, and 48 maximum cut benchmark problems, a special case of the UBQP, with the size ranging from 512 to 3375. Simulation results show that the THNN–EDA is better than the other HNN based algorithms, and is better than or competitive with metaheuristic algorithms and state-of-the-art algorithms.     

Minimizing weighted earliness–tardiness on parallel machines using hybrid metaheuristics

We consider the problem of scheduling a set of jobs on a set of identical parallel machines where the objective is to minimize the total weighted earliness and tardiness penalties with respect to a common due date. We propose a hybrid heuristic algorithm for constructing good solutions, combining priority rules for assigning jobs to machines and a local search with exact procedures for solving the one-machine subproblems. These solutions are then used in two metaheuristic frameworks, Path Relinking and Scatter Search, to obtain high quality solutions for the problem.The algorithms are tested on a large number of test instances to assess the efficiency of the proposed strategies.The results show that our algorithms consistently outperform the best reported results for this problem.     

Comparing multiobjective swarm intelligence metaheuristics for DNA motif discovery

In recent years, a huge number of biological problems have been successfully addressed through computational techniques, among all these computational techniques we highlight metaheuristics. Also, most of these biological problems are directly related to genomic, studying the microorganisms, plants, and animals genomes. In this work, we solve a DNA sequence analysis problem called Motif Discovery Problem (MDP) by using two novel algorithms based on swarm intelligence: Artificial Bee Colony (ABC) and Gravitational Search Algorithm (GSA). To guide the pattern search to solutions that have a better biological relevance, we have redefined the problem formulation and incorporated several biological constraints that should be satisfied by each solution. One of the most important characteristics of the problem definition is the application of multiobjective optimization (MOO), maximizing three conflicting objectives: motif length, support, and similarity. So, we have adapted our algorithms to the multiobjective context. This paper presents an exhaustive comparison of both multiobjective proposals on instances of different nature: real instances, generic instances, and instances generated according to a Markov chain. To analyze their operations we have used several indicators and statistics, comparing their results with those obtained by standard algorithms in multiobjective computation, and by 14 well-known biological methods.     

Approximate algorithms for the container loading problem

In this paper we develop several algorithms for solving three–dimensional cutting/packing problems. We begin by proposing an adaptation of the approach proposed in Hifi and Ouafi (1997) for solving two–staged unconstrained two–dimensional cutting problems. We show how the algorithm can be polynomially solved for producing a constant approximation ratio. We then extend this algorithm for developing better approximate algorithms. By using hill–climbing strategies, we construct some heuristics which produce a good trade–off between the computational time and the solution quality. The performance of the proposed algorithms is evaluated on different problem instances of the literature, with different sizes and densities (a total of 144 problem instances).     

A tabu search/path relinking algorithm to solve the job shop scheduling problem

We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to generate solutions to the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure to effectively construct a path linking the initiating solution and the guiding solution, and a reference solution determination mechanism based on two kinds of improvement methods. We evaluate the performance of TS/PR on almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains competitive results compared with state-of-the-art algorithms for JSP in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it solves a challenging instance that has remained unsolved for over 20 years.     

A variable neighborhood search algorithm for the surgery tactical planning problem

We address the tactical planning problem of surgeries that consists in building an admission plan of patients over a medium-term horizon planning so as to minimize over and under utilization of several resources such as operating theaters, beds and nursing care, compared with their target level of utilization. The problem is formulated as a mixed integer linear program for which exact solution methods fail to find an optimal solution in a reasonable execution time. We develop a Variable Neighborhood Search algorithm and show its ability to provide high quality solutions in short computational running times compared with CPLEX for numerous real-sized instances based on the surgery planning problem in a Dutch cardiothoracic center. Furthermore, with few parameters' settings and low computational memory requirements, this approach may easily be implemented in a decision support system for hospitals.     

一种用于车间作业调度问题的智能枚举算法

车间作业调度问题是优化组合中一个著名的难题,即使规模不大的算例,优化算法的时间也很长。文章提出了一种求解车间作业调度问题的快速智能枚举算法,选取了22个标准算例作为算法的测试试验集,该算法在较短的时间内找到了17个算例的最优解,试验结果表明智能枚举算法确实是一种快速的、有效的求解车间作业调度问题的近似算法。     

求解最大割问题的多启动禁忌搜索算法

为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索（MSTS）算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。     

两层应急抢修系统选址问题的核搜索算法

提出了用于描述两层应急抢修系统选址问题的0-1整数线性规划模型, 该模型能保证整个应急抢修系统的服务质量。设计了求解该问题的两种核搜索算法, 在两种方法中分别根据原问题的线性松弛和拉格朗日松弛确定原问题的核问题和子问题, 从而大大减小了问题的规模。用提出的算法对56个计算实例进行求解, 算例计算结果表明, 与MOSEK软件直接求解得到的结果进行比较, 基于拉格朗日松弛的核搜索算法可以在相对较短的时间内求得较好的解, 这说明拉格朗日松弛对偶问题的最优解能为求解原问题提供非常有效的信息。