ant colony optimization
Latest papers
9 papers2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.
We study a stylized single-vehicle replenishment-routing problem in which the cities of a national logistics network are both demand points and supply points: a vehicle of limited capacity delivers to every city once, and when its load is insufficient for the next city it must detour to a city already served that can still supply goods. A 100-node benchmark is built from Korean population and geographic data, with the cities divided into 10 levels; the per-visit supply coefficient and the allowed number of stops decrease geometrically with the level. Building on matrix-based ant colony optimization, we keep the states of the whole colony in arrays, couple route construction with a fixed greedy replenishment-decoding policy, and evaluate the candidate moves of a local search in batches. With frozen parameters and 30 runs on seeds never used for tuning, the matrix-based ant colony search with the batch local search (MACO) reaches a mean total distance of 3081.7 km; a genetic algorithm equipped with the same local search at the same frequency reaches 3074.9 km (no significant difference), and a MAX-MIN ant system with the same local search 3142.2 km. Ablation identifies the batch local search as the main contributor to solution quality; a load-aware transition factor gives no significant gain. Within the parameter ranges tested, raising the supply coefficients of the cities below the top level shortens the route more than relaxing the stop limits, which are not binding here.
Decentralised Drone Swarm Formation under Silent Failures with ACO Pheromone Claims and PSO Tuning
We study decentralised drone formation, without a central planner, under the conditions that make it hard: nobody knows how many drones are alive, failures are silent, radio is short-ranged and lossy, and actuation is noisy. In our controller, ant colony optimisation (ACO) allocates drones to picture positions through claims that behave as reinforced, evaporating pheromone and are gossiped between neighbours, so evaporation doubles as failure detection. A particle swarm optimisation (PSO) law flies the drones, a noise-buffered Voronoi filter keeps them apart, and PSO also tunes the controller offline. We prove that claims of destroyed drones vanish within bounded time, that conflicts between drones that exchange tables are resolved consistently, that survivors cover the picture to within a factor of two, and that drones cannot collide while their safety cells are feasible. On held-out seeds and with two tuned configurations, the controller formed the picture in 95-99% of runs in the hardest regime, restored it after a silent loss of half the swarm in 96-100% of runs at normal difficulty, transferred unchanged to eight unseen shapes and to 300 drones, and overlapped in 5 of 21,088 runs. A CBBA-style baseline that shares the evaporating claims but uses argmax without swaps was at least as reliable as ours once tuned with the same budget, and repaired faster, whereas ours generalised better to unseen shapes. The benefit thus comes from the pheromone dynamics and from tuning, not from ACO's stochastic construction or PSO's social terms. A centralised oracle is faster.
Large Language Model-Assisted Adaptive Heuristic Search for Agile Earth Observation Satellite Scheduling
Agile Earth observation satellites must coordinate imaging tasks within limited observation windows, while accounting for attitude maneuvering and onboard energy constraints. Competition among observation opportunities makes scheduling performance sensitive to the heuristic rules used for task selection. This letter proposes a large language model (LLM)-assisted adaptive heuristic search method for agile Earth observation satellite scheduling. The LLM generates an initial heuristic rule according to the characteristics of the scheduling instance. During the subsequent ant colony search, search performance and scheduling information are fed back to the LLM to refine the heuristic rule. The proposed modifications are evaluated through paired solution constructions before being incorporated into the search process. A unified scheduling procedure determines task selection, satellite assignment, and observation timing under the operational constraints. Experiments on six scheduling scenarios involving 50--200 imaging tasks demonstrate that the proposed method achieves 4.3%--9.6% higher mean observation benefit than the strongest baseline.
A Metaheuristic Optimization Framework for Discrete Optimization under Strict Time Limits
Real-time applications often rely on optimization approaches that can find high-quality solutions to hard problems on the order of milliseconds. Metaheuristic optimization frameworks (MOFs) are useful tools for such tasks, as they provide large sets of general-purpose search mechanisms that can return solutions under different computational budgets. However, existing work largely overlooks the available computation time as an explicit dimension of analysis. In this work, we introduce STILO, a MOF specifically designed for optimization under strict time limits. STILO integrates fine-grained configuration spaces for ant colony optimization (ACO), genetic algorithm (GA), and simulated annealing (SA), combining existing and novel operators. We performed experiments using both synthetic and benchmark instances of various discrete optimization problems. The results indicate that the proposed discrete distance calculation mechanism for SA is useful for optimization under strict time limits. They also show that the relative effectiveness of the proposed problem-independent graph structures for ACO can vary across time limits, even for the same instance characteristics. More generally, the results demonstrate that the effectiveness of algorithm families and operators depends not only on the problem type, but also on the characteristics of the instance and the available computational budget.
Implicit Q-learning-bootstrapped ant colony optimization for maritime moving-target observation scheduling with agile satellites
Maritime moving-target observation scheduling with agile Earth observation satellites is a dynamic, sequence-dependent combinatorial optimization problem. Sea-surface targets move continuously, causing feasible observation windows to vary with target motion and satellite orbital geometry. The scheduler must jointly determine task selection, satellite assignment, observation-window selection, and observation ordering under time-window, attitude-maneuvering, and onboard-resource constraints. This paper proposes an implicit Q-learning-bootstrapped ant colony optimization method, termed IQACO, for multi-satellite maritime moving-target observation scheduling. Rather than directly learning a task-selection policy, IQACO embeds an offline implicit Q-learning module into constructive ant colony optimization to adaptively adjust the pheromone factor, heuristic factor, and evaporation rate. A compact search-state representation captures pheromone distribution, current and historical-best solution quality, and iteration progress. During online scheduling, ant colony optimization constructs feasible observation sequences, while the learned policy adjusts the search behavior according to the current search state. Experiments on 14 scenarios with different scales and satellite configurations show that IQACO consistently outperforms the compared algorithms, improving the mean objective value over conventional ant colony optimization by 2.86%-9.41%. Further comparative and supplementary experiments demonstrate its effectiveness and robustness across different scheduling conditions and problem settings. These results indicate that offline value learning provides an effective adaptive search-control mechanism for constrained maritime moving-target observation scheduling.
Bi-Layer Ant Colony Optimization for Multi-Robot Task Allocation and Routing in Delivery Applications
This paper addresses the multi-robot task allocation (MRTA) problem, which is essential for delivery and logistics applications. Our approach first defines a new cost function that transforms the MRTA into a unified optimization problem capturing both task assignment and routing. A bi-layer ant colony optimization (ACO) algorithm is then introduced, integrating two interdependent decision layers within a single colony process to solve the problem. This hierarchical framework enables simultaneous optimization of task allocation and route planning across multiple robots. Comparative experiments with mixed-integer linear programming (MILP) and particle swarm optimization (PSO) demonstrate that the proposed bi-layer ACO achieves the shortest total travel distance and fastest completion time across all task sizes. Specifically, it reduces total travel distance by up to 17.7% and completion time by nearly 20% compared with baseline methods. These results confirm the efficiency, scalability, and reliability of the proposed bi-layer ACO for multi-robot delivery tasks.
Hub-Aware Hybrid Search: Accelerating the Locally Aligned Ant Technique
Finding manifold structures in noisy and high-dimensional point clouds is a challenging but important problem. In astronomical observation survey and simulation data the detection of filaments, streams (1D), walls (2D) and clusters (3D) gives rise to deeper understanding of the evolution of our universe. The Locally Aligned Ant Technique (LAAT) uses biologically inspired agents to efficiently recover faint and multidimensional structures. However, very dense hubs (e.g. nodes or globular clusters) dominate the ants' activity, creating unnecessary computational overheads. In this paper we propose a two-stage solution. First a fast preprocessing step locates the hubs and replaces them with a tailored likelihood model. Subsequently, a mixed likelihood-pheromone strategy guides the ants to efficiently bridge the dense regions. We demonstrate improvements in detection efficiency and robustness of LAAT with synthetic and a large-scale astronomical N-body simulation of the cosmic web.
Beyond Static Priors: Dynamic Neural Guidance for Large-Scale Ant Colony Optimization
Neural-guided Ant Colony Optimization (ACO) suffers from a fundamental training-inference misalignment: policies are typically trained to generate static priors (e.g., heatmaps), yet deployed to guide iterative, long-horizon search processes. In this paper, we present DyNACO, a novel framework that achieves dynamic neural guidance by periodically observing the pheromone distribution and the incumbent solution. To make DyNACO tractable at scale, we pair the policy with a perturbation-based ACO backend and a scope-restricted refinement mechanism that jointly ensure efficacy and stable credit assignment. On TSP, DyNACO scales to 100,000-node instances and outperforms neural baselines while often reducing total runtime compared to the unguided solver. We extend DyNACO to CVRP via a capacity-aware backend, consistently improving the unguided baseline with less than 1% neural overhead. We further provide in-depth analysis validating the model's generalization capabilities and elucidating why dynamic guidance outperforms static priors. Our work underscores the necessity of aligning neural training with iterative search dynamics in learning-guided optimization. The code is available at https://github.com/shoraaa/DyNACO.
Efficient and Interpretable Multi-Agent LLM Routing via Ant Colony Optimization
Large Language Model (LLM)-driven Multi-Agent Systems (MAS) have demonstrated strong capability in complex reasoning and tool use, and heterogeneous agent pools further broaden the quality--cost trade-off space. Despite these advances, real-world deployment is often constrained by high inference cost, latency, and limited transparency, which hinders scalable and efficient routing. Existing routing strategies typically rely on expensive LLM-based selectors or static policies, and offer limited controllability for semantic-aware routing under dynamic loads and mixed intents, often resulting in unstable performance and inefficient resource utilization. To address these limitations, we propose AMRO-S, an efficient and interpretable routing framework for Multi-Agent Systems (MAS). AMRO-S models MAS routing as a semantic-conditioned path selection problem, enhancing routing performance through three key mechanisms: First, it leverages a supervised fine-tuned (SFT) small language model for intent inference, providing a low-overhead semantic interface for each query; second, it decomposes routing memory into task-specific pheromone specialists, reducing cross-task interference and optimizing path selection under mixed workloads; finally, it employs a quality-gated asynchronous update mechanism to decouple inference from learning, optimizing routing without increasing latency. Extensive experiments on five public benchmarks and high-concurrency stress tests demonstrate that AMRO-S consistently improves the quality--cost trade-off over strong routing baselines, while providing traceable routing evidence through structured pheromone patterns.