<p>The Capacitated Arc Routing Problem (CARP) is a traditional NP-hard optimization problem that has many applications in municipal and infrastructure services including waste collection, snow removal, and street maintenance. However, in most real-life scenarios, there are edges that have to be serviced earlier because of safety, operational urgency, or strategic significance. To effectively deal with this practical necessity, this paper presents a new variant, which is known as the Capacitated Arc Routing Problem with Priority Edges (CARP-PE) where there is a given ordered set of priority edges that have to be served as soon as possible and at the lowest possible overall routing cost. A priority sequencing model is formed by creating an integer linear programming (ILP) formulation of the classical CARP model. As the proposed model is more complex in terms of computation, a specific Genetic Algorithm (GA) is developed to find near-optimal solutions in an efficient way. The suggested GA is justified by the exact solutions of CPLEX on the small-scale problems and a comparison with Particle Swarm Optimization (PSO) algorithm on the bigger ones. Computational findings show that the GA always attains better objective values and reduces computational time in large scale problems. The presented framework will improve the relevance of CARP to priority-sensitive systems of services and offer a systematic decision-making instrument to routing issues in which service urgency is a decisive factor.</p>