<p>This paper focuses on solving the capacitated arc routing problem with time-dependent service costs (CARPTDSC), which is motivated by winter gritting applications. In the current literature, exact algorithms designed for CARPTDSC can only handle small-scale instances, while heuristic algorithms fail to obtain high-quality solutions. To overcome these limitations, we propose a novel dual-stage algorithm, which consists of a routing stage and a vehicle departure time optimization stage. The former obtains the routing plan, while the latter determines the vehicle departure time. Importantly, existing literature often ignores the characteristic information contained in the relationship between the route cost and the vehicle departure time. The most significant innovation of this paper lies in the exploitation of this characteristic information during the vehicle departure time optimization stage. Specifically, we conduct a detailed analysis of this relationship under various scenarios and employ tailored methods to obtain the (approximately) optimal vehicle departure time. Furthermore, we propose an improved initialization strategy that considers time-dependent characteristics to achieve better solution quality. In addition to the modified benchmark test sets, we also experiment on a real-world test set. Experimental results demonstrate that the proposed algorithm can obtain high-quality solutions on both small-scale and larger-scale instances (including the real-world test set) of CARPTDSC.</p>