The Periodic Vehicle Routing Problem (PVRP) and its variants, extend the well-known Capacitated Vehicle Routing Problem (CVRP) by adding characteristics of real scenarios in the logistic sector. In the PVRP, delivery routes are planned over multiple days, and each customer has to be served on certain days according to pre-specified visit combinations. The goal is to find the minimum cost routes satisfying customer requirements. We address a challenging extension of the PVRP in which each client must be served by the same vehicle (driver) in multiple visits during the planning horizon (driver consistency). The same-driver requirement addresses real-world situations in systems, such as beverage distribution, integrated order delivery, retail merchandising, and healthcare services, where managers seek to foster driver-customer relationships and maintain service quality. We propose several heuristics for the Periodic Capacitated Vehicle Routing Problem with Driver Consistency (PVRP-DC) based on the Variable Neighborhood Search methodology, and test their performance on a set of instances for which high-quality solutions, including optimal values, have been identified. Additionally, we propose a Path Relinking post-processing for improved outcomes. Our experimental testing shows the effectiveness of our heuristics compared with a recently published method as well as with known optimal solutions.

Scatter search (SS) is a well-established metaheuristic for hard combinatorial optimization problems. SS is characterized by its versatility and ease of context adaptation and implementation. Although the literature includes SS parallelization schemes for specific problems, a general parallel framework for scatter search has not been developed and tested. We introduce three SS parallel designs, each focusing on a different task, namely, reducing computational time, increasing search exploration, and balancing search intensification and diversification. The proposed designs are tested on problems where the state of the art is a traditional (sequential) SS approach. This testing platform helps us assess the contributions of the parallel computing strategies to solution speed and quality. Our publicly available code is designed to be adapted to optimization problems that are not considered here. The results show promising avenues for establishing a general framework of SS parallelization. • Several designs for parallelizing scatter search are proposed. • The new parallel designs are tested on three combinatorial optimization problems. • Computational results assess the performance of the parallel designs. • The advantages and disadvantages of each parallel design are discussed.

Abstract In this paper, a new solution method is implemented to solve a bi‐objective variant of the vehicle routing problem that appears in industry and environmental enterprises. The solution involves designing a set of routes for each day in a period, in which the service frequency is a decision variable. The proposed algorithm, a muti‐start multi‐objective local search algorithm (MSMLS), minimizes total emissions produced by all vehicles and maximizes the service quality measured as the number of times that a customer is visited by a vehicle in order to be served. The MSMLS is a neighbourhood‐based metaheuristic that obtains high‐quality solutions and that is capable of achieving better performance than other competitive algorithms. Furthermore, the proposed algorithm is able to perform rapid movements thanks to the easy representation of the solutions.

Metaheuristic optimization is at the heart of the intersection between computer science and operations research. The INFORMS Journal of Computing has been fundamental in advancing the ideas behind metaheuristic methodologies. Fred Glover’s “Tabu Search—Part I” was published more than 30 years ago in the first volume of the then ORSA Journal on Computing. This article, one of the most cited in the area of heuristic optimization, paved the way for many contributions to the methodology and practice of operations research. As a continuation of this stream of research, we describe a new scatter search design for multiobjective optimization. The design includes a short-term memory tabu search and a path relinking combination method. We show how the strategies and mechanisms within scatter search and tabu search can be combined to produce a highly effective approach to multiobjective optimization.

We study the problem of minimizing the profile of a graph and develop a solution method by following the tenets of scatter search. Our procedure exploits the network structure of the problem and includes strategies that produce a computationally efficient and agile search. Among several mechanisms, our search includes path relinking as the basis for combining solutions to generate new ones. The profile minimization problem (PMP) is NP‐Hard and has relevant applications in numerical analysis techniques that rely on manipulating large sparse matrices. The problem was proposed in the early 1970s but the state‐of‐the‐art does not include a method that could be considered powerful by today's computing standards. Extensive computational experiments show that we have accomplished our goal of pushing the envelope and establishing a new standard in the solution of the PMP. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 10–21. 2015

Metaheuristic approaches based on the neighborhood search escape local optimality by applying predefined rules and constraints, such as tabu restrictions (in tabu search), acceptance criteria (in simulated annealing), and shaking (in variable neighborhood search). We propose a general approach that attempts to learn (off-line) the guiding constraints that, when applied online, will result in effective escape directions from local optima. Given a class of problems, the learning process is performed off-line, and the results are applied to constrained neighborhood searches to guide the solution process out of local optimality. Computational results on the constrained task allocation problem show that adding these guiding constraints to a simple tabu search improves the quality of the solutions found, making the overall method competitive with state-of-the-art methods for this class of problems. We also present a second set of tests on the matrix bandwidth minimization problem.

Drug discovery is the process of designing compounds that have desirable properties, such as activity and nontoxicity. Molecule classification techniques are used along with this process to predict the properties of the compounds to expedite their testing. Ideally, the classification rules found should be accurate and reveal novel chemical properties, but current molecule representation techniques lead to less-than-adequate accuracy and knowledge discovery. This work extends the propositionalization approach recently proposed for multirelational data mining in two ways: it generates expressive attributes exhaustively, and it uses randomization to sample a limited set of complex (“deep”) attributes. Our experimental tests show that the procedure is able to generate meaningful and interpretable attributes from molecular structural data, and that these features are effective for classification purposes.

The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity problem to increase diversity in the reference set, (2) a dynamic adjustment of a key parameter within the search, and (3) the adaptive selection of a combination method. We perform extensive computational experiments to first study the effect of changes in critical scatter-search elements and then to compare the efficiency of our proposal with previous solution procedures.

A fertile complementarity exists between scatter search (SS) and particle swarm optimization (PSO). Shared and contrasting principles underlying these methods provide a fertile basis for combining them to create a hybrid method. We identify a specific hybrid, Scatter PSO, giving rise to two variants that prove more effective than the constriction factor model of PSO. Applied to finding global minima for continuous nonlinear functions, Scatter PSO not only is able to obtain better solutions to a widely used set of benchmark functions, but also proves more robust under a variety of experimental conditions.

We describe the development and testing of a metaheuristic procedure, based on the scatter-search methodology, for the problem of approximating the efficient frontier of nonlinear multiobjective optimization problems with continuous variables. Recent applications of scatter search have shown its merit as a global optimization technique for single-objective problems. However, the application of scatter search to multiobjective optimization problems has not been fully explored in the literature. We test the proposed procedure on a suite of problems that have been used extensively in multiobjective optimization. Additional tests are performed on instances that are an extension of those considered classic. The tests indicate that our adaptation of scatter search is a viable alternative for multiobjective optimization.

In this paper, we develop a general-purpose heuristic for permutations problems. The procedure is based on the scatter-search and tabu-search methodologies and treats the objective-function evaluation as a black box, making the search algorithm context-independent. Therefore, our main contribution consists of the development and testing of a procedure that uses no knowledge from the problem context to search for the optimal solution. We perform computational experiments with four well-known permutation problems to study the efficiency and effectiveness of the proposed method. These experiments include a comparison with two commercially available software packages that are also based on meta-heuristic optimization technology and allow solutions to be represented as permutations.

Abstract Cost reduction is a major concern when designing optical fiber networks. Multiwavelength optical devices are new technology for increasing the capacity of fiber networks while reducing costs, when compared to installing traditional (e.g., SONET) equipment and new fiber. In this article we discuss the development of a metaheuristic method that seeks to optimize the location of Wavelength Division Multiplexing (WDM) and Optical Crossconnect (OXC) equipment in fiber networks. The procedure combines ideas from the scatter search, tabu search, and multistart methodologies. Computational experiments with both real‐world and artificial data show the effectiveness of the proposed procedure. The experiments include a comparison with a permutation‐based approach and with lower bounds generated with CPLEX. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 199–209 2005

In this article, we develop a greedy randomized adaptive search procedure (GRASP) for the problem of minimizing straight line crossings in a 2-layer graph. The procedure is fast and is particularly appealing when dealing with low-density graphs. When a modest increase in computational time is allowed, the procedure may be coupled with a path relinking strategy to search for improved outcomes. Although the principles of path relinking have appeared in the tabu search literature, this search strategy has not been fully implemented and tested. We perform extensive computational experiments with more than 3,000 graph instances to first study the effect of changes in critical search parameters and then to compare the efficiency of alternative solution procedures. Our results indicate that graph density is a major influential factor on the performance of a solution procedure.