A machine learning-based branch and price algorithm for a sampled vehicle routing problem

A vast number of variants of vehicle routing have been proposed and solved either heuristically or exactly over the last decades. For a detailed classification and review of most variants, the reader is referred to Braekers et al. (2016). For a definition and review on “rich” vehicle routing, i.e., routing problems that impose a significant set of practical constraints see Campbell and Wilson (2014).

The structure of SVRPs proposed in this paper may best be classified as a vehicle routing problem with stochastic customers (VRPSC). These problems consist of a set of customers, each assigned a probability of appearance. Thereby, it can be distinguished between two models: (a) the existence of customers is known a priori (as assumed in this paper) or (b) customers are revealed during the planning horizon (see for example Albareda-Sambola et al. (2014)). Note that in model (b) additional stochastic inputs, such as demand (VRPSDC) may be considered. For reviews on stochastic vehicle routing, including the VRPSC, the reader is referred to Pillac et al. (2013), Ritzinger et al. (2016), or Oyola et al. (2018). Already in the early work of Waters (1989), the two most common solution approaches for such problems are outlined: adapting a master solution and reoptimization. The first makes use of an a priori computed solution for the base customer set (first state), that is then adapted (usually heuristically) in a second stage when the actual customer set is known. However, Waters (1989) has already shown that re-optimization yields significantly better results for the VRPSC when the set of appearing customers is small compared to the base set. Generally, the VRPSC has been studied less than other stochastic routing problems, e.g., vehicle routing problems with stochastic demands. Most published studies propose methodologies that are based on adapting a master solution. For a vehicle routing problem including stochastic demand, Gendreau et al. (1995) introduce an exact algorithm which minimizes the original costs in the master problem and the expected costs in the second state for the VRPSDC. Gendreau et al. (1996) follow the same approach but use a tabu search instead of an exact solving procedure. Erera et al. (2009) heuristically compute primary routes, i.e., a solution to a master problem including additional real world constraints, which are then heuristically adapted to operational routes (second stage). Zhong et al. (2007) follow a slightly different approach, by summarizing customers to “cells” and “areas”, for which a strategic routing plan is computed a priori and heuristically altered in the second stage. Sörensen and Sevaux (2009) compute “flexible” routes used for the master problem that may be effectively adapted in the second stage. The work of Sungur et al. (2010) includes stochastic customers, demand service times for a real-world courier elivery problem. Similar to previously outlined approaches, a master plan is adapted on a daily basis to generate daily schedules. The optimization goal is to maximize the number of customers that are served and the route similarity (with respect to the master plan), while minimizing earliness and lateness penalties and the total travel distance.

The ML-based algorithm proposed in this paper substantially differs from existing work, as it does not rely on the adaption of a master plan. It is based on an a priori training phase and on trained ML models that are used to accelerate an exact branch and price algorithm for unseen customer combinations.

Exactly solving variants of vehicle routing problems have gained much attention over the last decades. The most commonly used solution techniques to compute optimal solutions are branch price and cut algorithms. Among the first to propose such a method for the CVRP were Fukasawa et al. (2006). Advancements of the main branch price and cut principle can be classified in: (i) sub-problem relaxation and corresponding solving procedures and (ii) definition of cutting planes. The work of Pecin et al. (2017a) for VRPTW (and, respectively, Pecin et al. (2017b) for CVRP) denote the latest advancement of exact solving procedures, and include route enumeration, variable fixing and strong branching elements besides above-mentioned techniques. Further, it has to be noted that the above reported literature on exact algorithms does not include other variants than VRPTW and CVRP. Pessoa et al. (2020) generalize recent development on latter problem types to a generic exact solving procedure for multiple variants of routing problems. For a recent review, the reader is referred to Costa et al. (2019)..

The idea to combine methods from classical optimization and ML has gained significant attention over the last few years, especially for real-world settings where optimization algorithms are used in a repetitive manner. Thereby, the idea of gathering knowledge during these optimization runs, that can be utilized in future calls of the algorithm, seems to be very intriguing.

In its pure essence, an algorithm is a sequence of decisions to be made. In a vast number of algorithms that are used in practice, even in exact ones, a lot of these decisions are made heuristically, for example the selection of neighborhood operators in local search procedures, or the selection of variables to branch on in tree searches. ML models could enhance those heuristic policies within the considered optimization algorithms. Recent research on the heuristic use of ML models has already demonstrated their potential to do so.

In general, Bengio et al. (2018) identified three abstract ways to incorporate ML into optimization (or combine ML and optimization). First, (i) “End-to-End” learning includes ML approaches that are able to directly construct solutions for optimization problems. Hence, it extends classical heuristics by ML-based ones. Second, (ii) ML is used to gather information on the problem at hand in a pre-processing step and pass that information on to a classical optimization algorithm. Third, (iii) ML models are utilized to make online heuristic decisions within classical optimization algorithms.

A fourth possible way, (iv) that is not within those categories, is to use ML models to predict an objective value of a problem, but not the solution yielding that value. In the following, examples for each category are given. For comprehensive reviews, the reader is referred to Bengio et al. (2018); Lombardi and Milano (2018); Dilkina et al. (2017). However, it is interesting to observe that little research has been done on problem definitions that incorporate pre-defined patterns for instance generation. Only a few exceptions have to be mentioned. Lodi et al. (2019) assume that instances being solved for the facility location problem are random perturbations of a single reference instance, which is similar to the idea of a base instance introduced in this paper. Xavier et al. (2019) assume a fixed topology of the problem structure and generate instances by altering parameters with respect to historic data. Thereby, parameters are either sampled from past observations, or a distribution is fitted on historic data which is used to generate parameters. Fischetti and Fraccaro (2019) mention that part of their data that defines instances is based on historic data.

It is the opinion of the authors that patterns in instance generation could be an interesting direction for research on the combination of ML and traditional optimization. First, from a practical point of view, when optimization is used in a setting where certain elements remain fixed over time, e.g., a fixed number of machines, a fixed set of possible customers, structures in item definitions for bin packing, and many more. Second, assuming structures in the instances being solved could lead to an enhanced use of ML models for optimization, as it enables to engineer features and models that are explicitly making use of the those structures.

Summarizing, to the best knowledge of the authors, the contribution of this paper is threefold:

Column generation procedures have been extensively applied to solve NP-hard optimization problems, including many variants of the vehicle routing problem. The general idea is to split problems of the form similar to (1)–(9) into a master problem (constraints (2)) and (often identical) sub-problems (constraints (3)–(9) define one sub-problem per vehicle). This approach is based on the block structure of the problem and on the observation that routes of the vehicles can be independently constructed in the sub-problems and linked together in the master problem. Assuming that the set of all possible routes is known, and denoted by P, the master problem can be formulated as a set-covering problem of the following form:Note that \(c_p\) denotes the total distance of a route and \(n_{i,p}\) denotes the number of times a customer i is visited on a route p and \(y_p\) counts the number of times a route is used. However, set P is extremely large and cannot be enumerated even for medium sized instances. Therefore, set P is replaced by a smaller set of known paths \(\tilde{P}\subset P\) in formulation (10)–(12) Let us denote by \(\pi _i\) the dual multiplier related to constraint (11) for some node \(i\in N_I\) for a given set \(\tilde{P}\). The values \(\pi _i\) are used to compute the reduced costs \({\hat{c}}_{i,j}\) of the edge \(\{i,j\}\) in the original network, in particular \({\hat{c}}_{i,j} = c_{i,j} - \pi _i\).

Based on this reduced cost structure, a sub-problem solver is used to compute routes with total negative reduced costs. If it fails, i.e., no routes with negative reduced cost can be identified, an optimal solution to the problem (10)–(12) is found and the corresponding node in the branch and price algorithm is considered as processed. Otherwise, set \(\tilde{P}\) is updated by routes with negative reduced costs.

The sub-problem imposed by constraints (3)–(9) and a modified objective function (replacing costs \(c_{i,j}\) by \({\hat{c}}_{i,j}\) and summing just over i and j but not over k, since there is a subproblem for every k) is essentially an ESPPRC. Note that \({\hat{c}}\) may not satisfy the triangular inequality and also may take negative values. Therefore, negative cycles may exist in the network. Since the ESPPRC is NP-hard, the sub-problem is relaxed such that specific cycles are allowed. The objective function (10) ensures however that in an optimal solution the routes will be cycle-free. Further time window and resource constraints prevent infinite cycling if negative cycles are present in the network.

In this paper, we have used a 2-cycle elimination Irnich and Villeneuve (2006) procedure for the SVRPTW, the routes are not allowed to contain cycles of the form (i, j, i), and ng-route relaxation for the SCVRP.

Informally speaking, ng-route relaxation works as follows. Each customer i is assigned a set of customers, i.e., \(N_i\). Further, for each route p a “memory” \(\varPi (p)\) is kept. Route p is only allowed to be extended to customer i if \(i \notin \varPi (p)\). On the other hand, if the extension is feasible, the memory of the resulting path \(p'\) is computed by \(\varPi (p') = \varPi (p) \cap N_i \cup \left\{ i \right\} \). Sets \(N_i\) are usually composed of the \(\delta \) nearest customers, where \(\delta \) is a chosen parameter. For a more formal definition, the reader is referred to Baldacci et al. (2011) or Martinelli et al. (2014).

In case that solving (10)–(12) using column generation does not yield an integer solution, we define branching decisions on the accumulated flow over edges (see for example (see Desaulniers et al. (2006)), i.e., \(\sum _{k \in V} x_{i,j,k}\) for a given edge (i, j). In particular, all edges with a fractional flow are eligible for branching. The child nodes arise by introducing additional restrictions: either, edge (i, j) is simply removed from the network, or all edges entering j (except (i, j)) and all edges leaving i (except (i, j)) are removed from the network. A node is discarded if the resulting instance is infeasible, the solution is integer, or the resulting lower bound is higher than the objective function value corresponding to the best integer solution known so far.

As the CVRP is a symmetric problem, branching decisions are made on the flow \(\tilde{x}_{i,j,k} = x_{i,j,k} + x_{j,i,k}\). For \(\sum _{k \in V} \tilde{x}_{i,j,k}=0\), both edges are removed from the network, otherwise constraints of the from \(\sum _{k \in V} \tilde{x}_{i,j,k}=1\) are added to the master problem.

To further improve the quality of obtained bounds for the SCVRP, we extend the branch and price framework to a branch price and cut framework. Cutting planes are computed at the root node of the tree, using the CVRPSEP library, see Lysgaard et al. (2004), and maintained for all nodes in the tree.

In case of more than one edge with an accumulated fractional flow, the branch and price algorithm must choose an edge to branch on. The general principle behind variable selection algorithms is to assign a score to each candidate variable, in our case to each edge, and choose the variable with the highest score. Multiple strategies have been proposed to compute such scores. For an overview, the reader is referred to Achterberg et al. (2005). The most commonly used score computing approaches and the ones used as benchmarks in this paper are outlined in the remainder of this section.

Besides choosing an edge to branch on, the node to process next has to be chosen from a set of unprocessed nodes in each branch and price iteration. Most common strategies to select nodes include: “depth first”, i.e., selecting nodes that are situated at lower levels of the tree or equivalently nodes with large depth in the tree, “breadth first”, i.e., nodes with lower depth in the tree, “best first”, i.e., selecting nodes with the best lower bound, or combinations of the latter. In this paper, the “best first” approach is used as a standard node selection strategy.

Given an instance I of SVRPTW with corresponding customer set \(N_I\) for a chosen “base customer” set \(N_B\), the most simple classification task one may think of is whether an edge (i, j) with \(i,j \in N_I\) will be part of a route in the optimal solution. Let \(V_I = (v_i)_{i \in N_B}\) be a binary vector of size \(|N_B|\), whose i-th element indicates whether customer i is in \(N_I\) or not. Although, the “base-instance” contains information on the location of customers and corresponding time windows, this information is abstracted for a specific instance I via \(V_I\).

Let \(I_{\text {Train}}\) be a set of instances with known optimal solutions, i.e., computed “off-line” by some exact algorithm as described in Sect. 4, and \(I_{\text {Test}}\) be a set of instances with unknown optimal solutions derived from the same “base instance”. Further, for a given edge (i, j) with \(i,j \in N_B\) let \(I^{(i,j)}_{\text {Train}} = \left\{ I \in I_{\text {Train}} | i \in N_I \wedge j \in N_I \right\} \) be the set of instances that contain both nodes. The resulting feature and response set is illustrated by Fig. 1, where responses are 1 if the optimal solution contains edge (i, j) and 0 otherwise.

Based on the structure of features and responses described by Fig.  1, we train a family of edge-models \(M^{(i,j)}_E\) for every edge (i, j) with \(i,j \in N_B\). In the following, we use models \(M^{(i,j)}_E\) as functions \(M^{(i,j)}_E(V)\) that map binary vectors V of size \(|N_B|\) to \(\left\{ 0,1 \right\} \), i.e., predicted to be in the optimal solution or not. In this paper, we use random forest classifiers for models \(M^{(i,j)}_E(V)\) Murphy (2012), but compare results to other ML models. Note that the resulting feature and response data are strongly unbalanced in many cases, which is addressed by performing bootstrapping on the training data.

Note that for the SCVRP we treat (i, j) and (j, i) as one edge. Hence, models are only constructed once and features are set to 1 if either edge is in the optimal solution.

Experiments have shown that models \(M_E\) have a relatively high precision, but a medium to low hit-rate. In other words, when predicting an edge to be in the optimal solution, the probability that the edge is actually in the optimal solution is relatively high, but models seem to quite often predict optimal edges not to be in the optimal solution. Therefore, a second family of models is proposed in the following section.

The second fundamental prediction task one may think of when predicting solution structures of vehicle routing problems is to predict the successor of a given node in the optimal solution.

Therefore, we use a similar feature set as illustrated by Fig. 1, but \(I^{i}_{\text {Train}}\) is the set of instances that contain i and we replace the binary responses by customer indices of the successor of i, as shown by Fig. 2.

Using features and responses described above, we train ranking models \(M_N^n\) for all nodes \(n \in N_B\). Analogously to Sect. 5.1, models \(M^n_N\) may be seen as a function \(M^n_N(V)\) mapping any binary vector V of size \(|N_B|\) to the set of nodes \(N_B\). In principle, any ranking model may be used, in this paper we use a probability-based model resulting from random forest classifications Murphy (2012). Note that this may also result in predictions that violate constraints (6). Note that models are not used for the SCVRP.

Computational experiments have shown that the precision of models \(M_N\) is significantly lower than the precision of models \(M_E\). However, a closer investigation of the results identified that \(M_E\) models often failed to classify “obvious” optimal edges, which were correctly classified by \(M_N\). Hence, we propose a combined use of models \(M_E\) and \(M_N\), as described in the following section.

To combine strengths of models \(M_E\) and \(M_N\) and reduce their weaknesses, we propose the following combined approach. Given an instance \(I \in I_{Test}\), we first apply models \(M_E^{(i,j)}(V_I)\) for every edge (i, j) with \(i,j \in N_I\). Let \(P_E\) be the resulting set of edges that were predicted to be in the optimal solution and \(P_E^s\) the set of start nodes of edges in \(P_E\) and respectively \(P_E^e\) the set of end nodes . Second, we apply a first post-processing procedure to correct for violations of constraints (6). This first post-processing procedure prioritizes the removal of edges that contribute most to in-degrees (or out-degrees) of nodes bigger than one and breaks ties by edge lengths, a detailed description is provided in the appendix (Algorithm 3). This is motivated by the observation that the edge-based ML models show a higher precision in predicting the presence of an edge in the optimal solution. Moreover, computational experiments have shown that removing a smaller number of edges is beneficial.

Third, we apply models \(M_N^n(V_{I})\) for nodes \(n \in N_{I}\) to obtain newly predicted edges \(\tilde{P}_E\). However, we only keep those predictions if they are not conflicting with the predictions of models \(M_E\). Hence, if the start (or end) node of a predicted edge \((i,j) \in \tilde{P}_E\) is in the set of start nodes \(P_E^s\) (or end nodes \(P_E^e\)), then e is discarded. This is motivated by the fact that in the case of conflicting predictions, only one is potentially a true positive. Experimentation has shown that models \(M_E\) yield a higher precision than models \(M_N\), i.e., the probability of a true positive prediction is higher for \(M_E\) models, but \(M_N\) models are capable of “adding” optimal edges that have been missed by edge-based models.

Finally, we apply a second post-processing procedure that corrects for violations of time window constraints (8) and capacity constraints (3). See Algorithm 4 in the appendix. The resulting predicting solution procedure is illustrated by Algorithm 1.

For the SCVRP, the correction procedure does not distinguish between in- and out-degrees and removes edges as long as there are customer nodes with degree strictly larger than 2.

Note that as prediction results are used for node selection policies, rather than constructing feasible solutions, the application of post-processing methods to resolve feasibility violations would not be necessary. However, the existence of violations implies false positives, i.e., “wrongly” predicted edges in the solution. Experimentation has shown that: the proposed post-processing methods on average remove more false positive than true positive predicted edges; and that the negative affect of false positives on the performance of the proposed node selection method (that will be introduced in Sect. 7) is larger than the negative affect of false negatives.

The quality of prediction results obtained by Algorithm 1 is significantly lower for edges incident to the depot than for edges connecting two customers. Further, for single depot variants of routing problems, optimal solutions are uniquely defined by edges (i, j) with \(i,j \in N_I\). Therefore, Algorithm 1 is only applied for edges between customers.

Given a branch and bound tree and the associated set O of unprocessed nodes in the tree, the task of any node selection procedure H(O) is to select a node for processing. However, for each node \(o \in O\) there is a unique edge (i, j) that was chosen for branching in the predecessor node of o that led to the creation of o. In other words, node o is a result of adding either constraint \(\sum _{k \in V} x_{i,j,k} = 0\) or \(\sum _{k \in V} x_{i,j,k} = 1\) (or removing corresponding edges from the network) to the problem formulation, i.e., in the optimal solution edge (i, j) is either used, or not.

Hence, knowing the optimal solution, one could partition set O into \(O^{opt}\) and \(O^{nopt}\) with \(O = O^{opt} \cup O^{nopt}, O^{opt} \cap O^{nopt} = \emptyset \), where \(O^{opt}\) denotes the set of nodes resulting from decisions that lead to an optimal solution and \(O^{nopt}\) the set of nodes resulting from decisions which do not lead to an optimal solution. Although, usually the optimal solution is not known during the search, we use the predictions of Algorithm 1 to classify a node \(o \in O\) as belonging to either \(O^{opt}\) or \(O^{nopt}\).

The procedure works as follows. In a pre-processing step, we compute a set of predicted edges \(P_E\) using Algorithm 1. Whenever node \(o_1\) and \(o_2\) are created in the branch and bound tree using an edge (i, j), by inclusion and exclusion of edge (i, j), the indicator function \(\mathbb {1}_{P_E}((i,j))\) is evaluated. If \(\mathbb {1}_{P_E}((i,j))=1\), then \(o_1\) is added to \(O^{opt}\) and \(o_2\) is added to \(O^{nopt}\). Analogously, if \(\mathbb {1}_{P_E}((i,j))=0\), then \(o_2\) is added to \(O^{opt}\) and \(o_1\) is added to \(O^{nopt}\).

Given a standard node selection procedure H, we define the corresponding predicted node selection \(H^p\) as follows:To select nodes within subsets \(O^{\mathrm{opt}}\) and \(O^{\mathrm{nopt}}\), i.e., the standard procedure H we use best-first heuristic in this paper (selecting the node with the best lower bound).

Assuming a perfect prediction \(P_E\), \(H^p\) would lead to a shorter search trajectory to the optimal solution, and hence a smaller tree. During experimentation, we observed that imperfect predictions \(P_E\) also lead to a reduction in the resulting tree size by narrowing down the search to regions that contain decisions with a higher likelihood to be optimal.

In the following, we define two variable selection methods that make use of the prediction models introduced in Sect. 6. Denote by \(\varTheta _{(i,j)}(b_n)\) the predicted FSB score for edge (i, j) for a given instance I and a node \(b_n\) in the branch and price tree (and associated features).

The first presented method, referred to as Prediction Branching (PB), simply ranks candidate edges according to their predicted scores \(\varTheta _{(i,j)}(b_n)\). In case no model exists for edge (i, j), the score is set to \(-1\). This may happen if edge (i, j) has never been considered for branching, i.e., never had a fractional value in the solution of some relaxed problem in any training instances. For such an edge, no branching information has been collected during training and consequently, no model has been generated.

For the second method, referred to as Reliability Prediction Branching (RPB), we keep lists \(\varUpsilon _{(i,j)}^+\) and \(\varUpsilon _{(i,j)}^-\) for each edge in I to store observed bound increases that result from including (\(\varUpsilon _{(i,j)}^+\)) or excluding (\(\varUpsilon _{(i,j)}^-\)) edge (i, j)) and processing the associated node. Further, let \(\varPhi _{(i,j)}\) be a quality indicator for each edge (i, j) that is initially set to zero for all edges. Algorithm 2 outlines the proposed procedure.

Note that except for the lines 13 to 25 Algorithm 2 behave similarly as RB. In line 6, it is checked whether “enough” node evaluations on the corresponding edge have been performed previously. This is analogous to the decision whether to use PCB or FSB in RB. The required number of node evaluations is controlled by the reliability parameter \(\eta _{\mathrm{rel}}\). However, even in the early phase of the search where FSB is used to compute edge scores, the corresponding edge models \(\varTheta _{(i,j)}\) are applied to assess the quality of the predictions. To this end the resulting predicted score is compared to the actual computed score. If the deviation is within a chosen limit \(\delta \) (or \({\tilde{\delta }}\) if the actual computed score is zero) the quality indicator \(\varPhi _{(i,j)}\) is increased by one, otherwise it is decreased by one, see lines 12-15. Models with a negative quality indicator are discarded after the reliability phase and the PCB score is used for the corresponding edges instead.

The definition of a benchmark instance for the SVRPTW (and respectively SCVRP) involves a base instance and a sampled instance for this base instance. Base instances for the SVRPTW were obtained either from the Solomon 100 customer instances Solomon (1987), or from the Gehring & Homberger instances with 200 customers Gehring and Homberger (2005). Those instances are divided into three categories, r class instances (randomly distributed customers), c class instances (clustered customers) and rc class instances (a mix of randomly distributed and clustered customers).

For each base instance, we created 1000 randomly sampled instances consisting of exactly n customers. Those instances were used for training ML models. Further, for each base instance, we randomly sampled 200 evaluation instances of exactly n customers as an evaluation set. In the following, we use the Solomon and Gehring & Homberger instance nomenclature to refer to results corresponding to one base instance, e.g., when referring to instance r101.n, we consider all evaluation instances of size n for the base instance r101.

In addition to evaluation instances of fixed size, we created evaluation instances with a randomly chosen number of customers from the interval \(\left[ 40 , 60 \right] \) for a selected set of base instances. Those instances are referred to by their Solomon identifier, followed by “RS”, e.g., c109.RS.

For the SCVRP, the same principle is applied to derive benchmark instances based on the classical instance datasets A, B, E, and M.

During the training phase, all sampled training instances of one base instance are solved to optimality using FSB. Thereby, the following data sets are generated. First, a collection of binary instance vectors and corresponding optimal solutions is created. Second, we record all feature sets, as described by Table 1, and the resulting FSB scores of all nodes in the corresponding branch and price trees. A time limit of 4 hours was applied for each solving procedure. Further, we terminate the search if the number of unprocessed nodes exceeds 25000. We will refer to these settings as time limit and node limit through the rest of the paper, respectively.

The regression forest estimator of the scikit-learn library was used to fit the models presented in Sect. 6 (FSB score prediction) and the regression classifier estimator for the models presented in Sect. 5 (solution structure prediction). In both cases, we used 100 trees to build a single forest.

Further, in cases when FSB failed to compute a sufficiently large number of optimal solutions on the training set to fit models \(M_E\) and \(M_N\) within the time limit, RB was applied to compute optimal solutions for sampled instances where FSB failed.

In this section, the performance of Algorithm 1 for the prediction of solution structure is evaluated. To this end Algorithm, 1 is applied to all 200 sampled evaluation instances for each base instance. This yields a set of predicted edges for each instance.

To evaluate the performance of random forest classifiers used within Algorithm 1, prediction results are also computed using neural networks classifiers for both \(M_E\) and \(M_N\) models (referred to as NN) and logistic regression classifiers for \(M_E\) models (referred to as LR).

However, all above outlined versions of Algorithm 1 require an expensive training phase. To compare the performance of Algorithm 1 to an approach that is not based on a training set of optimal solutions, we adopt a method to compute so-called generator arcs in granular heuristics for vehicle routing problems. Informally speaking, granular heuristics (e.g., granular tabu search) function similarly to standard neighborhood heuristics, but drastically reduce the size of considered neighborhoods to achieve a beneficial trade-off between solution quality and computational effort. Thereby, a common practice for vehicle routing problems is to compute a set of generator arcs, i.e., arcs with a high probability of being in an optimal or at least good solution, and allow only neighborhood moves that result in a generator arc being in the solution. The generator arcs are usually selected by sorting the arcs with respect to some cost measure, i.e., original costs or reduced costs from the relaxed problem formulation. Then the arcs the costs of which lie below a certain threshold are selected. Alternatively, a predefined number of arcs with smallest costs are chosen. For a detailed definition and description, the reader is referred to Schneider et al. (2017). We follow a similar approach and sort arcs with respect to network relaxation with time-adjusted cost for the SVRPTW and network relaxation with original cost for the SCVRP (for a precise definition see Schneider et al. (2017)). Further, we iterate through sorted arcs and add arcs to a set of predicted edges if the insertion does not yield a degree violation among predicted edges. The proposed method is referred to as granular generator arcs (GGA).

Further, during the execution of the algorithms Most Fractional Branching (MFB), Pseudo Cost Branching (PCB), Reliability Branching (RB), Prediction Branching (PB) and Reliability Prediction Branching (RPB), optimal solutions for those instances were computed and collected. Note that sampled instances for which none of the aforementioned algorithms was able to compute an optimal solution within the proposed time and node limits were excluded from the analysis. Hence, it is possible that the results reported for a given base instance are based on less than 200 test cases.

In order to assess the quality of the prediction of optimal edges in comparison with the computed optimal edges, the following terms need to be defined. True Positives (TP) refer to edges that have been predicted to be in the optimal solution and actually are. False Positives (FP) denote edges that were predicted to be optimal, but are not part of any route in the optimal solution. True Negatives (TN) and False Negatives (FN) can be defined accordingly for edges that were predicted not to be in the optimal solution. Note that we compute TP, FP, TN and FN for each sampled instance of a specific base instance and, in the following, report the average of those values (per base instance). Further, we define the precision as \(\mathrm{Precision} =\frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FP}}\). Analogously to the above, we compute the precision per sampled instance and report the average of all sampled instances as the precision of a specific base instance. In general, the classification over edges is strongly unbalanced, i.e., the majority of edges are not in the optimal solution. To assess the prediction quality of such unbalanced classifiers, the Matthews Correlation Coeffecient (MCC) is often used. It is computed byand returns values between \(-1\) and 1, where 1 denotes a perfect prediction, 0 a random prediction and \(-1\) a prediction doing exactly the opposite to real world observations. Values above 0.4 are considered to indicate a strong positive correlation between predictions and real world observations, and values above 0.7 a very strong correlation. Results regarding the MCC are also reported as the average over MCC values per sampled instances. The results are summarized in Table 2.

It can be observed that instances with a clustered set of customers of size \(n=50\), i.e., the c1 class, leads to better results in terms of both precision and MCC, with a few exceptions. The precision exceeds 85% for most of those instances. Hence, a large percentage of edges of an optimal solution can be predicted by Algorithm 1. For some of these instances the branch and price trees are very small and the optimal solutions are relatively easy to predict (see next section). For other instances, as for example c109, the branch and price trees are significantly larger, but the optimal solutions are still predicted well by Algorithm 1. In general, it can be observed that the precision is above 70% for a majority of instances. Further, the MCC is above 0.5 for almost all instances, indicating a strong correlation between prediction and observations. For most c1 class instances, the MCC is above 0.7, indicating a very strong correlation.

The observed precision and MCC for \(n=100\) customers and SCVRP instances clearly demonstrate that the prediction quality yield by Algorithm 1 is independent of instance sizes and the consideration of time windows.

Comparing results of different ML models, one may observe that random forest classifiers outperform neural networks and logistic regression models for all instances regardless of the size and the inclusion of time windows. Further, the prediction quality of the GGA approach is inferior compared to models based on a training phase. Interestingly, GGA achieves significantly better precision values for SCVRP instances than for instances including time windows. This may lead to the conclusion that the importance of edge costs, i.e., lengths, is significantly higher for instances without time windows and that the time adjusted reduced arc costs only have limited potential to abstract the complexity that is inherit to the decision if an edge is part of the optimal solutions.

In this section, we evaluate branching strategies PB and RPB compared to the commonly known variable selection strategies outlined in Sect. 4.4. For all evaluation instances, the reliability parameter used by RB and RPB was set to \(\eta _{\mathrm{rel}} = 2\). The quality limits for RPB were set to \(\delta = 0.4\) and \({\tilde{\delta }} = 0.05\). Further, the same time limit and node limit as in the training phase, i.e., 4 hours or 25000 unprocessed nodes, were applied for every instance and algorithm. In the following section, we evaluate the performance of PB and RPB on instances of fixed size. Then we demonstrate that PB and RPB are robust with respect to small changes in instance sizes by evaluating the two approaches on instances r110.RS, r111.RS, c109.RS and rc106.RS in Sect. 8.3.2.