cs.NEJul 29, 2025

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

Organizations: Guangdong Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China · School of Information Management, Central China Normal University, Wuhan, China · Hunan Key Laboratory of Computational Intelligence, Xiangtan University, Xiangtan, China · School of Data Science, Lingnan University, Hong Kong SAR, China

Abstract

The capacitated arc routing problem with time-dependent service costs (CARPTDSC) is a challenging combinatorial optimization problem that arises from real-world applications. CARPTDSC has two main challenges in reducing computational time. First, it is an NP-hard problem. Second, the time-dependent service costs of tasks require frequent evaluations during the search process, significantly increasing the computational burden. 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 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. 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.

Explore similar work

CardsList
  1. Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

    Aug 14, 2026Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1Vehicle RoutingMetaheuristic Optimization

  2. Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

    Sep 28, 2026Jiale Zhao, Sirui Mao, Zimu Chen +5Traveling Salesperson ProblemCombinatorial Optimization

  3. KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering

    Jul 25, 2026Florian Rascoussier, Romain Billot, Lina Fahed +1Metaheuristic OptimizationVehicle Routing