Abstract
The Chinese Postman Problem with Load-dependent costs (CPP-LC) is a complex arc routing problem where traversal costs vary based on the vehicle's current load. This paper introduces Arc-DRL, a deep reinforcement learning framework that transforms arc routing into a node-based graph attention task. By employing an autoregressive encoder-decoder model and a polynomial-time dynamic programming recursion for edge orientation, Arc-DRL achieves near-optimal solutions (within 0.13% of optimality) while operating orders of magnitude faster than traditional meta-heuristics.
Introduction
The Chinese Postman Problem (CPP) requires finding the shortest path that traverses every edge in a network at least once. While standard CPP is solvable in polynomial time, the Load-dependent costs (CPP-LC) variant is NP-hard. In real-world applications like waste collection or snow plowing, a vehicle's weight changes as it operates, directly impacting fuel consumption and operational costs. This dynamic cost structure creates a highly irregular solution space that challenges conventional optimization methods.
Methodology: The Arc-DRL Framework
The authors propose a multi-stage approach to tackle the complexities of CPP-LC:
Arc-MDP and Graph Transformation
To apply modern Graph Neural Networks (GNNs), the authors perform a graph transformation where each edge in the original network is represented as a node in a "transformed graph." This allows the model to use a Graph Attention Encoder to learn rich, context-aware embeddings of the streets and their relationships.
Autoregressive Model
The core of Arc-DRL is an encoder-decoder architecture. The encoder uses multi-head attention to process the transformed graph. The decoder then sequentially selects the next street to service based on the current vehicle load, the last visited street, and the global graph state. A key innovation is the use of a Dynamic Programming (DP) recursion to determine the optimal traversal direction for each selected edge, significantly reducing the agent's action space.
Experimental Evaluation
The model was evaluated against several benchmarks, including classic graph types (Eulerian, Christofides, Hertz) and a set of "difficult" instances with up to 232 edges. Training was conducted using the REINFORCE algorithm with a greedy rollout baseline on 100,000 synthetic Eulerian instances.
Key Results and Discussion
Arc-DRL demonstrates a superior balance between solution quality and computational efficiency.
Optimality and Speed
As shown in the performance summary for Dataset 1, Arc-DRL consistently achieves optimality gaps between 0.05% and 0.13%. This performance is comparable to high-quality Evolutionary Algorithms (EA) but achieved at a fraction of the time.
On large-scale instances, the speed advantage becomes even more pronounced. Arc-DRL was found to be 4x to 10x faster than standard heuristics like Variable Neighborhood Search (VNS) and Iterative Local Search (ILS). Most impressively, it outperformed the specialized Evolutionary Algorithm by a factor of approximately 345x in terms of execution speed on the largest instances (e.g., 3,456s for EA vs. 10s for Arc-DRL).
Conclusion
Arc-DRL represents a significant step forward in neural arc routing. By cleverly transforming the problem space and delegating low-level decisions to dynamic programming, the framework provides a robust, scalable solution for the CPP-LC. Future work will explore extending this architecture to multi-vehicle fleets and incorporating additional real-world constraints such as time windows.
The authors have released their C++ implementations and data generation tools to support further research in this domain.
Summary updated