Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization

摘要

Vehicle routing problems (VRP) are very important in many real-world applications and has been studied for several decades. Recently, neural combinatorial optimization (NCO) has attracted growing research effort. NCO is to train a neural network model to solve an optimization problem in question. However, existing NCO methods often build a different model for each routing problem, which significantly hinders their application in some areas where there are many different VRP variants to solve. In this work, we make a first attempt to tackle the crucial challenge of cross-problem generalization in NCO. We formulate VRPs as different combinations of a set of shared underlying attributes and solve them simultaneously via a single model through attribute composition. In this way, our proposed model can successfully solve VRPs with unseen attribute combinations in a zero-shot generalization manner. In our experiments, the neural model is trained on five VRP variants and its performance is tested on eleven VRP variants. The experimental results show that the model demonstrates superior performance on these eleven VRP variants, reducing the average gap to around 5% from over 20% and achieving a notable performance boost on both benchmark datasets and real-world logistics scenarios.