Knowledge-Guided Memetic Algorithm for Capacitated Arc Routing Problems with Time-Dependent Service Costs

• URL: http://arxiv.org/abs/2507.21740v1
• Date: Tue, 29 Jul 2025 12:17:25 GMT
• Title: Knowledge-Guided Memetic Algorithm for Capacitated Arc Routing Problems with Time-Dependent Service Costs
• Authors: Qingya Li, Shengcai Liu, Wenjie Chen, Juan Zou, Ke Tang, Xin Yao,
• Abstract summary: This paper proposes a knowledge-guided memetic algorithm with golden section search and negatively correlated search.<n>It achieves higher search efficiency than the state-of-the-art methods.
• Score: 18.734871315760717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The capacitated arc routing problem with time-dependent service costs (CARPTDSC) is a challenging combinatorial optimization problem that arises from winter gritting applications. CARPTDSC has two main challenges about time consumption. First, it is an NP-hard problem. Second, the time-dependent service costs of tasks require frequent evaluations during the search process, significantly increasing computational effort. These challenges make it difficult for existing algorithms to perform efficient searches, often resulting in limited efficiency. To address these issues, this paper proposes a knowledge-guided memetic algorithm with golden section search and negatively correlated search (KGMA-GN), where two knowledge-guided strategies are introduced to improve search efficiency. First, a knowledge-guided initialization strategy (KGIS) is proposed to generate high-quality initial solutions to speed up convergence. Second, a knowledge-guided small-step-size local search strategy (KGSLSS) is proposed to filter out invalid moves, thereby reducing unnecessary evaluations and saving the computation time. Experimental results on five benchmark test sets, including both small- and larger-scale instances, demonstrate that KGMA-GN achieves higher search efficiency than the state-of-the-art methods. Moreover, the ablation study further confirms that the knowledge-guided local search operators in KGSLSS can significantly reduce runtime compared to traditional operators, especially for the knowledge-guided swap operator, which achieves more than a tenfold improvement in speed.

Related papers

• Demystifying and Enhancing the Efficiency of Large Language Model Based Search Agents [9.862334188345791]
  Large Language Model (LLM)-based search agents have shown remarkable capabilities in solving complex tasks.<n>We introduce SearchAgent-X, a high-efficiency inference framework for LLM-based search agents.<n>SearchAgent-X consistently outperforms state-of-the-art systems such as vLLM and HNSW-based retrieval.
  arXiv  Detail & Related papers  (2025-05-17T16:07:01Z)
• Resource Constrained Pathfinding with Enhanced Bidirectional A* Search [10.100786663811666]
  This research introduces a novel constrained search framework that uses efficient pruning strategies to allow for accelerated and effective RCSP search in large-scale networks.<n>Results show that, compared to the state of the art, our enhanced framework can significantly reduce the constrained search time, achieving speed-ups of over to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-12-18T14:29:40Z)
• Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem [10.316443594063173]
  Job shop scheduling problem (JSSP) and its solution algorithms have been of enduring interest in both academia and industry for decades.<n>In recent years, machine learning (ML) is playing an increasingly important role in advancing existing and building new solutions for the JSSP, aiming to find better solutions in shorter times.<n>We build on top of a state-of-the-art deep reinforcement learning (DRL) agent, called Neural Local Search (NLS), which can efficiently and effectively control a large local neighborhood search on the JSSP.
  arXiv  Detail & Related papers  (2024-09-04T13:33:38Z)
• Quantum Algorithm Exploration using Application-Oriented Performance Benchmarks [0.0]
  The QED-C suite of Application-Oriented Benchmarks provides the ability to gauge performance characteristics of quantum computers. We investigate challenges in broadening the relevance of this benchmarking methodology to applications of greater complexity.
  arXiv  Detail & Related papers  (2024-02-14T06:55:50Z)
• COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems [19.442683583536137]
  COMBHelper employs a Graph Neural Network (GNN) to identify promising nodes for the solution set. It also uses a Knowledge Distillation (KD) module and a problem-specific boosting module to bring further efficiency and efficacy. Our experiments show that the traditional CO algorithms with COMBHelper are at least 2 times faster than their original versions.
  arXiv  Detail & Related papers  (2023-12-14T16:17:20Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  This paper introduces an efficient algorithm for the Maximum Independent Set (MIS) problem, incorporating two innovative techniques.<n>The proposed algorithm outperforms state-of-the-art algorithms in terms of solution quality, computational efficiency, and stability.
  arXiv  Detail & Related papers  (2022-08-16T14:39:38Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• CATCH: Context-based Meta Reinforcement Learning for Transferrable Architecture Search [102.67142711824748]
  CATCH is a novel Context-bAsed meTa reinforcement learning algorithm for transferrable arChitecture searcH. The combination of meta-learning and RL allows CATCH to efficiently adapt to new tasks while being agnostic to search spaces. It is also capable of handling cross-domain architecture search as competitive networks on ImageNet, COCO, and Cityscapes are identified.
  arXiv  Detail & Related papers  (2020-07-18T09:35:53Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining [69.00394670035747]
  Hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques.
  arXiv  Detail & Related papers  (2019-08-28T13:12:30Z)

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.