Learning to Solve Routing Problems via Distributionally Robust Optimization

Authors

  • Yuan Jiang Nanyang Technological University
  • Yaoxin Wu Nanyang Technological University
  • Zhiguang Cao Singapore Institute of Manufacturing Technology
  • Jie Zhang Nanyang Technological University

DOI:

https://doi.org/10.1609/aaai.v36i9.21214

Keywords:

Planning, Routing, And Scheduling (PRS), Constraint Satisfaction And Optimization (CSO), Machine Learning (ML)

Abstract

Recent deep models for solving routing problems always assume a single distribution of nodes for training, which severely impairs their cross-distribution generalization ability. In this paper, we exploit group distributionally robust optimization (group DRO) to tackle this issue, where we jointly optimize the weights for different groups of distributions and the parameters for the deep model in an interleaved manner during training. We also design a module based on convolutional neural network, which allows the deep model to learn more informative latent pattern among the nodes. We evaluate the proposed approach on two types of well-known deep models including GCN and POMO. The experimental results on the randomly synthesized instances and the ones from two benchmark dataset (i.e., TSPLib and CVRPLib) demonstrate that our approach could significantly improve the cross-distribution generalization performance over the original models.

Downloads

Published

2022-06-28

How to Cite

Jiang, Y., Wu, Y., Cao, Z., & Zhang, J. (2022). Learning to Solve Routing Problems via Distributionally Robust Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 9786-9794. https://doi.org/10.1609/aaai.v36i9.21214

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling