EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3674. Learning to Generate Hard Instances: Towards Robust Solutions for Vehicle Routing Problems
Invited abstract in session TA-3: (Deep) Reinforcement Learning for Combinatorial Optimization 3, stream Data Science Meets Optimization.
Tuesday, 8:30-10:00Room: 1005 (building: 202)
Authors (first author is the speaker)
| 1. | Xia Jiang
|
| Industrial Engineering and Innovation Sciences, Eindhoven University of Technology | |
| 2. | Yaoxin Wu
|
| Eindhoven University of Technology | |
| 3. | Yingqian Zhang
|
| Industrial Engineering, TU Eindhoven |
Abstract
Deep models have shown promising results in solving vehicle routing problems (VRPs). However, existing models are often trained on instances from specific distributions and their worst-case performance is largely underexplored, thereby hindering the understanding and improvement of their robustness. In this paper, we present a generic framework to generate hard instances for obtaining robust VRP solutions. Given a pretrained deep model, we first develop an attack method that comprises an autoregressive sampling network (ASN) and a hardness measurement network (HMN). The two networks are trained alternately by reinforcement learning, aiming to generate hard instances for the given deep model and gauge the attack effect (i.e., hardness) of the instances, respectively. Then, we propose a simple yet effective training algorithm to robustify the deep model, which is progressively replaced by the continually trained HMN. Experimental results show that the attack method significantly degrades the performance of various deep models and conventional heuristics. Moreover, the training algorithm showcases the ability to enhance the robustness of the deep model, demonstrating its promising zero-shot generalizability.
Keywords
- Machine Learning
- Vehicle Routing
Status: accepted
Back to the list of papers