End-to-end Deep Reinforcement Learning for Stochastic Multi-objective Optimization in C-VRPTW
Authors: Abdo Abouelrous
Laurens Bliek
Yaoxin Wu
Yingqian Zhang
Venue: Accepted by TMLR ()

Abstract: In this work, we consider learning-based applications in routing to solve a Vehicle Routing variant characterized by stochasticity and multiple objectives. Such problems are repre- sentative of practical settings where decision-makers have to deal with uncertainty in the
operational environment as well as multiple conflicting objectives due to different stakeholders. We specifically consider travel time uncertainty. We also consider two objectives, total travel time and route makespan, that jointly target operational efficiency and labor regulations on shift length, although more/different objectives could be incorporated. Learning-based methods offer earnest computational advantages as they can repeatedly solve problems with limited interference from the decision-maker. We specifically focus on end-to-end deep learning models that leverage the attention mechanism and multiple solution trajectories. These models have seen several successful applications in routing problems. However, since travel times are not a direct input to these models due to the large dimensions of the travel time matrix, accounting for uncertainty is a challenge, especially in the presence of multiple objectives. In turn, we propose a model that simultaneously addresses stochasticity and multi-objectivity and provide a refined training mechanism for this model through scenario clustering to reduce training time. Our results show that our model is capable of constructing a Pareto Front of good quality within acceptable run times compared to three baselines. We also provide two ablation studies to assess our model’s suitability in different settings.

Published in Transactions on Machine Learning Research (02/2026)
End-to-end Deep Reinforcement Learning for Stochastic Multi-objective Optimization in C-VRPTW
Abdo Abouelrous
G.g.m.abouelrous@@tin ml
Deportment of Information Systems, Faculty of Industrial Engineering and Innovation Sciences, Technical University Eindhoven, The Netherlands
Laurens Blick
Lblick&tue..t
Department of Information Systems, Facully of Industrial Engincering and Innovation Sciences, Technical University Eindhoven, The Netherlands
Yaoxin Wu
y. w.w.2@lue.d
Department of Information Systems, Faculty of Industrial Engineering and Innovation Sciences, Technical University Findhoven, The Netherlands
Yingqian Zhang
ygahang@tue.. nl
Department of Information Systems, Faculty of Industrial Engineering and Innovation Sciences, Technical University Eindhoven, The Netherlands
Reviewed on OpenReview: https: // openreview. foru?? id= 4a
Abstract
In this work, we consider learning-based applications in routing to solve a Vehicle Routing variant characterized by stochasticity and multiple objectives. Such problems are repre- sentative of practical settings where decision-makors have deal with uncertainty in the operational environment as well as multiple conflicting objectives due different stakehold- We specifically consider travel time uncertainty. We also consider two objectives, total travel time and route makespan, that jointly target operational efficiency and labor regula- tions on shift length, although more more/different different objectives could be incorporated. Learning- based methods offer earnest computational advantages as they can repeatedly solve problems with limited interference from the decision-maker. We specifically focus on end-to-ond deep learning models that leverage the attention mechanism and multiple solution trajectories. These models have seen several successful applications in routing problems. However, since travel times are not direct input these models due to the large dimensions of the travel time matrix, accounting for uncertainty is challenge, especially in the presence of multiple objectives. In turn, we propose model that simultaneously addresses stochasticity and mujti-objectivity and provide a refined training mechanism for this model through scenario clustoring to reduce training time. Our results show that our model is capable of construct- ing Pareto Front of good quality within acceptable run times compared to three baselines. We also provide two ablation studies assess our model's suitability in different settings.
Stochastic, Multi-Objective Optimization, Vehicle Routing Problem, Reinforcement Learning, Active Search, End-to-End
Keywords:
1 Introduction
The Vchicle Routing Problem (VRP) problem of significant industrial relevance contemporary oconomies where vehicle delivery operations play pivotal role in the supply chain (Vidal et al., 2020). Real-life variants often characterized by certain challenging features. Fxamples of such features include

---

Published in Transactions on Machine Learning Research (02/2026)
stochasticity and the presence of several (conflicting) objectives simultaneously. Accounting for these fea- tures during decision-making is important. Otherwise, sub-optimal decisions may lead to elevated costs. In practical settings, computational budgets are often limited as solutions need to be generated quickly in accordance with operational requirements (Horvitz, 2013). To that end, one seeks optimization tochniques that are capable of delivering near-optimal solutions efficiently in the presence of compulational challenges posed by factors like uncortainty and multi-objectivity.
In the literature, numerous techniques have been proposed to solve Combinatorial Optimization (CO) prob- lems like VRP, ranging from hand-crafted heuristics to Machine Learning (ML) models that are indepen- dently able to generate solutions also known as end-to-end methods (Kotary et al., 2021). The spectrum also covers hybrid methods, which incorporate both heuristics and ML models. ML models are particularly useful in cases where problem parameters follow a known distribution. In such cases, an ML model can be trained on a dataset of problems from this distribution and used generate solutions for problem instances arising in the future. This is because ML models have the capacity to learn from the collective expert knowl- edge. Through learning common solution structures and relationships to problem parameters. Although the training resources required are not trivial, ML models can be quickly applied for solving thereafter. (Bengio et al., 2021; Giuffrida et al., 2022; Mazyavkina et al., 2021; Zhang et al., 2021; Kool et al., 2018).
In our estimation, CO problems treated in the literature by ML barely treated stochastieity and multi- objectivity together. The objective of our study is to extend the framework ML in optimization to settings that jointly combine both problem features. Solving a multi-objective problem requires the definition of a Pareto Front (Ngatchou et al., 2005), comprising of a set of Pareto optimal solutions by which improving one objective can not be done without worsening other objectives. Solutions would then have to be validated sample of scenario realizations to estimate their quality and feasibility. In optimization context, this poses a challenge that requires novel intervention. This is because multi-objectivity induces the generation of several solutions to estimate the Pareto Front, while stochasticity imposes that each solution be feasible with a good score for a large number of stochastic realizations. The repeated evaluation of multiple solutions, in this setting, a cumbersome lask that requires careful choices in the optimization methodology to maintain computational costs within practical limits.
In response, we present framework that addresses the given computational issucs in this paper to solve Capacitated Vehicle Routing Problem with Time Windows (C-VRPTW), popular variant of VRP (Liu et al., 2023). We specifically focus on stochasticity in travel times and consider two objectives that are travel time-based, although our method could account for more different objectives. The major contributions prescribed by this paper are:
Presenting the first end-to-end (independently constructs solution without interference of a heuristic) deep-learning model that jointly treats stochasticity and multiple objectives for routing. Providing a retraining mechanism for parameter uncertainty through an active search that considers multiple objectives rather than just one objective.
Presenting a scenario-clus clusterrnn technique that enhances the computational efficiency of model re- training during active scarch.
The remainder of the paper is organized as follows. Section 2 introduces previous rescarch. Section 3 describes the relevant problem in detail. Section 4 outlines our methodology Section 5 presents numerical experiments and results. Lastly, Section 6 asserts the conclusions.
2 Previous Work
We restrict our attention to ML applications in stochastic and/or multi-objective cases for routing. These models generally rely on concepts of Reinforcement Learning (RL) to make decisions. These approaches fall into two major categories, hybrid and end-to-end. Hybrid models integrate a ML model with a heuristic to enhance the hcuristic's performance. The way which the ML model applied largely depends on the heuristic at hand. A common example is that the RL agent selects a heuristic with some probability from a set of discrete heuristics. In contrast, End-to-end models are able independently solve routing problem
2

---

Published in Transactions on Machine Learning Research (02/2026)
without interference of a heuristic. When deciding on the ordering of node visits, the decision to visit node after node i is based on probability Pij. Such a probability may be determined by features of nodes i and j, the status of the current (partial) solution and the estimated corresponding reward. In both categories, the decisions are determined by interaction of the problem input with the ML model's parameters which are optimized during model training to maximize the final reward.
For the multi-objective setting, works like Wu et al. (2024) and Deng al. (2024) explore applications to routing with hybrid methods through genetic algorithms. Yao et al. (2017), the other hand, focus on hyper- heuristic selection by the RL agent to complete solution. In the Stochastic setting, Bayliss (2021) make use of simulation-augmentee optimization for urban-routing. Joc & Lau (2020) employ a hybrid approach with a genetic algorithm to address a dynamic problem with stochastic customers. Works integrating both stochastic and multi-objecctvv components are rare, at least in routing. Tozer et al. (2017) propose an RL model that selects voting methods based on social choice theory for path-finding. Niu et al. (2024) and Niu al. (2021) embed a decision tree that learns node orderings in a genetic algorithm in location and vehicle routing, while Peng et al. (2023) adapt the same approach but for multi-modal transportation. Zhang et al. (2024), in contrast, optimize multi-modal transportation routing using framework aided by simple Q-learning.
Recent innovations in the literature have prompted the use of Deep Reinforcement. Learning (DRL) to solve CO problems. Among the earliest of end-to-end ML applications in routing was Kool et al. (2018) who leverage a Graph Attention network Veličković et al. (2017) to estimate P.j- Kwon et al. (2020) extended on this by presenting a model that uses multiple solution trajectories during model training and solution inference (generation) which we refer to Policy Optimization with Multiple Optima (POMO) for simplicity. POMO is able to process complex graph information and greedily decide on the next node visit most likely to minimize the objective value(s). The model is well-credited for its ability to generate solutions of high quality in a relatively short time compared to alternative solvers and heuristics for a multitude of routing problems given a cortain distribution. During training, POMO Iearns the relationship between node orderings and the resulting final objective values to look for orderings that minimize the objective in the future.
The impressive performance of DRL-based methods like POMO has led to adaptations in multi-objective and stochastic cases for routing. For multi-objective CO routing problems, DRL has been proposed in works like Sarker el al. (2020), Wang et al. (2023), Chen et al. (2023) and Lin et al. (2022). For applications in stochastic CO routing problems, works like Schmitt-Ulms et al. (2022), Achamrah (2024), Iklassov et al. (2024) and Zhou et al. (2023) showcase end-to-end methods addressing demand and travel-time uncertainty, which is usually accounted for by fine-tuning the pre-trained model's parameters. In these works, routing problems are solved in an end-to-end fashion whereby the RL model decides on successive node visits. This is in contrast to other DRL innovations that rely on hybrid methods (Jia et al., 2025; Son et al., 2024) for stochastic and multi-objective applications.
To the best of our knowledge, there is no end-to-end DRL mechanism for solving routing (or CO) problems characterized by both unceraiinyy and multiple objectives. Many of the multi-objective DRL architectures can not be easily adapted to account for uncertainty and vice-versa. On the other end, existing hybrid methods depend on the heuristics at hand which are often problem-specific. For example, deriving voting mothods or lcarning node orderings with decision trees may not be suitable for more complicated vehiele routing variants such as ones with time windows. Ideally, one would like to come up with an end-to-end model that can be easily adapted to solve a multitude of routing problems without the complexities associated with external assumptions or hyper-heuristics. The novelty of this paper is embedded in deriving such a framework for solving C- C-VRPTW, although the framework can be casily adopted to solve other routing problems as explained below.
3 Problem Description
Consider a C-VRPTW instance with parameter imput P and stochastic travel times T, where T E P. Fur- thermore, assume the problem is characterized by a sct of K objectives for which preference Ag corresponds to objective (.)/k E K. The preferences d are embodded in a vector x. For simplicity, assume Σ ) =1 and 0 < (a))
3

---

Published in Transactions on Machine Learning Research (02/2026)
Such preferences could reflect the decision- view of importance of one objective relative to another. Such preferences may not be explicitly defined initially, but repeatedly solving the problem with different As values enables the decision-maker to understand the relationship between decisions and corresponding objective values through the construction a Pareto Front. Thereafter, the docision-maker can choose decisions on the Parelo Front that aligu with their preferences. The proposed model should therefore be able to approximate a Pareto optimal solution for any set of preferences as much as possible.
Let be the number of nodes that may be visited in a solution and V be the set of nodes, so that [V = Each node i V is characterized by some features that depend the problem at hand, such demand or time-windows. Between cach pair of nodes, there is an are with travel times corresponding to the stochastic parameters T. That said, T is a nt x matrix with elements bij representing the travel times between nodes and j E V. Let ty follow some predetermined probability distribution (.)(). Depending on the problem, a depot may be defined as well. If so, we index the depot by 0, so that V and define stochastic travel times for and tu for each other node i V.
The objective is to jointly optimize all the K objectives while satisfying operational constraints. In C- VRPTW, time-window constraints, well as objective values, are largely determined by travel times. As such, we are dealing with a CO problem where the objective values and constraint satisfaction for a set of actions/decisions are uncertain.
Our proposed model strives to define a mapping- specified by a set of parameters 0 between graph information and associated node ordering in a solution that maximizes rewards (i.e. delivers good objective values). Our model takes into account the uncertainty in travel times represented by the graph's are lengths and conflicting rewards (objectives). The mechanism by which define this mapping serves the purpose of our study. Furthermore, cases with uncertain travel times T pose greater challenge than others in the literature such as in Niu et al. (2021) which deal with stochastic demand. This is because the number of travel time parameters is much more than demand parameters, invoking a larger computational capacity to process the associated uncertainty. Furthermore, different node orderings can give different feasibility and solution scores for a given set of travel time realizations, contrast to the case with stochastic demand. Tn the following section, we present method that treats the problem presented above.
4 Methodology
We propose a single machine learning model whose training is partitioned into two phases. One phase deals with the multi-objective component of the problem and the latter with the stochastic component. Our model is variant of the POMO model whose parameters correspond to 0. It is firstly trained on sample of multi-objective deterministic instances. Afterwards, the parameters embedding information on the travel times are re-trained to account for the stochasticity. The retraining is done by means of an Efficient Active Search (EAS) which we will explain below. Finally, given problem input P and a vector of preferences X, we apply a solution generation procedure with the re-trained POMO model to produce a solution. The Pareto Front can then be estimated by repeatedly solving the problem P for different values of X. An overview of our overall method is illustrated in Figure In the following section, we elaborate on the components of our approach.
4.1 Multi- Oujei-Obeective Component
The standard POMO model seen in Kwon et al. (2020) defines a mapping with parameters / between problem parameter input P and resulting reward/objectivg value. More precisely, the model's main architecture is given by an encoder-decoder duo. The encoder with parameters fenc takes as input problem parameters to construct an embedding w, which is a summary of the problem features as explained in Kool et al. (2018). w is then used alongside other dynamic information pertaining to the current status of the solution by the decoder with parameters dde to take actions until a solution is complete with corresponding reward. Since the reward is constant for every set of parameter input P, the decoder can automatically process w and make a decision.
4

---

Published in Transactions on Machine Learning Research (02/2026)
Train multi- abjective POMO model on data
Multi-objective Component
Pro-trained POMO model with deterministic embedding
Predetermined Training Dataset
Retrain Model with Efficient Active Search
X, P
Stochastic Component
Stochastic Embedding
Pareto Front
Apply solution generation mechanism given problem input
Figure 1: Visual illustration of our complete approach using pre-trained POMO model.
In the multi-objective sctting, the reward depends on the preferences A. To that end, the information neoded to make decision is not entirely prescribed by the embedding In turn, Lin et al. (2022) propose multi- objective variant of POMO. The idea is to equip the decoder with Multi-Tayer Perceptron with parameters i that takes X as imput and determines the corresponding decoder parameters 0(A/v)) The resulting POMO model can then be used to construct Pareto Front by repeatedly sampling realizations of À and solving the corresponding problem for a single realization one time. Since POMO models can solve a single instance quite efficiently, the Pareto Front would require significant computational budget to be constructed.
Figure 2 depicts the process by which solution is generated with the model of Lin et al. (2022). This model and its training correspond to the Multi-objective component in Figure 1. In the following section, we explain how the embedding w generated from this model is updated by means of an EAS to adapt to stochastic travel times T E P.
Encoder with model parameters Denc
Embedding w summarizing problem data
problem input fed
problem input processed
Embedding fed
Multi-Layer Perceptron with parameters
A
Model decoder with parameters dee (2ep)))
preference: fed
hyper-nelwork estimates decoder parameters
POMO greedy mechanism constructs solution
Solution Generated
Figure 2: Overview of solution generation with the model of Lin et al. (2022).
5

---

Published in Transactions on Machine Learning Research (02/2026)
To compute the reward for given solution म; for problem instance 8t, Lin et al. (2022) propose a linear aggregation technique. The K' objectives are aggregated into single objective (reward) as follows:
{kfa(T)))
(1)
KEK
with fs))) representing objective k. The term in (1) corresponds to the reward L[T; (1,)) for solution n; given instance 8; and preferences A. Solution is generated according to a probability distribution Pa(x) (Ti(s:) which can be constructed in greedy or sampling fashion.
There is an important considcration with regards to lincar aggregation. While lincar aggregation has been proposed in studies like Lin al. (2022), it unable produce a non-convex front, which may arise in CO problems based on mixed integer programs like C-VRPTW (Pappas al., 2021). One should, thus, consider the observed objective values and see whether they are in line with the comparison metrics.
The model is trained by repeatedly sampling preference vector À and corresponding batch of B instances. Thereafter, M different solution trajectories are created where each trajectory represents one possible solu- tion. The average reward over all the M different solution trajectories and / instances is computed, where the reward from one trajectory corresponds to some aggregation of the K objectives such as in (1). The average reward is, turn, used to compute the loss function and associated gradient for optimizing the model's parameters 0. To estimate the gradient loss, we make use of the REINFORCE training algorithm of Williams (1992) with the ADAM optimizer. The training algorithm is summarized in Algorithm 1.
Algorithm Training POMO Model from Lin et al. (2022)
Input: preference distribution A, instances distribution 8, number of Training steps T, number of objectives K, batch size B, number of solution trajectories M.
Output: model parameter 0.
3: for t= 1.... do
4: Sample 2 from A for k E K.
5: Sample B instances from
Generate M different solutions using (-(ss)(-(s;) for each instance 8,.
7: Define shared baseline reward for instance 8; using by मे Σn [TT a.)
Vi[I,...,
8: Compute gradient A = BM
1 E ( - bo) log Po(x) (o(2)(==/11))) [m/
9: 0= A-AAM Ae)
10: end for
11: return 0.
4.2 Stochastic Component
Given that travel times are not encoded with the problem input for POMO, but implicitly represented by parametrized embedding w, an EAS is introduced in Schmitt-Ulms et al. (2022) by which the model is re-trained to adapt to the different possible stochastic realizations of T. In the retraining phase, only w is updated. In each step, a gradient Aw is computed with M solution trajectories by the following formula:
1 M Σ [((T)))) b) log log
A
(2)
and w is updated by means of gradient ascent. For consistency, we use the ADAM optimizer for the update, Observe that the gradient computation in (2) is similar to the one in Line 8 in Algorithm 1 based on the REINFORCE algorithm. The major differences is that this update concerns only one instance rather than a batch of B instances, and the only parameters being updated are w. As such, the probability distribution Pw(x) (w)x)(T>)s)) is determined by updates in w.
The embedding updated over a series of Tw steps for instance with expected travel times E|T] and then evaluated on W stochastic realizations every le iterations. be can be interpreted as the evaluation

---

Published in Transactions on Machine Learning Research (02/2026)
frequency. Further, the number W should be sufficiently large to address many possible realizations. Since this evaluation is expensive, it is only done in a few of the Tw steps. The value that gives the lowest mean aggregate objective value over all W scenarios in the evaluation steps is selected as the final embedding.
There is an important consideration regarding the active search described in Schmitt-Ulma et al. (2022). In the evaluation epoch, the resulting embedding w evaluated on a large number of realizations W. Many of these realizations are similar and the resulting objective values as specified by the pretrained POMO model from Section 4.1, rendering these evaluations somewhat repetitive and unnecessary. Idcally, are interested in evaluations that are distinctive in input and resulting objective values. Secondly, because W is rather large, this constrains the number of evaluations we can carry out during retraining. That said, a more efficient evaluation method may not only reduce retraining time but also allow us to evaluate the embedding more frequently with a smaller te, giving us a larger search space that may possibly result in a larger embedding.
To account for the aforementioned consideratious, we propose some adjustments to the EAS. Firstly, we sample the W possible scenarios. Thereafter, we cluster these methods to get a subset of scenarios that are sufficiently representative of the spectrum of realizations. To do that, use the clustering method of Abouelrous et al. (2022).
We consider the initial embedding w generated by training the entire model in Algorithm 1. We solve, the W problems in batches of to speed up their evaluation. For each instance 5, we select the solution trajectory from the M trajectories with the highest aggregate reward L(T (s)) max,ee(,.... .M [(*) which will be used to compare with other scenarios. The highest is chosen instead of the mean as it represents the best solution found. The aggregate reward is calculated with fixed preferences Ả during clustering, although the preferences may change later during the active search. Fixing parameter values and assuming perfect information has been shown to be very beneficial for clustering (Abouelrous et al., 2022). Two scenarios st and 8 are clustered together if:
(sT")s))= - L(T <
with |-| being the absolute operator and being some threshold. Thus, scenarios st and sy are clustered together if their objective values with the initial embedding are sufficiently close.
The first scenario automatically forms a cluster. The scenarios are compared to the clusters in order. So, scenario sy is compared to the scenario representing cluster 1. If it meets (3), they are clustered together. Otherwise, 8% is compared to the scenario in cluster 2 and so forth. If s is compared with all existing clusters and not clustered with any, it forms a new cluster. The result of the clustering procedure a subset of W < W scenarios. These scenarios are then used in the embedding evaluations which happen every te iterations. Since W is much smaller than W, we can opt for a smaller te value and evaluate the embeddings more frequently and efficiently.
Our active search is summarized in Algorithm 2. An important distinction with the active search proposed in Schmitt-Ulm et al. (2022) is that preferences À are repcatedly sampled during re-training to ensure that the uncertainty is incorporated under different sets of preferences determined by the decision-maker. When new preferences are sampled, the decoder parameters have to be updated, but one should ensure that the embedding w is not alterod as it is being retrained (Line 14). Similarly, during evaluation (Line 20), all decoder parameters are updated except w. We also fix the preference vector À during evaluation (Line 20) to ensure fair evaluation as the model's performance for different values of À may be uneven.
The returned w' is then saved to solve the problem instance with unknown travel times using a greedy policy that maximizes the probability of the next visited node. The distribution of nodes to be visited is defined by the retrained POMO model. We refer to the model trained using Algorithm as EAS-cluster.

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm 2 EAS-cluster Training
1: Input: number of scarch steps Tw. total number of realizations to consider W, clustering threshold c, batch size during evaluation H, initial preferences X, evaluation frequency te.
2: Output: updated embedding w'
3: Initialization: initial embedding w
for the W scenarios do Sample them in batches of H
Evaluate the H instancos using and fixed preferences Å.
7: Cluster the instances according to (3)
8: end for
9: W = Nr. of clusters.
10: w" = ~
11: Evaluate -² on the W scenarios with X to determine initial mean aggregate reward L(x ,,,w w*)
12: for t= 1... do
13:
Sample new preferences
14:
Update Decoder parameters without updating
15:
Solve deterministic instance using current embedding w' for given X.
16:
Compute gradient Aw using (2).
17:
S ADAM(Auu w)
18:
if is an evaluation epoch (a multiple of (e) then
19:
Evaluate w on the W scenarios with Å. Let L(x w) be the resulting mean aggregate reward.
Ensure that w not. updated in the evaluation.;
20:
if L(aT" w) L(xx WW then
21:
w" L(T"IW,W" WW))
22:
23:
end if
24: end if
25: end for
26: return w..
4.3
Extension to other DRL Architectures
Our proposed framework largely based on the POMO architecture common to both the multi-objective and stochastic component. In that sense, our framework is largely restricted to POMO-based architectures. However, the architecture is largely considered pillar in using DRL for solving CO problems (Wang et al., 2024). Much of the recent literature on multi-objective DRL work mentioned in Section 2 also makes use of encoder-decoder architecture of Lin et al. (2022) making the framework relevant to many applications.
Extension to other DRL architectures is not straightforward. Assuming another encoder-decoder architecture where the docoder paramcters contain a graph embedding w, the general framework may be still applicable. Figure offers an important guideline, however, into solving stochastic multi-objective problems. One should first establish the multi-objective component before proceeding with the stochastic one. The reason being that the model should first be able to generate multiple diverse solutions for given problem before being able to assess these solutions on a set of stochastic scenarios. This is particularly evident in the retraining mechanism Section 4.2 whereby preference vectors À are repeatedly sampled during the EAS in Algorithm 2.
5 Numerical Experiments
To evaluate our method, we propose a series of numerical experiments where we solve a bi-objective (K = 2) C-VRPTW with stochastic travel times. jointly minimize the objective of total travel times and makespan (total time consumed by longest route). We compare the performance of our method on unseen instances relative to alternative methods. For the comparison, we consider the final objective value well the total
8

---

Published in Transactions on Machine Learning Research (02/2026)
run time. In the following sections, we elaborate on the set-up of our numerical experiments and analyze their results.
5.1 Set Up
We consider three instance classes of sizes n {50, 100, 200} with B = 20 instances for each n. For all instance classes, the locations are given in 2-D space where the x-y coordinates are sampled from a square of length 1. The vehicle capacities are 40, 50 and 70 for the three classes in increasing n. Node demand is sampled uniformly as integer from the interval [1,9]- Time windows are such that the lower time window twoow is sampled uniformly as integer from the interval [0,16], the time window width twaidth from the interval [2.8] and the upper time window equal to min + tWwidsh, thhorizon) } with the tWhorison being the planning horizon. Naturally, the depot 's time window is [0, [Whorizon] and we set Wohoriso to 18. Service times are sampled uniformly between [0.2,0.5]. Lastly, the mean travel times E[T] are equal to the euclidean distance, and the travel times follow normal distribution with standard deviation 0.2 x El4yy] for are (i.j).
For each instance size n, we train a different POMO model with 200 epochs and 100,000 episodes, giving a total of 20,000,000 instances. The instances were sampled from the aforementioned distribution in batches of for n = 50 and 32 for n = 100, 200. Training was conducted on a GPU node with Intel Xeon Platinum 8360Y (Intel (2025)) Processors and a NVIDIA A100 Accelerator (Nvidia (2025)). The training times of the multi-objective POMO model were 18, 60 and 144 hours for =50, 100 and 200.
For EAS-cluster, we initially consider a sample of W = 1, 000 scenarios in batches of H 64 from which we decide on the clusters W. In doing so, we consider initial preferences b = X2 = 0.5 to assign all objectives equal importance when reducing scenarios. Two scenarios are clustered together if their aggregated objective values A (TT) + (xT=(T")) differ by less than e = 1% where n" is the best solution found by the pre-trained MT. model from Section 4.1 before EAS for the corresponding instance.
For n =50, 100 and 200, EAS-cluster produced 7.3, 6.5 and 5.75 clusters on average across the B 20 instances. This shows that we significantly reduce the number of scenarios many of these correspond to similar figures of (1) and f2(-) for fixed X. Furthermore, the number of clusters deceases as n increases, likely due to differences in objective values becoming less significant as objective values like travel time become larger for larger n.
Once the scenarios are clustered, we conduct an active search with Tw = 500 steps where the embedding is evaluated every te = 100 steps. We use three benchmark methods, that test different aspocts of our study. They are as follows:
NoEAS: the model without active search, which is simply the multi-objective POMO model from Lin al. (2022) without any updates to embedding w applied to solve the deterministic instance. This bascline has been repeatedly shown to outperform other methods such as NSGA-II (Kalyan- moy, 2002) and MOEA/D Zhang& & Li (2007) in solving multi-objective combinatorial optimization problems, especially in routing, so we focus comparing with it. We generate 101 values of X, where Y is computed from 100 evenly spaced intervals in the range [0,1] and A2 = 1 - a to represent the Parcto Front.
EAS-basic: with the active search of Schmitt-Ulne et al. (2022) with t, 250. Similarly, we use the same 100 evenly spaced X realizations as above. Solution inference is done using greedy policy defined by the retrained model.
LGA: the method of Niu et al. (2021). It is carning-based Genetic Algorithm which makes use of decision-tree to learn optimal customer orderings. We adjust this method slightly to allow for time-window configurations, since it was originally developed for a VRP variant with stochastic demand only. Adding time-windows increases the frequency of infeasible solutions. We respond to this by increasing the mumber of Genetic Algorithm iterations to 2,000 from the original 200 and the number of evaluation scenarios in the population to 50- from the original 10. LGA required no pre-training, although new ML supervised model had to be trained for each instance during solution generation.
9

---

Published in Transactions on Machine Learning Research (02/2026)
LGA+noML: An LGA variant where machine learning component is used. Solution search is done purely using genetic perturbations (operators).
LALNS: An adapted version of LGA where the random genetic operators are replaced by an Adaptive Large Neighborhood Search (ALNS)- similar to Pisinger & Ropke (2007) which is known to work well with C-VRPTW. The ALNS is combined with the decision tree classifier from LGA. We run it for 200 iterations due to the high computational cost of ALNS.
The resulting solutions for each method and preference À are evaluated on R = 500 stochastic realizations of the travel times. The resulting mean objective value is used for comparison as it represents the expected objective value at the Pareto Front for the given X. Infeasible realizations are excluded from the evaluation. Solution Inference was done on the same GPU nodes used for training, (Intel, 2025; Nvidia, 2025). For LGA variants, no GPU is needed, so an AMD EPYC 9654 (AMD, 2025) CPU node was used. The results of the baselines compared to method on the proposed set of instances are given in the following section.
5.2 Results
To compare results, we consider the same hyper-volume technique mentioned in Lin et al. (2022). The hyper- volume measures the area covered by the Pareto Front from reference point, with larger hyper-volumes translating to better Pareto Fronts. Let P define the Pareto Front for a certain policy and r* be some reference point that is dominated by all solutions in P. Then, the hyper-volume HV(P) of P is given by the volume of area S that defined as follows:
S (r E By such that y < pr<rr"
(4)
where y < indicates that solution dominates solution r. Given baseline I and instance b, the associated hyper-volume is given by HV*)).. To estimate this volume, we make use of the Python package 'pymoo' (Blank, 2026). We are particularly interested in the percentage increase in hyper-volume due to using EAS- cluster. This percentage is then averaged over all B instances in the test set to give our main performance mcasure Z that is given by:
HV EAS--luste- cluster - HV(P")) x 100 HV(Pb);
Z
B
For FAAS-cluster and EAS-basic the retraining times of the active search are compared. We report the average ratio if of EAS-cluster's active search EEAS (EAS-cluserr relative to the active search of EAS-basic pbasic More precisely:
EES cluster
tfav
Fav
(6)
EAS basic
tao
such that values indicate smaller time with EAS-cluster. Furthermore, report the total time for solution inference per instance tanf, which represents the total time it would take to generate and evaluate for given number of solutions. For FAS--lluter and F.AS-basic, this includes the total run time with the active search and solution generation using POMO's greedy policy for all À values, while only the latter is incorporated for NoEAS as it lacks active search. For each of the POMO-based methods, inference times are consistent among all instances for fixed n. For LGA and LALNS, this includes the solution gencration and training of the supervised lcarning model which happens during inference.
We also report the number of solutions Qr generated at the Pareto Front by each method. Note that this number is equal for all rased models (101). Larger Qr values indicate a method's ability to generate more solutions at the Parcto Front, and possibly, increased diversity. Lastly, we report the average number of feasible realizations Rd out of the lotal R = 500 for the solution constructed from the greedy policy for each n. This particularly relevant to assess solutions' practicality as solutions which are feasible for only a handful scenarios might not be appealing even if they result in better objectives. Table 1 compares the result of EAS-cluster with the five baselines. Additional statistics on the percentage increase in hyper-volume are reported in Table 5 in Appendix C.
10

---

Published in Transactions on Machine Learning Research (02/2026)
n
Metric
EAS-cluster
BAS-basic
NoEAS
LGA
LGA+noML
LALNS
Z (avg. ratio)
-0.02%
8.14%
368.31%
336.52%
8.36%
iaa (ratio)
0.44
tinf (mins)
49
58
42
0.17
~ 0.17
2
Qr (Nr.)
101
101
101
8
8
18
R (Nr./500)
474
494
494
426
411
440
100
Z
0
-0.28%
6.34%
636.57%
612.50%
14.52%
tfa
1
0.43
linf
90
105
78
R 0.67
R 0.67
R 10
Qr
101
101
101
30
R
438
443
447
380
314
345
200
7
-0.51%
4.73%
970.48%
1041.67%
tfav
0.40
Linf
164
195
143
3.25
R 3.25
Qr
101
101
101
13
14
RJ
422
430
410
257
263
Table 1: Results EAS-cluster compared to EAS-basic 20 different multi-objective C-VRPTW instances with stochastic travel times T for each instance size
For EAS-cluster, 7, 12 and 21 minutes per instance were spent on the EAS alone for the given values of n. For all values of n (-0.02%-00.2%% and -0.51%), EAS-cluster results in slightly worse Pareto Front than EAS-basic as given by values of close zeros. This slight deterioration could be due to the bias imposed by the evaluation significantly different from 0, with p-values of 0.98, 0.75 and 0.34 for sizes 50, 100 and 200 assuming t-test with B - 19 degrees of freedom. To emphasize
the few scenarios in W. Statistical testing implies that the results are not
the distribution of the value of Z among the B = 20 instances, we provide Figure 3 in Appendix B. EAS-basic incurs a larger computational during the active search, consuming more than twice the run time of EAS-chuste for all instances as result of the larger number of evaluations on scenarios sampled from W. This gives ifav ratios of 0.44, 0.43 and 0.40 for the corresponding values of n, despite EAS-cluster incurring more than twice the evaluations of EAS-basie (25 to 10) during the 2,500 retraining steps. The resulting minutes per instance compared to EAS-cluster's 49, 90 and 164 minutes. Feasibility also slightly improves with EAS-basic as the number of feasible evaluations R is 494 443 and 430 compared to EAS cluster's 474, 438 and 422 which could be attributed to the aforementioned bias. With these results, we observe that the roduction in computation time due to EAS-cluster outweighs the small deterioration in the Pareto Front hyper-volume and scenario feasibility.
times for F.AS-basic
58, 105 and 195
The added value of active search, and EAS-cluster specifically, shown in the significant improvement in hyper-volume compared to NoEAS, with Z values of 8.14%, 6.34% and 4.73% for the given For the sake of clarity, provide the distribution of the Z values in Figure 4 in Appendix B. We see that Z decreases n increases due to the increased difficulty of solving larger problems. The run times of NoFAS only include the time for Pareto Front construction which is similar for EAS-cluster, giving 42, 78 and 143 minutes. Solution feasibility better for n = 50 and 100, with R = 494 and 447 scenarios. However, for n = 200, R decreases to 410. This could be possibly due to the more pronounced effect stochasticity in larger instances that can not be casily treated by the original embedding w. In fact, R decreases as increases for all methods becomes increasingly difficult for given solution to meet all the time windows of the customers.
We consider standard LGA from Niu et al. (2021). Since the existing implementation we found makes use of multi-threading, it was difficult to accurately estimate the run time per instance, which we observed to be less than a minute. However, LGA gives significantly inferior solutions compared to EAS-cluster as given by Z values of 368.31%, 636.57% and 970.48%. This can largely be attributed the method's random genetic operators which can not casily produce feasible solutions the case of time-windows. Furthermore, the simple decision tree is unable to learn information time-windows from customer orderings, thus struggling
11

---

Published in Transactions on Machine Learning Research (02/2026)
to find quality feasible solutions. A prominent advantage of POMO-based models, on the other hand, is their ability to learn complex CO problems which can be easily configured in the model's environment and adequately processed by the encoder. LGA is also unable to find as many solutions as POMO-based methods on the Pareto Front with 8, 10 and 13 solutions on average with respect to the 101 of the POMO-basod models. Furthermore, since these solution do not. correspond to a specific balance of objectives [x((), is difficult to verify their diversity for different maaiinn criteria. In contrast, POMO-based methods can provide such diversity through À parameters to balance the objectives fx())
To further investigate the computational difficulty posed by time-windows for LGA, we consider the results of I.GA+noMI, where the decision tree is omitted and solutions are generated purely by mcans of genetic algorithm's 's perturbation operators. The performance is rather similar to standard LGA with hyper-volumes of 336.52%, 612.50% and 1041.67% for sizes n =50, 100 and 200. The number of feasible runs and solutions on the Pareto Front is fairly simílar, except in the case of 100 where the number of feasible runs decrease to 314. These results stress the need for a hcuristic suitable for solving a VRP variant with time-windows like ALNS.
Finally, we consider LALNS. As expected, the hyper-volume improves significantly compared to the two LGA baselines, although it still falls short to EAS-cluster. The mean hyper-volume increase is 8.36% and 14.52% for n = 50 and 100. The number of solutions observed al the Pareto Front was 18 and 30 respectively with 440 and 345 feasible evaluation scenarios. The run-times were also relatively short at 2 and 10 minutes approximately. For n = 200, we encountered an out-of-memory error as LGA's multi-threading mechanism and the application of ALNS at multiple points at the Pareto Front led to significant computational memory consumption. While these results indicate an improvement over LGA,, LALNS is still inferior to other POMO-based methods which can treat complex CO problems although at a much higher run-time. Further, by observing the trend from n = 50 to 100, we expect that the difference in hyper-volume compared to EAS-cluster is significantly larger for larger instances. This asserts the added value of EAS-cluster in solving larger problems, which we investigate further in Section A.3.
For clear comparison of the resulting Pareto Front of all the methods, we refer to Figure in Appendix B. The figure compares the Pareto Front from EAS-cluster with each of the baselines for one of the test instances of size 100. The comparison with EaS-basic in Figure 5a shows that the Pareto Fronts are fairly close, while the comparison with NoEAS in Figure 5b shows more prominent difference especially when preferences are more oriented towards minimizing travel-times. Lastly, the comparisons with LGA and LALNS in Figures 5c and Figure 5d demonstrate the superiority EAS-cluster's Pareto Front compared to either baselines. In Appendix A, we provide a series of ablation studies concerning the model's sampling policy and generalization to more variable scenarios and larger problem instances.
6 Conclusions
In this paper, we provided an end-to-end method to solve a multi-objective stochastic C-VRPTW. We specifically considered stochastic travel times and minimized total travel distance and make-span. Our model is based on a variant of POMO that is first trained on deterministic multi-objective instance and then retrained through an active search to account for travel time stochasticity. The model could not only be configured to treat a variety of routing problems through its flexible environment, but also account for more different objectives. The end-to-end mechanism of the model not only simplifies solution generation, but is also invariant of other external assumptions on the model environment and the action space.
We provide training mechanism for the model and enhance it using a clustering algorithm that speeds up evaluations during active search and run time result. Our results show that our model is very close in performance compared to baseline employing standard active search from the literature while being faster. It also siguificantly outperformed another POMO baseline that disregards stochasticity as well as a common learning-based method for VRP from the literature, resulting in more dominant. Pareto Fronts.
Our model is able to generate as many solutions as desired for any set of preferences and in reasonable run times. Its greedy policy is also sufficient to generate good results, reducing the need for sampling policies often associated with POMO-based models. It also generalizes well to other instances with different
12

---

Published in Transactions on Machine Learning Research (02/2026)
distribution than the one encountered during active search. Nonetheless, it often results in less feasible solutions compared to the considered baselines, possibly due to the bias induced by the clustered sample of scenarios. Furthermore, there still lacks a common framework that streamlines evaluation for specific cases like larger scale instance and non-convex Pareto Fronts.
Future research should focus more on synchronizing multi-objective training with active search and the derivation of superior clustering techniques while streamlining evaluation methods by which the associated model performance could be accurately judged. Additionally, problems with more objectives certainly of interest.
References
Abdo Abouelrous, Adriana F Gabor, and Yinggian Zhang. Optimizing the inventory and fulfillment of omnichannel retailer: stochastic approach with scenario clustering. Computers & Industrial Engineering, 173:108723, 2022.
Fatima Ezzahra Achamrah. Leveraging transfer learning in deep reinforcement learning for solving combi- natorial optimization problems under uncertainty. IEEE Access, 2024.
AMD. Server processor specifications, 2025. URL https://www amd. cww/ comp////pprrdctsss/potttcttttoos server-procesee html. Accessed: 26-02-2025.
Christopher Bayliss. Machine learning based simulation optimisation for urban routing problems. Applied
Soft Computing, 105:107269, 2021.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):405 421, 2021.
Julian Blank. руmоо 0.6.1.6, 2026. URL https://pypi..rg/prrrt
Accessed: 05-01-2026.
Jinbiao Chen, Jiahai Wang, Zizhen Zhang, Zhiguang Cao, Te Ye, and Siyuan Chen. Efficient meta neu- ral heuristic for multi-objective combinatorial optimization. Advances in Neural Information Processing Systems, 36:56825- 56:50825-56837, 2023.
Jianjun Deng, Junjie Wang, Xiaojun Wang, Yiqiao Cai, and Peizhong Liu. Multi-takk multi-objective evolutionary search based on deep reinforcement learning for multi-objective vehicle routing problems with time windows. Symmetry, 16(8):1030, 2024.
Nadia Giuffrida, Jenny Fajardo-Callerin, Antonio D Masegosa, Frank Werner, Margarete Steudter, and Francesco Pilla. Optimization and machine learning applied to last-mile logistics: A review. Sustainability, 14(9):5329, 2022.
Eric J Horvitz. Reasoning about beliefs and actions under computational resource constraints. arXiv preprinl arXiv:1304.2755: 2013.
Zangir Iklassov, Ikboljon Sobirov, Ruben Solozabal, and Martin Takáč. Reinforcement learning for solving stochastic vehicle routing problem. Asian Conference on Machine Learning, pp. 502 517. PMLR, 2024.
Intel. Intel xeon@ platinum 8360y processor, 2025. URL https://www.inteet com/ content/wwwttt -xeo--plainum p00000 cache- 2-40- 2-40-ghz/ specifications. html. Accessed: 26-02-2025.
Ziying Jia, Zeyu Dong, Miao Yin, and Sihong He. How robust reinforcement learning enables courier- friendly route planning for last-mile delivery? In ICML 2025 Workshop Progrommatic Representations for Agent Learning, 2025.
Waldy Joe and Hoong Chuin Lau. Deep reinforcement learning approach solve dynamic vehicle routing problem with stochastic customers. In Proceedings of the international conference on automated planning and scheduling, volume 30, pp. 394-402, 2020.
13

---

Published in Transactions on Machine Learning Research (02/2026)
Deb Kalyanmoy. A fast and elitist multi-objective genetic algorithm: Nsga-ii. IEEE Trans. Evolutionary Compulation, ((2):182-197, 2002.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn to solve routing problems! arXiv preprint wrXiv:1803.08477 2018.
James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey. arXiv preprint arXiv:210.. 16378, 2021.
Yeong-Dae Kwon, Jinho Choo, Byoungiip Kim, Iijoo Yoon, Youngiune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 18:21188-21199 2020.
Xi Lin, Zhiyuan Yang, and Qingfu Zhang. Pareto set learning for neural multi-objective combinatorial optimization. arXiv preprint arx:22203. 15386, 2022.
Xiaobo Liu, Yen-Lin Chen, Lip Yee Por, and Chin Soon Ku. A systematic literature review of vehicle routing problems with time windows. Sustainability, 15(15):12004, 2023.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combi- natorial optimization: A survey. Computers Operations Research, 134:105400, 2021.
Patrick Ngatchou, Anahita Zarei, and A El-Sharkawi. Pareto multi objective optimization. In Proceedings of the 13th international conference on, intelligent systems application to power systems, pp. 84-91. IEEE, 2005.
Yunyun NIu, Detian Kong, Rong Wen, Zhiguang Cao, and Jianhua Xiao. An improved learnable evolu- tion model for solving multi-objective vehicle routing problem with stochastic demand. Knowledge-Boud Based Systems, 230:107378, 2021.
Yunyun NIu, Chang Xu, Shubing Liao, Shuai Zhang, and Jianhua Xiao. Multi-objective Docatin-rrutting optimization based on machine learning for green municipal waste management. Waste Management, 181: 157-167, 2024.
Nvidia. NVIDIA A100 tensor core GPU, 2025. URL http:///tw////./.o/aaa//c//////. Accessed: 26-02-2025.
Tosif Pappas, Styliani Avraamidou, Justin Katz, Baris Burnak, Bureu Beykal, Metin Turkay, and Efstratios N Pistikopoulos. Multiobjective optimization of mixed-integer linear programming problems: a multipara- metric optimization approach. Industrial & engineering chemistry research, 60(23):84933-5)) 8503, 2021.
Yong Peng, Shu Han Gao, Dennis Yu, Yun Peng Xiao, and Yi Juan Luo. Multi-objective optimization for multimodal transportation routing problem with stochastic transportation time based on data-driven approaches. RATRO-Operations Research, (7(4):1745-1766) 2023.
David Pisinger and Stefan Ropke. A general heuristic for vehicle routing problems. Computers & operations research, 34(8):2403 2435,, 2007.
Ankur Sarker, Haiying Shen, and Kamran Kowsari. A data-driven reinforcement learning based multi- objective route recommendation system. In 2020 IEEE 17th international conference on mobile ad hoc and sensor systems (mass), pp. 103 111. IEEE, 2020.
Fynn Schmitt- Ulms, André Hottung, Meinolf Sellmann, and Kevin Tierney. Learning to solve stochas- tic orienteering problem with time windows. In International Conference on Learning and Intelligent Optimization, pp. 108-122. Springer, 2022.
Jiwoo Son, Minsu Kim, Sanghyook Choi, Hyconah Kim, and Jinkyoo Park. Equity-rransfommer: Solving np-hard min-max routing problems as sequential generation with equity context. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 38, pp. 20265-20273, 20273, 2024.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Bentz Tozer, Thomas Mazzuchi, and Shahram Sarkani. Many-objective stochastic path finding using rein- forcement learning. Expert Systems with Applications, 72:371-384 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiu:1710.1000 2017.
Thibaut Vidal, Gilbert Laporte, and Piotr Matl. A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research, 286(2):401 416, 2020.
Feng Wang, Qi He, and Shicheng Li. Solving combinatorial optimization problems with deep neural network: A survey. Tsinghua Science and Technology, 29(5):1266 1282, 2024.
Zhenkun Wang, Shunyu Yao, Genghui Li, and Qingfu Zhang. Multiobjective combinatorial optimization using single deep reinforcement learning model. IEEE transactions cybernetics, 54(3))1984-1996, 2023.
Ronald Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229 256, 1992.
Rixin Wu, Ran Wang, Jie Hao, Qiang Wu, Ping Wang, and Dusit Niyato. Multiobjective vehicle routing optimization with time windows: hybrid approach using deep reinforcement learning and nsga-ii. 1EEE Transactions on Intelligent Transporlation Systems, 2024.
Yuan Yao, Zhe Peng, Bin Xiao, and Jichang Guan. An efficient learning-based approach to multi-objective route planning in a smart city. In 2017 IEEE International Conference on Communications (ICC), pp- 1-6. IEEE, 2017.
Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decomposition. 1EEE Transactions on evolutionary computation, 11(6):712-731, 2007.
Tie Zhang, Jia Cheng, and Yanbiao Zou. Multimodal transportation routing optimization based on multi- objective q-lcarning under time uncertainty. Compler & Intelligent Systems, 10(2):3133-3152 2024.
Zizhen Zhang, Hong Liu, MengChu Zhou, and Jiahai Wang. Solving dynamic traveling salesman problems with deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 34(4): 2119 2132, 2021.
Chenhao Zhou, Jingxin Ma, Louis Douge, Ek Peng Chew, and Loo Hay Lee. Reinforeement learning- based approach for dynamic vehicle routing problem with stochastic demand. Computers & Industrial Engineering, 109440,44, 2023.
15

---

Published in Transactions on Machine Learning Research (02/2026)
n
Metric
EAS-cluster (Monte Carlo Simulation)
EAS-cluster (Greedy)
50
Z (avg- ratio)
0
0.33%
linf (mins)
17
49
Qr (Nr.)
11
101
R (Nr./500)
489
474
100
7
0
-1.26%
tinf
37
90
Qr
11
101
R/
470
438
Table 2: Results of EAS-cluster with Monte Carlo Simulation compared to greedy policy for each instance
size n.
A Ablation Studies
To study the ability of our method to deliver improved results and generalize to settings with different distributions, propose two sets of experiments. In the first set of experiments, we combine our method with Monte Carlo Simulation. This is in line with the recommendations in Schmitt-L'mms et al. (2022) who state that Monte Carlo Simulation may improve over a greedy policy. In the second set of experiments, we apply our method solve series of instances from different distribution with more variable travel times.
A.1 Monte Carlo Simulation
With the final embedding w"; Schmitt-Ulms et al. (2022) Monte Carlo simulation to evaluate the different actions at every step of the solution generation, i.e. node visit. More precisely, at each step, the top 5 recommended actions are evaluated by applying them in the succeeding step and completing each of the 5 solution trajectories using the trained model's policy. For each step, the process is repeated for a fixed number of runs ms, and the average is taken to determine the best action in the next step.
We make use of the same Monte Carlo simulation technique. There are some adjustments, however, we ought to incorporate in the application of the Monte Carlo Simulation for VRP. Firstly, Schmitt- et al. (2022) consider large number of simulation runs ms, - going up to 100s for cach problem instance. This results in long running times per solution as demonstrated by their nunerical experiments with instances of size 200 going up to 48 minutes. Since we repeatedly have to apply this procedure for several realizations of À as each realization of X invokes different solution, we consider a smaller value ms, = 10 so that the total run time per instance falls within the same order of magnitude of around 1 hour. Furthermore, we limit the number of sampled À values to 11 instead of 101.
Unlike the orienteering problem in Schmitt- Ulms al. (2022), not possible to realize the stochastic travel times after taking step since repeated visits to the depot in VRP would then imply that we travel back in time. As such, the travel time realization the travel time, while stochasticity is incorporated in future decisions by the Monte Carlo runs. To impose feasibility constraints we require that the decisions considered at each step are feasible for at least half of the ms, = 10 runs, otherwise they are discarded. We require that solutions are only feasible 50% of the time. Similar to the greedy policy, we evaluate the resulting solution on a sample of R = 500 realizations and use the average estimate the objective values for given À at the Pareto Front.
make after taking a decision concerns the expected value of
We compare the performance of the Monte Carlo approach to the greedy policy of EAS-cluster from Section 5.2 in Table 2. Additional statistics on the percentage increase in hyper-volume are reported in Table 6 in Appendix C. Due to the expensive evaluation, we only consider n =50 and 100. The reported linf times also include the run times for active search which is identical for both methods as they used the same embedding.
The results generally imply that Monte Carlo simulation is of limited added value to multi-objective op- timization. While a marginal improvement of 0.33% observed for n 50, deterioration of 1.26% is observed for n 100 compared to using the greedy policy. The average time per instance given by
16

---

Published in Transactions on Machine Learning Research (02/2026)
n
Metric
EAS-cluster (Greedy)
NoEAS
50
(avg. ratio)
8.39%
R (Nr./500)
448
480
100
Z
6.56%
R
391
413
200
Z
4.35%
R
334
340
Table 3: Results of EAS-cluster with greedy policy compared to NoEAS and more variable travel times for each instance size n.
fin is slightly less than third of the greedy policy's run time, with Monte Carlo simulation requiring on average 17 and 37 minutes per instance for 50 and 100. Yet, the number of solutions on the Pareto Front generated from the greedy policy is 10 times much.
Nonetheless, the Monte Carlo simulation slightly improves the number of feasible realizations from 474 to 489 and from 438 to 470 for n =50 and 100. This could be attributed to the repetitive evaluations in the Monte Carlo runs that require that a node visit be feasible for at least half the ms, = 10 for it to be considered in the solution. As a result, a stronger feasibility requirement imposed compared the greedy policy and more scenarios are satisfied by the resulting solution. For cases where feasibility is crucial, one might still rosort to using Monte Carlo Simulation rather than greedy policy.
A.2 Travel Time Distribution
In this section, we study the performance of our retrained model EAS-cluster on a dataset with different travel time distribution. We refrain from conducting an active search and simply run the greedy policy on the new dataset to test model generalization. For the new datasct, we consider standard deviation E[t,y] x 0.4 which is twice as variable as the travel times considered in Section 5.2.
As benchmark, we consider NoEAS again. The rationale being that the difference of is still positive, then the model with updated embedding w" generalizes well to reasonable extent beyond model where retraining is involved. We consider the greedy policy with Q. 101 solutions again. Since solution inference times tinf and number of Pareto Front points Q, are identical, we only report Z and R in Table 3. Additional statistics on the percentage increase in hyper-volume are reported in Table 7 in Appendix C.
The results are largely in line with those Section 5.2. EAS-cluster improves the hyper-volume by 8.39%, 6.56% and 4.35% on average for n = 50, 100 and 200. While the performance of E.AS-cluster may deteriorate slightly in more variable dataset, it still outperforms NoEAS whose embedding w, significantly 'out-of- tune' with the more variable travel times T. NoEAS, however, provides more feasible solutions, giving R = 480, 413 and 340 solutions compared to EAS-cluster's 448, 391 and 334 for given n. This could be explained by the increased bias of cluster evaluations in a different dataset, although the difference in R! values decreases with larger due to the increased difficulty of solving larger instances as explained in Section 5.2.
A.3 Larger-Scale Instances
In this section, we test the generalization of our method to larger instance classes than the ones upon which the model was trained. In particular, we consider instances of size =400 and 600 with vehicle capacities 100 and 120. We consider the original standard deviation of E[t.y] 0.2 For these experiments, the POMO model trained on instances of size =200. Due to the associated computational burden, we consider B = 10 instances for each size with 21 values. This poses certain evaluation challenges as there is not a sufficintt number of solutions on P to give a relatively accurate estimation of the hyper-volume using (5) (Lin al., 2022), contrast to the previous experiments with 101 solutions. Indood, we saw that our method ended up scoring worse hyper-volumes despite consistently generating better objective values for almost. all values of X.
use
17

---

Published in Transactions on Machine Learning Research (02/2026)
In response, concluded that alternative evaluation measures ought to be used which take to be the average percentage decrease in mean euclidean distance Zene between each point on P and the reference point r". We saw that this measures correlated positively with the definition of Z as per (5) and could accordingly be used for this evaluation. Intuitively, it represent the average improvement offered by solutions in P over reference point r" In line with Section A.2, we compare with NoEAS and report the Zeve and R metrics in Table
The results demonstrate the consistent added value of EAS-cluster with respect to NoEAS even for larger instances where Zeuc increased by 15.28% and 18.16% for 400 and 600. The number of feasible realiza- tions deteriorated significantly for both methods to less than 300 and 200 for both instance sizes. This is because it becomes more difficult to find solution that satisfies all time windows as the number of customer grows with highly variable travel times. Nonetheless, our method still yields significant improvements in the objectives for the considered instances. To assert this, we consider Figure 6 in We see that the distribution of Zeue among the different instances of size 600 in 6a is always above 10%. Furthermore, the distribution of Euclidean distances between points in P and r* for both EAS-cluster and NoEAS given in 6b and 6c for one of the instances of size 600, such that the former is skewed towards larger values indicating larger improvements over r" by the corresponding solutions in P.
n
Metric
EAS-cluster (Greedy)
NoEAS
400
Zewe (avg. ratio)
15.28%
R (Nr./500)
288
295
600
Zeuc
18.16%
R!
110
188
Table 4: Results of EAS-cluster with greedy policy compared to NoEAS for larger instances.
18

---

Published in Transactions on Machine Learning Research (02/2026)
B
Figures
Reequency
-2
Hypervoiume Difference (%)
(a) y
Prqqueccy
Frequency
1-
30
Hypervolume Difference (96)
Hypervolume Difference (%)
(b)
100
(c)
200
Figure 3: Histogram of Z values of EAS-cluster against EAAS-bascc
19

---

Published in Transactions on Machine Learning Research (02/2026)
10
20
25
Hypervoiume Diffarence (%)
(a) 50
T
L
Hyperrolume 1%6)
Hypervolume (c) 200
(b) 100
Figure 4: Histogram of Z values of EAS-cluster against NoEAS
20

---

Published in Transactions on Machine Learning Research (02/2026)
Dos-Cluster
Custe
0.90
0.500
0323
Malt-pan
0.15
0.32
0.895
(a) EAS-cluster vs. LAS--basi
(b) EAS-cluster vs. No EAS
EasiCluster
0.98
LCAt
033
0.230
0.50
Matespon
0.930
0.54
0.355
0.92
0.90
0.000
0.90
1.0
1.3
2.5
2.3
3.3
1.0
1.3
2.0
2.5
350
rrvvl time
rravel lime
(c) EAS-cluster vs. LGA
(d) EAS-cluster vs. LALNS
Figure 5: Plots comparing the Pareto Front generated by EAS-cluster against other methods for one of the instances of size 100.
21

---

Published in Transactions on Machine Learning Research (02/2026)
L
Requertc
14
16
18
20
Euclidean Cistance Difference (%)
(a) Distribution of mean euclidean distance Zeuc among the different B = 10 instances of size 600.
10
3.4
1.6
2.0
2.
2.4
2.6
0.5
10
1.5
2.0
2.5
Fuclidsan Distances
Furlidean Distances
(b) Distribution of euclidean distances for points on P (c) Distribution of euclidean distances for points on relative to r" for given instance of size 600 with EAS- relative to r" for given instance of size 600 with EAS- cluster.
cluster.
Figure 6: Histograms of Euclidean distances of Pareto Front from EAS-cluster compared NoEAS.
C Hyper-volume Additional Statistics
In this section, report additional statistics the percentage increase in hyper for our experiments. Our statistics concern the quantity:
HV ( dlster HV(P")) x 100
(7)
HV((bb);
for which the mean across all instances represents the metric Z used Section 5.2. In addition to the mean, we report the standard deviation, the min and max values in the following Tables. Table 5 concerns results in Table 1, Table 6 concerns results in Table and Table 7 concerns results in Table 3.
22

---

Published in Transactions on Machine Learning Research (02/2026)
n
Metric
EAS-basic
NoEAS
LGA
LGA+noML
LALNS
50
Dev
3.72%
6.4%
112.82%
65.11%
8.28%
Max
7.54%
25.23%
574.86%
466.55%
33.43%
Min
-6.98%
-3.94%
178.75%
221.02%
-0.08%
100
St Dev
3.97 %
4.63 %
206.67%
147.31%
6.13%
Max
10.16 %
15.8 %
1251.36 %
938.33%
27.53%
Min
-5.63 %
0.57 %
348.12 %
889.11%
4.10%
200
St Dev
2.37 %
3.34 %
171.33 %
241.78%
Max
5.44 %
11.15 %
1372.69 %
1643.61%
Min
-5.0 %
-0.6 %
676.73%
697.78%
Table 5: Statistics on percentage increase in hyper-volume of EAS-cluster relative to baseline for the exper- iments reported Table
n
Metric
EAS-cluster (Greedy)
St Dev
2.4
Max
6.86 %
Min
-3.87 %
100
St Dev
1.95 %
Max
3.47 %
Min
-5.73 %
Table 6: Statistics percentage increase in hyper-volume of E.AS-cluster with Monte Carlo Simulation relative to Greedy policy for the experiments reported in Table 2
Metric
No-EAS
50
St Dev
6.57 %
Max
25.7 %
Min
-2.71 %
100
St Dev
4.73
Max
16.66 %
Min
0.3 %
200
St Dev
3.53
Max
10.99 %
Min
-0.87 %
Table 7: Statistics on percentage increase in hyper-volume of E.AS-cluster relative to NoFAS for the experi- ments reported in Table 3 with more variable travel times.
23


Reviews:
[{"review_id": "DGG8my0VU6", "reviewer": "Reviewer_N8t7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a reinforcement learning-based approach capable of jointly handling stochastic travel times and multiple objectives in the Capacitated Vehicle Routing Problem with Time Windows (C‑VRPTW). \nBuilding on the POMO method, the authors introduce an active search retraining mechanism to efficiently adapt the model’s embedding to uncertainty in travel times. Numerical experiments across multiple instance sizes show that the proposed approach achieves Pareto fronts close to (slightly worse than) alternative active learning protocols, while significantly reducing the computational time. The ablation study confirms the effectiveness of the proposed active search, as the multi-objective POMO alone leads to inferior results. \n\nThe model generalizes reasonably well to travel time distributions different from the training ones. The authors tested the case of the variance being doubled with respect to the training distribution.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The proposed approach effectively employs reinforcement and active learning techniques for the C-VRPTW. The experiments prove the soundness of the design. I am not an expert in the specific problem, therefore I find it difficult to thoroughly evaluate the empirical analysis. However, I did not find any major error on the reinforcement or active learning side of the approach.", "audience_yn": "Yes", "audience_explanation": "The paper focuses on the C-VRPTW. Readers already familiar with this topic would find in the paper a nice technical description of the proposed approach. I think the problem in itself can be of interest for machine learning practitioners (e.g., also related to graph neural networks). \n\nHowever, as I suggest to the authors, the paper is difficult to read by a broader machine learning audience. If that is not intended, then the paper requires some restructuring and a gentle introduction to the problem at hand, especially when it comes to the evaluation metrics and how to interpret them.", "requested_changes": "- The current version of the paper is very technical and interesting for a reader already very familiar with the C-VRPTW. To make the paper more accessible to a wider audience, I would suggest providing a gentle introduction to the problem. In particular, the empirical evaluation is quite difficult to understand. To support the formal description of the evaluation metrics, I suggest discussing how to interpret them, for example, by providing an intuitive understanding of the upper/lower bounds for each metric. Overall, a more detailed description of the experimental protocol and results would really benefit the reader interested in the problem but not well-versed in its technical details. I expect most of TMLR readers to fall in this latter category.\n\n- The paper could have provided a robustness analysis on some of the design choices that are not explicitly addressed in the current version. For example, the choice of $\\epsilon=1\\%$ is provided with no explanation. Did some tuning of $\\epsilon$ occur? Or is the method robust to variations of its value?", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "x1loS5cNVl", "reviewer": "Reviewer_qeJU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose slight modifications to existing methodologies (mostly, they start off the one of Lin & al., 2022 and add scenario clustering) that improve their running times.", "claims_and_evidence_yn": "No", "claims_explanation": "Apart from a minor point (minor comment below), the numerical results do not include comparisons to strong baselines, both in terms of computing times and solution quality. While the authors improve compared to other ML-based techniques, as a potential implementer of the said methodology, I do not know if I should pursue an ML-based implementation or a classical implementation.", "audience_yn": "Yes", "audience_explanation": "The topic of of deep reinforcement learning is of interest to the TMLR community.", "requested_changes": "End-to-end Deep Reinforcement Learning for Stochastic Multi-objective Optimization in C-VRPTW\n\nMajor comments:\n- Section 3, page 3: the authors seem to focus on one method to compute the Pareto front, namely the weighted sum method. This is just one method of producing the Pareto front; in particular, it cannot produce a nonconvex front (as all linearisation methods). As your problem is equivalent to a mixed-integer linear program, the front can be nonconvex. See, for instance, https://pubs.acs.org/doi/10.1021/acs.iecr.1c01175. I think this issue requires some discussion to show the limits of your methodology. \n- The considered instance sizes are rather small (up to 200 locations), although the number of scenarios is large. \n- Section 5.2: you only compare your methodology to ML-based techniques to solve the problem. I have doubts that you are comparing your technique to a strong baseline. I would prefer to see, among your baselines, a traditional solver for CVRPTW: for instance, LGA is based on eugenic algorithms with some ML, there is no reason why the same eugenic algorithms wouldn't work on the same problem (or other local-search-based or column-generation-based solvers); you could also use the simple weight technique over a stochastic solver to get this baseline. \n\nMinor comment:\n- Section 1, page 2: \"Although the training resources required are not trivial, ML models can be quickly applied for solving thereafter (Zhang et al., 2021)\". The reference only applies to toy problems (TDTSP with up to 100 locations). They get good results, but they are very inconclusive due to the size of the instances. The authors of the submission thus make a very bold claim that is not substantiated by their citation. \n\nOpen-ended question (I'd like to see it answered in this paper, but you can delay it to a future paper):\n- You consider only two objective functions, which is a very limited case of multiobjective optimisation. It would be interesting to see how your technique generalises to more objectives.", "broader_impact_concerns": "Not present and not useful for this submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bm9qXld5uM", "reviewer": "Reviewer_gJMp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces a two tiered approach for the stochastic nature of the Vehicle Routing Problem with Time Windows. The first tier is an adaptation of the POMO approach to generate solutions in deterministic settings with preference vectors for the objectives. The second tier applies the Efficient Active Search (EAS) strategy to deal with the stochastic nature of the travel times. To prevent the combinatorial explosion of evaluation across many stochastic scenarios, this work introduces a clustering-based scenario selection approach, by clustering scenarios together if they demonstrate a high similarity in objective values.\n\nOther: The authors claim that this is a 'Regular submission (no more than 12 pages of main content)'. However, this submission has 14 pages of content.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors describe the two tiered approach to generating solutions to the vehicle routing problem. The clustering technique, the active search and the sampling approach is written in detail along with algorithmic details.\n1. The authors conduct numerical experiments on three levels of instances with sizes 50, 100, and 200 with 500 difference stochastic realizations. While this provides a basis for extensive evaluation, the clustering significantly reduces the number of scenarios, and may also harm the quality of the Pareto Front.\n2. I found the nature of the baselines weak and lacking. It would be interesting to see how the proposed approach fares against other baselines that are not POMO.\n3. Additionally, to convincingly state the strong generalization of this approach to unseen stochastic travel time, more experiments are needed with more larger number of nodes, and a greater degree of standard deviation.", "audience_yn": "Yes", "audience_explanation": "Yes, I believe this work is relevant to the greater TMLR community as it provides an interesting take on the stochastic nature of the vehicle routing problem. This work sits at the intersection of machine learning, reinforcement learning, optimization and graph theory.\n\nThe findings of this work are empirical in nature. Through a series of experiments, the authors demonstrate how EAS clustering improves solution quality under stochastic travel time conditions, which is an interesting take on problems that can easily get intractable.\n\nI believe these findings would be relevant for the interests of the broader TMLR community.", "requested_changes": "1. The biggest critique to this work is the lack of baselines. I would be interested in seeing how the proposed approach fares against other baselines that are not POMO. \n2. The stochasticity follows a normal distribution with a standard deviation of 20 percent of the expected value. This value is realistic. However, an ablation study along various increasing levels of standard deviation and increasing number of nodes would be incredibly useful in understanding the true benefit of this work.\n3. It seems that the true benefit of the EAS-cluster over the non-cluster version seems to be in the time efficiency. The benefit in solution quality does not seem significant. A further explanation along with a statistical significance test would help in understanding the difference between the two approaches. \n4. I believe the writing can be improved at several instances. For e.g., 'independently constructs solution without interference of a heuristic' is missing an article. I would recommend taking another pass at the paper to fixing typos and write sentences in a simplified manner.\n\nOther:\n\n1. The authors claim that this is a 'Regular submission (no more than 12 pages of main content)'. However, this submission has 14 pages of content. This discrepancy needs to be fixed.\n2. Figures 1 and 2 and subsequently the images in the appendix are bitmap images. They are already pixelated and do not adhere to the standards of TMLR. I recommend using vector graphics for images.\n3. Formatting near section 4 seems to have a large empty space.", "broader_impact_concerns": "A broader impact statement is not present and not required.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)