First Competitive Ant Colony Scheme for the CARP

• URL: http://arxiv.org/abs/2212.02228v1
• Date: Sat, 19 Nov 2022 10:31:27 GMT
• Title: First Competitive Ant Colony Scheme for the CARP
• Authors: Lacomme Philippe, Prins Christian, Tanguy Alain
• Abstract summary: Ant Colony schemes can compute solutions for medium scale instances of VRP. The Ant Colony scheme is coupled with a local search procedure and provides high quality solutions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the Capacitated Arc Routing Problem (CARP) using an Ant Colony Optimization scheme. Ant Colony schemes can compute solutions for medium scale instances of VRP. The proposed Ant Colony is dedicated to large-scale instances of CARP with more than 140 nodes and 190 arcs to service. The Ant Colony scheme is coupled with a local search procedure and provides high quality solutions. The benchmarks we carried out prove possible to obtain solutions as profitable as CARPET ones can be obtained using such scheme when a sufficient number of iterations is devoted to the ants. It competes with the Genetic Algorithm of Lacomme et al. regarding solution quality but it is more time consuming on large scale instances. The method has been intensively benchmarked on the well-known instances of Eglese, DeArmon and the last ones of Belenguer and Benavent. This research report is a step forward CARP resolution by Ant Colony proving ant schemes can compete with Taboo search methods and Genetic Algorithms

Related papers

• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Convergence and Running Time of Time-dependent Ant Colony Algorithms [0.0]
  Ant Colony Optimization (ACO) is a well-known method inspired by the foraging behavior of ants. We consider two time-dependent adaptations of Attiratanasunthron and Fakcharoenphol's $n$-ANT algorithm. Our results show that $n$-ANT/tdev has a super-polynomial time lower bound on the shortest path problem.
  arXiv  Detail & Related papers  (2025-01-18T16:20:39Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Comparative Analysis of Four Prominent Ant Colony Optimization Variants: Ant System, Rank-Based Ant System, Max-Min Ant System, and Ant Colony System [0.0]
  This research conducts a comparative analysis of four Ant Colony Optimization (ACO) variants -- Ant System (AS), Rank-Based Ant System (ASRank), Max-Min Ant System (MMAS), and Ant Colony System (ACS) Our findings demonstrate that algorithm performance is significantly influenced by problem scale and instance type.
  arXiv  Detail & Related papers  (2024-05-24T09:51:13Z)
• Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
  Generative Flow Ant Colony Sampler (GFACS) is a novel meta-heuristic method that hierarchically combines amortized inference and parallel search. Our method first leverages Generative Flow Networks (GFlowNets) to amortize a multi-modal prior distribution over a solution space.
  arXiv  Detail & Related papers  (2024-03-11T16:26:06Z)
• ACO-tagger: A Novel Method for Part-of-Speech Tagging using Ant Colony Optimization [1.7403133838762448]
  Ant Colony Optimization (ACO) is inspired by the foraging behavior of ants and their pheromone laying mechanism. Part-of-Speech (POS) tagging is a fundamental task in natural language processing that aims to assign a part-of-speech role to each word in a sentence. This research paper proposes a high-performance POS-tagging method based on ACO called ACO-tagger.
  arXiv  Detail & Related papers  (2023-03-27T11:48:40Z)
• Ant Hill Colonization optimization algorithm(AHCOA) for controlling the side lobe of a uniform linear array [1.588193964339148]
  AHCOA is a novel new nature inspired algorithm mimicking how the ants built and sustain the ant hill for their survival and sustenance for many years. AHCOA is used by writing equations of volumetric analysis of the ant hill mould the manner in which the structure is architected. This paper shows why AHCOA is a strong candidate for antenna optimization used in linear arrays.
  arXiv  Detail & Related papers  (2022-06-22T16:44:37Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Improving Ant Colony Optimization Efficiency for Solving Large TSP Instances [0.0]
  We present a novel Ant Colony Optimization (ACO) variant, namely the Focused ACO (FACO) FACO is a mechanism for controlling the number of differences between a newly constructed and a selected previous solution. The mechanism results in a more focused search process, allowing to find improvements while preserving the quality of the existing solution.
  arXiv  Detail & Related papers  (2022-03-04T10:26:02Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) considers the setting where the agent does not have access to a reward function during exploration. We show that this separation does not exist in the setting of linear MDPs. We develop a computationally efficient algorithm for reward-free RL in a $d$-dimensional linear MDP.
  arXiv  Detail & Related papers  (2022-01-26T22:09:59Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• Continuous Ant-Based Neural Topology Search [62.200941836913586]
  This work introduces a novel, nature-inspired neural architecture search (NAS) algorithm based on ant colony optimization. The Continuous Ant-based Neural Topology Search (CANTS) is strongly inspired by how ants move in the real world.
  arXiv  Detail & Related papers  (2020-11-21T17:49:44Z)
• Hybrid 2-stage Imperialist Competitive Algorithm with Ant Colony Optimization for Solving Multi-Depot Vehicle Routing Problem [0.0]
  This paper introduces a hybrid 2-stage approach based on two population-based algorithms. In the proposed hybrid algorithm, ICA is responsible for customer assignment to the depots while ACO is routing and sequencing the customers. Results show clear improvement over simple ACO and ICA and demonstrate very competitive results when compared to other rival algorithms.
  arXiv  Detail & Related papers  (2020-04-07T17:43:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.