A novel dual-stage algorithm for capacitated arc routing problems with time-dependent service costs

Qingya Li, Shengcai Liu, Juan Zou, Ke TangarXiv 2024 · DOI · arXiv

Abstract

This paper addresses the Capacitated Arc Routing Problem with Time-Dependent Service Costs (CARPTDSC), a complex logistics challenge where the cost of servicing road segments varies over time. We propose MAENS-GN, a novel dual-stage algorithm that decouples the problem into a routing stage and a vehicle departure time optimization stage. By mathematically analyzing the relationship between departure times and total route costs, we employ tailored search techniques—Golden Section Search and Negatively Correlated Search—to optimize timing. Experimental results on benchmark and real-world datasets demonstrate that MAENS-GN significantly outperforms existing heuristics and provides high-quality solutions where exact algorithms fail to scale.

Introduction

The Capacitated Arc Routing Problem (CARP) is a foundational problem in logistics, involving the efficient servicing of road segments (arcs) by a fleet with limited capacity. Applications range from waste collection to mail delivery. However, in scenarios like winter gritting, the cost of servicing an arc is not static; it fluctuates based on time-dependent factors such as temperature and traffic. This variant, known as CARPTDSC, requires optimizing not just the sequence of tasks but also the precise timing of vehicle departures.

Existing approaches to CARPTDSC often struggle with a trade-off between scalability and solution quality. Exact algorithms, while precise, are computationally prohibitive for instances exceeding 40 tasks. Conversely, traditional heuristics often overlook the intricate relationship between departure time and eventual service costs, leading to sub-optimal routing plans.

The MAENS-GN Framework

To overcome these limitations, we developed the MAENS-GN framework, which separates the optimization process into two distinct stages.

Stage 1: Routing Optimization (MAENS)

The first stage utilizes a Memetic Algorithm with Extended Neighborhood Search (MAENS) to determine the optimal sequence of tasks for each vehicle. This stage focuses on the spatial component of the problem—the "where."

Figure 1: An example of a routing plan and its corresponding ordered sequence of tasks.

As illustrated in Figure 1, the output of this stage is an ordered sequence $X$ that defines the path from the depot through various service tasks and back. To improve the quality of these initial routes, we introduced a novel initialization strategy using roulette-wheel selection that favors tasks with lower time-dependent costs, ensuring a balance between solution quality and population diversity.

Stage 2: Departure Time Optimization (GN)

The second stage determines the optimal departure time ($dt$) for each route. Our key innovation lies in the mathematical analysis of how the "slope" of the time-dependent cost function affects the total route cost.

Figure 2: Two types of linear cost functions used to model time-dependent service costs: (a) Three-segment and (b) Two-segment.

Depending on the complexity of the cost function (see Figure 2), we apply different optimization strategies:

  • Two-segment functions: The optimal departure time is typically zero.
  • Three-segment functions (Unimodal): If the cost fluctuation is moderate, the relationship between departure time and cost is unimodal. We use Golden Section Search (GSS) to rapidly find the minimum.
  • Three-segment functions (Non-unimodal): If fluctuations are steep, the cost relationship becomes complex with multiple local minima. In these cases, we employ Negatively Correlated Search (NCS), an evolutionary technique, to ensure global optimization.

Experimental Results

We evaluated MAENS-GN across modified standard benchmarks (gdb, egl, Solomon) and a real-world dataset from Jingdong (JD.com).

  • Scalability and Speed: MAENS-GN successfully solved large-scale instances (e.g., Solomon-40) where exact Column Generation (CG) methods failed due to memory constraints. On smaller sets like Solomon-25, MAENS-GN was approximately 45 times faster than CG while maintaining comparable quality.
  • Solution Quality: Compared to the state-of-the-art heuristic Variable Neighborhood Descent (VND), MAENS-GN showed marked improvements. For instance, on the gdb 2LP benchmark, MAENS-GN achieved an average performance degradation ratio (PDR) of 1.37%, significantly better than VND's 10.82%.

Conclusion

MAENS-GN represents a significant advancement in solving arc routing problems with time-dependent costs. By explicitly modeling and optimizing vehicle departure times based on the mathematical properties of cost functions, the algorithm achieves a superior balance of efficiency and solution quality. Future work will focus on reducing the computational complexity of local search operators and further narrowing the gap to theoretical lower bounds in highly complex cost scenarios.

Summary updated

Abstract

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, called MAENS-GN, that consists of a routing stage and a vehicle departure time optimization stage. The former obtains the routing plan, while the 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 in 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 MAENS-GN can obtain high-quality solutions on both small-scale and larger-scale instances of CARPTDSC.
BibTeX
@misc{li2024novel,
  author = {Qingya Li and Shengcai Liu and Juan Zou and Ke Tang},
  title = {{A novel dual-stage algorithm for capacitated arc routing problems with time-dependent service costs}},
  year = {2024},
  eprint = {2406.15416},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.15416},
}
Figure