Prompt Learning for Generalized Vehicle Routing

1 Introduction

The Vehicle Routing Problem (VRP) can be found in many real-world applications such as logistics, transportation, retail distribution, waste collection, and manufacturing [Toth and Vigo, 2014]. Its objective is to manage a fleet of vehicles optimally, minimizing the total cost while satisfying the demands of customers. As an NP-hard problem, exact methods can hardly solve it efficiently, while heuristic algorithms require costly handcrafted designs with domain knowledge. In contrast, neural combinatorial optimization (NCO), which learns a heuristic based on neural networks, has received growing attention [Bengio et al., 2021;

∗ corresponding author

Raza et al., 2022; Bai et al., 2023; Bogyrbayeva et al., 2024]

solutions without much human effort [Vinyals et al., 2015; Kool et al., 2018; Bogyrbayeva et al., 2024].

Most existing neural combinatorial optimization methods focus on solving in-distribution instances, while real-world routing problem instances are typically from diverse distributions. Therefore, their performance could deteriorate dramatically on out-of-distribution instances [Bi et al., 2022; Zhou et al., 2023]. Recent efforts have focused on enhancing the generalization capabilities for out-of-distribution tasks [Jiang et al., 2022; Bi et al., 2022; Fu et al., 2021; Pan et al., 2023; Manchanda et al., 2023; Drakulic et al., 2023; Jiang et al., 2023; Zhou et al., 2023]. The majority of these approaches involve training a single generalized model using meta-learning techniques [Jiang et al., 2022; Bi et al., 2022; Manchanda et al., 2023; Zhou et al., 2023], which can be adapted effectively to tackle instances from different distributions. However, these methods often necessitate complex and time-intensive meta-learning-based training, while the learning capacity is constrained by the fixed model structure.

This paper proposes a novel approach, which uses prompt learning [Zhou et al., 2022; Liu et al., 2023] to enable fast zero-shot adaptation of a pre-trained NCO model to tackle out-of-distribution routing problem instances. As shown in Figure 1, we keep the pre-trained encoder-decoder NCO model fixed and efficiently learn a pool of key-prompt pairs incorporated into the model for handling different problem instances from diverse distributions. The cross-distribution information is learned through the shared prompts. For solving a new problem instance, the most suitable key will be automatically selected, and its matched prompt will be used to adjust the pre-trained NCO model in a zero-shot manner for better inference. In this way, the proposed prompt learning method can efficiently extend the learning capacity of the pre-trained NCO model, demonstrating competitive generalization performance.

The contributions of this work are summarized as follows:

• We investigate how to incorporate prompt learning into neural combinatorial optimization and propose the first prompt learning method for solving cross-distribution vehicle routing problems.
• We develop a novel and efficient prompt-based attention

model to tackle different routing problem instances from diverse distributions via fast zero-shot adaption.

• We evaluate our proposed prompt learning method on extensive cross-distribution routing instances as well as benchmark instances. With a much lower training cost, our method achieves superior performance compared to existing meta learning methods.

2 RelatedWorks

2.1 Neural Combinatorial Optimization (NCO)

NCO intends to automatically learn a heuristic based on neural networks for solving combinatorial optimization problems. Compared to the other approaches, such as exact methods and heuristic algorithms, it usually generate high-quality solutions with a fast runtime [Bengio et al., 2021]. As a result, NCO has gained much attention in the past decade [Bengio et al., 2021; Bogyrbayeva et al., 2024]. As one of the most important combinatorial optimization problems, the vehicle routing problems have been extensively studied in NCO works [Vinyals et al., 2015; Bello et al., 2016; Nazari et al., 2018; Kool et al., 2018; Li et al., 2022].

There are mainly two categories of works along this line: the end-to-end construction-based methods [Vinyals et al., 2015; Bello et al., 2016; Kool et al., 2018; Kwon et al., 2020; Joshi et al., 2022] and the improvement-based methods [Chen and Tian, 2019; Hottung and Tierney, 2019; Chen and Tian, 2019; Kool et al., 2022]. The former aims to construct a solution without any assistance from classical solvers, while the latter incorporates additional algorithms to improve performance. This work focuses on the construction-based method.

2.2 NCO for Cross-distribution Routing Problem

Several meta learning methods have been developed to improve the out-of-distribution generalization performance for routing problems. Jiang [2022] and Bi [2022] explored the robust optimization over multiple geometrical distributions. Several works [Fu et al., 2021; Pan et al., 2023; Manchanda et al., 2023; Drakulic et al., 2023] studied the generalization to large-scale problems. Zhou [2023] considered generalization in terms of both problem size and geometrical distribution. Most of the existing works adopt a single generalized model and use meta learning methods to improve cross-distribution performance, which might lead to time-consuming training and constrained learning capacity.

2.3 Prompt Learning

Prompt learning has recently gained significant attention in many research areas, such as natural language processing (NLP) [Liu et al., 2023], computer vision (CV) [Jia et al., 2022; Zhou et al., 2022; Ge et al., 2023], and reinforcement learning (RL) [Xu et al., 2022]. In NLP, seminal works like GPT-3 [Brown et al., 2020] and InstructGPT [Ouyang et al., 2022] showcase the effectiveness of prompts in guiding text generation for diverse tasks. In CV, prompt learning can enable few-shot learning [Zhang et al., 2023] and improves image captioning [Wang et al., 2023] by conditioning on specific instructions. In RL, prompt learning can leverage the flexible adaption of prompts to enhance the few-shot policy generalization performance [Xu et al., 2022].

In recent years, many well-trained models have been developed for combinatorial optimization [Kool et al., 2018; Kwon et al., 2020; Bogyrbayeva et al., 2024]. However, the effective utilization of these pre-trained models has not been thoroughly investigated. This paper proposes a prompt learning method to efficiently adapt a fixed pre-trained model for addressing cross-distribution vehicle routing problems.

3 Prompt Learning for Routing

3.1 ProblemFormulation

We denote a basic capacited vehicle routing problem (CVRP) on an undirected graph G = (V,E). V = {v0, . . . , vn}, where v0 is the depot and v1, . . . , vn are the n customers. Vc = {v1, . . . , vn} is the customer set. For the i-th customer, there is a demand di. E = {eij}, i, j ∈ {1, . . . , n} are the edges between every two nodes. For each edge eij, there is an associated cost (distance) cij. A fleet of homogeneous vehicles with a capacity of C is sent out from the depot to visit the customers and return to the depot. All the customer's demands should be served. Each customer must be visited once. The objective is to minimize the total traveling distance of all the routes with all the constraints satisfied.

3.2 Main Idea and Basic Framework

The typical constructive-based NCO methods [Kool et al., 2018; Kwon et al., 2020] use an attention-based encoderdecoder model to directly construct a valid solution (e.g., a tour) for the mentioned routing problem. They learn the best model parameters for the attention model to minimize the total distances. In this case, the objective of model training would be:

where G represents the given instance, θ is the model parameter, and τ is the trajectory (e.g., tour) constructed by the model. The goal is to find the best model parameter θ∗ to minimize the average total distance (as the training loss L) for τ over a given distribution p(G).

When explicitly considering multiple distributions in model training, most existing works treat each distribution as a task and use meta learning for model training [Manchanda et al., 2023; Zhou et al., 2023]. The objective is to learn a single yet robust model parameter θ∗ that can generalize well over various distributions.:

where T is the number of tasks, and p(G) represents the distribution over i-th task.

Different from the two approaches, we propose to incorporate prompt learning into the NCO model for tackling crossdistribution vehicle routing problems. The objective can be formulated as:

where {P1, . . . , PM} are M prompts, and P is the selected prompt for each given instance. In this prompt-based model, we can learn the M prompts instead of the entire set of model parameters θ. The objective here is to learn the best prompts that adapt the pre-trained model with a fixed θ for acrossdistribution performance.

As illustrated in Figure 1, our proposed prompt learning consists of three main components: 1) feature extractor, 2) prompt engineering, and 3) prompted model. We adopt pretrained attention networks as the feature extractor and the model, which remain fixed during training and testing. The keys are also predetermined based on the features of the randomly generated training instances. The only adjustable components are the prompts. The input instance is fed into both the model and the feature extractor. The feature extractor converts the input instance into a feature vector, allowing us to identify the most appropriate key from the key-prompt pair pool to match the input feature. The key and prompt are coupled together. The associated prompt of the best-matched key is then used to prompt the pre-trained model. A solution is generated by the prompted model, based on the selected prompt. The solution is used to calculate rewards for updating the selected prompt during training.

3.3 Feature Extractor

In this work, we directly use the encoder of the attention model [Kool et al., 2018] as the feature extractor. The encoder consists of L stacked multi-head attention (MHA) blocks. The input of the encoder is the node features fi, i = 1, . . . , n. In our experiments, the input features for the i-th node are denoted as fi = {xi, yi, di}, where (xi, yi) are the coordinates and di is the demand. The input features are embedded through a linear projection to generate the initial feature embedding h(0) i . The skip connections [He et al., 2016] and instance normalization (IN) are used in each MHA layer:

where l and l - 1 represent the current and last embedding layers, respectively. The feedforward (FF) layer contains a hidden sublayer with ReLU activations. The above encoding process generates the final node embeddings h(L) i .

Different from the commonly used feature extraction approach in CV and NLP, which uses the embedding of a specific hidden layer, we concatenate the embeddings from multiple layers. Specifically, we concatenate the output layer of every MHA (before normalization):

where F l is the hidden embedding before the last norm layer of the l-th MHA and F is the concatenated feature of all L layers. Each hidden embedding F l is averaged over all n nodes to facilitate generalization across different problem sizes. The final output feature for prompt engineering is adjusted by standard scalarization, given as F = (F -mean)/stand, where mean and stand represent the mean and standard deviation of the preprocessing instances, respectively. These preprocessing instances are employed for determining the keys. The mean and standard deviation are calculated element-wise.

3.4 Prompt Engineering

We maintain a key-prompt pair pool, which consists of M key-prompt pairs {Ki, Pi}, i = 1, . . . ,M, where Ki and Pi are the i-th key and prompt, respectively. Each pair has a fixed key and a learnable prompt. For each input feature Fi, we find the best-matched key ˆK = minS(Fi,Kj), j = 1, . . . ,M, where S() is the distance function. The distance function we employ is the Euclidean distance of the input feature and the key. The prompt ˆ P associated with ˆK is then selected to prompt the pre-trained neural solver. In each batch with B instances, B keys are chosen, and the associated B prompts are updated during training.

The keys Ki, i = 1, . . . ,M are predetermined vectors of the same size as the feature. They remain fixed throughout the training process. We randomly sample 128 instances from each of the 341 distributions, resulting in a total of 43, 648 instances for generating the feature data. The 341 distributions are introduced in the Appendix. For each instance i, we utilize the feature extractor introduced in equation (5) to extract the features Fi. We divide the samples into four groups based on problem sizes. For each group, we employ K-means clustering to cluster the samples into N clusters. The cluster centers of the features are then used as the keys. Ultimately, we obtain M = 4·N vector cluster centers, which are utilized as the keys for prompt learning.

For each key Ki, we randomly initialize a vector as the associated prompt Pi according to a uniform distribution and scale the prompt within the range [-1, 1].

The key-prompt pairs are connected only in terms of utilization, meaning the associated prompts are used based on selected keys. While their values are decoupled, we only update prompts with key fixed during training. The structure is intentionally kept simple, without dynamically adjusting both keys and prompts. Furthermore, the sizes of the keys and pairs are also different. The former is determined by the feature size, while the latter should be sufficiently long to prompt the pre-trained model, which is introduced in the next subsection.

3.5 PromptedModel

We choose the well-known Attention model [Kool et al., 2018; Kwon et al., 2020] as our pre-trained model because it is extensively employed in various routing problems [Bogyrbayeva et al., 2024]. The model consists of a six-layer encoder and a one-layer decoder. During inference, the encoder inferences once, and the solution of the target routing instance is generated iteratively by the decoder. The selected prompts are used for prompting the six-layer encoder, which allows more control over the pre-trained attention model.

Encoder The structure of the pre-trained encoder is the same as that used for the feature extractor. It consists of a sixlayer MHA, with the linear projection h(0) i of instance feature fi as the input and the final node embedding h(L) i as the output.

Prompted Encoder The selected prompt P from prompt engineering is firstly split into L subprompts P l , l = 1, . . . ,L. Each subprompt P l is used for the corresponding embedding layer of the pre-trained encoder. P l has a length of D·E, where D is the number of tokens and E is the length of the token. Then, the l-th subprompt P l is reshaped into D prompt tokens p(l) i , i = 1, . . . ,D:

These tokens are concatenated into the corresponding l-th layer of the encoder. Specifically, for the l-th MHA, the D prompt tokens are concatenated with the input hidden layer as follows:

As a result, the length of the input tokens of l-th layer of MHA is always larger than the input tokens of l - 1-th layer by D. There will be n + L · D output embedding tokens in the last layer of the encoder. We only use the first output n embedding tokens for the decoder instead of all the n+L ·D tokens. The first n embedding tokens represent the n nodes of the instance, which are controlled by the L·D prompt tokens.

Decoder The decoder constructs a solution sequentially. It consists of one MHA layer and one single-head attention (SHA) layer with clipping. The MHA is slightly different from that used in the encoder, where the skip connection, instance normalization, and FF sublayer are now not used [Kool et al., 2018]. The t-th step of inference is as follows:

where h(L) t and at represent the embedding of selected node and attribute in the t-th step, respectively. The output embedding of MHA ˆhc is used as the input of the SHA. The SHA outputs the probabilities of choosing the next node using a softmax pi = eui ∑j euj with the unsatisfied nodes masked. We omit the step indicator t for readability. The detailed structure of the MHA and SHA can be found in Kwon [2020].

3.6 Training with Reinforcement Learning

We use the REINFORCE algorithm with a shared baseline following Kwon [2020] to update the selected prompts in each batch. We use greedy inference, i.e., a deterministic trajectory τ is constructed iteratively based on the policy. In each construction step t, the next node vt is selected as the one with the maximum softmax probability t = arg maxi(pi) predicted by the decoder. n trajectories are constructed from n different starting points.

The rewards R(τ1), . . . ,R(τn) are the negative total distances of trajectories τ1, . . . , τn. We use the following gradient ascent to update prompts P in each batch with size B:

∇P J (θ, P )

where P and θ are trained prompts and fixed parameters for the model. s represents the instances. pθ,P (τ i j ) is the aggregation of the probability of selection in each step of the decoder based on both the fixed θ and the prompts P. b(s) is the shared baseline [Kwon et al., 2020].

4 Experiments

4.1 Experimental Setting

Model Settings We use the Attention model as our backbone pre-trained model. It is only trained on uniformly distributed CVRP instances of size 100. All the settings for the pre-trained model are the same as that used in the paper of Kwon [2020]. The number of encoder MHA layers is six and the decoder consists of one MHA and one SHA.

The settings of the key-prompt pair pool are as follows: The prompt size is set to be M = 16, and the number of prompted tokens for each layer is D = 5. As there are L = 6 MHA layers in the encoder and the embedding size for each token is E = 128, the lengths of the key and prompt vectors are 6 · 128 = 768 and 5 · 6 · 128 = 3840, respectively.

InstanceGeneration We trained themodel on a set of routing tasks with diverse sizes and geometrical distributions.

The detailed instance generation is introduced in the Appendix, which is the same as that used by Zhou [2023]. The problem size ranges from 50 to 200 with both uniform distribution and various clustered Gaussian distributions. There are in total 341 distributions.

Training Setup The prompts are trained with a batch size of B = 64. The 341 distributions are sequentially used during the training. In each batch, we randomly sample B instanced from one distribution. As a result, every distribution will be sampled in 341 epochs. The maximum number of epochs is 10, 000 and there are 1, 000 instances for each epoch. The learning rate decays from 1e-3 to 1e-5. It takes only about 2.5 days on a single RTX 2080Ti with 11 GB GPU memory.

Baselines We compared our proposed prompt learning to three different types of methods. 1) Baseline heuristic VRP solvers: hybrid genetic search (HGS) [Vidal et al., 2013], LKH3 [Helsgaun, 2017]; 2) NCO methods: basic POMO [Kwon et al., 2020] trained on single-distribution, and POMO [Zhou et al., 2023] trained on diverse distribution; 3) meta learning NCO methods: Meta-POMO [Manchanda et al., 2023], and the newest revision of meta-learning method for omni-generalization on vehicle routing problems (Omni) [Zhou et al., 2023]. The results for HGS and LKH are obtained by executing the open-source code on the instances. For the basic POMO, we train the model by ourselves on CVRP of size 100 with uniform distribution. This model is also utilized as the pre-trained model in our proposed prompt learning approach. For the meta-learning methods, we utilized the pre-trained model from Zhou [2023] as it was trained on the same distributions as ours.

4.2 Results on Training Tasks

The results on training distributions are compared in Table 1. For simplicity, we list the averaged results over 1,000 instances on three problem sizes with uniform distribution. More results are included in the Appendix. We use HGS as the baseline and compare the training cost, average distances (Dis.), average gap to the baseline (Gap), and the inference time cost (Time). We executed HGS and LKH with time limits of 5s and 10s for problem sizes of 50 and 100, respectively. For instances with a problem size of 200, the time costs for each instance with HGS and LKH were 20s and 60s, respectively. It should be noted that LKH3 is not fully converged in some instances. We adopted the same data augmentation method (aug) as in Kwon [2020]. Additionally, for our prompt learning, we present the inference results using the top-k matched prompts. Further discussion on the top-k prompts is provided in the following section.

The proposed prompt learning method has a considerable reduction in training costs when compared to meta-learning methods. According to Zhou [2023], the second-order derivative method needs about 6 days and 71GB GPU memory and the training cost can be reduced to 3 days on 25GB GPU with a smarter strategy. For a fair comparison, we adjust the training cost of our prompt learning approach to match the experimental settings of the meta-learning methods. Specifically, prompt learning requires roughly 1 day on a 25GB GPU, considering the allowance for a larger batch size.

Our prompt learning model outperforms existing metalearning methods and the basic POMO model on all three problem sizes in terms of average distances. The basic POMO model with single-distribution learning overfits the training distribution. Because the basic POMO is trained on uniform distribution instances with a size of 100, it has good performance on the 100 instances set but deteriorates on the other two sizes. The two meta-learning methods' performance is more robust across different sizes compared with the basic POMO. Our prompt learning further reduces the gap. The prompt learning with the top 8 prompts ranks first in all sizes.

4.3 Zero-shot Generalization

We demonstrate the zero-shot generalization performance of prompt learning on new distributions that were not used during training. We adopt the distribution proposed by Bi [2022], which consists of a total of 12 different distributions, including cluster (CL), expansion (EA), explosion (EO), implosion (IM), grid (GR), and mixed (MX). Each distribution encompasses two different problem sizes, and we conduct tests on 1,000 instances for each distribution. We use HGS as the baseline. The total execution times on each distribution for both HGS and LKH on sizes 50 and 100 are 1.4h and 2.8h, respectively.

Table 2 lists the zero-shot generalization performance on the 12 new distributions. The best results are in bold. Our prompt learning achieves the best average results. The average gap to the baseline is about 3%. With data augmentation, the gap can be further reduced to less than 2%.

4.4 Top-k Prompts

Instead of relying on a single best-matched prompt, we can employ multiple prompts simultaneously during the inference stage to enhance performance. To achieve this, we propose a top-k strategy, in which the top-k prompts (determined by the Euclidean distance between the key and feature vectors) are chosen. These k prompts are then used concurrently during inference, and the best solution is selected as the final solution for each instance. This approach allows us to fully leverage our learned prompts without incurring any additional training costs.

Figure 2 shows the results obtained on instances of three different problem sizes with uniform distribution. The x-axis represents the number of prompts (k) employed in the top-k strategy, while the y-axis represents the difference in performance compared to the baseline HGS. Generally, the performance improves with an increase in the number of prompts. Moreover, the reduction in the gap is not linearly proportional to the number of prompts used, which suggests that the bestmatched prompt is more significant than others.

4.5 Prompt Token Size

The number of prompt tokens D in each encoder layer influences the performance of our prompt learning network. A larger number of tokens results in a longer prompt vector, providing the ability to prompt the attention-based encoder more effectively. In order to investigate the impact of the token number on our models, we conducted two additional prompt learning experiments. Specifically, we set the token numbers in the two models as 1 and 10, respectively. Consequently, the lengths of the prompt vectors in these models are 1 · 6 · 128 = 768 and 10 · 6 · 128 = 7680. All other training models and settings remain unchanged.

The outcomes of the experiments involving different numbers of prompt tokens are presented in Table 3. The table includes results from four training distributions, distinguished by their numbers of prompt tokens. U and GM represent uniform distribution and Gaussian distribution with 3 clusters and scaled by 50 (details of instance generalization please refer to the Appendix). Minor differences in results are observed for instances with a size of 100, while more significant variations are noticed across other distributions. This discrepancy arises because the pre-trained basic POMO model utilized in prompt learning is trained on routing instances with a size of 100. Hence, the model already exhibits satisfactory performance on in-distribution instances. However, when adapting the pre-trained model to out-of-distribution instances, the number of tokens assumes importance. For example, in the case of 200 GM instances, there is approximately a 1% performance increase (reduction in gap) from 1 token (2.93%) to 10 tokens (2.02%). Overall, prompt learning with a larger token size allows better generalization performance.

4.6 Real-world Instances

More experiments on real-world instances are conducted on five test suites: set A, B, P, X [Uchoa et al., 2017], and XML [Queiroga et al., 2021] from CVRPLIB 1 . There are 115 instances in total with various geometrical distributions, demands, and problem sizes, which can provide a comprehensive evaluation of our proposed method. Table 4 summarizes the average gap to the best-known results from CVRPLIB. The best results are in bold. The detailed results can be found in the Appendix.

In Figure 3, we visualize the selected frequencies (normalized) of 16 prompts on test set P, X, and XML. Set X and Set XML have similar frequency distributions, which are different from Set P. For example, prompts 11-15 are frequently used for Set X and XML while rarely used in Set P. The results show that the instances from Set X and Set XML are of similar distributions. As has been mentioned in the paper of Queiroga [2021], the generator of XML is the same one used for X instances. It answers why the basic POMP performs well on these two sets while much worse on Set P. It also demonstrates that our prompt learning can recognize the features of new instances and select the best-matched prompt for better performance.

1 http://vrp.atd-lab.inf.puc-rio.br/

5 Conclusion

This paper investigates the first prompt learning based neural combinatorial optimization (NCO) method to solve vehicle routing problems over diverse distributions. We propose a prompt-based attention network with a learnable keyprompt pair pool to facilitate the fast zero-shot adaptation of the pre-trained NCO model for cross-distribution generalization. To evaluate the effectiveness of our proposed prompt learning method, we conduct extensive experiments on test instances with various distributions. The results clearly demonstrate the superiority of our approach over classical single-distribution learning methods and existing meta learning techniques. Our prompt-based model achieves improvements in both in-distribution prediction and zero-shot generalization to a diverse set of new tasks while requiring lower training costs.

Acknowledgments

The work described in this paper was supported by the Research Grants Council of the Hong Kong Special Administrative Region, China (GRF Project No. CityU 11215723) and the Shenzhen Technology Plan, China (Grant No. JCYJ20220530113013031).