Graph Attention-based Deep Reinforcement Learning for solving the Chinese Postman Problem with Load-dependent costs

Cong Dao Tran, Truong Son HyarXiv 2023 · DOI · arXiv

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.

Example of load-dependent cost calculations for a specific edge sequence, illustrating how costs vary with vehicle load.

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.

Comparative performance of Arc-DRL against meta-heuristics on Dataset 1, highlighting the low optimality gaps and fast execution times.

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

Abstract

Recently, Deep reinforcement learning (DRL) models have shown promising results in solving routing problems. However, most DRL solvers are commonly proposed to solve node routing problems, such as the Traveling Salesman Problem (TSP). Meanwhile, there has been limited research on applying neural methods to arc routing problems, such as the Chinese Postman Problem (CPP), since they often feature irregular and complex solution spaces compared to TSP. To fill these gaps, this paper proposes a novel DRL framework to address the CPP with load-dependent costs (CPP-LC) (Corberan et al., 2018), which is a complex arc routing problem with load constraints. The novelty of our method is two-fold. First, we formulate the CPP-LC as a Markov Decision Process (MDP) sequential model. Subsequently, we introduce an autoregressive model based on DRL, namely Arc-DRL, consisting of an encoder and decoder to address the CPP-LC challenge effectively. Such a framework allows the DRL model to work efficiently and scalably to arc routing problems. Furthermore, we propose a new bio-inspired meta-heuristic solution based on Evolutionary Algorithm (EA) for CPP-LC. Extensive experiments show that Arc-DRL outperforms existing meta-heuristic methods such as Iterative Local Search (ILS) and Variable Neighborhood Search (VNS) proposed by (Corberan et al., 2018) on large benchmark datasets for CPP-LC regarding both solution quality and running time; while the EA gives the best solution quality with much more running time. We release our C++ implementations for metaheuristics such as EA, ILS and VNS along with the code for data generation and our generated data at https://github.com/HySonLab/Chinese_Postman_Problem
BibTeX
@misc{tran2023graph,
  author = {Cong Dao Tran and Truong Son Hy},
  title = {{Graph Attention-based Deep Reinforcement Learning for solving the Chinese Postman Problem with Load-dependent costs}},
  year = {2023},
  eprint = {2310.15516},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.15516},
}
Figure