GRASP and path relinking for the matrix bandwidth minimization

In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the non-zero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a path relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with path relinking is also found to be competitive with a recently published Tabu search algorithm that is considered one of the best currently available for bandwidth minimization.     

Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking

The two-echelon location-routing problem (LRP-2E) arises from recent transportation applications like city logistics. In this problem, still seldom studied, first-level trips serve from a main depot a set of satellite depots, which must be located, while second-level trips visit customers from these satellites. After a literature review on the LRP-2E, we present four constructive heuristics and a hybrid metaheuristic: A greedy randomized adaptive search procedure (GRASP) complemented by a learning process (LP) and path relinking (PR). The GRASP and learning process involve three greedy randomized heuristics to generate trial solutions and two variable neighbourhood descent (VND) procedures to improve them. The optional path relinking adds a memory mechanism by combining intensification strategy and post-optimization. Numerical tests show that the GRASP with LP and PR outperforms the simple heuristics and an adaptation of a matheuristic initially published for a particular case, the capacitated location-routing problem (CLRP). Additional tests on the CLRP indicate that the best GRASP competes with the best metaheuristics published.     

Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach

This paper deals with the problem of scheduling jobs in uniform parallel machines with sequence-dependent setup times in order to minimize the total tardiness relative to job due dates. We propose GRASP versions that incorporate adaptive memory principles for solving this problem. Long-term memory is used in the construction of an initial solution and in a post-optimization procedure which connects high quality local optima by means of path relinking. Computational tests are carried out on a set of benchmark instances and the proposed GRASP versions are compared with heuristic methods from the literature.     

Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

This paper addresses the problem of scheduling jobs in a single machine with sequence dependent setup times in order to minimize the total tardiness with respect to job due dates. We propose variants of the GRASP metaheuristic that incorporate memory-based mechanisms for solving this problem. There are two mechanisms proposed in the literature that utilize a long-term memory composed of an elite set of high quality and sufficiently distant solutions. The first mechanism consists of extracting attributes from the elite solutions in order to influence the construction of an initial solution. The second one makes use of path relinking to connect a GRASP local minimum with a solution of the elite set, and also to connect solutions from the elite set. Reactive GRASP, which probabilistically determines the degree of randomness in the GRASP construction throughout the iterations, is also investigated. Computational tests for instances involving up to 150 jobs are reported, and the proposed method is compared with heuristic and exact methods from the literature.     

Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design

In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems.     

A reactive GRASP with path relinking for capacitated clustering

This paper presents a greedy randomized adaptive search procedure (GRASP) coupled with path relinking (PR) to solve the problem of clustering n nodes in a graph into p clusters. The objective is to maximize the sum of the edge weights within each cluster such that the sum of the corresponding node weights does not exceed a fixed capacity. In phase I, both a heaviest weight edge (HWE) algorithm and a constrained minimum cut algorithm are used to select seeds for initializing the p clusters. Feasible solutions are obtained with the help of a self-adjusting restricted candidate list that sequentially guides the assignment of the remaining nodes. At each major GRASP iteration, the list length is randomly set based on a probability density function that is updated dynamically to reflect the solution quality realized in past iterations. In phase II, three neighborhoods, each defined by common edge and node swaps, are explored to attain local optimality. The following exploration strategies are investigated: cyclic neighborhood search, variable neighborhood descent, and randomized variable neighborhood descent (RVND). The best solutions found are stored in an elite pool.     

Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem

Path relinking is a method to generate new solution by exploring trajectories that connect high quality solutions. In this paper, a class of new hybrid heuristics are proposed by combining a genetic algorithm and path relinking and applying these to a multiple-level warehouse layout problem. Parallel and series combinations to integrate crossover and mutation operations of a genetic algorithm with path relinking are investigated. We proposed position and sequence based path relinking methods to connect two solutions, which are either elites or ones selected randomly. Extensive experiments are carried out to compare the performance of the new heuristics.     

Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.     

A tabu search heuristic procedure for the capacitated facility location problem

A tabu search heuristic procedure is developed, implemented and computationally tested for the capacitated facility location problem. The procedure uses different memory structures. Visited solutions are stored in a primogenitary linked quad tree. For each facility, the recent move at which the facility changed its status and the frequency it has been open are also stored. These memory structures are used to guide the main search process as well as the diversification and intensification processes. Lower bounds on the decreases of total cost are used to measure the attractiveness of the moves and to select moves in the search process. A specialized network algorithm is developed to exploit the problem structure in solving transportation problems. Criterion altering, solution reconciling and path relinking are used to perform intensification functions. The performance of the procedure is tested through computational experiments using test problems from the literature and new test problems randomly generated. It found optimal solutions for almost all test problems from the literature. As compared to the heuristic method of Lagrangean relaxation with improved subgradient scheme, the tabu search heuristic procedure found much better solutions using much less CPU time.     

Path relinking and GRG for artificial neural networks

Artificial neural networks (ANN) have been widely used for both classification and prediction. This paper is focused on the prediction problem in which an unknown function is approximated. ANNs can be viewed as models of real systems, built by tuning parameters known as weights. In training the net, the problem is to find the weights that optimize its performance (i.e., to minimize the error over the training set). Although the most popular method for training these networks is back propagation, other optimization methods such as tabu search or scatter search have been successfully applied to solve this problem. In this paper we propose a path relinking implementation to solve the neural network training problem. Our method uses GRG, a gradient-based local NLP solver, as an improvement phase, while previous approaches used simpler local optimizers. The experimentation shows that the proposed procedure can compete with the best-known algorithms in terms of solution quality, consuming a reasonable computational effort.     

Hybridized evolutionary local search algorithm for the team orienteering problem with time windows

The orienteering problem (OP) consists in finding an elementary path over a subset of vertices. Each vertex is associated with a profit that is collected on the visitor’s first visit. The objective is to maximize the collected profit with respect to a limit on the path’s length. The team orienteering problem (TOP) is an extension of the OP where a fixed number m of paths must be determined. This paper presents an effective hybrid metaheuristic to solve both the OP and the TOP with time windows. The method combines the greedy randomized adaptive search procedure (GRASP) with the evolutionary local search (ELS). ELS generates multiple distinct child solutions using a mutation mechanism. Each child solution is further improved by a local search procedure. GRASP provides multiple starting solutions to the ELS. The method is able to improve several best known results on available benchmark instances.     

A three-phase matheuristic for capacitated multi-commodity fixed-cost network design with design-balance constraints

This paper proposes a three-phase matheuristic solution strategy for the capacitated multi-commodity fixed-cost network design problem with design-balance constraints. The proposed matheuristic combines exact and neighbourhood-based methods. Tabu search and restricted path relinking meta-heuristics cooperate to generate as many feasible solutions as possible. The two meta-heuristics incorporate new neighbourhoods, and computationally efficient exploration procedures. The feasible solutions generated by the two procedures are then used to identify an appropriate part of the solution space where an exact solver intensifies the search. Computational experiments on benchmark instances show that the proposed algorithm finds good solutions to large-scale problems in a reasonable amount of time.     

Scatter search for project scheduling with resource availability cost

This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.     

两级定位-路径问题模型及变邻域粒子群算法

为满足B2C电子商务中高效率、低成本配送需求,建立了两级定位-路径问题的三下标车流模型,提出了一种求解该问题的变邻域粒子群算法。该算法引入路径重连思想,将粒子群算法中粒子动态更新设计为当前解的邻域搜索、当前解与个体历史最优解之间的路径重连、当前解与种群历史最优解之间的路径重连;在此基础上,提出变邻域搜索策略,动态改变邻域结构以拓展搜索空间。实验结果表明,该算法能有效求解两级定位-路径问题。     

A Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy

In this paper, we present a parallel greedy randomized adaptive search procedure (GRASP) for the Steiner problem in graphs. GRASP is a two-phase metaheuristic. In the first phase, solutions are constructed using a greedy randomized procedure. Local search is applied in the second phase, leading to a local minimum with respect to a specified neighborhood. In the Steiner problem in graphs, feasible solutions can be characterized by their non-terminal nodes (Steiner nodes) or by their key-paths. According to this characterization, two GRASP procedures are described using different local search strategies. Both use an identical construction procedure. The first uses a node-based neighborhood for local search, while the second uses a path-based neighborhood. Computational results comparing the two procedures show that while the node-based variant produces better quality solutions, the path-based variant is about twice as fast. A hybrid GRASP procedure combining the two neighborhood search strategies is then proposed. Computational experiments with a parallel implementation of the hybrid procedure are reported, showing that the algorithm found optimal solutions for 45 out of 60 benchmark instances and was never off by more than 4% of the optimal solution value. The average speedup results observed for the test problems show that increasing the number of processors reduces elapsed times with increasing speedups. Moreover, the main contribution of the parallel algorithm concerns the fact that larger speedups of the same order of the number of processors are obtained exactly for the most difficult problems.     

A nonmonotone GRASP

A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP).     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

GRASP with path relinking for the orienteering problem

In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adaptive Search Procedure (GRASP) and the Path Relinking methodologies—for finding approximate solutions to this optimization problem. We explore different constructive methods and combine two neighbourhoods in the local search of GRASP. Our experimentation with 196 previously reported instances shows that the proposed procedure obtains high-quality solutions employing short computing times.     

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.     

A column generation approach for an emission-oriented vehicle routing problem on a multigraph

In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach.