The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems

In the last few years, a significant number of multi-objective metaheuristics have been proposed in the literature in order to address real-world problems. Local search methods play a major role in many of these metaheuristic procedures. In this paper, we adapt a recent and popular indicator-based selection method proposed by Zitzler and Künzli in 2004, in order to define a population-based multi-objective local search. The proposed algorithm is designed in order to be easily adaptable, parameter independent and to have a high convergence rate. In order to evaluate the capacity of our algorithm to reach these goals, a large part of the paper is dedicated to experiments. Three combinatorial optimisation problems are tested: a flow shop problem, a ring star problem and a nurse scheduling problem. The experiments show that our algorithm can be applied with success to different types of multi-objective optimisation problems and that it outperforms some classical metaheuristics. Furthermore, the parameter sensitivity analysis enables us to provide some useful guidelines about how to set the parameters.     

A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP

The difficulty to solve multiple objective combinatorial optimization problems with traditional techniques has urged researchers to look for alternative, better performing approaches for them. Recently, several algorithms have been proposed which are based on the ant colony optimization metaheuristic. In this contribution, the existing algorithms of this kind are reviewed and a proposal of a taxonomy for them is presented. In addition, an empirical analysis is developed by analyzing their performance on several instances of the bi-criteria traveling salesman problem in comparison with two well-known multi-objective genetic algorithms.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

Coupling ant colony systems with strong local searches

Ant colony system is a well known metaheuristic framework, and many efficient algorithms for different combinatorial optimization problems have been derived from this general framework. In this paper some directions for improving the original framework when a strong local search routine is available, are identified. In particular, some modifications able to speed up the method and make it competitive on large problem instances, on which the original framework tends to be weaker, are described. The resulting framework, called Enhanced Ant Colony System is tested on three well-known combinatorial optimization problems arising in the transportation field. Many new best known solutions are retrieved for the benchmarks available for these optimization problems.     

An effective greedy heuristic for the Social Golfer Problem

The Social Golfer Problem (SGP) is a combinatorial optimization problem that exhibits a lot of symmetry and has recently attracted significant attention. In this paper, we present a new greedy heuristic for the SGP, based on the intuitive concept of freedom among players. We use this heuristic in a complete backtracking search, and match the best current results of constraint solvers for several SGP instances with a much simpler method. We then use the main idea of the heuristic to construct initial configurations for a metaheuristic approach, and show that this significantly improves results obtained by local search alone. In particular, our method is the first metaheuristic technique that can solve the original problem instance optimally. We show that our approach is also highly competitive with other metaheuristic and constraint-based methods on many other benchmark instances from the literature.     

Iterated greedy for the maximum diversity problem

The problem of choosing a subset of elements with maximum diversity from a given set is known as the maximum diversity problem. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we present a simple iterated greedy metaheuristic that generates a sequence of solutions by iterating over a greedy construction heuristic using destruction and construction phases. Extensive computational experiments reveal that the proposed algorithm is highly effective as compared to the best-so-far metaheuristics for the problem under consideration.     

Hybrid multi-objective Bayesian estimation of distribution algorithm: a comparative analysis for the multi-objective knapsack problem

Nowadays, a number of metaheuristics have been developed for efficiently solving multi-objective optimization problems. Estimation of distribution algorithms are a special class of metaheuristic that intensively apply probabilistic modeling and, as well as local search methods, are widely used to make the search more efficient. In this paper, we apply a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm (HMOBEDA) in multi and many objective scenarios by modeling the joint probability of decision variables, objectives, and the configuration parameters of an embedded local search (LS). We analyze the benefits of the online configuration of LS parameters by comparing the proposed approach with LS off-line versions using instances of the multi-objective knapsack problem with two to five and eight objectives. HMOBEDA is also compared with five advanced evolutionary methods using the same instances. Results show that HMOBEDA outperforms the other approaches including those with off-line configuration. HMOBEDA not only provides the best value for hypervolume indicator and IGD metric in most of the cases, but it also computes a very diverse solutions set close to the estimated Pareto front.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries

This paper deals with a routing problem variant which considers customers to simultaneously require delivery and pick-up services. The examined problem is referred to as the Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries (VRPSPD). VRPSPD is an NP-hard combinatorial optimization problem, practical large-scale instances of which cannot be solved by exact solution methodologies within acceptable computational times. Our interest was therefore focused on metaheuristic solution approaches. In specific, we introduce an Adaptive Memory (AM) algorithmic framework which collects and combines promising solution features to generate high-quality solutions. The proposed strategy employs an innovative memory mechanism to systematically maximize the amount of routing information extracted from the AM, in order to drive the search towards diverse regions of the solution space. Our metaheuristic development was tested on numerous VRPSPD instances involving from 50 to 400 customers. It proved to be rather effective and efficient, as it produced high-quality solutions, requiring limited computational effort. Furthermore, it managed to produce several new best solutions.     

Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows

This work deals with a new combinatorial optimization problem, the two-dimensional loading capacitated vehicle routing problem with time windows which is a realistic extension of the well known vehicle routing problem. The studied problem consists in determining vehicle trips to deliver rectangular objects to a set of customers with known time windows, using a homogeneous fleet of vehicles, while ensuring a feasible loading of each vehicle used. Since it includes NP-hard routing and packing sub-problems, six heuristics are firstly designed to quickly compute good solutions for realistic instances. They are obtained by combining algorithms for the vehicle routing problem with time windows with heuristics for packing rectangles. Then, a Memetic algorithm is developed to improve the heuristic solutions. The quality and the efficiency of the proposed heuristics and metaheuristic are evaluated by adding time windows to a set of 144 instances with 15–255 customers and 15–786 items, designed by Iori et al. (Transport Sci 41:253–264, 2007) for the case without time windows.     

A benchmark library and a comparison of heuristic methods for the linear ordering problem

The linear ordering problem consists of finding an acyclic tournament in a complete weighted digraph of maximum weight. It is one of the classical NP-hard combinatorial optimization problems. This paper surveys a collection of heuristics and metaheuristic algorithms for finding near-optimal solutions and reports about extensive computational experiments with them. We also present the new benchmark library LOLIB which includes all instances previously used for this problem as well as new ones.     

Multi-objective decision analysis for competence-oriented project portfolio selection

This paper develops a multi-objective optimization model for project portfolio selection taking employee competencies and their evolution into account. The objectives can include economic gains as well as gains expressed in terms of aggregated competence increments according to pre-defined profiles. In order to determine Pareto-optimal solutions, the overall problem is decomposed into a master problem addressing the portfolio selection itself, and a slave problem dealing with a suitable assignment of personnel to the work packages of the selected projects over time. We provide an asymptotic approximation of the problem by a linearized formulation, which allows an efficient and exact solution of the slave problem. For the solution of the master problem, we compare the multi-objective metaheuristics NSGA-II and P-ACO. Experimental results both for synthetically generated test instances and for real-world test instances, based on an application case from the E-Commerce Competence Center Austria, are presented.     

Heuristics and metaheuristics for the maximum diversity problem

This paper presents extensive computational experiments to compare 10 heuristics and 20 metaheuristics for the maximum diversity problem (MDP). This problem consists of selecting a subset of maximum diversity from a given set of elements. It arises in a wide range of real-world settings and we can find a large number of studies, in which heuristic and metaheuristic methods are proposed. However, probably due to the fact that this problem has been referenced under different names, we have only found limited comparisons with a few methods on some sets of instances. This paper reviews all the heuristics and metaheuristics for finding near-optimal solutions for the MDP. We present the new benchmark library MDPLIB, which includes most instances previously used for this problem, as well as new ones, giving a total of 315. We also present an exhaustive computational comparison of the 30 methods on the MDPLIB. Non-parametric statistical tests are reported in our study to draw significant conclusions.     

Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic

Metaheuristics represent an important class of techniques to solve, approximately, hard combinatorial optimization problems for which the use of exact methods is impractical. Some researches have been combining machine learning techniques with metaheuristics to adaptively guide and improve the search for near optimal solutions. An example of such development is the DM-GRASP, a hybrid version of the Greedy Randomized Adaptative Search Procedures (GRASP) metaheuristic which incorporates a data mining process. In this hybrid proposal, after executing half of the total number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the optimization problem. These patterns present characteristics of near optimal solutions and can be used to guide the following half GRASP iterations in the search through the solution space. In this work, we explore new versions of the DM-GRASP metaheuristic to experiment, not a single activation, but multiple and adaptive executions of the data mining process during the metaheuristic execution. We also applied the data mining technique into a reactive GRASP to show that a more sophisticated and not memoryless GRASP approach can also benefit from the use of this technique. In order to evaluate these new proposals, we adopted the server replication for reliable multicast problem since the best known results for this problem were obtained by GRASP and DM-GRASP implementations. The computational experiments, comparing traditional GRASP, DM-GRASP, and the new proposals, showed that multiple and adaptive executions of the data mining process can improve the results obtained by the DM-GRASP hybrid metaheuristic—the new proposals were able to find better results in less computational time for the reliable multicast problem.     

Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems

High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requirements. This family of problems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient search of optimal or near-optimal solutions is still a challenge for many problems of practical size. In this paper, we investigate mixed-integer programming formulations and a parallel metaheuristic based algorithm for solving high school timetabling problems with compactness and balancing requirements. We propose two pattern-based formulations and a solution algorithm that simultaneously exploits column generation and a team of metaheuristics to build and improve solutions. Extensive computational experiments conducted with real-world instances demonstrate that our formulations are competitive with the best existing high school timetabling formulations, while our parallel algorithm presents superior performance to alternative methods available in the literature.     

Metaheuristics approach for solving personalized crew rostering problem in public bus transit

The crew rostering problem in public bus transit aims at constructing personalized monthly schedules for all drivers. This problem is often formulated as a multi-objective optimization problem, since it considers the interests of both the management of bus companies and the drivers. Therefore, this paper attempts to solve the multi-objective crew rostering problem with the weighted sum of all objectives using ant colony optimization, simulated annealing, and tabu search methods. To the best of our knowledge, this is the first paper that attempts to solve the personalized crew rostering problem in public transit using different metaheuristics, especially the ant colony optimization. The developed algorithms are tested on numerical real-world instances, and the results are compared with ones solved by commercial solvers.     

A brain storm optimization approach for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a combinatorial optimization problem which aims to minimize the sum of arrival times at customers. This paper presents a brain storm optimization algorithm to solve the CCVRP. Based on the characteristics of the CCVRP, we design new convergent and divergent operations. The convergent operation picks up and perturbs the best-so-far solution. It decomposes the resulting solution into a set of independent partial solutions and then determines a set of subproblems which are smaller CCVRPs. Instead of directly generating solutions for the original problem, the divergent operation selects one of three operators to generate new solutions for subproblems and then assembles a solution to the original problem by using those new solutions to the subproblems. The proposed algorithm was tested on benchmark instances, some of which have more than 560 nodes. The results show that our algorithm is very effective in contrast to the existing algorithms. Most notably, the proposed algorithm can find new best solutions for 8 medium instances and 7 large instances within short time.     

Cárnico-ICSPEA2—A metaheuristic co-evolutionary navigator for a complex co-evolutionary farming system

This paper introduces Cárnico-ICSPEA2, a metaheuristic co-evolutionary navigator designed by its end-user as an aid for the analysis and multi-objective optimisation of a beef cattle enterprise running on temperate pastures and fodder crops in Chalco, Mexico State, in the central plateau of Mexico. By combining simulation routines and a multi-objective evolutionary algorithm with a deterministic and stochastic framework, the software imitates the evolutionary behaviour of the system of interest, helping the farm manager to ‘navigate’ through his system’s dynamic phase space. The ultimate goal was to enhance the manager’s decision-making process and co-evolutionary skills, through an increased understanding of his system and the discovery of new, improved heuristics. This paper describes the numerical simulation and optimisation resulting from the application of Cárnico-ICSPEA2 to solve a specific multi-objective optimisation problem, along with implications for the management of the system of interest.     

Variable neighborhood search: Principles and applications

Systematic change of neighborhood within a possibly randomized local search algorithm yields a simple and effective metaheuristic for combinatorial and global optimization, called variable neighborhood search (VNS). We present a basic scheme for this purpose, which can easily be implemented using any local search algorithm as a subroutine. Its effectiveness is illustrated by solving several classical combinatorial or global optimization problems. Moreover, several extensions are proposed for solving large problem instances: using VNS within the successive approximation method yields a two-level VNS, called variable neighborhood decomposition search (VNDS); modifying the basic scheme to explore easily valleys far from the incumbent solution yields an efficient skewed VNS (SVNS) heuristic. Finally, we show how to stabilize column generation algorithms with help of VNS and discuss various ways to use VNS in graph theory, i.e., to suggest, disprove or give hints on how to prove conjectures, an area where metaheuristics do not appear to have been applied before.     

Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem

The response time variability problem (RTVP) is a scheduling problem with a wide range of real-world applications: mixed-model assembly lines, multi-threaded computer systems, network environments, broadcast of commercial videotapes and machine maintenance, among others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. Since the RTVP is NP-hard, several heuristic and metaheuristic techniques are needed to solve non-small instances. The published metaheuristic procedure that obtained the best solutions, on average, for non-small RTVP instances is an algorithm based on a variant of the variable neighbourhood search (VNS), called Reduced VNS (RVNS). We propose hybridising RVNS with three existing algorithms based on tabu search, multi-start and particle swarm optimisation. The aim is to combine the strengths of the metaheuristics. A computational experiment is carried out and it is shown that, on average, all proposed hybrid methods are able to improve the best published solutions.