A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem

We are concerned with the exact solution of a graph optimization problem known as minimum linear arrangement (MinLA). Define the length of each edge of a graph with respect to a linear ordering of the graph vertices. Then, the MinLA problem asks for a vertex ordering that minimizes the sum of edge lengths. MinLA has several practical applications and is NP-Hard. We present a mixed 0-1 linear programming formulation of the problem, which led to fast optimal solutions for dense graphs of sizes up to n = 23.     

A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems

This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.     

Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem

This paper presents a highly effective reinforcement learning enhancement of multi-neighborhood tabu search for the max-mean dispersion problem. The reinforcement learning component uses the Q-learning mechanism that incorporates the accumulated feedback information collected from the actions performed during the search to guide the generation of diversified solutions. The tabu search component employs 1-flip and reduced 2-flip neighborhoods to collaboratively perform the neighborhood exploration for attaining high-quality local optima. A learning automata method is integrated in tabu search to adaptively determine the probability of selecting each neighborhood. Computational experiments on 80 challenging benchmark instances demonstrate that the proposed algorithm is favorably competitive with the state-of-the-art algorithms in the literature, by finding new lower bounds for 3 instances and matching the best known results for the other instances. Key elements and properties are also analyzed to disclose the source of the benefits of our integration of learning mechanisms and tabu search.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

Metaheuristics for the linear ordering problem with cumulative costs

The linear ordering problem with cumulative costs (LOPCC) is a variant of the well-known linear ordering problem, in which a cumulative propagation makes the objective function highly non-linear. The LOPCC has been recently introduced in the context of mobile-phone telecommunications. In this paper we propose two metaheuristic methods for this NP-hard problem. The first one is based on the GRASP methodology, while the second one implements an Iterated Greedy-Strategic Oscillation procedure. We also propose a post-processing based on Path Relinking to obtain improved outcomes. We compare our methods with the state-of-the-art procedures on a set of 218 previously reported instances. The comparison favors the Iterated Greedy - Strategic Oscillation with the Path Relinking post-processing, which is able to identify 87 new best objective function values.     

Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem

We consider the generalized version of the classical Minimum Spanning Tree problem where the nodes of a graph are partitioned into clusters and exactly one node from each cluster must be connected. We present a Variable Neighborhood Search (VNS) approach which uses three different neighborhood types. Two of them work in complementary ways in order to maximize search effectivity. Both are large in the sense that they contain exponentially many candidate solutions, but efficient polynomial-time algorithms are used to identify best neighbors. For the third neighborhood type we apply Mixed Integer Programming to optimize local parts within candidate solution trees. Tests on Euclidean and random instances with up to 1280 nodes indicate especially on instances with many nodes per cluster significant advantages over previously published metaheuristic approaches. This work is supported by the RTN ADONET under grant 504438.     

Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naïve ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for this problem. The constructive method can be coupled with a local search procedure or a short-term tabu search for improved outcomes. Extensive computational experiments with medium and large instances show that the proposed procedure outperforms the best heuristics reported in the literature within short computational times.     

Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem

This paper studies heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree using edges that are as similar as possible. Given an undirected labelled connected graph, the minimum labelling spanning tree problem seeks a spanning tree whose edges have the smallest number of distinct labels. This problem has been shown to be NP-hard. A Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighbourhood Search (VNS) are proposed in this paper. They are compared with other algorithms recommended in the literature: the Modified Genetic Algorithm and the Pilot Method. Nonparametric statistical tests show that the heuristics based on GRASP and VNS outperform the other algorithms tested. Furthermore, a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristics.     

Intelligent variable neighbourhood search for the minimum labelling spanning tree problem

Given a connected, undirected graph whose edges are labelled (or coloured), the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours). In recent work, the MLST problem has been shown to be NP-hard and some effective heuristics have been proposed and analyzed. In a currently ongoing project, we investigate an intelligent optimization algorithm to solve the problem. It is obtained by the basic Variable Neighbourhood Search heuristic with the integration of other complements from machine learning, statistics and experimental algorithmics, in order to produce high-quality performance and to completely automate the resulting optimization strategy. Computational experiments show that the proposed metaheuristic has high-quality performance for the MLST problem and it is able to obtain optimal or near-optimal solutions in short computational running time.     

Variable neighbourhood search for bandwidth reduction

The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix which keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents a non-zero element of the matrix. We propose a variable neighbourhood search based heuristic for reducing the bandwidth of a matrix which successfully combines several recent ideas from the literature. Empirical results for an often used collection of 113 benchmark instances indicate that the proposed heuristic compares favourably to all previous methods. Moreover, with our approach, we improve best solutions in 50% of instances of large benchmark tests.     

Local search for the minimum label spanning tree problem with bounded color classes

In the Minimum Label Spanning Tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most r times in the input graph. This special case is polynomially solvable for r=2, and NP- and APX-complete for any fixed r?3.We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k=2 any local optimum yields an (r+1)/2-approximation of the global optimum, and that this bound is tight. For every k?3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.     

A guided local search metaheuristic for the team orienteering problem

In the team orienteering problem (TOP) a set of locations is given, each with a score. The goal is to determine a fixed number of routes, limited in length, that visit some locations and maximise the sum of the collected scores. This paper describes an algorithm that combines different local search heuristics to solve the TOP. Guided local search (GLS) is used to improve two of the proposed heuristics. An extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space. The algorithm is compared with the best known heuristics of the literature and applied on a large problem set. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. Applying GLS to solve the TOP appears to be a very promising technique. Furthermore, the usefulness of exploring more areas of the solution space is clearly demonstrated.     

A variable neighbourhood search algorithm for the open vehicle routing problem

In the open vehicle routing problem (OVRP), the objective is to minimise the number of vehicles and then minimise the total distance (or time) travelled. Each route starts at the depot and ends at a customer, visiting a number of customers, each once, en route, without returning to the depot. The demand of each customer must be completely fulfilled by a single vehicle. The total demand serviced by each vehicle must not exceed vehicle capacity. Additionally, in one variant of the problem, the travel time of each vehicle should not exceed an upper limit.     

General solutions to the single vehicle routing problem with pickups and deliveries

The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice.     

Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem

This paper focuses on introducing a concept of diversified local search strategy under the scatter search framework for the probabilistic traveling salesman problem (PTSP). Different combinations of three commonly used local search methods in the PTSP, i.e., 1-shift, 2-opt, and 3-opt, were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on randomly generated test instances. The numerical results and the permutation test showed that the diversified local search strategy, especially by combining 1-shift and 2-opt algorithms, can most effectively solve the homogeneous and heterogeneous PTSP in most of the tested instances in comparison with the single local search strategy under scatter search framework.     

Local search methods for the flowshop scheduling problem with flowtime minimization

Flowshop scheduling is a very active research area. This problem still attracts a considerable amount of interest despite the sheer amount of available results. Total flowtime minimization of a flowshop has been actively studied and many effective algorithms have been proposed in the last few years. New best solutions have been found for common benchmarks at a rapid pace. However, these improvements many times come at the cost of sophisticated algorithms. Complex methods hinder potential applications and are difficult to extend to small problem variations. Replicability of results is also a challenge. In this paper, we examine simple and easy to implement methods that at the same time result in state-of-the-art performance. The first two proposed methods are based on the well known Iterated Local Search (ILS) and Iterated Greedy (IG) frameworks, which have been applied with great success to other flowshop problems. Additionally, we present extensions of these methods that work over populations, something that we refer to as population-based ILS (pILS) and population-based IG (pIGA), respectively. We calibrate the presented algorithms by means of the Design of Experiments (DOE) approach. Extensive comparative evaluations are carried out against the most recent techniques for the considered problem in the literature. The results of a comprehensive computational and statistical analysis show that the presented algorithms are very effective. Furthermore, we show that, despite their simplicity, the presented methods are able to improve 12 out of 120 best known solutions of Taillard’s flowshop benchmark with total flowtime criterion.     

A note on the minimum interval cost flow problem

We reduce the problem of minimum interval cost flow problem (MICFP) introduced by Hashemi et al. (2006) to the well-known minimum cost flow problem (MCFP).     

Local search for the undirected capacitated arc routing problem with profits

This paper deals with a recently introduced routing problem variant called the undirected capacitated arc routing problem with profits (UCARPP). The UCARPP model considered in the present study is primarily aimed at generating the route set which maximizes the profit collected from a set of potential customers, represented by edges of the examined transportation network. The secondary objective is to minimize the total route travel time. The generated routes are subject both to capacity and travel time constraints. To tackle the examined problem, we propose a local search metaheuristic development which explores two solution neighborhood structures. The conducted search is effectively diversified by means of the promises concept which is based on the aspiration criteria used in tabu search approaches. The proposed algorithm was tested on UCARPP benchmark instances taken from the literature. It efficiently produced high-quality results, improving several previously best known solutions.     

Variable neighborhood search for minimum sum-of-squares clustering on networks

Euclidean Minimum Sum-of-Squares Clustering amounts to finding p prototypes by minimizing the sum of the squared Euclidean distances from a set of points to their closest prototype. In recent years related clustering problems have been extensively analyzed under the assumption that the space is a network, and not any more the Euclidean space. This allows one to properly address community detection problems, of significant relevance in diverse phenomena in biological, technological and social systems. However, the problem of minimizing the sum of squared distances on networks have not yet been addressed. Two versions of the problem are possible: either the p prototypes are sought among the set of nodes of the network, or also points along edges are taken into account as possible prototypes. While the first problem is transformed into a classical discrete p-median problem, the latter is new in the literature, and solved in this paper with the Variable Neighborhood Search heuristic. The solutions of the two problems are compared in a series of test examples.