Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

8-2023

Abstract

Recently, neural heuristics based on deep learning have reported encouraging results for solving vehicle routing problems (VRPs), especially on independent and identically distributed (i.i.d.) instances, e.g. uniform. However, in the presence of a distribution shift for the testing instances, their performance becomes considerably inferior. In this paper, we propose a multi-view graph contrastive learning (MVGCL) approach to enhance the generalization across different distributions, which exploits a graph pattern learner in a self-supervised fashion to facilitate a neural heuristic equipped with an active search scheme. Specifically, our MVGCL first leverages graph contrastive learning to extract transferable patterns from VRP graphs to attain the generalizable multi-view (i.e. node and graph) representation. Then it adopts the learnt node embedding and graph embedding to assist the neural heuristic and the active search (during inference) for route construction, respectively. Extensive experiments on randomly generated VRP instances of various distributions, and the ones from TSPLib and CVRPLib show that our MVGCL is superior to the baselines in boosting the cross-distribution generalization performance.

Keywords

Graph embeddings, Graph theory, Vehicle routing

Discipline

Databases and Information Systems

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, Pittsburgh, USA, 2023 July 31-August 4

Volume

216

First Page

984

Last Page

994

Publisher

PMLR

City or Country

Pittsburgh, PA, USA

Copyright Owner and License

Authors

Additional URL

https://proceedings.mlr.press/v216/jiang23a/jiang23a.pdf

Download

Share

COinS