Deep Reinforcement Learning for Traveling Purchaser Problems

Haofeng Yuan, Rongping Zhu, Wanlu Yang, Shiji Song, Keyou You, Wei Fan, C. L. Philip ChenIEEE Transactions on Emerging Topics in Computational Intelligence 2024 · arXiv

TL;DR

This paper introduces a novel deep reinforcement learning (DRL) approach for the Traveling Purchaser Problem (TPP) that decouples route construction and purchasing decisions, allowing for more efficient and effective solutions. By using a unique bipartite graph representation and a meta-learning strategy, their method significantly outperforms existing heuristics, achieving optimality gaps reduced by 40%-90% and demonstrating strong generalization capabilities.

What Problem Does This Paper Address?

The Traveling Purchaser Problem (TPP) is a complex optimization challenge with real-world applications in logistics and supply chain management. It involves deciding which markets to visit and what quantities of products to purchase to meet demands, all while minimizing total travel and purchasing costs. The core difficulty lies in the inherent coupling between routing and purchasing decisions. Traditional methods either tackle both simultaneously, leading to high computational costs and scalability issues, or rely on hand-crafted heuristics that require extensive domain expertise and often lack generalization. This paper aims to overcome these limitations by proposing a DRL-based framework that separates these decisions while optimizing the overall objective.

Methods

The authors propose a "solve separately, learn globally" framework. This involves two main stages:

  1. Route Construction: A deep reinforcement learning (DRL) agent, specifically a policy network, sequentially builds a route by selecting markets to visit. This is framed as a Markov Decision Process (MDP).
  2. Purchase Planning: Once a route is determined, an optimal purchasing plan is derived using a linear transportation problem.

Key novelties include:

  • Bipartite Graph Representation: TPP instances are represented as bipartite graphs where markets and products are nodes, and edges capture supply information (quantity, price). This representation is size-agnostic and effectively captures market-product interdependencies.
  • Policy Network Architecture: A GNN-based architecture is used to process the bipartite graph, followed by a Transformer-style encoder and a decoder for route construction. This architecture is designed to be size-agnostic.
  • Meta-Learning Strategy: To address training instability and improve generalization on large instances, a meta-learning approach is employed. This pre-trains a policy network on a distribution of TPP instances, enabling it to adapt quickly to new, unseen instances with minimal fine-tuning.
  • "Solve Separately, Learn Globally" Principle: The DRL agent is trained to optimize the global objective (total cost) even though it only directly controls the route construction. This allows the agent to learn routes that are not only short but also conducive to low purchasing costs.

Datasets

  • Synthetic TPP Instances: The authors generate synthetic instances for both Unrestricted TPP (U-TPP) and Restricted TPP (R-TPP) with varying numbers of markets (|M|) and products (|K|), including sizes (50,50), (50,100), (100,50), and (100,100).
  • TPPLIB Benchmark: This is a standard benchmark for TPPs, used for evaluating the approach on pre-defined instance distributions.
  • Larger-Sized Instances: For zero-shot generalization tests, larger instances (up to 300 markets and 300 products) were generated, which were not seen during training.

Key Insights and Ideas

  • Decoupling for Efficiency: Separating route construction and purchasing, while learning a policy that optimizes the combined objective, is a powerful strategy for tackling complex combinatorial problems like TPP.
  • Bipartite Graphs are Key: The bipartite graph representation is crucial for capturing the intricate relationships between markets and products, which is essential for effective TPP solutions, and it enables a size-agnostic model.
  • Meta-Learning for Robustness: Training stability and generalization on large, unseen instances are significant challenges in DRL for optimization. Meta-learning proves to be an effective solution, preventing training collapse and enabling adaptation.
  • "Learning to Learn" for Optimization: The meta-learning strategy allows the model to learn how to learn, making it more robust and adaptable to diverse problem instances, a critical aspect for real-world deployment.

Key Results

  • Superior Solution Quality: The DRL-based approach significantly outperforms well-established heuristics like GSH+TRH and CAH+TRH.
  • On synthetic instances, the DRL approach consistently achieved better objective values.
  • On the TPPLIB benchmark, the optimality gap was reduced by 40%-90% compared to baselines, with the RL+TRH method achieving gaps consistently within 6%.
  • Efficient Runtime: The DRL approach demonstrates a significant advantage in runtime, especially on larger R-TPP instances. While U-TPP instances are solved quickly by all methods, R-TPP instances show a pronounced difference, with the DRL approach exhibiting near-linear scaling with the number of visited markets.
  • Strong Generalization: The meta-learning strategy enables zero-shot generalization to larger-sized TPP instances that were never encountered during training, showcasing the model's ability to learn transferable knowledge.
  • Ablation Studies: The bipartite graph representation was found to be more effective than complete or k-NN graphs. All components of the policy network (input embedding, market encoder, LSTM) contributed to performance, with the input embedding module being particularly critical.

Limitations and Future Work

  • Generalization Drop on Very Large Instances: While the model shows good generalization, a drop in performance was observed on the largest tested U-TPP instances (300x300) and R-TPP instances (150x150).
  • Future Work: The authors suggest exploring better generalization techniques for even larger instances and developing a more generic framework to address other TPP variants, such as multi-vehicle TPP and dynamic TPP. They also mention the potential for integrating their approach with local search methods for further improvements.

Summary updated

Abstract

The traveling purchaser problem (TPP) is an important combinatorial optimization problem with broad applications. Due to the coupling between routing and purchasing, existing works on TPPs commonly address route construction and purchase planning simultaneously, which, however, leads to exact methods with high computational cost and heuristics with sophisticated design but limited performance. In sharp contrast, we propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">separately</i>, while evaluating and optimizing the solution from a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">global</i> perspective. The key components of our approach include a bipartite graph representation for TPPs to capture the market-product relations, and a policy network that extracts information from the bipartite graph and uses it to sequentially construct the route. One significant advantage of our framework is that we can efficiently construct the route using the policy network, and once the route is determined, the associated purchasing plan can be easily derived through linear programming, while, by leveraging DRL, we can train the policy network towards optimizing the global solution objective. Furthermore, by introducing a meta-learning strategy, the policy network can be trained stably on large-sized TPP instances, and generalize well across instances of varying sizes and distributions, even to much larger instances that are never seen during training. Experiments on various synthetic TPP instances and the TPPLIB benchmark demonstrate that our DRL-based approach can significantly outperform well-established TPP heuristics, reducing the optimality gap by 40%–90%, and also showing an advantage in runtime, especially on large-sized instances.
BibTeX
@misc{yuan2024deep,
  author = {Haofeng Yuan and Rongping Zhu and Wanlu Yang and Shiji Song and Keyou You and Wei Fan and C. L. Philip Chen},
  title = {{Deep Reinforcement Learning for Traveling Purchaser Problems}},
  year = {2024},
  eprint = {2404.02476},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.02476},
}
Figure