Multi-view graph contrastive learning for solving vehicle routing problems

• Main Authors: JIANG, Yuan, CAO, Zhiguang, WU, Yaoxin, ZHANG, Jie
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Graph embeddings; Graph theory; Vehicle routing; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/8166; https://ink.library.smu.edu.sg/context/sis_research/article/9169/viewcontent/227_multi_view_graph_contrastive_l.pdf
• Institution: Singapore Management University

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.