VARL: a variational autoencoder-based reinforcement learning Framework for vehicle routing problems

摘要

The vehicle routing problem as a classic NP-hard problem could be optimized by path choices due to its practical application value. This study proposes a novel variational autoencoder framework for path optimization on graphs, involving graph neural networks and generative adversarial networks. We took the center node as the root node to divide the graph into different subgraphs and find the nodes that compose the optimal solution through variational reasoning. We next used reinforcement learning to optimize the entire variational framework end-to-end. This contribution can also apply in both modeling and training combinatorial optimization over graphs. An extensive experiment on different scales of traveling salesman and vehicle routing instances was conducted. The findings indicate that our framework is efficient and effective in learning and reasoning, and its accuracy and generalization outperform the baselines.