China
Africa
Explore chapters and articles related to this topic
An Introductory Illustration to Hybrid Quantum-Inspired Metaheuristics
Published in Siddhartha Bhattacharyya, Mario Köppen, Elizabeth Behrman, Ivan Cruz-Aceves, Hybrid Quantum Metaheuristics, 2022
Siddhartha Bhattacharyya, Mario Köppen, Elizabeth Behrman, Ivan Cruz-Aceves
There exists few popular constructive metaheuristics in the literature, out of them Ant Colony optimization and Greedy Randomized Adaptive Search Procedure (GRASP) are the most popular and mostly used metaheuristics. The basics of these two methods are described below.
A new formulation and algorithm for the maximum leaf spanning tree problem with an application in forest fire detection
Published in Engineering Optimization, 2023
Amir Masoud Hosseinmardi, Hamid Farvaresh, Isa Nakhai Kamalabadi
From the aspect of exact and approximation algorithms, Fujie (2003) introduced the first algorithm of the exact type and reported the results obtained for random graphs with at most 100 vertices, comparing them with those of the approximation algorithms of Lu and Ravi (1998) and Solis-Oba (1998). Lucena, Maculan, and Simonetti (2010) developed two branch-and-cut algorithms based on the two reformulations mentioned above and an improved version of an MLSTP branch-and-bound algorithm for instances with at most 200 vertices. Gendron et al. (2014) developed exact algorithms based on two approaches: a Benders decomposition and a branch-and-cut method. Moreover, they developed a hybrid algorithm that combines the two approaches. A brief review of these two articles (Lucena, Maculan, and Simonetti 2010; Gendron et al. 2014) can be found in the supplementary material. Xia, Zhou, and Lai (2015) analysed the performance of the (1 + 1) evolutionary algorithm and indicated that this algorithm obtains two approximation algorithms with the runtimes O(nm2) and O(nm4). Sánchez-Oro et al. (2015) designed a metaheuristic algorithm based on a strategic oscillation approach and reported the results for 480 samples along with the comparison with those of two other metaheuristic algorithms, namely, strategic oscillation (SO) and the greedy randomized adaptive search procedure (GRASP). Finally, a two-approximation algorithm was designed for the MLSTP, which has provided the best ratio so far for an arbitrary graph (Solis-Oba, Bonsma, and Lowski 2017).
On solving the densest k-subgraph problem on large graphs
Published in Optimization Methods and Software, 2020
Different heuristic methods are tested for solving the densest k-subgraph problem. Kincaid [33] uses simulated annealing and tabu search heuristics to solve the DkS problem. His results show that the tabu search algorithm performs better than the simulated annealing algorithm for solving the densest k-subgraph problem. In [41], Macambira implements tabu search heuristics for the heaviest k-subgraph problem. Although the tabu search algorithm from [41] does not perform diversification, it outperforms the greedy randomized adaptive search procedure. A variable neighborhood search (VNS) heuristics for the heaviest subgraph problem and graphs up to 3000 vertices is implemented by Brimberg et al. [13]. Their results show that the VNS outperforms the tabu search heuristic and multi-start local search heuristics in solving the DkS. The VNS performs extremely well on sparse graphs. Running times needed to find the best solutions for instances with 3000 vertices is about 425 s. A heuristic based on a two-step filtering approach is used to extract dense web communities in Dourisboure et al. [16].
A bi-objective transportation-location arc routing problem
Published in Transportation Letters, 2020
Alireza Amini, Reza Tavakkoli-Moghaddam, Sadoullah Ebrahimnejad
Lopes et al. (2014) developed a mathematical model and some heuristics for the LARP. The authors employed tabu search (TS), greedy randomized adaptive search procedure (GRASP), and variable neighborhood search (VNS) meta-heuristics and used their proposed heuristics to enhance the meta-heuristics. In addition, Hashemi Doulabi and Seifi (2013) developed two mathematical models for single-depot and multiple-depot LARPs, respectively. They took the advantages of meta-heuristics, as well, along with some heuristics as the local search algorithms for those meta-heuristics. Also, Riquelme-Rodríguez, Gamache, and Langevin (2016) addressed an inventory-based LARP. In one of the latest studies, Amini, Tavakkoli-Moghaddam, and Ebrahimnejad (2017) employed scenario-based approaches to study uncertain LARPs (SLARP). In addition, Tavakkoli-Moghaddam, Amini, and Ebrahimnejad (2018) developed two types of mathematical models for a multi-product LARP, MPLARP.