BucketGraph-final-clear-15.txt

                 ABucket Graph Based Labelling Algorithm for Vehicle
                                                             Routing
                                 Ruslan Sadykov, Artur Alves Pessoa, Eduardo Uchoa
                   To cite this version:
                 Ruslan Sadykov, Artur Alves Pessoa, Eduardo Uchoa. A Bucket Graph Based Labelling Algorithm
                 for Vehicle Routing. Transportation Science, 2021, 55 (1), pp.4-28. ￿10.1287/trsc.2020.0985￿. ￿hal-
                 02378624v2￿
                                                HALId: hal-02378624
                                  https://inria.hal.science/hal-02378624v2
                                                    Submitted on 3 Nov 2020
                 HAL is a multi-disciplinary open access              L’archive ouverte pluridisciplinaire HAL, est
             archive for the deposit and dissemination of sci-    destinée au dépôt et à la diffusion de documents
             entific research documents, whether they are pub-    scientifiques de niveau recherche, publiés ou non,
             lished or not.   The documents may come from émanant des établissements d’enseignement et de
             teaching and research institutions in France or recherche français ou étrangers, des laboratoires
             abroad, or from public or private research centers.  publics ou privés.
                                                       HALAuthorization
                                 ABucket Graph Based Labeling Algorithm with
                                                 Application to Vehicle Routing
                                                             1                      2                         2
                                        Ruslan Sadykov , Eduardo Uchoa , and Artur Pessoa
                          1INRIA Bordeaux – Sud-Ouest 200 Avenue de la Veille Tour, 33405 Talence,
                                                                       France
                          2Universidade Federal Fluminense - Engenharia de Produ¸c˜ao , Rua Passo da
                                               P´atria 156, Niter´oi - RJ - Brasil - 24210-240,
                                                                       Abstract
                                 Weconsider the Shortest Path Problem with Resource Constraints (SPPRC) arising as
                             a subproblem in state-of-the-art Branch-Cut-and-Price algorithms for vehicle routing prob-
                             lems. We propose a variant of the bi-directional label correcting algorithm in which the
                             labels are stored and extended according to the so-called bucket graph. Such organization
                             of labels helps to decrease significantly the number of dominance checks and the running
                             time of the algorithm. We also show how the forward/backward route symmetry can be
                             exploited and how to eliminate arcs from the bucket graph using reduced costs. The pro-
                             posed algorithm can be especially beneficial for vehicle routing instances with large vehicle
                             capacity and/or with time window constraints. Computational experiments were performed
                             on instances from the distance constrained vehicle routing problem, including multi-depot
                             and site-dependent variants, on the vehicle routing problem with time windows, and on
                             the “nightmare” instances of the heterogeneous fleet vehicle routing problem. Significant
                             improvements over the best algorithms in the literature were achieved and many instances
                             could be solved for the first time.
                       1     Introduction
                       The best known exact approach for many classical variants of the Vehicle Routing Problem
                       (VRP) is a Branch-Cut-and-Price (BCP) algorithm in which the master problem contains route
                       variables, customer visiting constraints and additional cuts. Because of their exponential number,
                       theroutevariablesaregenerateddynamicallybysolvingpricingsubproblemsmodeledasShortest
                       Path Problems with Resource Constraints (SPPRC). In those problems, one looks for least cost
                       paths joining a source vertex with a sink vertex such that the accumulated consumption of
                       resources along the path respects given lower and upper limits. Dynamic Programming labeling
                       algorithms are the most usual way of solving those problems.
                           Labeling algorithms differ from the traditional “table filling” dynamic programming algo-
                       rithms because they only store (as labels) the reachable states, those representing feasible partial
                       paths. More importantly, while traditional dynamic programming only performs dominance
                       over identical states, labeling algorithms perform dominance between labels corresponding to
                                                                                                0
                       non-identical states. Typically, a label L0 representing a path PL is dominated, and therefore
                       eliminated, if there is another label L representing a path PL that ends in the same vertex
                                                                                                 0
                       and is not more costly and does not use more resources than PL . Mono-directional labeling
                       algorithms start from a single label representing a null path at the source vertex. At each step,
                       a non-extended label L is extended to additional labels corresponding to the possible ways of
                       adding a single arc to PL. Dominance may be used to eliminate labels, avoiding future exten-
                       sions. If there are no non-extended labels, the algorithm stops and optimal solutions are found
                       among the labels representing paths ending in the sink vertex. The general labeling algorithm
                                                                           1
         has several degrees of freedom. In particular, there are many possible ways of choosing the
         next label to be extended and how often and how extensively dominance checks are performed.
         Particular labeling algorithms are classified as being either label-setting or label-correcting. The
         defining property of a label-setting algorithm is that it only extends labels that can never be
         dominated by another label created after that extension.
           There is a large literature on labeling algorithms for SPPRC, we refer to Irnich and De-
         saulniers (2005) and Pugliese and Guerriero (2013) for surveys. However, somehow surprisingly,
         not so many papers discuss in depth issues related to label organization and dominance strate-
         gies. In fact, even though the pricing time is a bottleneck in many BCP algorithms for VRP,
         authors often skip the details of the labeling algorithm used. An exception is the recent algo-
         rithm for the Capacitated VRP (CVRP) in Pecin et al. (2017b). In that case, assuming that the
         consumptions of the single resource (capacity) are given by positive integer numbers, labels are
         organized in buckets corresponding to each possible consumption. Dominance is only performed
         for labels in the same bucket, that by definition have the same resource consumption. However,
         that approach cannot be applied in cases where resource consumptions are given by arbitrary
         real numbers. In fact, if the consumptions are given by larger integer numbers the algorithm
         becomes slow, since few dominance checks are performed and too many undetected dominated
         labels are expanded. The opposite approach is to perform full label dominance after each ex-
         tension. In this case, the running time may suffer a lot from too many dominance checks with
         negative results.
           Lozano and Medaglia (2013) proposed the so-called Pulse Algorithm for the SPPRC. Pulse is
         better viewed as a depth-first branch-and-bound search algorithm than as a dynamic program-
         ming labeling algorithm, because it uses dominance in a severely limited way — each vertex
         only keeps a handful of partial paths for performing dominance checks. The main mechanism
         in Pulse for trying to avoid an exponential explosion in its search is bounding, a partial path is
         pruned if it can be shown that it cannot be extended into a full path ending at the sink vertex
         that costs less than the currently best known source to sink path. Pulse produced excellent
         results, much better than label-setting algorithms, on some stand-alone SPPRCs where all arc
         costs are positive. The last feature helps Pulse because it allows good bounds to be computed by
         Dijkstra’s-like algorithms. Up to now, as far as we know, Pulse was only tested as a subproblem
         solver in a column generation algorithm for VRP with Time Windows (VRPTW) in Lozano,
         Duque, and Medaglia (2015). The SPPRCs that appear in that context are more complex be-
         cause the master dual variables make arc costs to be possibly negative. The test was calculating
         the elementary route bound on instances with 100 customers. The variant of Pulse used for the
         VRPTWonlyperformsanevenmorebasicformofdominancecalledrollbackpruning. However,
         it proposes a more sophisticated bounding mechanism that only considers the time resource. The
         obtained results compare favourably with the labeling algorithms of Desaulniers, Lessard, and
         Hadjar (2008) and Baldacci, Mingozzi, and Roberti (2011). It is not known how Pulse would
         perform on larger instances and how it would handle the modifications in the SPPRC induced
         by cuts, essential for modern BCP algorithms for VRP.
           The main original contributions of this paper are the following:
           • In Section 3, a new variant of the labeling algorithm is proposed. The approach relies on
            a so-called bucket graph, consisting of buckets and bucket arcs. Labels for paths ending
            in the same vertex of the original graph and having similar resource consumption are
            grouped together in buckets. A bucket arc links two buckets if a label in the first one
            can be possibly extended to a label in the second. Labels within the same bucket are
            always pairwise undominated, i.e. there is no label which is dominated by another label
            in the same bucket. However, dominance checks between labels in different buckets are
            only performed before an extension, when it is checked whether a candidate label to be
            extended is dominated or not. Moreover, this inter-bucket dominance uses bounds on the
            costs of all labels in a bucket, avoiding many unnecessary checks. The key parameter of
            the algorithm is the step size, used for determining the resource consumption intervals that
            define each bucket. If the step size is sufficiently small, the bucket graph is acyclic and the
            algorithm becomes a label-setting algorithm. In general, the bucket graph has cycles and
                              2
                           the algorithm is a label-correcting algorithm. A bi-directional version of the bucket graph
                           based labeling algorithm is also proposed (since Righini and Salani (2006) it is known
                           that bi-directional labeling algorithms are often more efficient than their mono-directional
                           counterparts). The concatenation of labels step is also accelerated by bounds on the costs.
                           Bi-directional search also allows us to exploit the forward/backward symmetry of routes
                           that exists on some VRP variants, for example, on the classical Capacitated VRP (CVRP).
                           Onthosecases, the backward search is replaced by a “reversed copy” of the forward search,
                           reducing the running time.
                         • In Section 4, a procedure for accelerating the labeling algorithm by removing arcs from the
                           bucket graph using reduced cost arguments is proposed. We call it bucket arc elimination
                           procedure.  The concept of jump bucket arcs is introduced. The new fixing procedure
                           generalizes both the procedures in Irnich et al. (2010) and in Pessoa et al. (2010). After a
                           fixing, some bucket arcs are eliminated, and thus the number of extensions and the running
                           times are reduced in future calls to the labeling algorithm.
                         The new labeling algorithm was embedded as the pricing method in a modern BCP algo-
                     rithm for VRPs. Our BCP also includes many ingredients found in other state-of-the-art BCP
                     algorithms, like dynamic ng−path relaxation, rounded capacity cuts, limited arc memory rank-
                     1 cuts, automatic dual price smoothing stabilization, a procedure for enumerating elementary
                     paths, and multi-phase strong branching with pseudo-costs. The algorithm was computation-
                     ally tested on several VRP variants with time window constraints and/or large vehicle capacity.
                     Pretests have shown that the labeling algorithm could perform very well, but that performance
                     is rather sensitive to the choice of the step size parameter. Moreover, the good step size val-
                     ues varied strongly from instance to instance. Therefore, a simple but effective scheme for an
                     automatic dynamic adjustment of the step size was devised. Other specific experiments indi-
                     cate that, on the hardest instances, the new bucket arc fixing procedure can indeed be better
                     than existing schemes for fixing arcs by reduced cost. Lastly, extensive experiments show that
                     the final BCP algorithm outperforms significantly other recent state-of-art algorithms for the
                     VRPTW and the Multi-Depot VRP with Distance Constraints (MDVRPDC). Moreover, our
                     algorithm is the first exact approach that can handle medium-sized instances of the classical
                     Distance Constrained Vehicle Routing Problem (DCVRP), including the site-dependent vari-
                     ant. Our algorithm is also the first exact method successfully applied for a set of “nightmare”
                     instances of the Heterogeneous Fleet VRP (HFVRP).
                         The remainder of this article has the following structure. Section 2 defines the exact SPPRC
                     solved in this paper. It is explained how this SPPRC arises as a pricing subproblem for solving a
                     Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HFVRPTW) by a column-
                     and-cut generation algorithm. Section 3 describes the bucket graph labeling algorithm proposed
                     in this work. Section 4 presents the bucket arc elimination procedure and introduces the key
                     concept of jump bucket arcs. Section 5 presents the complete BCP algorithm for HFVRPTW
                     where the bucket graph labeling algorithm was embedded. Section 6 presents results of the
                     computational experiments. There are experiments devised to assess the impact of the bucket
                     step size and experiments for measuring the impact of the introduced bucket arc elimination
                     procedure. Moreover, extensive experiments evaluate the overall BCP performance on several
                     classical VRP variants that are particular cases of the HFVRPTW. Section 7 contains final
                     remarks. Finally, very detailed computational results are presented in the online appendix.
                     2     Application
                     In order to give a precise definition of the SPPRC addressed in this paper, we first need to define
                     its application; defining the family of VRPs that we ultimately want to solve and outlining the
                     column-and-cut generation algorithm where that SPPRC arises as the pricing subproblem.
                                                                     3
                       2.1     HFVRPTWDefinition
                       The Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HFVRPTW) (Jiang
                       et al. 2014) is defined as follows. Let G = (V,A) be a directed graph with vertex set V =
                       {0,...,n +1}. For convenience, the depot vertex is split into the source vertex 0 and the sink
                       vertex n + 1; vertices in V 0 = V \ {0,n + 1} represent the n customers. The arc set is defined
                       as A = {(v,v0) : v,v0 ∈ V,v 6= v0,v 6= n + 1,v0 6= 0,(v,v0) 6= (0,n + 1)}. Each vertex v ∈ V
                       has a demand w , a service time (duration) s , and a time window [l ,u ] associated with it.
                                         v                                v                          v  v
                       Demands and service times are non-negative for customers v ∈ V0 and equal to zero for the
                       depot vertices, l is assumed to be equal to 0. The fleet is composed of a set M of different types
                                        0
                       of vehicles. For each m ∈ M, there are U          available vehicles, each with a capacity W . Let
                                                                      m                                                 m
                       W=max{Wm:m∈M}bethelargest capacity. Every vehicle type is associated with a fixed
                       cost denoted by fm. For each arc a ∈ A and m ∈ M there is a cost cm and a non-negative travel
                                                                                                 a
                       time tm associated to the traversal of this arc by a vehicle of type m. We assume that G does
                              a
                       not have any cycle where, for some vehicle type, all vertices have zero demands and zero service
                       times and all arcs have zero time. A route P = (v = 0,v ,...,v ,v             =n+1)foravehicle of
                                                                             0        1      k   k+1
                       type m ∈ M is a walk where v ,...,v are not necessarily distinct customers in V0 and is said to
                                                        1       k      P
                       be feasible if 1) it satisfies vehicle capacity:    k   w ≤W ;and2)theearliest start of service
                                                                          j=1   vj     m
                       time Sj at every visited vertex vj, 0 ≤ j ≤ k + 1, falls within the corresponding time window:
                       l  ≤S ≤u ,whereS =l andS =max{l ,S                         +s      +tm         }. A vehicle may arrive
                        v      j    v            0    0       j          v    j−1     v
                         j           j                                    j            j−1    (v   ,v )
                                                                                                j−1 j
                       at a vertex before the beginning of its time window and wait, but it cannot arrive after the end
                                                                                           P
                       of the time window. The cost of route P is calculated as f       + k+1cm            . A route is said to
                                                                                      m      j=1 (v     ,v )
                                                                                                    j−1 j
                       be elementary if the same customer is not visited more than once. The objective is to determine
                       a set of feasible elementary routes with minimal total cost such that: (i) each customer is visited
                       by exactly one route; (ii) the number of routes associated to a vehicle type does not exceed its
                       availability. Clearly, some of most classical VRP variants, like CVRP, VRPTW and HFVRP,
                       are particular cases of HFVRPTW. Other variants that are also particular cases of HFVRPTW
                       are listed below.
                           In the Multi-Depot VRP (MDVRP), the vehicles themselves are identical, they only differ
                       by being attached to different depots. It can be easily modeled as a HFVRP by associating each
                       depot to a vehicle type and setting costs cm         and times tm      for leaving the depot, together
                                    m                    m            (0,v)             (0,v)
                       with costs c         and times t          for entering the depot, that depend on m ∈ M. The Site
                                    (v,n+1)              (v,n+1)
                       Dependent VRP (SDVRP), a variant where vehicles differ only by the subset of the customers
                       that they can visit, is also easily modeled as a HFVRP by setting infinite costs for cm                 if
                                                                                                                        (v,v0)
                       vehicle type m cannot visit either v or v0.
                           Theclassical Distance Constrained Vehicle Routing Problem (DCVRP) can also be solved as
                       a HFVRPTW.Inthisvariant, besides the capacity constraint, the route length is also forbidden
                       to be above a certain threshold D. Since service times are included in that “length”, this is
                       actually a time limit for returning to the depot. It can be modeled by setting time window [0,D]
                       for every v ∈ V .
                       2.2     Set Partitioning Formulation and Cuts
                       Let Ωm be the set of all feasible elementary routes for vehicle type m ∈ M. A set partitioning
                       formulation over those sets would lead to a hard pricing problem, probably intractable on large
                       instances. A more tractable (but weaker) formulation can be defined using a relaxed set of
                       routes that includes some non-elementary routes, i.e. routes in which some customers are visited
                       more than once. In this work we assume that the ng-route relaxation (Baldacci, Mingozzi, and
                       Roberti 2011), a route relaxation with a good tradeoff between formulation strength and pricing
                       difficulty, is being used. Let N ⊆ V0 be the neighborhood of v ∈ V0, typically containing the
                                                         v
                       closest customers to v. An ng-route can only revisit a customer v, forming a cycle, if the cycle
                       contains another customer v0 with v ∈/ N 0. In many cases, reasonably small neighborhoods (for
                                                                   v
                       example, with |N | = 8) already provide bounds that are close to those that would be obtained
                                          v
                       by pricing elementary routes (Poggi and Uchoa 2014, Contardo, Desaulniers, and Lessard 2015).
                                                                           4
                           Let ΩN ⊇ Ωm be the set of ng-routes for vehicle type m ∈ M with respect to a given set
                                 m
                                                                                                                  N        P
                       of neighborhoods N = (N ,...,N ). We denote by c               the cost of route P ∈ Ω , by x          0
                                                    1        n                      P                P            m        (v,v )
                                                       0                                        P                           P
                       the number of times arc (v,v ) ∈ A appears in route P, and by y            =        +       −      x /2
                                                                                               v       a∈δ ({v})∪δ ({v}) a
                       the number of times vertex v ∈ V0 is visited in route P (this “symmetric” definition of yP is
                                                                                                                           v
                       exploited in Section 3.6). Let λP be a binary variable indicating whether route P is selected or
                       not in the solution. The Set Partitioning Formulation (SPF) for the HFVRPTW considered in
                       this paper is the following.
                                       (SPF) min X X c λ                                                                    (1)
                                                                 P P
                                                    m∈MP∈ΩN
                                                              m
                                         subject to X X yPλP =1                             ∀v ∈ V0,                        (2)
                                                                  v
                                                     m∈MP∈ΩN
                                                      X m
                                                           λ ≤U                             ∀m∈M,                           (3)
                                                             P     m
                                                     P∈ΩN
                                                         m
                                                    λ ∈{0,1}                                ∀m∈M,P ∈ΩN.                     (4)
                                                      P                                                      m
                       Acolumngeneration algorithm should be used to solve the linear relaxation of (1)-(4). However,
                       even using large neighborhoods (or even enforcing that all routes are elementary) the resulting
                       bounds are often not good enough for building an effective branch-and-price algorithm. There-
                       fore, the SPF should be reinforced by adding cuts.
                           Let C ⊆ V0 be a subset of the customers, define w(C) = P              wv as its total demand. The
                                                                                            v∈C
                       value dw(C)/We is a valid lower bound on the number of vehicles that must visit C. Therefore,
                       the following Rounded Capacity Cut (RCC) (Laporte and Nobert 1983) is valid:
                                                X X X P
                                               m∈M       N      +      −    xaλP ≥2dw(C)/We.                              (5)
                                                     P∈Ωm a∈δ (C)∪δ (C)
                       RCCs are known to provide a significant reinforcement of the SPF on the CVRP (Fukasawa
                       et al. 2006). However, they do not work so well on many HFVRP and VRPTW instances. This
                       happens because the expression dw(C)/We, which depends only on the largest vehicle capacity
                       Wanddisregards time windows, can be a poor bound on the actual number of vehicles visiting
                       C. The coefficient of a variable λ        in a RCC is given by a linear expression over the values of
                                                            P
                       xP. This means that RCCs are robust cuts (Pessoa, de Arag˜ao, and Uchoa 2008), such cuts do
                        a
                       not have any impact in the difficulty of the pricing subproblem.
                           Using a Chv´atal-Gomory rounding of a subset C ⊆ V0 of Constraints (2), relaxed to ≤, with
                       multipliers p (0 < p < 1), v ∈ C, the following valid Rank-1 Cut (R1C) is obtained:
                                     v        v
                                                      X X$XpyP%λ ≤$Xp%.                                                     (6)
                                                                         v v     P           v
                                                      m∈MP∈ΩN v∈C                      v∈C
                                                                m
                       The Subset Row Cuts (SRCs) proposed in Jepsen et al. (2008) are the particular R1Cs with
                       multipliers p   = 1/K, where K is an integer, for all v ∈ C. Recently, the optimal multiplier
                                     v
                       vectors for R1Cs with up to five rows have been determined by Pecin et al. (2017c)
                           • For |C| = 3, (1, 1, 1).
                                            2 2 2
                           • For |C| = 4, (2, 1, 1, 1) and its permutations.
                                            3 3 3 3
                           • For |C| = 5, (1, 1, 1, 1, 1), (2, 2, 1, 1, 1), (3, 1, 1, 1, 1), (3, 2, 2, 1, 1), (1, 1, 1, 1, 1),
                                               3 3 3 3 3        4 4 4 4 4        4 4 4 4 4       5 5 5 5 5        2 2 2 2 2
                             (2, 2, 2, 1, 1), (3, 3, 2, 2, 1) and their permutations.
                              3 3 3 3 3       4 4 4 4 4
                       Theyareoptimal in the sense that they generate R1Cs that are equivalent or dominate the R1Cs
                       generated with any other multipliers. When non-elementary routes can be generated, one can
                       also apply cuts (6) with C = {v} and p = 1/2 for some v ∈ V0.
                                                                  v
                                                                           5
                           R1Cs are known to be very effective. However, because of the rounding down operator, the
                                                                                                                             P
                       coefficient of a variable λP in a R1C is not given by a linear expression over the values of x ,
                                                                                                                             a
                       so those cuts are non-robust. The concept of limited-memory for reducing the negative impact
                       of R1Cs in the pricing, first proposed in Pecin et al. (2014, 2017b), represented a breakthrough
                       in the performance of BCP algorithms for VRP. In this paper, we assume that the generalized
                       arc memory variant of the concept (Pecin et al. 2017a) is being used. Each R1C, indexed by `,
                       is associated to a customer subset C` ⊆ V0, a multiplier vector (p`)v∈C`, and an arc memory
                                                                                                 v
                       set AM` with AM` ⊆ A. The idea is that, when a route P ∈ ΩN leaves the memory set, i.e.
                                                                                               m
                       follows an arc not in AM`, it “forgets” previous visits to nodes in C`, yielding a coefficient for
                                                                                              P        ` P
                       λP in the cut ` that may be smaller than the original coefficient b            ` p y c. The memory set
                                                                                                v∈C    v v
                       AM` is defined during the cut separation procedure as a minimal set preserving the coefficients
                       of the route variables λP that have a positive value in the current linear relaxation solution.
                       Given C ⊆ V0, a multiplier vector p of dimension |C|, and a memory arc set AM ⊆ A, the
                       limited-arc-memory R1C cut is defined as:
                                                      X Xα(C,AM,p,P)λP ≤$Xpv%                                               (7)
                                                     m∈MP∈ΩN                             v∈C
                                                               m
                       where the coefficient α(C,AM,p,P) of the route variable λP, P ∈ ΩN, is computed by the
                                                                                                      m
                       following pseudocode:
                         Function α(C, AM, p, P = (v = 0,v ,...,v ,v               =n+1))
                                                           0       1       k   k+1
                           α←0,S←0;
                           for j = 1 to k do
                               if (v   , v ) ∈/ AM then
                                    j−1  j
                                  S ←0;
                               if v ∈ C then
                                   j
                                  S ←S+p ;
                                              v
                                               j
                                  if S ≥ 1 then
                                      S ←S−1,α←α+1;
                           return α;
                           This function can be explained as follows. Whenever a route P visits a vertex v ∈ C,
                       the multiplier p    is added to the state variable S. When S ≥ 1, S is decremented and α is
                                        v                                  P
                       incremented. If AM = A, the function returns b              p yPc and the limited-memory cut would
                                                                              v∈C v v
                       be equivalent to the original cut. On the other hand, if AM ⊂ A, it may happen that P
                       uses an arc not in AM when S > 0, causing the state S to be reset to zero and “forgetting”
                       some previous visits to nodes in C. In this case, the returned coefficient may be less than the
                       original coefficient. However, memory sets can be “corrected” in the next separation round. The
                       final linear relaxation bound obtainable with limited memory R1Cs is exactly that potentially
                       achieved with ordinary R1Cs.
                       2.3     Pricing Problem
                       We now define the pricing problem for the SPF over ng-routes and with additional RCCs and
                       limited-memory R1Cs, which decomposes into subproblems, one for each vehicle type. In the
                                                                                     N
                       subproblem for type m ∈ M, we search for a route P ∈ Ω           with the minimum reduced cost. Let
                                                                                     m
                       J be the current set of active RCCs (5), and L be the current set of active limited memory R1Cs
                       (7). Each cut  ∈ J is determined by a set C of customers. Each cut ` ∈ L is determined by
                                     `      `  `
                       the triple (C ,AM ,p ). Let (π,µ,ν,σ) be the current dual solution of the linear relaxation of
                       (1)-(4) with sets J and L of cuts added, where π corresponds to the partitioning constraints (2),
                       µ corresponds to Constraints (3), ν corresponds to the set J of active RCCs, and σ corresponds
                                                                           6
                                                                                                                        m
                                   to the set L of active limited memory R1Cs. Let c¯ (π,ν) be the vector of current arc reduced
                                   costs, where                                                                                           X
                                                                     m                       m            πv       πv0
                                                                    c¯     0 (π,ν) = c            0   −        −          −                                  ν,                              (8)
                                                                     (v,v )                  (v,v )        2         2
                                                                                                                                          ∈J:
                                                                                                                              (v,v0)∈δ+(C)∪δ−(C)
                                                                                                                                                      m
                                   where π0 and πn+1 are defined as zero. The pricing subproblem (PSP ) for vehicle type m ∈ M
                                   is then formulated as
                                                                              X m                        X                   `         `    `                 !
                                                                    min                c¯  (π,ν)−              σ ·α(C ,AM ,p ,P)−µ                               .
                                                                          N             a                        `                                         m
                                                                   P∈Ωm a∈P                              `∈L
                                   3        Bucket Graph based Labeling Algorithm
                                   3.1        SPPRCover Forward and Backward graphs
                                   We now formulate the pricing problem defined in Section 2.3 as a SPPRC in a forward graph
                                   ~               ~                                                  ~
                                   G = (V,A) that is identical to G, so A = A. In this section we consider the dual solution
                                   (π,µ,ν,σ) fixed and also drop index m for more clarity. Therefore, the reduced cost of an arc
                                          ~
                                   a ∈ A is denoted simply as c¯ . Define a set of two resources R = {1,2} corresponding to vehicle
                                                                                  a
                                                                                                                                                          0       ~                       0
                                   capacity and time. The capacity resource consumption of each arc (v,v ) ∈ A equals to wv and
                                   the time resource consumption of the same arc equals to s +t                                                 0 . For convenience, we use the
                                                                                                                                   v      (v,v )
                                                                                                                                            ~
                                   same notation d                 for the resource consumption of an arc ~a ∈ A for both resources r ∈ R. Each
                                                             ~a,r
                                   vertex v ∈ V has lower and upper bounds l                                   andu          on the accumulated resource consumption
                                                                                                         v,r            v,r
                                   to v of each resource r ∈ R. For the second resource (time) these bounds correspond to original
                                   time windows. For the first (capacity) resource, we have l                                                =0and u                =W. To simplify
                                                                                                                                      v,1                     v,1
                                   the notation, we often drop the resource index r to represent a vector with the corresponding
                                   values for all resources in R, e.g. l = (l                              , . . . , l      )>. Moreover, we use x  y to denote the
                                                                                             v         v,1           v,|R|
                                                                                                                                                                                 ~
                                   component-wise product of two vectors x and y. We always represent a forward path P in graph
                                                                                           ~      ~            ~                  ~           ~        ~        ~              ~
                                   ~                                           ~           P     P            P                   P           P        P       P              P
                                   Gas defined by its arcs: P = (~a ,~a ,...,~a                                     ), with ~a         =(v          , v   ), v      =0, v            =n+1.
                                                                                           1     2              ~                 j          j−1       j       0                ~
                                                                                                              |P|                     ~                                       |P|
                                   For lightening the notation, we may drop the superscript P when it is clear from the context.
                                                                                                                                             ~          |R|
                                            ~                                                                                                P
                                   Path P yields a vector of accumulated resource consumptions qj ∈ IR                                                       at vertices that can be
                                   computed as:                                       (
                                                                                           l                                           if j = 0;
                                                                               ~            0      n                         o
                                                                            qP =                       ~                                                                                      (9)
                                                                              j            max qP +d , lv                        ,     otherwise
                                                                                                       j−1         ~aj      j
                                   where the max denotes the component-wise maximum function of two vectors. A forward path
                                   ~
                                   P is feasible if it respects
                                        • the resource consumption bounds:
                                                                                                 ~
                                                                                                 P                                        ~
                                                                                               qj ≤ uv ,           ∀j ∈ {0,...,|P|};                                                        (10)
                                                                                                            j
                                        • and ng-path neighborhoods:
                                                                                                             ~
                                                          ∀(i,j) ∈ {(i,j) : 0 ≤ i < j ≤ |P|, v = v = v}                                     ∃h: i < h < j, v 6∈ N                   .       (11)
                                                                                                                     i       j                                                  v
                                                                                                                                                                                  h
                                                                                                                                          ~
                                   Condition (11) can be rewritten in the following way. Let FP be the set of vertices defined as
                                                                                                                                         j
                                      ~                     ~           ~                                                                                                                     ~
                                      P                    P           P                                                       ~                                                              P
                                   F =∅andF =(F                              ∩N )∪{v }for all 1 ≤ j ≤ |P|. Then (11) is equivalent to v 6∈ F
                                     0                     j           j−1          vj          j                                                                                   j        j−1
                                                                             ~
                                                             ~              P                                                                             ~
                                   for all 1 ≤ j ≤ |P|. Let c¯ (π,µ,ν,σ) be the total reduced cost of path P:
                                                                  ~                        X                       X
                                                                  P                                                                   `         `    ` ~
                                                                c¯  (π,µ,ν,σ) =                  c¯ (π,ν) −              σ ·α(C ,AM ,p ,P)−µ.
                                                                                                   ~a                      `
                                                                                               ~                   `∈L
                                                                                          ~a∈P
                                                                                                                  7
                                                 ~
                                  Let also P be the set of all feasible forward paths. The pricing subproblem then can be refor-
                                                                                                                                                                 ~
                                                                                   ~                                                                            P
                                  mulated as finding a path in P minimizing the total reduced cost: min~ ~ c¯ (π,µ,ν,σ). In the
                                                                                                                             P                         P∈P
                                  remainder of this section, we use simplified notations c¯                                       and c¯ as the dual solution (π,µ,ν,σ)
                                                                                                                                          a
                                  is fixed.
                                                                                                       ~            ~                                                             ~
                                        Wenowdefine the backward graph G = (V,A) with source n+1 and sink 0. Set A contains
                                                                           0                                                       0       ~
                                  one backward arc a~ = (v ,v) for each forward arc ~a = (v,v ) ∈ A. Each backward arc a ~ has the
                                  same reduced cost c¯ = c¯ and same resource consumption d = d as the corresponding forward
                                                                   a~      ~a                                                        a~       ~a
                                  arc.
                                                                        ~                         ~                                                 ~
                                        AbackwardpathP isdenotedbyP =(a~ ,a~ ,...,a~                                            ) in graph G, a ~         =(v          , v ), v     =n+1,
                                                                                                          1    2               ~                       j         j−1      j      0
                                                                                                                           |P|                              ~
                                  v ~    =0, possibly containing cycles, where we may add the superscript P if necessary as in the
                                    |P|                                                                                          ~        |R|
                                  forward graph. The accumulated consumption vector qP ∈ IR                                                     in P ~   is calculated recursively
                                                                                                                               j
                                  as                                                (
                                                                                         u       ,                                   if j = 0;
                                                                               ~           n+1
                                                                           qP =                 n P~                       o
                                                                            j            min q            −d , uv              ,     otherwise.
                                                                                                                a~        j
                                                                                                    j−1           j
                                  where the min denotes the component-wise minimum function of two vectors. Feasibility condi-
                                  tions for a backward path P ~ are the same as for a forward path except that (10) is replaced by
                                    P~                                                ~                                ~
                                  q     ≥l , for all j ∈ {0,...,|P|}. We denote as P the set of all feasible backward paths. Sets
                                             v
                                    j          j
                                     P~                     ~
                                  Fj , 0 ≤ j ≤ |P|, are defined in the same way as for a forward path.
                                                                                                   ~                     ~
                                        It is easy to see that a forward path P belongs to P if and only if the corresponding backward
                                              ~                      ~             ~            ~                  0                                0                       ~
                                  path P belongs to P, where |P| = |P|, ~a = (v,v ) and a ~                                                  =(v,v), 1 ≤ j ≤ |P|. Also, we
                                                                                                     j                          |P|+1−j
                                             ~           ~
                                             P        P                             ~
                                  have qj ≤ q ~                for 0 ≤ j ≤ |P|. An example of a pair of forward and backward paths together
                                                      |P|−j
                                  with their consumption of one resource is given in Figure 1. Moreover, the total reduced costs
                                          ~        ~
                                  of P and P are equal, as coefficients α(C,AM,p,P) do not change if we traverse path P in the
                                  backward order in function α. Therefore the pricing problem defined in Section 2.3 can be also
                                  reformulated as finding a path in P~ minimizing the total reduced cost.
                                                                                    vP~     vP~      vP~     vP~      vP~      vP~     vP~
                                                                                     6        5        4       3        2        1       0
                                                                               qP                                                            u
                                                                                 j,1                                                           v
                                                                                                                                             l
                                                                                                                                              v
                                                                             ~                                                                 ~
                                                                          P( )                                                                P( )
                                                                                      ~        ~       ~        ~       ~        ~        ~
                                                                            0 = vP          vP       vP      vP       vP       vP      vP =n+1
                                                                                     0        1        2       3        4        5       6
                                  Figure 1: An example of a forward and the corresponding backward paths in the case of one
                                  resource
                                                                                         ~                                                    ~
                                        From now on, we use accent ◦ for a forward entity, accent ◦ for a backward entity, and no
                                  accent for an entity which can be both forward or backward (when it is applied). We also use
                                              ~ ~
                                  accent ◦◦ for an entity of the opposite sense.
                                                                                                                8
                                   3.2        Labels and Dominance Rule
                                                                                                                                                                                    L L L L L
                                   WedevisealabelingalgorithmforthepreviouslydefinedSPPRCwhereeachlabelL = (c¯ ,vP,q ,F ,S )
                                   corresponds to a partial forward or backward path P (partial means that we may have v                                                                        6∈
                                                                    L        P       L        P        L        P         L          P                L          |L|                      |P|
                                   {0,n+1}), where c¯ = c¯ , v                          =v ,q =q ,F =F ,andS ∈IR givesthecurrent
                                                                                              |P|               |P|                  |P|
                                   state (computed as in Function α) of each cut ` ∈ L for label L.
                                                                                                         0                0                0                                                    0
                                                                                       0      L        L       L        L      L         L                                          L         L
                                        Alabel L dominates label L if v                          =v ,q ≤q (q ≥q forbackwardlabels),F ⊆F ,
                                   and                                                                      X
                                                                                                                                      0
                                                                                               L                                    L
                                                                                             c¯   −                      σ ≤c¯ ,                                                            (12)
                                                                                                                            `
                                                                                                                       0
                                                                                                      `∈L: SL>SL
                                                                                                               `     `
                                                                                                                       L        L0
                                   as σ` ≤ 0, ` ∈ L (Jepsen et al. 2008). Condition c¯ > c¯                                          is sufficient to verify that L does not
                                   dominate L0.
                                   3.3        Bucket Graph
                                   A critical aspect of labeling algorithms that solve the previously described SPPRC is when to
                                   performdominancechecks. Givenasetoflabelsthatpotentiallydominateeachother, dominance
                                   checks may be performed for all pairs of labels. However, it can be prohibitively time consuming.
                                   Alternatively, skipping too many dominance checks may cause a premature explosion on the
                                   number of maintained labels. One approach to address this issue is to partition the labels into
                                   buckets and to ensure that no pair of labels inside a bucket dominate each other. Pecin et al.
                                   (2017b) followed this approach by defining buckets for every possible resource consumption of
                                   labels and skipping inter-bucket dominance checks. In this paper we define buckets differently
                                   in order to avoid resource discretisation. Also, we perform inter-bucket dominance checks, but
                                   less frequently.
                                        In the proposed labeling algorithm, labels are grouped into buckets based on their final
                                   vertices and on ranges defined for both accumulated resource consumption values. Moreover,
                                   we define bucket arcs connecting pairs of buckets through which the labels can be extended.
                                   Different bucket graphs are then defined for forward and backward labeling. Bucket graphs are
                                   useful because they help to determine an efficient order of treatment for the buckets. If the
                                   bucket graph is acyclic, it is desirable to process the buckets in its topological order because
                                   no further extension from a bucket is necessary after it has been processed.                                                             If the bucket
                                   graph contains cycles, then buckets are handled in the topological order of the graph’s strongly
                                   connected components, trying to minimize such reprocessing. Additionally, the bucket graph is
                                   used to avoid label extensions that are proved not to contribute to a solution that improves the
                                   current best one. This is achieved by removing arcs from the bucket graph based on a reduced
                                   cost argument. In what follows, we present all the notation required to formalize these ideas.
                                                                                                                                                                                         ˜
                                        The set of buckets associated to a given vertex v ∈ V is determined by a step size d for
                                                                                                                                                                                           r
                                   each resource r ∈ R. Let K be the set of all |R|-dimensional integer vectors such that the r-th
                                                                                v
                                                                                                                   ˜                                                   ~
                                   component belongs to {0,1,...,b(u                                −l        )/d c}, r ∈ R. A forward bucket b is defined by a
                                                                                              v, r       v, r       r
                                                                                                          ˜                             ˜
                                   pair of vertex and lower bound vector (v˜ ,l ) = (v,l + κ  d), v ∈ V , κ ∈ K . A forward label
                                                                                                       ~ ~                v                                         v
                                                                                                       b   b
                                                                                                  ~                             ~
                                   ~                                                      ~       L                   ˜        L       ˜      ˜
                                   Lis contained in forward bucket b if v                             =v˜ and l ≤ q <l +d. Similarly, a backward bucket
                                                                                                           ~           ~                ~
                                                                                                            b          b                b
                                     ~                                                                                                                               ˜
                                  b is defined by a pair of vertex and upper bound vector (v˜ ,u˜ ) = (v,u −κd), v ∈ V, κ ∈ K .
                                                                                                                                   b ~  b ~            v                                        v
                                                                     ~                                                         ~     L~                            L~               ˜           L
                                   Abackward label L is contained in backward bucket b if v = v˜ ~ and u˜ ~ ≥ q                                                        >u˜ ~ − d. Let b
                                                                                                                                              b            b                 b
                                   be the bucket containing label L.
                                                                                                              b                                                         ˜                        ˜
                                        For a forward (backward) bucket b, let κ be the vector κ ∈ K                                                   such that l = l                +κd
                                                                                                                                                   v˜                    b        v˜
                                                                                                                                                    b                              b
                                                               ˜                                        0
                                   (u˜   =u −κd). Wesaythat bucket b is component-wise smaller than bucket b (denoted as
                                      b        v˜
                                                 b                                                                              0
                                    0                                                                    0                     b         b
                                   b ≺b) if buckets are of the same sense, v˜                               =v˜ , and κ            ≤κ.
                                                                                                        b        b
                                                ~       ~                                                                                                    ~       ~
                                        Let B (B) be the set of all forward (backward) buckets. We define as Γ (Γ) the following set
                                   of directed forward (backward) bucket arcs.
                                                                                                                  9
                                            Each forward/backward bucket arc γ ∈ Γ is defined by a pair (b ,a ) of bucket and arc of the
                                                                                                                                                               γ     γ
                                      corresponding sense, b ∈ B, a ∈ A, and v˜                                            is the tail of a . The tail of a forward/backward
                                                                               γ              γ                       bγ                             γ
                                                                                               ~                           ˜                          0                 0
                                      bucket arc γ is bucket b . Set Γ contains ~γ if l                                          +d ≤u ,where v is the head of ~a . The
                                                                                  γ                                         ~          ~a           v                                                   ~γ
                                                                                                                             b           ~γ
                                                                                                                              ~γ
                                                                                                     ~                            head                               ~0        ~                                   0
                                      head of a forward bucket arc ~γ ∈ Γ, denoted by b                                                  , is the bucket b ∈ B such that v˜ 0 = v
                                                                                                                                  ~γ                                                                    ~
                                                                                        	                                                                                                              b
                                              ˜                   ˜                    0         ˜         ˜              ~                                                 0                 0
                                      and l 0 ≤ max l                   +d ,l               <l 0 +d. Set Γ contains γ ~ if u˜                            −d ≥l ,where v is the head
                                               ~                   ~          ~a      v           ~                                                    ~       a~         v
                                               b                    b           ~γ                b                                                  b           γ~
                                                                     ~γ                                                                               γ~
                                                                                                                                                   head                                0~         ~
                                      of a ~   .   The head of a backward bucket arc γ,~                                   denoted by b                   , is the bucket b ∈ B such that
                                             γ~                                                         	                                        γ~
                                                  0                                                     0                   ˜           ~         ~ ~                   ~         ~    ~
                                      v˜ 0 = v and u˜ 0 ≥ min u˜                        −d ,u                >u˜ 0 −d. Let B = (B,Γ) and B = (B,Γ) be the directed
                                          ~                      ~                    ~       a~      v               ~
                                        b                      b                    b           γ~                  b
                                                                                     γ~
                                      forward and backward bucket graphs, respectively.
                                            For each forward/backward bucket b ∈ B, we define the set Φb of “adjacent” component-wise
                                      smaller buckets:
                                                                        n 0           0                 0             b0         b              b0         b                         0  o
                                                              Φ = b : v˜ =v˜ , ∃r ∈ R,κ 0 = κ 0 −1, κ = κ , ∀r ∈ R\{r } .
                                                                 b                  b          b                      r          r              r          r
                                                                                                                                                 0                          0                           Φ       Φ
                                                                                                                                                                                                     ~           ~
                                      As |R| = 2, we have |Φb| ≤ 2. By definition, we have b ≺ b for all b ∈ Φb. Let Γ                                                                                       (Γ )
                                                                                                                                                 0                                           0
                                      be the set of directed forward (backward) bucket arcs (b ,b) such that b ∈ B, b ∈ Φb. Let
                                       ~                               Φ                                                                                                                  head
                                         Φ         ~        ~       ~                                                                                                ~                                         ~
                                      B =(B,φ(Γ)∪Γ )betheextended forward bucket graph, where φ(Γ) = {(b ,b                                                                                      ) : ~γ ∈ Γ}.
                                                                                                                                                                                    ~γ    ~γ
                                                                    ~
                                                                  Φ                                Φ
                                                                                 ~        ~        ~
                                      Analogously, B                  = (B,φ(Γ) ∪ Γ ) is the extended backward bucket graph. Those extended
                                      graphs are not used in the core of the labeling algorithm, they are needed only in the initialization
                                      to compute their sets of strongly connected components and appropriate topological orders for
                                      them. Let Cb be the strongly connected component of a forward/backward bucket b.
                                            Forward/backward label L, obtained by extension from label L0 along a bucket arc γ with
                                                     0
                                      bγ = bL , is not necessary contained in bucket bhead. For forward labels, this happens when
                                                                                                                                 γ
                                        L0                      ˜                ˜
                                      q      +d            ≥lhead +d , for some r ∈ R. The backward case is analogous. So, we may have
                                        r          aγ,r          bγ     ,r         r
                                        head           L
                                      bγ        ≺ b . Even in this case, we still consider that such an extension has been made along
                                                                                                                                                                         0
                                                                                    Φ                                                                                 L            L
                                      γ. The bucket arcs in Γ                           ensure that there is always a path from b                                           to b       in the extended
                                      forward bucket graph. Therefore, C L cannot be before C 0 in the topological order of strongly
                                                                                                       b                                      bL
                                                                                        Φ
                                      connected components in Γ .
                                                                                                          v = 1                           v = 3
                                                                source                                                                                                             sink
                                                                                                          v = 2                           v = 4
                                                                                        Figure 2: An example of Forward Graph
                                            Figure 3 shows a small extended bucket graph that corresponds to the forward graph depicted
                                      in Figure 2. In this figure, each rectangle represents the space of possible resource consumption
                                      vectors for partial paths finishing in a corresponding vertex. The consumptions of the first
                                      and second resource determine the shifts in the horizontal and vertical directions, respectively.
                                      Thus, each square is associated with two ranges for the consumptions of both resources whose
                                      dimensions are determined by the bucket steps. Each node of the extended bucket graph is
                                                                                                                                                                              ~           ~Φ
                                      depicted inside the corresponding square. The bucket arcs that belong to Γ and Γ                                                                           correspond
                                      to arrows between rectangles and between squares of the same rectangle, respectively. Finally,
                                      an example of a strongly connected component of this extended bucket graph is bold printed in
                                      the figure.
                                                                                                                           10
                                                  ˜
                               bucket             d1     v = 1                             v = 3
                                steps
                                           ˜
                                           d
                                            2
                              source                                                                                 sink
                                         u               v = 2                             v = 4
                                          2,2
                                       r = 2
                                          l2,2
                                                         r = 1        u
                                             l2,1                      2,1
                             Figure 3: An example of Extended Bucket Graph for the forward graph of Figure 2
                       3.4     Mono-directional labeling algorithm
                       Inthissubsection, wedescribethemono-directionallabelingalgorithm, whichcanberunineither
                       forward or backward sense to solve the pricing problem. An auxiliary function Extend(L0,γ,L)
                                                             0
                       presented below extends a label L to label L along a bucket arc γ ∈ Γ. It returns false if this
                       extension is not possible. One can easily see that the steps performed by this function initialize
                       the reduced cost and the final vertex of the new label, calculate its resource consumptions and
                       check their bounds, obtain its ng-route information and check its feasibility, and finally update
                       its reduced cost considering the active R1Cs.
                                                                                                                            best
                           ThelabelingalgorithmispresentedinAlgorithm1. Inthisalgorithm, wemaintainvaluesc¯
                                                                                                                            b
                       equal to the smallest reduced cost of labels L such that bL  b. It also uses the auxiliary function
                       DominatedInCompWiseSmallerBuckets(L,b,Bvisited) presented below, which checks whether a
                                                                                   0             0      0     visited
                       label L is dominated by a label contained in a bucket b such that b  b, b 6∈ B              . To avoid
                                                                                                             best
                       checking all component-wise smaller buckets, it assumes that the values of c¯              are updated
                                                                                                             b
                                                     L
                       (for all buckets preceding b     in the topological order) and uses it to prune the search. If the
                                                   0             best     L                                         0
                       search reaches a bucket b such that c¯ 0       >c¯ , one can conclude that no label in b or in the
                                                                 b
                       component-wise smaller buckets can dominate L, and this search branch can be pruned. This
                       function also receives the set Bvisited of visited buckets needed to avoid processing the same
                       bucket twice. For our case with one or two resources it is easy to do a specific implementation
                       to verify whether a bucket belongs to set Bvisited in a constant time. The same implementation
                       can be used in Functions ConcatenateLabel and UpdateBucketsSet described later.
                                                0            0
                           Twobucketsbandb suchthatb ∈ Φb maybelongtothesamestronglyconnectedcomponent.
                       This may happen, for example, when b and b0 are forward buckets and there is another forward
                                00        00      0                  ˜0      ˜00     ˜
                       bucket b with v˜      6=v˜ = v˜ such that l        <l      <l , for some r ∈ R. In that case, the
                                         b       b     b             b ,r    b ,r     b,r
                                                                                       0        00   00  0
                       extended bucket graph may contain the directed cycle ((b ,b),(b,b ),(b ,b )). Therefore values
                        best
                       c¯    for buckets in the same strongly connected component are calculated in a lexicographic
                        b
                                  b                  best                best
                       order of κ to ensure that c¯ 0     is set before c¯  .
                                                     b                   b
                                                                          11
                                         Function Extend(L0,γ,L)
                                                         0
                                             L         L                 L
                                            c¯   ←c¯ +c¯ , v ←the head of a
                                                                 aγ                                     γ
                                                          0
                                            qL ←qL
                                            if L is a forward label then
                                                  qL ←max{qL+d ,l }
                                                                                aγ     vL
                                                  if    qL > u           then return false
                                                                   vL
                                            if L is a backward label then
                                                  qL ←min{qL−d ,u }
                                                                               a         L
                                                                                 γ     v
                                                  if qL < l           then return false
                                                                 vL
                                                              0
                                            if vL ∈ FL then return false
                                                              0
                                            FL←(FL ∩N )∪{vL}
                                                                       vL
                                            for ` ∈ L do                                          0
                                                  if a ∈ AM` then SL ← SL
                                                        γ                            `          `
                                                  else SL ← 0
                                                             `
                                                  if vL ∈ C` then
                                                           L          L        `
                                                         S` ←S` +p L
                                                                               v
                                                         if SL ≥ 1 then
                                                               `
                                                                  L         L            L         L
                                                               S ←S −1,c¯ ←c¯ −σ
                                                                 `          `                                `
                                            return true
                                      3.5         Bi-directional labeling algorithm
                                                                                                                           ~              ~
                                      Wecall a pair of forward and backward labels L and L ω-compatible if
                                                                 ~           ~       ~                               ~        ~            ~                        ~          ~
                                                              vL 6= vL,            qL +d                    ≤qL, FL∩FL=∅, andc¯(PL||PL)<ω,
                                                                                                  ~      ~
                                                                                                  L L
                                                                                               (v ,v )
                                                     ~          ~                                                                                                            ~                  ~
                                      where PL||PL is the path obtained by concatenation of partial paths PL and PL along arc
                                         ~        ~                                                                  ~          ~
                                         L L              ~                                                          L       L
                                      (v ,v ) ∈ A, and its total reduced cost c¯(P ||P ) is calculated as
                                                                                          ~         ~        ~                             ~         X
                                                                                         L       L           L                           L
                                                                                   c¯(P     ||P ) = c¯ +c¯ ~                    ~  +c¯ −                        σ .
                                                                                                                         L L                                       `
                                                                                                                      (v ,v )
                                                                                                                                                   ~`∈L:~
                                                                                                                                                SL+SL≥1
                                                                                                                                                  `      `
                                                                                                                                                               ~            ~   ~                              ~
                                                                                                                          ~               ~                    L         L      L                           L
                                            For a pair of forward and backward labels L and L such that v                                                          6=v , c¯ +c¯ ~                   ~ +c¯ is
                                                                                                                                                                                             L L
                                                                                                                                                                                          (v ,v )
                                                                                        ~         ~
                                      a lower bound on value c¯(PL||PL).
                                            For the bi-directional labeling algorithm, we need to choose a resource r∗ ∈ R and a threshold
                                      value q∗ ∈ [l             ∗,u            ∗] for it. The bi-directional labeling algorithm is presented in Algorithm 2.
                                                           0,r        n+1,r
                                                                                                                                          ~   best       visited
                                                                                                                                   ~                      ~
                                      It uses the auxiliary procedure ConcatenateLabel(L,b,P                                                        , B             ), presented below, which
                                                                                                                       L~             L~          visited
                                                                                                 ~                      ~          ~    ~          ~                                                 ~       ~
                                      tries to find a backward label L such that b                                           b, b         6∈ B               , and such that pair (L,L) is
                                          best                                                                                           ~                 ~                     ~        ~
                                       P                                                                                                 L              L                        L L
                                      c¯        -compatible, i.e. concatenation of partial paths P                                           and P along arc (v ,v ) improves on
                                         best                                  best
                                      P        .  We use values c¯                     as bounds to prune the search. From the reasoning of the previous
                                                                 ~                                            best
                                                                 L                           best          P
                                      paragraph, if c¯ + c¯ ~                          +c¯           ≥ c¯            then such a label does not exist. All buckets that
                                                                           (vL,v˜ )            ~
                                                                                  b ~        b
                                                                                        ~                                     best                                                                    best
                                      may contain extensions for L that improve on P                                                 are tried. In the literature, values c¯ ~                               are
                                                                                                                                                                                                      b
                                      referred as completion bounds (Christofides, Mingozzi, and Toth 1981).
                                      3.6         Symmetric case
                                      In this section, we suppose that 1) all time windows are the same; and 2) R1Cs arc memories
                                      are symmetric: (v,v0) ∈ AM` if and only if (v0,v) ∈ AM` for all ` ∈ L. We now show that in
                                      this case the forward/backward route symmetry can be exploited.
                                                                                                                          12
                                   Algorithm 1: Mono-directional labeling algorithm
                                     if forward algorithm then Linit ← (0,0,l ,∅,0)
                                                                                                 0
                                     if backward algorithm then Linit ← (0,n+1,u                               , ∅, 0)
                                                                                                          n+1
                                                                                              init
                                                                  init                       L                       init
                                     insert initial label L             to its bucket b             and mark L             as non-extended
                                     foreach strongly connected component C in BΦ in a topological order do
                                           repeat
                                                foreach bucket b ∈ C do                         0    L0
                                                      foreach non-extended label L : b                   =bdo
                                                                                                                                       0
                                                                                                                                  0  L
                                                           if not DominatedInCompWiseSmallerBuckets(L ,b ,∅) then
                                                                                                                               0
                                                                 foreach bucket arc γ ∈ Γ such that b = bL do
                                                                                                                      γ
                                                                                        0
                                                                      if Extend(L ,γ,L) then
                                                                            if L is not dominated by a label in bL then
                                                                                 mark L as non-extended and insert in bL
                                                                                 remove labels dominated by L from bL
                                                           mark L0 as extended
                                           until all labels in all buckets b ∈ C are extended                      b
                                           foreach bucket b ∈ C in a lexicographic order of κ do
                                                  best                               L           0        best 	
                                                c¯      ←min min              L    {c¯ },min            {c¯ 0   }
                                                  b                      L: b =b                b ∈Φb      b
                                                    best                             L               0
                                     return P            =argminPL:vL=v0 c¯ , where v is the sink in G
                                   Function DominatedInCompWiseSmallerBuckets(L,b,Bvisited)
                                     Bvisited ← Bvisited ∪ {b}
                                                                                                                  L       best
                                     if C precedes C L in the topological order used and c¯ < c¯                                then return false
                                           b                b                                                             b
                                     if b 6= bL and L is dominated by a label in bucket b then return true
                                     for b0 ∈ Φb \ Bvisited do
                                           if DominatedInCompWiseSmallerBuckets(L,b0,Bvisited) then return true
                                     return false
                                     First, we redefine the resource consumption of arcs. We make the capacity resource consump-
                                                                0      ~                1          1    0
                                tion of each arc (v,v ) ∈ A equal to 2wv + 2wv , and we make the time resource consumption of
                                this arc equal to 1s + t                   0  +1s 0. Thus, the cost and the resource consumption of two arcs
                                                           2 v        (v,v )      2 v
                                (v,v0) and (v0,v), v,v0 ∈ V , become the same. Moreover, as for any route P coefficients xP 0
                                                                                                                                                                             (v,v )
                                and xP           are the same in constraints (2) and cuts (5), reduced costs of these arcs are the same:
                                         (v0,v)
                                                                                     c¯    0  =c¯ 0        ,    ∀v,v0 ∈ V.                                                    (13)
                                                                                      (v,v )        (v ,v)
                                                                                                                                                                L~
                                                                                           ~                                                            ~        ~           ~
                                     Consider now a backward label L and the corresponding partial path P = P . Let P be
                                                                                         ~          ~
                                                                                         P        P                     ~         ~
                                the partial forward path such that v                        =v , 1 ≤ j ≤ |P|, and L be the forward label such that
                                                                                         j        j
                                   ~
                                 ~L        ~
                                P =P. From (13) and from the fact that the R1Cs arc memories are symmetric, we have
                                  ~         ~    ~           ~           ~          ~
                                  L       L      L         L             L        L
                                c¯   =c¯ , F        =F ,and S =S . As time windows are the same, resource bounds are also the
                                                                                                   ~                     ~
                                same: [l ,u ] = [l,u] for all v ∈ V . Then, qL −l = u−qL. Moreover, for every backward bucket
                                            v     v
                                                                                                                                                     ~          ~
                                  ~                                                               ~                  ˜                                b       b
                                b, there exists a symmetric forward bucket b such that l −l = u−u˜ and κ = κ .
                                                                                                                      ~                     ~
                                                                                                                      b                   b
                                     In this case (which we call symmetric), in the bi-directional labeling algorithm, we set q∗ =
                                 1l    ∗ +1u            ∗, skip the backward labeling step, and use symmetric forward buckets and labels
                                 2 0,r       2 n+1,r
                                instead of backward buckets and labels in the concatenation step.
                                                                                                        13
                                 Algorithm 2: Bi-directional labeling algorithm
                                                                                                           ~
                                                                                                      ~    L       ∗
                                   run forward labeling algorithm where only labels L, q ∗ ≤ q are kept
                                                                                                           r
                                                                                                           ~ L~       ∗
                                   run backward labeling algorithm where only labels L, q ∗ > q , are kept
                                                                                                             r
                                   let Pbest be the best complete path obtained in the two algorithms above
                                                                 ~
                                   foreach forward label L do
                                                                                                 ~
                                                                        ~               ~      ~L
                                        foreach bucket arc ~γ ∈ Γ such that b = b                   do
                                                                                          ~γ
                                                                                ~0
                                                            ~     ~0            L       ∗
                                             if Extend(L,~γ,L ) and q ∗ > q then
                                                                                r
                                                                                                         ~0
                                                         ~     ~                                         L             ˜
                                                  let b ∈ B be the bucket such that u˜ ~ ≥ q                >u˜ ~ − d
                                                                                                  b              b
                                                                            ~    ~  best
                                                  ConcatenateLabel(L,b,P                 , ∅)
                                   return Pbest
                                                                                    ~  best     visited
                                                                              ~                  ~
                                 Procedure ConcatenateLabel(L,b,P                           , B          )
                                     visited         visited       ~
                                   B~         ←B~            ∪{b}
                                                            best      Pbest
                                   if c¯  +c¯ ~         +c¯      ≥c¯         then return
                                        ~        L            ~
                                        L      (v ,v˜ )     b
                                                     b~
                                   foreach label L~ : b ~ = b ~ do
                                                            L
                                                   ~     ~     Pbest
                                        if pair (L,L) is c¯           -compatible then
                                                                        ~      ~      

                                             Pbest ← P , ~a = (vL,vL), P
                                                            ~                          ~
                                                            L                        L
                                                0~            visited
                                   foreach b ∈ Φ ~ \B~                 do
                                                       b
                                                                      0~   best    visited
                                                                  ~                 ~
                                        ConcatenateLabel(L,b ,P                , B         )
                                   return
                              4       Bucket arc elimination
                              Arc elimination procedure by Irnich et al. (2010) can be employed to remove arcs from the
                              original graph using the argument that any path using one of these arcs is not contributing to
                              an optimal solution. In this section, we generalize this procedure to eliminate bucket arcs from
                              the bucket graph using the same argument. However, this generalization is not straightforward
                              because of the dominance between labels. Even labels from the same bucket may use different
                              bucket arcs when extended through the same path in the original graph. Hence, the same path
                              extension may be feasible for the dominated label and not feasible for the dominating label due
                              to removal of some bucket arcs. We introduce below the new concept of jump bucket arcs to
                              bring back compatibility between bucket arc elimination and dominance.
                                   We call a path P ∈ Ωm, m ∈ M, improving if λP participates in an integer solution of the
                              original problem (SPF) with a cost smaller than the cost of the best solution found so far. We
                              denote the latter cost as UB, as it is an upper bound on the optimal solution value of (SPF).
                              Let ΩI be the set of improving paths in Ωm. We can exclude paths proved to be non-improving
                                      m
                              from the solution space of the pricing problem. Note that if there are no improving paths (i.e.,
                              the best known solution is optimal) any path can be correctly excluded, so we only need to be
                              careful in the case where some ΩI sets are not empty. So, we assume that case in the remainder
                                                                             m
                              of the section.
                                   Suppose that some variables λP, P 6∈ ΩI , are fixed to zero in (SPF). Let (π¯,µ,¯ ν¯,σ¯) be the
                                                                                             m
                              dual solution of the current restricted linear relaxation of (SPF), corresponding to constraints
                              (2), (3) and to constraints of type (5) and (7). Let z(RSPF)(π¯,µ,¯ ν¯,σ¯) be the value of this solution.
                              The value
                                                      Lagr        (RSPF)                       X                          P                
                                                 LB         =z             (π¯, µ,¯ ν¯, σ¯) +        min 0, min c¯ (π¯,µ,¯ ν¯,σ¯)              · U
                                                                                                                      I                            m
                                                                                              m∈M                P∈Ωm
                              is a Lagrangian lower bound on the optimal solution value of (SPF). It is obtained by dualizing
                              constraints (2), (5) and (7) with multipliers π¯, ν¯, and σ¯. For any vector (z1,z2,...,z|M|) such
                                                                                                  14
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    that
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               m                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     P
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        z                                                                                                                                                                       ≤ min c¯ (π¯,µ,¯ ν¯,σ¯),                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      m∈M,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                (14)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  P∈ΩI
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            m
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    we have                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       X
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     LB=z(RSPF)(π¯,µ,¯ ν¯,σ¯) +                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    min{0,zm}·U ≤LBLagr.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           (15)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            m
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                m∈M
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Thus, LB is a valid lower bound on the optimum solution of (SPF). If an algorithm for solving
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          m                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 m
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    pricing sub-problem (PSP ) returns value z                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         satisfying condition (14), we say that this algo-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    rithm satisfies (14). Such an algorithm can be used to calculate a valid lower bound for (SPF)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         m
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    even if it does not necessarily solve (PSP ) to optimality. In the remainder of this section, we
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    again drop index m and consider dual solution (π¯,µ,¯ ν¯,σ¯) fixed for more clarity.
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      We say that a feasible forward/backward path P ∈ P passes through bucket arc γ ∈ Γ if
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                P                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ˜                                                                                                                                                                                                                                                                                                                                 P                                                                                                                                                                                                                                                                                                       ˜                                                                                                                                                                                                                                                                                 ˜
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    there is an index j, 1 ≤ j ≤ |P|, such that a                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     =a , and l                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       ≤q                                                                                                                                                                                                                                                                                                                                                           <l +dforaforward path
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                j                                                                                                                                                                                                                                                                                γ                                                                                                                                                                                                                                                                                                                                                                          bγ                                                                                                                                                                                                                                                                                           j−1                                                                                                                                                                                                                                                                                                                                          bγ
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             P                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ˜                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 P
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    (u˜                                                                                                                                                                                                                                ≥q                                                                                                                                                                                                                                                                                                                                                          >u˜                                                                                                                                                                                                                                                                                                  −dfor a backward path). We denote such a bucket arc as γ .
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            bγ                                                                                                                                                                                                                                                                                           j−1                                                                                                                                                                                                                                                                                                                                                                       bγ                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              j
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      We call a forward/backward γ ∈ Γ an improving bucket arc if there exists an improving
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    path of the same sense passing through it. The bucket arc elimination procedure described
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    in Section 4.2 reduces the current set Γ by removing some non-improving bucket arcs from it.
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    However, the labeling algorithm proposed in Section 3, in which labels are only extended over a
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    reduced set Γ of bucket arcs does not necessarily satisfy condition (14).
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Figure 4 illustrates a case where the value z of the best solution found by the labeling
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    algorithm does not satisfy (14). In this figure, the value of a single resource consumption r = 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    for each partial path is represented by the level of its end node in the vertical axis. P and P0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    are improving and non-improving forward paths, respectively. Thus, for each traversed arc, the
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    corresponding bucket arc that is passed through depends solely on the total resource consumed
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    up to this point. Paths P and P0 traverse different arcs until vertex vP                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  =vP0 andfinish with
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             i−1                                                                                                                                                                                                                                                                                                                                                                                  0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    i −1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    the same subpaths from this point until the sink vertex (but with such subpaths passing through
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    different bucket arcs).
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Assume that the reduced bucket graph does not contain the non-improving bucket arc γ
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    corresponding to (vP0 ,vP0). Suppose also that P0 has a reduced cost smaller than that of P,
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                    0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    i −1                                                                                                                                                                                                                                                                                i                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    0                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     P0                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            ¯
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    allowing the label L associated to P until vertex v 0                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 to dominate the label L associated to
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               i −1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    P until the same vertex. The reasoning for such domination is that one can always replace the
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 ¯                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    partial path of L by that of L, causing that P is replaced by P which has a smaller reduced cost.
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    However, absence of bucket arc γ in the reduced bucket graph prevents P0 from being found by
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    the labeling algorithm. Thus, neither P nor P0 are obtained by the labeling algorithm, and the
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    value z found by the algorithm may violate condition (14).
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                qP                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    P                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          P                                                                                                                                                                                                                                                                                             P
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     vi−1                                                                                                                                                                                                                                                                                                                   vP                                                                                                                                                                                                                                                  vi+1                                                                                                                                                                                                                                                                                          v|P|
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         i
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   ˜
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    l4,1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        ¯                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 00
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              L                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    P
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   ˜
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    l                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   00
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               3,1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 P                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            buc                                                              jump                                                                                                                     L
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   k
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    et
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   ˜                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  arc
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    l2,1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           P0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           domination
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   ˜                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         P0                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           L0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    l1,1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   L 6∈Γ
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   ˜
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    l0,1 s                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           0                                                                                                                                                                                                                                                                                                                     0                                                                                                                                                                                                                                                   0                                                                                                                                                                                                                                                                                             0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        vP                                                                                                                                                                                                                                                                                                                    vP                                                                                                                                                                                                                                                  vP                                                                                                                                                                                                                                                                                            vP
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 0                                                                                                                                                                                                                                                                                                                      0                                                                                                                                                                                                                                                   0                                                                                                                                                                                                                                                                                                                                                      0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    i −1                                                                                                                                                                                                                                                                                                                   i                                                                                                                                                                                                                                                   i +1                                                                                                                                                                                                                                                                                          |P |
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          Figure 4: Illustration of the proof of Proposition 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      The remainder of this section is divided in two parts. In Section 4.1, we show how to modify
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    our labeling algorithm so that it satisfies condition (14) when executed over a superset of all
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             15
                       improving bucket arcs. In Section 4.2, we present a procedure for finding non-improving bucket
                       arcs, and show the correcteness of its combination with the modified labeling algorithm.
                       4.1    Modified labeling algorithm
                       Toguaranteethefulfillmentofcondition(14), labelsinourforward(backward)labelingalgorithm
                                                                                       ~     ~
                       should not only be extended along the current reduced set Γ (Γ) of bucket arcs, but also along
                                ~     ~
                       the set Ψ (Ψ) of jump bucket arcs obtained as shown below. Jump bucket arcs impose an
                       additional resource consumption when traversed. Each forward/backward jump bucket arc ψ ∈
                                                         base  jump                base                      jump
                       Ψis characterized by a triple (b      , b    , a ), where b      is its base bucket, b     is its jump
                                                         ψ     ψ      ψ            ψ                         ψ
                                                                   base     jump                    0
                       bucket such that v˜ base = v˜ jump = v˜, b       ≺ b      , and a    = (v˜,v ) ∈ A is its arc of the
                                            bψ       b             ψ        ψ            ψ
                                                      ψ
                       corresponding sense. In the labeling algorithm, each label L should be extended along a jump
                                             L     base                           0
                       bucket arc ψ ∈ Ψ if b   =b     . Whenextendinglabel L along ψ ∈ Ψ, we first do the “jump”, i.e.
                                                   ψ                                                                        	
                                                                                            0                        0
                                                                 0                   L     L           L            L ˜jump
                       in the second line of function Extend(L ,ψ,L), instead of q     ←q ,wedoq ←max q ,l
                                              	                                                                        bψ
                                       0
                       (qL ← min qL ,u˜ jump     for a backward label). Function ObtainJumpBucketArcs(Γ) presented
                                          bψ
                       below obtains the current set Ψ of jump bucket arcs given the current reduced set Γ of bucket
                       arcs. This function can be used for both forward and backward sense.
                        Function ObtainJumpBucketArcs(Γ)
                          Ψ←∅
                          foreach bucket b ∈ B do
                              foreach a = (v,v0) ∈ A such that v = v˜ do
                                                                      b
                                  if 6 ∃γ ∈ Γ such that bγ = b, aγ = a then
                                      ¯      0                      0
                                      B←{b b: ∃γ∈Γ: bγ =b,aγ =a}
                                                    ¯
                                      remove from B all buckets which are not component-wise minimal
                                                0   ¯
                                      foreach b ∈ B do          base      jump    0
                                          Ψ←Ψ∪{ψ},whereb            =b, b      =b,a =a
                                                                ψ         ψ           ψ
                          return Ψ
                          Wedenote as LP the label corresponding to the partial path consisting of the first j arcs of
                                           j
                       path P. If P passes through γ, then there is an index j, 1 ≤ j ≤ |P|, such that label LP is
                                                                                                                          j
                                                     ~               ~
                       contained in bucket b . Let L(Γ,Ψ) and L(Γ,Ψ) be the sets of non-dominated labels generated
                                              γ
                       by the modified forward and backward mono-directional labeling algorithms, in which each label
                       L is extended along all bucket arcs γ ∈ Γ such that bγ = bL and along all jump bucket arcs
                                          base    L
                       ψ∈Ψsuchthat b           =b .
                                          ψ
                          Thenext proposition is auxiliary but very important. It shows that for every improving path
                       P, the modified mono-directional labeling algorithm either generates P or a path dominating
                       P. Moreover, this is true for any prefix of P. This proposition applies for both forward and
                       backward sense. Its proof is illustrated in Figure 4.
                       Proposition 1. Let set Γ be a superset of all improving bucket arcs, and Ψ be the set of jump
                       bucket arcs computed using procedure ObtainJumpBucketArcs(Γ). Then, for each improving
                       path P ∈ P and for each index j, 0 ≤ j ≤ |P|, either LP ∈ L or there exists a label L ∈ L
                                                                                      j
                                     P
                       dominating L , where L = L(Γ,Ψ).
                                     j
                       Proof. Consider an improving path P ∈ P. We prove this proposition by induction on the value
                                                                                                                          init
                       of the index j, 0 ≤ j ≤ |P|. For j = 0 the proposition is true since there is a single label L
                                        init
                                       L                                   P
                       in the bucket b      that corresponds to vertex v0 . Now, assume that the proposition is true for
                       j = i−1, 1 ≤ i ≤ |P|. We must prove that it is also valid for j = i. By the inductive hypothesis,
                       either LP    ∈ L or there exists a label L ∈ L dominating LP . Let us use the notation L
                                i−1                                                        i−1                       P
                                                                     P                                        L     L
                       defined for the latter case to also denote Li−1 in the former case. In all cases, b       b i−1. Let
                                                                         16
                                                                                           P
                         0                                                    L          L                           P        0
                        γ and γ be the bucket arcs such that b 0 = b , b = b i−1, and a 0 = a = a . If γ ∈ Γ,
                                                                       γ           γ                   γ      γ      i
                                    0                                           0               P                           0
                        the label L obtained by extending L through aγ dominates Li . In this case, either L ∈ L or
                        L0 is dominated by some label from L, which should also dominate LP. In both situations, the
                                                                                                       i
                                                                  0                                        L
                        proof is finished. Otherwise, since γ 6∈ Γ, γ is an improving arc, and b               ≺b , there exists a
                                                                                                                  γ
                                                                                               jump        P
                                                                        P    base     L                  L
                        jump bucket arc ψ ∈ Ψ such that aψ = a , b                =b , and b         b i . Existence of such a
                                                                        i    ψ                 ψ
                        jumpbucketarcs is guaranteed by the definition of procedure ObtainJumpBucketArcs(Γ). Thus,
                                                                        00                    P                        00          00
                        extending L through aψ leads to a label L that dominates Li . As before, either L ∈ L or L
                        is dominated by some label from L, which dominates LP, finishing the proof.
                                                                                       i
                            Wehavejustshownessentiallythatthemodifiedmono-directionallabelingalgorithm satisfies
                        condition (14). In Proposition 3, we show that the same condition is satisfied by the modified bi-
                        directional labeling algorithm. First observe that any complete path can be divided into forward
                        and backward parts by removing any arc it passes through. Moreover, the total reduced cost of
                        the concatenation of these parts is equal to the reduced cost of the complete path.
                        Observation 1. For a pair of corresponding forward/backward path P and the opposite sense
                                                                                                  ~~
                                                                                        P         PP
                              ~~                                                                ~ ~
                        path PP and each value j, 0 ≤ j < |P|, pair of labels Lj and LL|P|−j−1 is ω-compatible for all
                              P
                        ω >c¯ .
                            Secondly, we will need the following auxiliary proposition.
                                                                                                  0        0
                                                                                                ~          ~
                        Proposition 2. Suppose that i) forward and backward labels L and L are ω-compatible, ii)
                                      0                           0                    0                           0
                               ~     ~           ~              ~                 ~    ~            ~              ~               ~
                        either L = L or label L dominates L , iii) either L = L or label L dominates L . Then labels L
                        and L~ are also ω-compatible.
                                                           0   0
                                             ~    ~      ~      ~
                        Proof. Let a = (vL,vL) = (vL ,vL ). From the definition of dominance in Section 3.2 and the
                                                                                                      0       0
                                                                                             ~       ~        ~       ~   ~
                        definition of ω-compatible labels in Section 3.5, we have vL = vL 6= vL = vL, qL + da ≤
                          0             0                                   0             0          0      0
                         ~              ~      ~                   ~       ~      ~       ~        ~        ~
                        qL +d ≤qL ≤qL. We also have FL ⊆ FL , FL ⊆ FL , and FL ∩FL = ∅. It follows then
                                a
                                ~       ~                                              ~      ~
                        that FL ∩FL = ∅. From (12) and the definition of c¯(PL||PL) it follows
                                                               X                  0     X                       0     X               X
                            ~      ~        ~            ~                       ~                              ~
                            L    L          L          L                         L                            L
                        c¯(P  ||P )   = c¯ +c¯ +c¯ −                  σ ≤ c¯ +                 σ    +c¯ + c¯ +              σ    −            σ
                                                  a                     `                       `      a                      `                `
                                                               `∈L:                     `∈L: 0                        `∈L: 0          `∈L:
                                                              ~    ~                    ~   ~                          ~   ~         ~     ~
                                                            SL+SL≥1                   SL>SL                         SL>SL          SL+SL≥1
                                                             `    `                     `   `                        `   `           `   `
                                                                                |      {z       }            |       {z      }
                                                                                ~                              ~
                                                                                L                  0          L                 0
                                                                                     ~           ~                  ~           ~
                                                                              ≥c¯ as L dominates L         ≥c¯  as L dominates L
                                             0           0       X                 X              X             X               X
                                            ~             ~
                                            L           L
                                      = c¯ +c¯ +c¯ −                     σ +               σ +           σ +          σ −               σ
                                                   a                       `                `             `             `                 `
                                                                 `∈L:              `∈L:           `∈L:          `∈L:            `∈L:
                                                                0    0                                 0             0
                                                               ~     ~           0    0           ~   ~          ~   ~         0    0
                                                               L    L           ~     ~           L   L         L   L         ~     ~
                                                              S +S ≥1          SL +SL ≥1,       S >S          S >S          SL +SL <1,
                                           |              {z   `    `     }     `    `            `   `         `   `        `     `
                                                                                 ~     ~                                       ~    ~
                                                                                SL+SL<1                                      SL+SL≥1
                                                          0   0
                                                        ~      ~                 `   `                                        `    `
                                                   =c¯(PL ||PL )<ω             |     {z     }   |                   {z                    }
                                                                                 ≤0 as σ≤0                       ≤0 as σ≤0
                                                       ~      ~
                                                       L    L                                       ~         ~
                            It follows then that c¯(P ||P ) < ω. Hence, all conditions for L and L to be ω-compatible
                        are met.
                                              ~    ~~    ~
                            We define as z(Γ,Γ,Ψ,Ψ) the reduced cost of the best path obtained by the modified bi-
                                                                                                                              ~
                        directional labeling algorithm in which forward labels are extended along bucket arcs in Γ and
                        ~                                                                    ~       ~
                        Ψ, and backward labels are extended along bucket arcs in Γ and Ψ.
                                                      ~         ~
                        Proposition 3. Let sets Γ and Γ be supersets of all improving forward and backward bucket
                                    ~          ~
                        arcs, and Ψ and Ψ be the sets of forward and backward jump bucket arcs computed using
                                                                                    ~
                                                                                    P                               ~      ~
                        procedure ObtainJumpBucketArcs(Γ). Then z ≤ c                  for any improving path P ∈ P, where
                               ~    ~~    ~
                        z = z(Γ,Γ,Ψ,Ψ).
                                                                             ~     ~                      ~
                        Proof. Consider an arbitrary improving path P ∈ P. Let j, 0 ≤ j ≤ |P| be the largest index
                                      ~
                                     ~P
                                     Lj     ∗                                                  ~             ~
                        such that qr∗ ≤ q . We divide the proof into two cases: j = |P| and j < |P|.
                                                                             17
                                                                               ~                      ~
                                                        ~           ~       ~P                        L                         ~
                                        For j = |P|, let L = L . We have v                               =n+1. As P is improving, by Proposition 1, either
                                                                              j
                                                                                                                                                ~0                              ~0
                                   ~      ~ ~ ~                                         ~0      ~ ~ ~                              ~            L                            ~L          ~
                                   L∈L(Γ,Ψ) or there is a label L ∈ L(Γ,Ψ) dominating L. As v                                                       =n+1,path P                     ∈P and
                                                                                ~0             ~                     ~
                                                                              ~L              P                     P
                                   the total reduced cost of P                       is ≤ c¯ , thus z ≤ c¯ .
                                                                                 ~                ~                                                                     ~
                                        Suppose now that j < |P|. Let P be the corresponding backward path for P. By Observa-
                                                                                        ~                        ~                                                          ~
                                                                               0        P             0       P                                                             P
                                                                             ~       ~                ~        ~                                                                                ~
                                   tion 1, the pair of labels L = Lj and L = L ~                                            is ω-compatible for all ω > c¯ . As both P
                                                                                                               |P|−j−1
                                              ~                                                                  ~0       ~ ~ ~                                               ~       ~ ~ ~
                                   and P are improving, by Proposition 1 either L ∈ L(Γ,Ψ) or there exists a label L ∈ L(Γ,Ψ)
                                                          0                                                        0         ~                                                        ~
                                                       ~                                                            ~            ~   ~                                           ~           ~    ~
                                   dominating L . Also, by Proposition 1 either L ∈ L(Γ,Ψ) or there exists a label L ∈ L(Γ,Ψ)
                                                          0
                                   dominating L~ . Thus, by Proposition 2 there exists a pair of ω-compatible labels generated by
                                                                                                              ~                    ~         ~       ~                     ~
                                                                                                             P                     L      L          P                     P
                                                                                                                                ~          ~
                                   the modified labeling algorithm for all ω > c¯ . Then c¯(P ||P ) ≤ c¯ , thus z ≤ c¯ .
                                        We have just shown that our labelling algorithm can be modified in order to satisfy condi-
                                   tion (14) by adding jump bucket arcs. Now it can be executed over any superset Γ of improving
                                   bucket arcs. In the next section, we show how we can find non-improving bucket arcs, which
                                   then can be safely removed from the current set Γ.
                                   4.2        Aprocedure for finding non-improving bucket arcs
                                                                                                                                                                  m
                                   In this paragraph, we temporarily consider again all subproblems (PSP ), m ∈ M.                                                                           Let
                                   (π¯, µ,¯ ν¯, σ¯) be the current dual solution of the restricted linear relaxation of (SPF) together
                                                                                                                                           m
                                   with constraints (5) and (7). Suppose that the current sets Γ , m ∈ M, include all improving
                                   buckets arcs, and the modified labelling algorithms have returned values zm for all m ∈ M.
                                   By Proposition 3, the modified labeling algorithm satisfies condition (14). Thus the value LB
                                   given by (15) is a valid lower bound for (SPF). A necessary condition for a path P ∈ Ωm to be
                                                                                  m          P
                                   improving is LB −min{0,z }+c¯ (π¯,µ,¯ ν¯,σ¯) < UB. We denote
                                                                                         θm =UB−LB+min{0,zm}.                                                                               (16)
                                   Then, a sufficient condition for a forward/backward path P ∈ Ωm to be non-improving is
                                    P                           m
                                   c¯  (π¯, µ,¯ ν¯, σ¯) ≥ θ        .   The next proposition gives a necessary condition for a bucket arc to be
                                   improving. The proposition applies for both forward and backward sense. In the following, we
                                   drop again index m.
                                                                                                                                               arr      arr
                                                                                                                                             ~ ~      ~ ~
                                        For a (jump) bucket arc γ ∈ Γ (ψ ∈ Ψ), we denote as bb                                                       (bb     ) its arrival bucket of
                                                                                                                                               γ        ψ
                                                                                                                                                                  arr
                                                                                                                            ~                                      ~
                                   the opposite sense. For a forward bucket arc ~γ ∈ Γ, its arrival bucket b                                                           is the backward
                                                                                                            	                                                   ~γ
                                                  ~                                     ˜                   0                  ˜                0
                                   bucket b such that u˜ ≥ max l                             +d ,l               > u˜ − d, where v is the head node of ~a . For
                                                                        ~               ~          ~a     v               ~                                                            ~γ
                                                                      b                  b           ~γ                 b
                                                                                          ~γ
                                                                                       ~                                ~arr                                          ~                    ˜
                                   a backward bucket arc γ ~ ∈ Γ, its arrival bucket b                                         is the forward bucket b such that l ≤
                                                                                                                          γ~                                                                ~
                                                                  	                                                                                                                        b
                                                                  0        ˜       ˜                0
                                   min u˜         −d ,u               <l +d, where v is the head node of a~ . For a jump bucket arc ψ ∈ Ψ,
                                                ~       a~      v           ~                                                             γ~
                                              b           γ~                b
                                               γ~
                                                                                                                                                                                      jump
                                   the definition of its forward/backward arrival buckets is identical, just replacing bγ by b                                                                .
                                                                                                                                                                                      ψ
                                   Proposition 4. Let set Γ be a superset of all improving bucket arcs, Ψ be the set of jump bucket
                                   arcs computed using procedure ObtainJumpBucketArcs(Γ), and value θ be calculated according
                                   to (16). If γ ∈ Γ is an improving bucket arc then there exists a pair of θ-compatible labels L ∈ L
                                                                                             ~~
                                                                        L                    LL       arr
                                          ~ ~    ~ ~                                       ~ ~      ~ ~                                               ~ ~     ~ ~
                                   and LL ∈ LL such that b                 b and bb bb , where L = L(Γ,Ψ), and LL = LL(Γ,Ψ).
                                                                                 γ                    γ
                                   Proof. If γ is an improving bucket arc, then there exists an improving path P and an index j,
                                                                                      P
                                                                                    L                        P                        P
                                   0 ≤ j < |P|, such that b = b j and a = a                                       . We have c¯ < θ, as it is a necessary condition
                                                                           γ                       γ         j+1
                                                                                                                                                   ~~
                                                                                                                                    P              PP
                                                                                                                                                ~ ~
                                   for P to be improving. Then by Observation 1, labels Lj and LL|P|−j−1 are θ-compatible. If
                                               P                           P                                                                                                                    P
                                   label L        ∈L, let L = L , otherwise by Proposition 1 there exists a label L ∈ L dominating L
                                               j                           j                                                                                                                    j
                                                                 P                              ~~                                     ~~
                                                      L        L                                PP               ~ ~                   PP
                                   such that b           b j = b . If label ~ ~                                            ~ ~     ~ ~
                                                                           γ                 LL              ∈ LL, let LL = LL                     , otherwise by Proposition 1
                                                                                                |P|−j−1                                |P|−j−1        ~~
                                                                                                                                                      PP
                                                                                                         ~~                               ~~        ~~
                                                                                                         PP                               LL        LL                   arr
                                                                     ~ ~     ~ ~                      ~ ~                               ~ ~       ~ ~ |P|−j−1         ~ ~
                                   there exists a label LL ∈ LL dominating LL|P|−j−1 such that bb                                              bb                 bbγ . Finally, by
                                                                       ~ ~
                                   Proposition 2, L and LL are θ-compatible.
                                                                                                                 18
                                                                                                  Proposition 4 is the basis for the procedure to find non-improving bucket arcs. To prove
                                                                                    that a bucket arc γ is non-improving, we need to verify that there does not exist a pair of θ-
                                                                                                                                                                                                           ~ ~               ~ ~                                                                                                                                                                                                                                L
                                                                                    compatible labels L ∈ L and LL ∈ LL (one at the tail and one at the head of a ) such that b                                                                                                                                                                                                                                                                                          b
                                                                                                                                                                                                                                                                                                                                                                                                        γ                                                                              γ
                                                                                                           ~~
                                                                                                          LL                     arr
                                                                                                     ~ ~                    ~ ~
                                                                                    and bb                         bbγ . A direct approach is to exhaustively enumerate all such pairs of labels for every
                                                                                    bucket arc and verify whether at least one of them is θ-compatible. This approach is slow as the
                                                                                    same pair of labels may be verified for θ-compatibility several times.
                                                                                                  Toguarantee that no pair of labels is verified for θ-compatibility more than once, we compute
                                                                                                       ~~                                                                                                                                                                                                                                                                                                                              ~~
                                                                                    sets BB                               of buckets of opposite sense with respect to bucket b at the head of arc a. BB                                                                                                                                                                                                                                                  contains
                                                                                                             a,b                                                                                                                                                                                                                                                                                                                             a,b
                                                                                                                                           ~ ~                                                                                     ~ ~                 ~ ~
                                                                                    every bucket bb containing a label LL ∈ LL which is θ-compatible with a label L ∈ L such that
                                                                                        L                                                                                                                                                                                                                                                                                                                                                                                      arr
                                                                                                                                                                                                                                                                                                     ~~                                                                                                                                                 ~ ~               ~ ~
                                                                                    b            b. Thus, a bucket arc γ is non-improving if BBa ,b does not contain any bucket bb  bbγ .
                                                                                                                                                                                                                                                                                                              γ γ
                                                                                                                                                                                                          ~~
                                                                                    An advantage of using sets BB                                                                                                            is that they can be constructed incrementally using adjacent
                                                                                                                                                                                                                a,b
                                                                                                                                                                 ~~                                                                                                                                                    ~~             0            0
                                                                                    buckets: every set BB                                                                          is initialized as the union of sets BB                                                                                                                , b ∈ Φ , and then augmented using
                                                                                                                                                                      a,b                                                                                                                                                    a,b                                        b
                                                                                    the recursive procedure UpdateBucketsSet which tries to find opposite sense buckets containing
                                                                                    a label which is θ-compatible with a label in b.
                                                                                                                                                                                                                                                                                                                                                                                                                               ~ ~        ~ ~                visited
                                                                                                                                                                                                                                                                                                                                                                                                                    ~~                                 ~~
                                                                                                  Wenowpresent formally the auxiliary procedure UpdateBucketsSet(θ, L, BB, bb, LL, BB                                                                                                                                                                                                                                                                                                ),
                                                                                                                                                                                                                                                                                        ~0~          ~0~                 ~ ~       ~0~                         visited
                                                                                                                                                                  ~~                                                                                                                                                                                     ~~
                                                                                    which adds to set BB all opposite sense buckets bb , bb  bb, bb 6∈ BB                                                                                                                                                                                                                             , containing at least one
                                                                                                           ~ ~               ~ ~                                                                                  ~ ~
                                                                                    label LL ∈ LL such that pair (L,LL) of labels is θ-compatible.
                                                                                                                                                                                                                                                                ~ ~        ~ ~                 visited
                                                                                                                                                                                                                                                      ~~                                 ~~
                                                                                           Procedure UpdateBucketsSet(θ, L, BB, bb, LL, BB                                                                                                                                                                             )
                                                                                                         visited                                    visited                            ~ ~
                                                                                                    ~~                                        ~~
                                                                                                  BB                              ←BB                                       ∪{bb}
                                                                                                                L                                                   best
                                                                                                  if c¯                +c¯ L                           +c¯                         ≥θthenreturn
                                                                                                                                   v ,v˜                           ~~
                                                                                                                                                 ~~                 bb
                                                                                                                                                 bb
                                                                                                           ~ ~              ~~
                                                                                                  if bb 6∈ BB then                                                                                     ~~
                                                                                                                                                                                                      LL
                                                                                                                                                                       ~ ~             ~ ~        ~ ~                 ~ ~
                                                                                                                 foreach label LL ∈ LL, bb                                                                    =bb do
                                                                                                                                                                        ~ ~
                                                                                                                               if pair (L,LL) is θ-compatible then
                                                                                                                                               ~~                  ~~                 ~ ~
                                                                                                                                             BB ← BB ∪{bb}
                                                                                                                                   ~0~                                        visited
                                                                                                                                                                         ~~
                                                                                                  foreach bb ∈ Φ \BB                                                                                   do
                                                                                                                                                           ~~
                                                                                                                                                           bb
                                                                                                                                                                                                                     ~0~         ~ ~             visited
                                                                                                                                                                                                             ~~                             ~~
                                                                                                                 UpdateBucketsSet(θ,L,BB,bb ,LL,BB                                                                                                                     )
                                                                                                                                                                                                                                                                                                                                                                                                                                                       ~ ~
                                                                                                  Finally, we present formally the main procedure BucketArcElimination(θ, Γ, Ψ, L, LL) which
                                                                                    can be used for both forward and backward sense. The procedure removes some non-improving
                                                                                    bucket arcs from Γ, given the set L of non-dominated labels of the same sense as Γ and the
                                                                                                    ~ ~
                                                                                    set LL of non-dominated labels of the opposite sense. In this procedure, in order to do the
                                                                                                                                                                                                         ~~                                                                                                                                                                                                                                              b
                                                                                    correct initialization of sets BBa,b, buckets b are considered in a lexicographic order of κ . When
                                                                                                                                                                                                                                                                                                                                                                                                                    ~~
                                                                                    considering bucket b, procedure UpdateBucketsSet is called to augment set BB                                                                                                                                                                                                                                                                        only if there
                                                                                                                                                                                                                                                                                                                                                                                                                          a,b
                                                                                    exists γ ∈ Γ such that b = bγ or there exists ψ ∈ Ψ such that b = bbase. If such a (jump) bucket
                                                                                                                                                                                                                                                                                                                                                                     ψ
                                                                                                                                                                                                                                                                  0                                                                        0                                                0                                                                               ~~
                                                                                    arc does not exist, there is no bucket arc γ ∈ Γ such that a                                                                                                                                                                                                =aandb b,andthussetBB
                                                                                                                                                                                                                                                                                                                                      γ                                                 γ                                                                                        a,b
                                                                                    is not used in the reminder of the algorithm.
                                                                                                  The next proposition proves formally that the combination of the modified bi-directional
                                                                                    labeling algorithm and the bucket arc elimination procedure is correct, i.e.                                                                                                                                                                                                                                                             it allows us to
                                                                                    compute a valid lower bound for the original problem.
                                                                                    Proposition 5. Let z be the reduced cost of the best path obtained by the modified bi-directional
                                                                                    labeling algorithm after performing j calls to procedure BucketArcElimination, for some integer
                                                                                                                                                                ~
                                                                                                                                                               P                                                                                                           ~                 ~
                                                                                    j ≥ 0. Then z ≤ c                                                                   for any improving path P ∈ P.
                                                                                    Proof. It is enough to prove that the current forward (backward) bucket graph obtained after
                                                                                    j calls of Procedure BucketArcElimination is a superset of all improving forward (backward)
                                                                                    bucket arcs, since this proposition is a direct consequence of this statement and Proposition
                                                                                    3.             We prove it by induction on the value of j. For j = 0, this is true because the initial
                                                                                    forward and backward bucket graphs contain all possible forward and backward bucket arcs.
                                                                                    Now, suppose by inductive hypothesis that this is valid for j = i, i.e. all improving forward
                                                                                                                                                                                                                                                                                   19
                                                                                                                                                       ~ ~
                                                Procedure BucketArcElimination(θ, Γ, Ψ, L, LL)
                                                                                                                                                          b
                                                    foreach bucket b ∈ B in a lexicographic order of κ do
                                                            if Φb 6= ∅ then                                     0                     ~~                          ~~
                                                                   foreach arc a = (v˜ ,v ) ∈ A do BB                                          ←∪0 BB 0
                                                                                                          b                             a,b             b ∈Φb        a,b
                                                            else
                                                                                                                0                     ~~
                                                                   foreach arc a = (v˜ ,v ) ∈ A do BB                                          ←∅
                                                                                                          b                             a,b
                                                            foreach jump bucket arc ψ ∈ Ψ such that bbase = b do
                                                                                                                                                   ψ
                                                                   foreach L ∈ L such that bL = b do
                                                                                                                                          arr
                                                                                                                            ~~          ~ ~      ~ ~
                                                                           UpdateBucketsSet(θ,L,BB                                    , bb     , LL, ∅)
                                                                                                                              aψ,b        ψ
                                                            foreach bucket arc γ ∈ Γ such that bγ = b do
                                                                   foreach L ∈ L such that bL = b do
                                                                                                                                          arr
                                                                                                                            ~~         ~ ~       ~ ~
                                                                           UpdateBucketsSet(θ,L,BB                                    , bb     , LL, ∅)
                                                                                                                              aγ,b        γ
                                                                              0                        0        arr
                                                                            ~ ~       ~~             ~ ~      ~ ~
                                                                   if 6 ∃bb ∈ BB                 : bb  bb             then Γ←Γ\{γ}
                                                                                         a ,b                   γ
                                                                                           γ
                                             (backward) bucket arcs are present in the current forward (backward) bucket graph before the
                                             (i + 1)th call to procedure BucketArcElimination. Then, by Proposition 4, for each improving
                                             (forward or backward) bucket arc γ ∈ Γ, the bi-directional labeling algorithm generates a pair
                                                                                                                                                                              ~~
                                                                                                                                               L                             LL            arr
                                                                                                                ~ ~                                                        ~ ~           ~ ~
                                             of θ-compatible labels L and LL such that b                                                             bγ and bb                     bb          .    Since this pair of labels
                                                                                                                                                                                           γ
                                             prevents γ to be removed in the next call to procedure BucketArcElimination, the statement
                                             under consideration is also true for j = i + 1, finishing the proof.
                                                    Let us now give some final remarks on our bucket arc elimination procedure.
                                                    • Our procedure can be viewed as a “resource-value dependent” arc elimination and thus
                                                         a generalization of the arc elimination procedure by Irnich et al. (2010). The latter can
                                                                                                                                                                                                                                       ~
                                                                                                                                                                                             ~                                        L
                                                         readily be extended to remove extensions of forward labels L along an arc if q                                                                                                    exceeds
                                                         a certain threshold (and extensions of backward labels L~ if qL~ is lower than a threshold).
                                                         The opposite case (“less than” for the forward sense and “greater than” for the backward
                                                         sense) is more complicated as shown in our analysis and necessitates introduction of jump
                                                         bucket arcs. Our procedure is more generic than both, and may result in elimination of
                                                         disjoint “resource-value” intervals for an arc.
                                                    • Necessity of adding jump bucket arcs essentially comes from the fact that the dominating
                                                         label may be contained in a different bucket than the dominated one. Restricting dom-
                                                         inance checks only to ones within buckets does not make jump bucket arcs redundant.
                                                         This is because two labels in the same bucket with distinct resource consumption may be
                                                         extended (over the same arc) to labels in different buckets. Only restricting the dominance
                                                         checks to labels with the same resource consumption allows one to skip the generation of
                                                         jump bucket arcs.
                                                    • “Resource-value dependent” arc elimination has already been used in Pessoa et al. (2010)
                                                         and in Pecin et al. (2017b). However, it was done at the cost of resource discretization,
                                                         limited dominance checks, and dropping the exploitation of the route symmetry. Our
                                                         procedure allows one to overcome these drawbacks.
                                             5           Branch-Cut-and-Price algorithm
                                             Weimplemented a BCP algorithm for the HFVRPTW using the new bucket graph labeling al-
                                             gorithm in its pricing and also the bucket arc elimination procedure. Other algorithmic elements
                                             are similar to the ones presented in Pecin et al. (2014), Pecin et al. (2017b) and Pecin et al.
                                             (2017a), except that a different dynamic ng-relaxation by Bulhoes, Sadykov, and Uchoa (2018)
                                                                                                                                                  20
                     and automatic dual price smoothing stabilization by Pessoa et al. (2018) are used. However, to
                     make this paper self-contained, we give a succinct algorithm description in what follows.
                        For each node of the branch-and-bound tree, the lower bound on the optimal cost is com-
                     puted by solving the linear relaxation of SPF enhanced with RCCs (5) and limited-memory
                     R1Cs (7). Before each cut generation round, the current SPF relaxation is solved through col-
                     umngeneration, using automatic (parameterless) dual pricing smoothing stabilization described
                     in Pessoa et al. (2018). To further speed up the convergence, three-stage column generation is
                     implemented. At the first stage, the “light” pricing heuristic is applied in which only one label
                     per bucket (with the smallest reduced cost) is kept. In the second stage, a more expensive pricing
                     heuristic is used in which states F and S are not taken into account in the dominance checks.
                                                                                                 heur      exact
                     In the last stage, the exact labeling algorithm is used. We use parameters χ    and χ      for
                     the maximum number of columns generated at each iteration of column generation at heuristic
                     and exact stages. When the number of columns in the restricted master exceeds χmax, we clean
                                               perc
                     them up and leave only χ     %columns with the least reduced cost. Basic columns are never
                     removed, however, non-basic columns with zero reduced cost may be removed.
                        The threshold value q∗ for the bi-directional labeling algorithm is an important parameter
                     in the non-symmetric case. Pecin et al. (2017b) and Tilk et al. (2017) proposed to modify
                     the labeling algorithm to automatically adjust this value. Here we adopt a simpler but still
                     effective approach. Value q∗ is initialized as the average middle value for all resource consumption
                     intervals. After each exact pricing we compare the number of forward and backward non-
                     dominated labels. If one number exceeds another by more than 20%, we adjust value q∗ by
                     moving it by 5% towards the maximum or minimum possible value.
                        The limited-arc-memory R1Cs are separated by complete enumeration for |C| ≤ 3 and by a
                     local search heuristic for |C| ∈ {4,5}. This heuristic is launched for each possible optimal vector
                     p. Given p, it tries to find a subset C of customers such that the corresponding cut is violated
                     with a full memory. If such C exists, an arc-memory AM of minimal size such that the cut
                     violation remains the same is identified. Then AM is completed with all arcs between vertices
                     in C. When there already exists a cut defined for the same subset C and vector p but for a
                     different arc-memory AM0, this cut is simply enhanced by enlarging its memory to AM0 ∪AM.
                     Otherwise, a new cut is added for C, p and AM. Also, memory sets are kept symmetric. This
                     means that if arc (v,v0) is added to AM, then (v0,v) must also be added. Parameter vector β
                     is used in which βk, k ∈ {0,1,3,4,5} is the maximum number of R1C with |C| = k separated
                     per round (β0 is the maximum number of RCCs generated per round). Other parameters are
                     δperc% and δnum which are used to stop the cut generation by tailing-off. If the number of times
                     the dual-primal gap is decreased by less than δperc% reaches δnum, then branching is performed.
                     At the root node, R1Cs are separated only if RCCs are exhausted or tail off. Before each cut
                     round, non-active cuts are removed from the restricted master.
                        In our algorithm, we use the dynamic variant of the ng-relaxation from Bulhoes, Sadykov,
                     and Uchoa (2018) which is inspired by Roberti and Mingozzi (2014). We start by generating
                     ng-neighborhood for each customer by including their ηinit closest customers (including itself).
                     After the convergence of column generation, we augment neighborhoods in order to forbid the
                     cycles in the columns forming the current fractional solution. For each such column we either
                     forbid all cycles of size at most η1 or, if there is no one, the minimum size cycle. Cycles in at most
                     η2 columns are forbidden in each round. After augmentation, the neighborhood of any customer
                     cannot exceed size ηmax. The same tailing-off parameters are applied here as for cutting planes.
                     Westart the root node by augmenting the ng-neighborhoods. Then, after tailing-off, RCCs are
                     separated. After another tailing-off, R1Cs are separated.
                        Each additional active inequality (7) or ng-neighborhood increase make the pricing problem
                     harder, since they weaken the dominance conditions. Because of that, separation is stopped
                     when the average exact pricing time since the last round of cuts has exceeded a given threshold
                     τ. In some extreme cases, R1Cs may be even removed by the roll-back procedure activated if a
                     single pricing time exceeds τ¯, as described in Pecin et al. (2017b).
                        The bucket arc elimination procedure is called after the initial convergence, and also each
                                                                   21
                        time the current primal-dual gap decreased by at least υ% since the last call to the bucket arc
                        elimination procedure. A bi-directional enumeration procedure is called after each reduced cost
                        fixing to try to generate all improving elementary routes, using the algorithm proposed in Pecin
                        et al. (2017b). The enumeration procedure is interrupted if the number of labels exceeds ωlabels
                        or if the number of enumerated routes exceeds ωroutes. After a successful enumeration for a
                        pricing subproblem corresponding to a vehicle type, this subproblem passes to the enumerated
                        state and the (SPF) relaxation is updated by excluding non-elementary columns coming from
                        this subproblem. The pricing subproblem in the enumerated state is solved by inspection. Elim-
                        ination procedure based on reduced costs is also performed for enumerated pricing subproblems,
                        but considering each route individually. If after some point, the number of enumerated routes
                        for each subproblem falls below ωMIP, the residual problem is handled by a standard MIP solver,
                        and the node is considered as processed.
                            Recall that to perform bucket arc elimination, the forward and backward passes of the labeling
                        algorithm must be performed completely. Thus the running time may increase substantially in
                        comparison with the “standard” exact labeling in which the labels beyond the bi-directional
                        threshold value q∗ are not stored. To accelerate the bucket arc elimination procedure, we use
                        what we call exact completion bounds technique: for every label L just created by extension
                                  ∗                                                                                 ~ ~
                        beyond q , we verify exhaustively whether there exists an opposite sense label LL such that L
                             ~ ~
                        and LL are θ-compatible. Here θ is as defined in Section 4. We keep label L only if such a
                              ~ ~
                        label LL exists. A similar approach is used in the bi-directional enumeration procedure. Using
                        completion bounds for labels before the bi-directional threshold value q∗, as it is done in Pecin
                        et al. (2017b), was not computationally beneficial for our labeling algorithm.
                            If tailing-off condition is attained, or at least one non-enumerated pricing subproblem becomes
                        too time consuming to solve, branching must be performed. This is done by adding constraints
                        to the master LP that correspond to tightening lower and upper bounds on the value of the
                        following aggregated variables corresponding to different branching strategies:
                            • gm = P           P0 01xP 0 +xP0                
λP, m ∈ M;
                                        P∈Ωm     v ∈V 2     (0,v )    (v ,n+1)
                            • gm = P           yPλP, v ∈ V, m ∈ M;
                                v       P∈Ωm v
                                   0     P        P          P         P              0             0
                            • g       =                    (x    0 +x 0 )λP, v,v ∈V, v 6= v .
                                {v,v }      m∈M     P∈Ωm (v,v )        (v ,v)
                        gm corresponds to the number of used vehicles of type m ∈ M; gm characterizes whether
                                                                                                        v
                        customer v ∈ V is served by a vehicle of type m; g{v,v0} characterizes whether edge (v,v0)
                        is used in the solution. Given a fractional branching variable g with fractional value f, two
                        child nodes are created by adding the constraints g ≤ bfc and g ≥ dfe to the master LP. A
                                                         P        P         P        m P
                        generic branching constraint                               α x λP ≥β added to the master LP with
                                                            m∈M      P∈Ωm     a∈A a a
                        associated dual variable ι can be considered by the pricing algorithm by subtracting ιαm from
                                                                                                                             a
                                              m
                        the expression of c¯ (π,ν) given by (8), for each m ∈ M and a ∈ A, thus, not making the
                                              a
                        subproblem harder. Moreover, the symmetry is preserved, as for any route P, coefficients xP
                                                                                                                               (v0,v)
                              P
                        and x     0  are the same in all branching constraints we use.
                              (v,v )
                            Theselection of the branching variable at each node is done using a sophisticated hierarchical
                        evaluation strategy similar to the one proposed in Pecin et al. (2017b). The idea is to spend more
                        time evaluating branching variables in the lowest levels of the branch-and-bound tree where each
                        selection has a greater impact on the overall time, and spend less time as the level increases,
                        taking advantage of the history of previous evaluations. The following three evaluation phases
                        are used:
                        Phase 0: Half of the candidates are chosen from history using pseudo-costs (if history is not
                              empty). The remaining candidates are chosen in a balanced way between the three strate-
                              gies. Within the same strategy, the candidates are chosen based on the distance from its
                              fractional value to the closest integer and for branching on edges, distance to the closest
                              depot (the smaller the better) is also taken into account.
                                                                             22
                 Phase 1: Evaluate the selected candidates from phase 0 by solving the current restricted master
                      LPmodified for each created child node, without generating columns. Select the variables
                      with the maximumvalueof∆LB ×∆LB ,where∆LB denotestheincreaseinthecurrent
                                                 1      2          i
                      lower bound obtained for the ith child node, for i = 1,2 (Product Rule, Achterberg (2007)).
                 Phase 2: Evaluate the selected candidates from phase 1 by solving the relaxation associated
                      to each created child node, including heuristic column generation, but not cut generation.
                      The best candidate is also selected by the Product Rule.
                 The parameters ζ and ζ are used to specify the maximum number of candidates chosen in
                                0      1
                 phases 0 and 1.
                 6    Computational experiments
                 TheBCPalgorithmdescribedintheprevioussectionwascodedinC++andcompiledwithGCC
                 5.3.0. The BaPCod package by Vanderbeck, Sadykov, and Tahiri (2017) was used to handle the
                 BCP framework. IBM CPLEX Optimizer version 12.6.0 was used as the LP solver in column
                 generation and as the IP solver for the set partitioning problem with enumerated columns. The
                 experiments were run on a 2 Deca-core Ivy-Bridge Haswell Intel Xeon E5-2680 v3 server running
                 at 2.50 GHz. The 128 GB of available RAM was shared between eight copies of the algorithm
                 running in parallel on the server. Each instance is solved by one copy of the algorithm using a
                 single thread.
                 6.1   Instances
                 VRPTWinstances For the vehicle routing problem with time windows, 14 most difficult
                      (according to Pecin et al. (2017a)) instances with 100 customers by Solomon (1987), as
                      well as 120 instances by Gehring and Homberger (2002) with 200 and 400 customers were
                      considered. Solomon instances used are C203, C204, RC204, RC207, RC208, R202, R203,
                      R204, R206, R207, R208, R209, R210, and R211. The instances are divided into classes of
                      clustered (C), random-clustered(RC), and random (R) location of customers on the plane.
                      Note that the capacity resource in Solomon instances, as well as Gehring and Homberger
                      instances of classes C2, RC2, and R2, is not tight. Therefore, the subproblem only considers
                      the time resource in those classes. The capacity resource is imposed through RCCs, which
                      are treated as “core” cuts, i.e. they are separated for every fractional but also for every
                      integer solution found during the search. The initial upper bounds were obtained by the
                      heuristic in Vidal et al. (2013). The same values were used in Pecin et al. (2017a).
                 DCVRPinstances Forthedistanceconstrainedvehicleroutingproblem, weusedsevenclassic
                      instances from Christofides, Mingozzi, and Toth (1979) with 50–200 customers, named
                      CMT6, CMT7, CMT8, CMT9, CMT10, CMT13, and CMT14. In spite of the fact that
                      those instances are ubiquitous in the heuristic literature for the CVRP, no exact methods
                      could solve them. The best known solutions for these instances are taken from Nagata and
                      Br¨aysy (2009).
                 MDVRPinstances Forthemulti-depotvehicleroutingproblem,weused22standarddistance
                      constrained instances by Cordeau, Gendreau, and Laporte (1997) with 80–360 customers,
                      named p08–p11, p13, p14, p15, p17, p19, p20, p22, p23, and pr01–pr10. The best known
                      solutions are taken from Vidal et al. (2012).
                 SDVRPinstances For the site-dependent vehicle routing problem, we used 10 standard dis-
                      tance constrained instances by Cordeau and Laporte (2001) with 48–288 customers, named
                      pr01–pr10. The best known solutions are taken from Cordeau and Maischberger (2012).
                                                        23
                                            Problem             Size      Resources   τ     τ¯  r∗
                                            VRPTW               100-200   1           10   30   time
                                            VRPTW               200       2            5   10   capacity
                                            VRPTW               400       1           20   60   time
                                            VRPTW               400       2           10   20   capacity
                                            HFVRP               any       1            5   10   capacity
                                            DCVRP               any       2            5   10   time
                                            MDVRP,SDVRP any               2           10   20   time
                                              Table 1: Parameterisation of pricing time thresholds
                      HFVRPinstances For the heterogeneous fleet vehicle routing problem, we used 96 instances
                             by Duhamel, Lacomme, and Prodhon (2011) with 20–256 customers. Each instance rep-
                             resents one of 96 French departments. The best known solutions are taken from Penna
                             et al. (2019). Following the convention used in those papers, we impose that each customer
                             should be visited exactly once. As the triangle inequality is not always satisfied in those
                             instances, allowing multiple visits could possibly reduce costs.
                      6.2     Algorithm parameterization
                                                                           heur        exact          max      0       perc
                      The column management parameter values are χ             =30, χ        =150, χ      =10000, χ        =
                      66%. The cut generation parameter values are β = β = β = β = 100, β = 150. The
                                                                             0      1     4      5           3
                      tailing off parameter values are δperc = 1.5%, δnum = 3. Dynamic ng-relaxation parameter
                      values are ηinit = 8, η1 = 5, η2 = 100, ηmax = 16. Parameter value for the bucket graph
                                                                                                         labels     0   0
                      elimination procedure is υ = 10%. Enumeration parameter values are ω                     = 1000000,
                        routes    0   0       MIP      0
                      ω       =5000000, ω         =10000. The strong branching parameter values are ζ0 = 50, ζ1 = 3.
                          The pricing time thresholds (in seconds) depend on instance class, instance size, and on the
                      number of resources (dimension of buckets). These thresholds as well as which resource is chosen
                      as r∗ in bidirectional labeling are shown in Table 1.
                          The bucket step size in the labeling algorithm is adjusted dynamically as explained below.
                      6.3     Impact of bucket step size and improved arc elimination
                      As two main contributions of the paper are using the bucket graph in the labeling algorithm and
                      improved procedure for bucket (or resource value dependent) arc elimination, we first estimate
                      their impact on the solution time of the BCP algorithm.
                          These tests were done on the set of 74 VRPTW instances with 100 and 200 customers. Only
                      the root node is considered. For instances which cannot be solved at the root, we establish the
                      “target” lower bounds. These values are determined in such a way that once they are achieved
                      by a good parameterisation of the algorithm in the root node, it is reasonable to branch because
                      either i) cuts are tailing off, or ii) pricing becomes too expensive. In Table 2, we give the instance
                      name, its optimum or Best Known Solution (BKS) value, and the Target Lower Bound (TLB)
                      value we use. For instances not shown in this table, the target lower bound equals the optimum
                      solution value.
                          Thefirst parameter we test is the “maximum number of buckets per vertex” which we denote
                                                                                      ˜
                      as ξ. For instances with one time resource, bucket step size d is determined as (u        −l )/ξ. For
                                                                                                            n+1    0
                                                                        ˜
                      instances with two resources, bucket step size d for the first (capacity) resource is determined as
                          √                                              1                                               √
                                                      ˜
                      W/ ξ, and bucket step size d for the second (time) resource is determined as (u              −l )/ ξ.
                                                       2                                                      n+1     0
                                  ˜
                      All values d are rounded off to one decimal place.
                                   r
                          The second binary parameter to test is whether the standard arc elimination procedure (as
                      in Irnich et al. (2010)) or improved bucket arc elimination procedure is applied. In the former
                      case, we fix arc a ∈ A if all bucket arcs γ ∈ Γ such that a = a can be fixed. When fixing original
                                                                                  γ
                      arcs, no jump bucket arcs are needed. The procedure for fixing original arcs runs faster, as once
                                                                         24
                                  Instance    BKS      TLB     Instance     BKS      TLB     Instance     BKS      TLB
                                  R208        701.0    699.0   R2 2 4     1928.5   1925.0    RC1 2 7    3177.8   3150.0
                                  C2 2 3    1763.4    1753.1   R2 2 6     2675.4   2674.6    RC1 2 8    3060.0   3044.8
                                  C2 2 4    1695.0    1663.5   R2 2 8     1842.4   1831.6    RC1 2 9    3074.8   3035.7
                                  R1 2 3    3373.9    3352.2   R2 210     2549.4   2545.3    RC1 210    2990.5   2966.0
                                  R1 2 4    3047.6    3035.3   RC1 2 1    3516.9   3499.1    RC2 2 2    2481.6   2477.5
                                  R1 2 5    4053.2    4044.1   RC1 2 2    3221.6   3204.4    RC2 2 4    1854.8   1848.0
                                  R1 2 6    3559.2    3544.2   RC1 2 3    3001.4   2980.7    RC2 2 7    2287.7   2279.7
                                  R1 2 8    2938.4    2933.3   RC1 2 4    2845.2   2832.8    RC2 2 8    2151.2   2150.3
                                  R1 2 9    3734.7    3726.0   RC1 2 5    3325.6   3310.0    RC2 2 9    2086.6   2072.0
                                  R1 210    3293.1    3277.3   RC1 2 6    3300.7   3289.0    RC2 210    1989.2   1962.0
                                               Table 2: Target lower bounds for VRPTW instances
                       we determine that a bucket arc γ ∈ Γ cannot be fixed, we do not try to fix bucket arcs γ0 ∈ Γ
                       such that a 0 = a . The resource value dependent arc elimination procedure proposed in Pessoa
                                    γ     γ
                       et al. (2010) is valid only for the single resource case with positive integer consumption. This
                                                                                                               ˜
                       procedure can be viewed as a fixing in a bucket graph with unitary step size (d = 1) under the
                       condition that the dominance checks are performed only between labels with the same resource
                       consumption.
                           Thebase variant of the algorithm which we denote as (O) is parameterized with ξ = 1, which
                       corresponds to the basic variant of the label correcting algorithm, and uses the standard arc
                       elimination procedure. The base variant is compared with variant (A) which is parameterized
                       with a fixed value ξ ∈ Ξ = {1,2,5,10,20,50,100,200,500,1000,2000} and uses the standard arc
                                                                                                    +
                       elimination procedure. Then variant (A) is compared with variant (A ) which uses a procedure
                       described below to automatically adjust value ξ and the standard arc elimination procedure.
                                           +                                   +
                       Finally variant (A ) is compared with variant (A B) which uses dynamically adjusted value ξ
                       and the improved procedure for bucket arc elimination.
                           Different bucket step sizes used in the labeling algorithm usually change the set of routes
                       returned by the “light” pricing heuristic to the master. This happens because a given non-
                       dominated label may be extended if one bucket step size is used and not extended if another
                       bucket step size is used. Thus, for each value ξ, the sequence of primal-dual master solutions
                       in the column generation may follow a different trajectory and converge to distinct alternative
                       optima. In turn, this changes the set of cuts returned by the separation procedures, affecting the
                       pricing difficulty for the next iterations. This “random noise” may make the experimental results
                                                                                                   ¯
                       less clear. To avoid this, for each instance i ∈ I we choose a value ξi ∈ Ξ. Then, two copies of
                                                                                         ¯
                       the labeling algorithm are created, the first one with value ξi, and the second one with the value
                       being tested ξ0 ∈ Ξ. Both copies are executed in each iteration of columns generation, and the
                       arc elimination procedure is also performed twice. Only the set of columns produced by the first
                       copy of the algorithm is sent to the master. Therefore, the sequence of primal-dual solutions of
                       the master problem is always the same regardless of the bucket step size parameterisation.
                           For each run, i.e. for each pair (i,ξ0), we collect the following statistics. The first one is the
                       ξ-subproblem time which includes the time to create the bucket graph and a topological order for
                       it, the total pricing time, the total bucket arc elimination time, and the total enumeration time.
                       The second statistics is the master time which is the difference between the overall running time
                                          ¯                           0
                       and the sum of ξi-subproblem time and ξ -subproblem time. The total time is the sum of the
                       master time and the ξ0-subproblem time. For each instance i ∈ I and each value ξ0 ∈ Ξ, we
                                          tot       sp                                                 0
                       calculate ratios %i,ξ0 and %   0 between the corresponding total time (or ξ -subproblem time) and
                                                    i,ξ
                       the minimum total time (minimum ξ-subproblem time) among all ξ ∈ Ξ for this instance. Ratio
                       %tot shows the speed-up of variant (A) of the algorithm over variant (O) for instance i ∈ I.
                         i,1
                                                                                                                   tot        sp
                           In Figure 5, we show the graphs for average and maximum values for both % 0 and % 0,
                                                                                                                   i,ξ        i,ξ
                       as well as graphs for these ratios for some representative individual instances. The averages are
                       shown for two groups of instances: with one and two resources. The time limit was reached
                       for ξ0 = 1,2,5,10,20,50,100 for 6, 6, 4, 4, 3, 1, 1 instances accordingly. Therefore average and
                       maximum values given in Figure 5 for these values of ξ are in fact their lower bounds. It can be
                       seen from the figure that parameter ξ has a large impact on the total pricing time, as well as
                                                                           25
                    on the overall time of the root node. The best value for this parameter is instance-dependent.
                    Two extreme values ξ = 1 and ξ = 2000 are bad parameterisations on average. The variant
                    (A) with parameterisation ξ = 200 is at least 2.85 times faster on average than variant (O).
                    The maximum speed-up reaches at least the factor of 20 (it is expected to be much higher for
                    instances stopped by the time limit).
                              Average (1 resource)       Average (2 resources)             Maximum
                                                      5
                                                      4                          20
                           4
                                                      3
                                                                                 10
                           2                          2
                                                      1                           0
                           ξ =1     10   100 1000        1     10   100 1000         1     10   100 1000
                                  Instance R203             Instance RC204              Instance RC1 2 5
                          10                          8
                                                      6                          20
                           5                          4                          10
                                                      2
                                                                                   0
                            ξ =1    10   100 1000      ξ =1    10   100 1000          1    10    100 1000
                                         Subproblem time ratio %sp                            tot
                                                                             Total time ratio %
                                                                 ξ                            ξ
                                  Figure 5: Impact of parameter ξ on the subproblem and total time
                        In Figure 5, the graph for instance RC 1 2 5 also shows the interest to have smaller buck-
                    ets than it is required to make the extended bucket graph acyclic. For this instance, setting
                    parameter ξ to 500 makes the extended bucket graph acyclic. However, the subproblem time
                    and the total time of the algorithm are, respectively, 14% and 12% smaller for parameterisation
                    ξ = 1000. Most of the time, however, the best parameterisation results in an extended bucket
                    graph with cycles.
                                     +         +
                        In variants (A ) and (A B) we use a scheme for dynamic adjustment of parameter ξ which
                    outperforms the best parameterisation (ξ = 200) for variant (A). In this scheme, we start with
                    ξ = 25. After each column generation convergence, we calculate the average ratio (among all
                    calls to exact pricing) of the number of dominance checks between labels in a same bucket and
                    the total number of non-dominated labels. If this average ratio is larger than 500 and the average
                    number of non-fixed bucket arcs (including jump bucket arcs) per vertex is less than 10’000, we
                    multiply ξ by 2. After each such multiplication, the bucket graph is regenerated.
                        In Figure 6(a), we show the performance profile which compares the total time for variant
                                                         +
                    (A) with ξ = 200 and for variant (A ). The geometric mean of the speed-up ratios between
                    these two variants is 7%, and the maximum speed-up reaches 83%.
                                                                                                 +         +
                        In Figure 6(b) we show the performance profile which compares variants (A ) and (A B) of
                    the algorithm. Although the geometric mean of the speed-up ratios due to improved bucket arc
                    elimination procedure is only 6%, for two instances the speed-up ratio reaches the factor of two.
                    These are instances RC2 2 8 and R2 2 4. In general, we noticed that one significantly benefits
                    from the improved bucket arc elimination procedure on hard instances with small primal-dual
                    gap. Such instances have usually long routes.
                                                                  26
                          h   80
                          whic
                          for 60
                          instances40
                          of
                          er
                          b   20
                          um                       (A) with ξ = 200                                     +
                          n                                                                           (A B)
                          =                                 +                                            +
                          Y    0                         (A )                                          (A )
                                   1      1.2    1.4     1.6     1.8       1    1.2   1.4   1.6   1.8   2
                                             (a)                                          (b)
                                    Total time for a variant is at most X times larger than the best
                                                                            +          +
                           Figure 6: Performance profiles for variants (A), (A ), and (A B) of the algorithm
                        Concluding this part, we summarize the results in Table 3. In it, we show the geometric
                    means of total solution time ratios for different variants of the algorithm. There, variant (A)
                    uses parameterisation ξ = 200. We give these ratios for all 74 instances as well as for subclasses of
                    instances. Looking at Table 3, we can say that the most computational improvement is achieved
                    whenpassing from variant (O) to variant (A) of the algorithm provided that the bucket step size
                    is well chosen. Additional speed-ups of variants (A+) and (A+B) are relatively small on average
                    but can be significant for certain instances.
                                                                            +      +      +
                                       Instances        (O)→(A)     (A)→(A )     (A )→(A B)
                                       100 customers         1.54         1.18            1.06
                                       200 customers         2.01         1.04            1.07
                                       Series 1              2.10         1.11            1.05
                                       Series 2              1.78         1.03            1.07
                                       Series C              1.20         1.21            1.03
                                       Series R              1.62         0.99            1.08
                                       Series RC             4.15         0.97            1.09
                                       All                   1.91         1.07            1.06
                           Table 3: Comparison of different variants of the algorithm on VRPTW instances
                    6.4    Impact of two-dimensional buckets
                    As proposed in Section 3.3, labels are grouped into buckets based on the accumulated resource
                    consumption values.    Thus, if there are two resources, we can say that buckets are “two-
                    dimensional”. However, buckets can also be formed based only on the accumulated consumption
                    of only one of two resources. Implementation of the labeling algorithm and bucket arc elimina-
                    tion procedure with such “one-dimensional” buckets is easier as sets Φ , b ∈ B, contain at most
                                                                                         b
                    one element. In this section we computationally verify whether an additional effort to implement
                    two-dimensional buckets pays off, i.e. it results in improved algorithm efficiency.
                        In this experiment, we use variant (A+B) of the algorithm to solve the root node of instances
                    with two resources. As the number of VRPTW instances with two resources is only 30 (these
                    are instances of classes C1, RC1, and R1), we add in this experiment MDVRP, SDVRP, and
                    DCVRP instances. In total, we have 69 instances. As before, for instances which cannot be
                    solved at the root, we set the “target” lower bounds, given in Table 4. Again, for instances not
                    shown in the table, the target lower bound equals the optimum solution value.
                                                                  27
                             Instance        BKS      TLB     Instance          BKS      TLB     Instance        BKS      TLB
                             CMT8          865.94     857.8   mdvrp p10      3631.11   3626.2    sdvrp pr04    3449.84   3432.3
                             CMT9         1162.55    1153.3   mdvrp p11      3546.06   3540.4    sdvrp pr05    4377.35   4332.6
                             CMT10        1395.85    1387.3   mdvrp pr05     2331.20   2318.7    sdvrp pr06    4422.02   4329.2
                             CMT13        1541.30    1475.2   mdvrp pr06     2676.30   2662.9    sdvrp pr08    2971.01   2962.6
                             mdvrp p08    4372.78    4347.6   mdvrp pr10     2868.26   2860.6    sdvrp pr09    3536.20   3527.7
                             mdvrp p09    3858.66    3849.9   sdvrp pr03     2575.36   2565.6    sdvrp pr10    4639.62   4659.4
                                   Table 4: Target lower bounds for MDVRP, SDVRP, and DCVRP instances
                                                                                                                           ˜
                            As before, when using two-dimensional buckets, given parameter ξ, bucket step size d is de-
                                         √                                         √                                        1
                                                  ˜
                        terminedasW/ ξ andd iscalculatedas(u                 −l )/ ξ. Naturally, when using one-dimensional
                                                   2                     n+1    0
                        buckets, “bucketization” is performed according to the most critical resource. This is the ca-
                                                                     ˜
                        pacity resource for VRPTW instances (d1 = W/ξ) and the time resource for the remaining ones
                         ˜
                        (d =(u       −l )/ξ). The most critical resource can easily be determined by running a reasonable
                          1      n+1    0
                        heuristic for the problem and analyzing the solutions obtained. As in the previous section, two
                        copies of the labeling algorithm are created to obtain the same sequence of primal-dual solutions
                        of the master problem for both tested configurations.
                            In Figure 7 we show the performance profile which compares variants with one-dimensional
                        and two-dimensional buckets. The geometric means of the speed-up ratios between the two
                        variants is 21%. On individual instances the maximum speed-up factor is 6.2. From detailed
                        results (not given here) it can be observed that it is important to use two-dimensional buckets
                        when both resources are similarly constraining.
                                                   h
                                                   whic 60
                                                   for
                                                        40
                                                   instances
                                                   of
                                                   er
                                                   b    20
                                                   um
                                                   n
                                                   =                        one-dimensional buckets
                                                   Y     0                  two-dimensional buckets
                                                               1      2       3      4       5      6
                                          Total time for a variant is at most X times larger than the best
                        Figure 7: Performance profiles for variants with one-dimensional and two-dimensional buckets
                            In Table 5 we give the geometric means of total solution time ratios for five variants of the
                        algorithm applied for instances with two resources. First three variants (O), (A), (A+), (A+B)
                                                                                    +
                        use one-dimensional buckets, and the last variant (A B) uses two-dimensional buckets. Again,
                        variant (A) uses parameterisation ξ = 200. We time ratios for all 69 instances as well as for
                        instances of different problems separately. Results in Table 5 suggest the most computational im-
                        provement is again achieved when passing from variant (O) to variant (A). Significant speed-ups
                                                                   +
                        achieved when passing from (A) to (A ) and from one-dimensional buckets to two-dimensional.
                        Impact of the bucket arc elimination procedure is very small here.
                        6.5     Results for the BCP algorithm
                        In this section, we present the performance of the proposed BCP algorithm on instances from the
                        literature. We start with 74 VRPTW instances having 100 and 200 customers. We compare our
                        algorithm with the state-of-the-art BCP algorithm for this problem by Pecin et al. (2017a). The
                                                                            28
                                                        One-dimensional buckets          One → two
                                                                    +       +     +             +
                            Instances  Number    (O)→(A)     (A)→(A )    (A )→(A B)          (A B)
                            DCVRP             7       2.72         1.08           1.05          1.02
                            MDVRP            22       1.80         1.25           1.01          1.12
                            SDVRP            10       6.16         0.88           0.93          1.89
                            VRPTW            30       1.78         1.23           1.05          1.14
                            All              69       2.23         1.16           1.02          1.21
                      Table 5: Comparison of different variants of the algorithm on instances with two resources
                                                  Our algorithm        Algorithm in Pecin et al. (2017a)
                            Class          Solved  Average   Geomean   Solved   Average     Geomean
                                                      time       time              time         time
                            Solomon hard    14/14      456        160   14/14      5324          961
                            C1              10/10      100         14   10/10      133            61
                            C2               9/10     4774        510    8/10      4096         3027
                            R1              10/10    11756       1418   10/10     12854         1861
                            R2              10/10     7248       2158    8/10     13626         8991
                            RC1              8/10    15370       6351    8/10     38940        13585
                            RC2              9/10    29970       3751    7/10     27372        14390
                            Overall         70/74     9044        690   65/74     13066         1956
                            Solved by both            4350        500             13066         1956
                   Table 6: Comparison of our BCP algorithm with the one in Pecin et al. (2017a) on the VRPTW
                   instances
                   difference between the two algorithms mainly resides in the different labeling routines included.
                   Another difference is a better dual price smoothing stabilization with the automatically adjusted
                   parameter (Pessoa et al. 2018) used by us. Also, we use only standard RCCs and limited-memory
                   R1Cs with up to five rows, whereas algorithm in Pecin et al. (2017a) uses also elementary
                   inequalities (a family of R1Cs) with six and seven rows and clique cuts (after enumeration).
                   Finally, different mechanisms to dynamically adjust ng-neighborhoods are employed. Other
                   components used in both algorithms are similar.
                       The computer used in Pecin et al. (2017a) and our computer have approximately the same
                   speed, according to www.cpubenchmark.net/singleThread.html. In Table 6, we present the
                   comparison of the two algorithms. Our algorithm outperforms the one by Pecin at al. for all
                   classes of VRPTW instances, except class R1 for which the results are similar. Our algorithm
                   proved optimality for five out of nine open instances with 200 customers for the first time. On
                   the set of instances solved by the both algorithms, our approach is three times faster if we
                   compare average solution times, and four times faster if we compare the geometric mean of
                   solution times. Speed-up factor on individual instances reaches 47.5 as demonstrated in the
                   detailed results presented in the online appendix. Interestingly, the largest improvement factors
                   are reached on instances for which the improved arc elimination procedure had the most impact.
                       WehavealsotestedouralgorithmonVRPTWinstanceswith400customers. Intheliterature
                   only one of these instances has been solved to optimality, by Kallehauge, Larsen, and Madsen
                   (2006). We managed to solve to optimality 24 instances out of 60. We observed three main
                   reasons (in decreasing order of the number of impacted instances) why algorithm could not solve
                   more 400-customer instances: (i) the labeling algorithm is not fast enough, so only relatively
                   few R1Cs can be added before the pricing time limit is exceeded, leaving a gap that is too large
                   (ii) R1Cs with up to five rows can be added almost until convergence, but they still leave a gap
                   that is too large, and (iii) column generation convergence is very slow.
                       In the next experiment, we compare our algorithm with the exact algorithm by Contardo
                   and Martinelli (2014) on the set of distance-constrained MDVRP instances. The main features
                   of that previous algorithm that differ from ours are:
                                                               29
                                               Our algorithm          Algorithm in Contardo and Martinelli (2014)
                        Class           Solved   Average   Geomean    Solved  Average                 Geomean
                                                    time       time               time                     time
                        “p”              12/12      4538        201      6/6       938                      342
                        “pr”             10/10     13773        937      4/7     39058                      903
                        Overall          22/22      7881        392    10/13     16186                      504
                        Solved by both               147         30              16186                      504
                    Table 7: Comparison of our BCP algorithm with the one in Contardo and Martinelli (2014) on
                    the distance-constrained MDVRP instances
                        • Useofstandardmono-directional label correcting algorithm for solving the pricing problem
                          (improved by decremental state-space relaxation);
                        • Absence of column generation stabilization;
                        • Separation of different families of valid inequalities, particularly, only a subset of R1Cs is
                          used (Subset Row Cuts), and the limited memory technique is not applied;
                        • Exclusive use of route enumeration for finishing the instance, without any branching.
                        ThespeedofthecomputerusedinContardoandMartinelli(2014)isapproximately 1.6 times
                    slower than ours, according to www.cpubenchmark.net/singleThread.html. Therefore, in the
                    following comparison, as well in the detailed results in the online appendix, the solutions times
                    of Contardo and Martinelli (2014) are divided by 1.6. In Table 7, we present the comparison of
                    the two algorithms. Our algorithm solves all instances, most of them for the first time. When
                    compared on the set of instances solved by the both algorithms, our approach is 110 times faster
                    in terms of the average time, and 16.5 times faster in terms of the geometric mean time (33 times
                    faster if the smallest instance “pr01” is not taken into account). Speed-up factor on individual
                    instances reaches three orders of magnitude as demonstrated in the detailed results presented
                    in the online appendix. We believe that all the differences pointed above, not only the bucket
                    graph pricing, contribute to this big improvement. For the instance “pr10”, we improved the
                    best known solution. For other instances, the values obtained by Vidal et al. (2012) are optimal.
                        In the following Table 8 we give the summary results for remaining instances. To our knowl-
                    edge, these instances are treated by an exact approach for the first time. We solved to optimality
                    six out of seven classic distance-constrained CVRP instances by Christofides, Mingozzi, and Toth
                    (1979). All best known solution values for these instances given in Nagata and Br¨aysy (2009) are
                    optimal. The only unsolved instance CMT13 is clustered and has many long arcs in the solution.
                    The gap for this instance is large even after adding many R1Cs. This gap can be reduced by
                    adding even more cuts, but exact pricing becomes too expensive.
                        We solved to optimality seven out of ten of distance-constrained site-dependent instances.
                    These instances happen to be harder than similar multi-depot instances in class “pr”. Best
                    known solution values from Cordeau and Maischberger (2012) were improved for four instances.
                        Finally, we have considered HFVRP instances from Duhamel, Lacomme, and Prodhon (2011)
                    who called these instances “nightmare”. Particularities of these instances are large capacities of
                    vehicles, very heterogeneous customer demands, and many – up to eight – very heterogeneous
                    vehicle types. We confirm that these instances are particularly difficult. We could not solve
                    several instances which have slightly more than 100 customers. Nevertheless, we have solved to
                    optimality all instances with up to 100 customers, 29 from 38 instances with 101–150 customers,
                    13 from 30 instances with 151–200 customers. Improved solutions were found for 43 instances.
                        The detailed results for all tested instances are given in the online appendix.
                                                                  30
                                        Class     Solved    Largest      Smallest   Average   Geomean
                                                           solved n   unsolved n       time        time
                                        DCVRP        6/7        199          120     5h30m      16m44s
                                        SDVRP       7/10        216          240    32m09s      11m26s
                                        HFVRP      56/96        186          107     3h56m      23m07s
                                   Table 8: Results for instances never attacked by exact methods before
                      7    Conclusions
                      This article proposed a new bucket-graph based variant of the labeling algorithm for the SPPRC.
                      It can handle the particularities of the SPPRCs that arise as pricing suproblems in the most
                      effective existing exact algorithms for the VRP: the partial route elementarity defined by ng-sets
                      and the numerous additional dimensions induced by limited-memory R1Cs. The algorithm is
                      especially better than existing variants when the consumptions, in at least one of the resources,
                      are given either by real numbers or by large integer numbers. Besides, a new procedure that
                      generalizes the principle of arc elimination by reduced costs to the bucket graph context was
                      given.
                         The new algorithms were embedded in an advanced BCP algorithm, that includes several
                      other features picked from the literature. The computational results were highly positive. On the
                      classical VRPTW, the new BCP is at least four times faster on average than a very recent BCP
                      algorithm (Pecin et al. 2017a). Moreover, the new BCP solved five additional VRPTW instances
                      to optimality. Since most other elements in those two BCP algorithms, like ng-paths and rank-
                      1 cuts, are similar, the significant improvement is clearly due to the techniques introduced in
                      the paper. The experimental investigation suggests that the largest improvement comes from
                      the organisation of labels in buckets which decreases the number of dominance checks in the
                      pricing. In fact, this proposed labeling implementation can better handle the large numbers that
                      define the time resource in the benchmark VRPTW instances. Other components as dynamic
                      adjustment of the bucket step size and an improved arc elimination procedure bring less speed-up
                      on average but can be important for some instances.
                         VerygoodresultswerealsoobtainedoninstancesfromotherimportantVRPvariants, includ-
                      ing classical DCVRP instances proposed almost 40 years ago, but only now solved to optimality.
                         Although the bucket implementation presented in this paper considered up to two resources,
                      it is not difficult to extend it for handling the SPPRCs with several resources that arise in other
                      VRP variants. We believe that those harder problems may also benefit from the approach.
                      However, substantial additional experimental work would be needed for determining how many
                      and which resources should be used for defining the buckets, the remaining resources being
                      treated as in the standard labeling.
                      Acknowledgements
                      Experiments presented in this paper were carried out using the PlaFRIM (Federative Platform
                      for Research in Computer Science and Mathematics), created under the Inria PlaFRIM devel-
                      opment action with support from Bordeaux INP, LABRI and IMB and other entities: Conseil
                      R´egional d’Aquitaine, Universit´e de Bordeaux, CNRS and ANR in accordance to the “Pro-
                      gramme d’Investissements d’Avenir” (see www.plafrim.fr/en/home).
                         APandEUvisited Bordeaux with funding from project FAPERJ E26/110.075/2014 (Inter-
                      national Cooperation FAPERJ/INRIA).
                         The authors are thankful to Thibaut Vidal for running the hybrid genetic algorithm and
                      communicating initial upper bounds for VRPTW instances with 200 and 400 customers.
                         Theauthors are grateful to two anonymous referees and the associate editor whose comments
                                                                      31
            helped to improve the quality of the paper.
            References
            Achterberg T, 2007 Constraint Integer Programming. Ph.D. thesis, Technische Universitat Berlin.
            Baldacci R, Mingozzi A, Roberti R, 2011 New route relaxation and pricing strategies for the vehicle
               routing problem. Operations Research 59(5):1269–1283.
            Bulhoes T, Sadykov R, Uchoa E, 2018 A branch-and-price algorithm for the minimum latency problem.
               Computers & Operations Research 93:66–78.
            Christofides N, Mingozzi A, Toth P, 1979 The vehicle routing problem. Christofides N, Mingozzi A, Toth
               P, Sandi C, eds., Combinatorial Optimization, 315–338 (Chichester, UK: Wiley).
            Christofides N, Mingozzi A, Toth P, 1981 State-space relaxation procedures for the computation of bounds
               to routing problems. Networks 11(2):145–164.
            Contardo C, Desaulniers G, Lessard F, 2015 Reaching the elementary lower bound in the vehicle routing
               problem with time windows. Networks 65(1):88–99.
            Contardo C, Martinelli R, 2014 A new exact algorithm for the multi-depot vehicle routing problem under
               capacity and route length constraints. Discrete Optimization 12:129 – 146.
            Cordeau JF, Gendreau M, Laporte G, 1997 A tabu search heuristic for periodic and multi-depot vehicle
               routing problems. Networks 30(2):105–119.
            Cordeau JF, Laporte G, 2001 A tabu search algorithm for the site dependent vehicle routing problem
               with time windows. INFOR: Information Systems and Operational Research 39(3):292–298.
            Cordeau JF, Maischberger M, 2012 A parallel iterated tabu search heuristic for vehicle routing problems.
               Computers and Operations Research 39(9):2033 – 2050.
            Dell’AmicoM,D´ıazJCD,HasleG,IoriM,2016Anadaptiveiterated local search for the mixed capacitated
               general routing problem. Transportation Science 50(4):1223–1238.
            Desaulniers G, Lessard F, Hadjar A, 2008 Tabu search, partial elementarity, and generalized k-path
               inequalities for the vehicle routing problem with time windows. Transportation Science 42(3):387–
               404.
            Duhamel C, Lacomme P, Prodhon C, 2011 Efficient frameworks for greedy split and new depth first
               search split procedures for routing problems. Computers and Operations Research 38(4):723 – 739.
            Escobar JW, Linfati R, Toth P, Baldoquin MG, 2014 A hybrid granular tabu search algorithm for the
               multi-depot vehicle routing problem. Journal of Heuristics 20(5):483–509.
            Fukasawa R, Longo H, Lysgaard J, Poggi de Arag˜ao M, Reis M, Uchoa E, Werneck R, 2006 Robust
               branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming
               106(3):491–511.
            Gehring H, Homberger J, 2002 Parallelization of a two-phase metaheuristic for routing problems with
               time windows. Journal of Heuristics 8(3):251–276.
            Irnich S, Desaulniers G, 2005 Shortest path problems with resource constraints. Desaulniers G, Desrosiers
               J, Solomon MM, eds., Column Generation, 33–65 (Boston, MA: Springer US).
            Irnich S, Desaulniers G, Desrosiers J, Hadjar A, 2010 Path-reduced costs for eliminating arcs in routing
               and scheduling. INFORMS Journal on Computing 22(2):297–313.
            Jepsen M, Petersen B, Spoorendonk S, Pisinger D, 2008 Subset-row inequalities applied to the vehicle-
               routing problem with time windows. Operations Research 56(2):497–511.
            Jiang J, Ng KM, Poh KL, Teo KM, 2014 Vehicle routing problem with a heterogeneous fleet and time
               windows. Expert Systems with Applications 41(8):3748 – 3760.
            Kallehauge B, Larsen J, Madsen OB, 2006 Lagrangian duality applied to the vehicle routing problem with
               time windows. Computers and Operations Research 33(5):1464 – 1487.
            Laporte G, Nobert Y, 1983 A branch and bound algorithm for the capacitated vehicle routing problem.
               ORSpectrum 5(2):77–85.
            Lozano L, Duque D, Medaglia AL, 2015 An exact algorithm for the elementary shortest path problem
               with resource constraints. Transportation Science 50(1):348–357.
            Lozano L, Medaglia AL, 2013 On an exact method for the constrained shortest path problem. Computers
               and Operations Research 40(1):378 – 384.
                                       32
            Nagata Y, Br¨aysy O, 2009 Edge assembly-based memetic algorithm for the capacitated vehicle routing
               problem. Networks 54(4):205–215.
            Pecin D, Contardo C, Desaulniers G, Uchoa E, 2017a New enhancements for the exact solution of the
               vehicle routing problem with time windows. INFORMS Journal on Computing 29(3):489–502.
            PecinD,PessoaA,PoggiM,UchoaE,2014Improvedbranch-cut-and-priceforcapacitated vehicle routing.
               Lee J, Vygen J, eds., Integer Programming and Combinatorial Optimization, 393–403 (Springer).
            Pecin D, Pessoa A, Poggi M, Uchoa E, 2017b Improved branch-cut-and-price for capacitated vehicle
               routing. Mathematical Programming Computation 9(1):61–100.
            Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H, 2017c Limited memory rank-1 cuts for vehicle routing
               problems. Operations Research Letters 45(3):206 – 209.
            Penna PHV, Subramanian A, Ochi LS, Vidal T, Prins C, 2019 A hybrid heuristic for a broad class of
               vehicle routing problems with heterogeneous fleet. Annals of Operations Research 273(1):5–74.
            Pessoa A, de Arag˜ao MP Marcus, Uchoa E, 2008 Robust branch-cut-and-price algorithms for vehicle
               routing problems. Golden B, Raghavan S, Wasil E, eds., The Vehicle Routing Problem: Latest
               Advances and New Challenges, volume 43 of Operations Research/Computer Science Interfaces,
               297–325 (Springer US).
            Pessoa A, Sadykov R, Uchoa E, Vanderbeck F, 2018 Automation and combination of linear-programming
               based stabilization techniques in column generation. INFORMS Journal on Computing 30(2):339–
               360.
            Pessoa A, Uchoa E, de Arag˜ao MP, Rodrigues R, 2010 Exact algorithm over an arc-time-indexed formula-
               tion for parallel machine scheduling problems. Mathematical Programming Computation 2(3):259–
               290.
            Poggi M, Uchoa E, 2014 New exact algorithms for the capacitated vehicle routing problem. Vehicle Rout-
               ing: Problems, Methods, and Applications, P. Toth, and D. Vigo (Eds), SIAM 59–86.
            Pugliese LDP, Guerriero F, 2013 A survey of resource constrained shortest path problems: Exact solution
               approaches. Networks 62(3):183–200.
            Righini G, Salani M, 2006 Symmetry helps: Bounded bi-directional dynamic programming for the ele-
               mentary shortest path problem with resource constraints. Discrete Optimization 3(3):255–273.
            Roberti R, Mingozzi A, 2014 Dynamic ng-path relaxation for the delivery man problem. Transportation
               Science 48(3):413–424.
            Solomon MM, 1987 Algorithms for the vehicle routing and scheduling problems with time window con-
               straints. Operations Research 35(2):254–265.
            Tilk C, Rothenb¨acher AK, Gschwind T, Irnich S, 2017 Asymmetry matters: Dynamic half-way points in
               bidirectional labeling for solving shortest path problems with resource constraints faster. European
               Journal of Operational Research 261(2):530 – 539.
            Vanderbeck F, Sadykov R, Tahiri I, 2017 BaPCod — a generic Branch-And-Price Code. URL
               https://realopt.bordeaux.inria.fr/?page id=2.
            Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W, 2012 A hybrid genetic algorithm for multidepot
               and periodic vehicle routing problems. Operations Research 60(3):611–624.
            Vidal T, Crainic TG, Gendreau M, Prins C, 2013 A hybrid genetic algorithm with adaptive diversity
               management for a large class of vehicle routing problems with time-windows. Computers and Op-
               erations Research 40(1):475 – 489.
            A Detailed results
            In this appendix, we present the detailed results for our BCP algorithm on all tested instances.
              In the following tables, we show the instance name, n — the number of customers, m — the
            number of different vehicle types or the number of depots, when applicable, the initial upper
            bound, the “robust” dual bound (before adding non-robust cuts), the dual bound obtained in the
            root node, the root node time, the number of R1Cs at the end of the root node, the number of
            nodes, the total time, and the best solution value obtained by the algorithm. For instances solved
            before by another algorithm in the literature, we give the corresponding time (which takes into
            account the difference between the speed of the computers used), and the improvement factor
                                      33
                      (ratio of the running times of the literature algorithm and ours). In Tables 9–15, “Time PCDU”
                      refers to the running time of the algorithm by Pecin et al. (2017a). In Tables 22–23, “Time CM”
                      refers to the running time of the algorithm by Contardo and Martinelli (2014). In the tables,
                      ∗ near the best solution value indicates that its optimality was proven for the first time. If the
                      best solution value is underlined, it improves on the best known solution value. All obtained
                      solutions were proven to be optimal except when the total time is given with the “>” sign.
                       Instance   Initial  Robust              Root              Nodes     Total    Final     Time     Improv.
                                   UB      bound     bound     time     #R1C number         time     UB      PCDU       factor
                       C203        588.8     588.7    588.7       27s        0         1      27s    588.7    6m05s        13.3
                       C204        588.2     588.1    588.1       40s        0         1      40s    588.1   27m28s        40.9
                       R202       1029.7    1022.2   1029.6    2m25s        72         1   2m25s    1029.6    5m16s         2.2
                       R203        870.9     866.9    870.8    1m16s        17         1   1m16s     870.8    9m25s         7.4
                       R204        731.4     724.9    731.3    3m04s        56         1   3m04s     731.3   24m55s         8.1
                       R206        876.0     866.8    875.9    2m30s        51         1   2m30s     875.9    9m06s         3.6
                       R207        794.1     790.1    794.0    1m43s        27         1   1m43s     794.0   12m08s         7.0
                       R208        701.1     691.6    697.7   14m57s      138          9   1h14m     701.0   17h48m        14.3
                       R209        854.9     841.4    854.8    3m45s      105          1   3m45s     854.8    9m59s         2.7
                       R210        900.6     889.4    900.5    4m34s      107          1   4m34s     900.5   12m09s         2.7
                       R211        746.8     734.6    746.7    3m42s      110          1   3m42s     746.7   22m00s         5.9
                       RC204       783.6     779.3    783.5    2m11s        15         1   2m11s     783.5   19m27s         8.9
                       RC207       963.0     947.3    962.9    3m21s        91         1   3m21s     962.9    5m47s         1.7
                       RC208       776.2     766.6    776.1    2m02s        36         1   2m02s     776.1    9m59s         4.9
                                        Table 9:   Detailed results for the hardest 100-customers Solomon
                                        VRPTWinstances
                       Instance   Initial  Robust             Root              Nodes     Total    Final    Time     Improv.
                                   UB      bound     bound     time    #R1C number        time      UB      PCDU      factor
                       C1 2 1     2698.7    2698.6   2698.6       8s        0         1       8s  2698.6       20s        2.2
                       C1 2 2     2694.4    2694.3   2694.3      20s        0         1      20s  2694.3       44s        2.1
                       C1 2 3     2675.9    2659.7   2675.8   4m39s       66          1   4m39s   2675.8   10m26s         2.2
                       C1 2 4     2625.7    2619.8   2625.6   6m51s       42          1   6m51s   2625.6     5m40s        0.8
                       C1 2 5     2695.0    2694.9   2694.9      11s        0         1      11s  2694.9       24s        2.1
                       C1 2 6     2695.0    2694.9   2694.9      15s        0         1      15s  2694.9       26s        1.7
                       C1 2 7     2695.0    2694.9   2694.9      18s        0         1      18s  2694.9       22s        1.2
                       C1 2 8     2684.1    2683.7   2684.0      19s        0         1      19s  2684.0       28s        1.4
                       C1 2 9     2639.7    2637.2   2639.6      54s        0         1      54s  2639.6     1m24s        1.5
                       C1 2 10    2624.8    2620.2   2624.7   2m40s       34          1   2m40s   2624.7     1m53s        0.7
                                       Table 10: Detailed results for 200-customer Gehring and Homberger
                                       VRPTWinstances of class C1
                       Instance   Initial  Robust              Root              Nodes      Total     Final     Time     Improv.
                                   UB      bound     bound     time     #R1C number         time       UB      PCDU       factor
                       C2 2 1     1922.2    1915.0   1922.1    3m06s        70         1    3m06s     1922.1   14m20s         4.6
                       C2 2 2     1851.5    1839.4   1851.4    6m57s        80         1    6m57s     1851.4    1h29m        12.9
                       C2 2 3     1763.5    1737.0   1752.1   32m16s      287         37   11h10m    1763.4∗     >96h       >8.6
                       C2 2 4     1695.1    1652.3   1663.2   28m59s      187        355     >60h     1695.1     >96h          −
                       C2 2 5     1869.7    1858.7   1869.6    3m57s        52         1    3m57s     1869.6   23m48s         6.0
                       C2 2 6     1844.9    1836.6   1844.8    3m22s        23         1    3m22s     1844.8   34m03s        10.1
                       C2 2 7     1842.3    1834.9   1842.2    3m03s        21         1    3m03s     1842.2   44m33s        14.6
                       C2 2 8     1813.8    1801.3   1813.7    3m11s        12         1    3m11s     1813.7   42m22s        13.3
                       C2 2 9     1815.1    1795.0   1815.0    9m17s      101          1    9m17s     1815.0    2h01m        13.1
                       C2 2 10    1791.3    1765.7   1791.2   13m04s        96         1   13m04s     1791.2    2h56m        13.5
                                         Table 11: Detailed results for 200-customer Gehring and Homberger
                                         VRPTWinstances of class C2
                                                                      34
                       Instance   Initial  Robust              Root              Nodes      Total     Final    Time     Improv.
                                   UB      bound     bound     time     #R1C number         time      UB       PCDU      factor
                       R1 2 1     4667.3    4655.0   4667.2       14s       22         1       14s   4667.2       59s        4.0
                       R1 2 2     3920.0    3907.2   3919.9       37s       75         1       37s   3919.9    2m42s         4.3
                       R1 2 3     3374.0    3320.3   3352.5   13m27s      502        693   17h01m    3373.9   25h56m         1.5
                       R1 2 4     3047.7    3001.5   3035.3   23m03s      635        267   10h45m    3047.6    5h00m         0.5
                       R1 2 5     4053.3    4007.6   4044.8    3m21s      290          9   10m51s    4053.2    7m25s         0.7
                       R1 2 6     3559.3    3493.4   3545.3   11m16s      559         71    2h00m    3559.1    2h00m         1.0
                       R1 2 7     3142.0    3099.2   3141.9    9m27s      335          1    9m27s    3141.9   16m42s         1.8
                       R1 2 8     2938.5    2902.2   2933.9   19m02s      436          5   27m38s    2938.4   41m39s         1.5
                       R1 2 9     3734.8    3678.3   3726.4    6m23s      443          7   14m43s    3734.7   12m51s         0.9
                       R1 2 10    3293.2    3244.9   3278.2    8m35s      489         49    1h47m    3293.1    1h23m         0.8
                                         Table 12: Detailed results for 200-customer Gehring and Homberger
                                         VRPTWinstances of class R1
                       Instance   Initial  Robust              Root              Nodes      Total     Final     Time     Improv.
                                   UB      bound     bound     time     #R1C number         time       UB       PCDU      factor
                       R2 2 1     3468.1    3462.5   3468.0    2m20s        19         1    2m20s     3468.0   34m43s        14.9
                       R2 2 2     3008.3    3000.9   3008.2    7m33s        69         1    7m33s     3008.2    1h07m         9.0
                       R2 2 3     2537.6    2516.3   2537.5   33m26s      181          1   33m26s     2537.5    5h50m        10.5
                       R2 2 4     1928.6    1918.3   1924.9   33m39s        94        33    3h59m    1928.5∗     >96h      >24.0
                       R2 2 5     3061.2    3029.4   3061.1   21m41s      123          1   21m41s     3061.1    1h45m         4.9
                       R2 2 6     2675.5    2644.9   2675.2   37m20s      249          3   50m39s     2675.4    4h04m         4.8
                       R2 2 7     2304.8    2277.8   2304.7   1h48m       335          1    1h48m     2304.7   12h16m         6.8
                       R2 2 8     1842.5    1808.9   1832.1   1h41m       393         19   11h47m    1842.4∗     >96h       >8.1
                       R2 2 9     2843.4    2824.3   2843.3   12m37s      110          1   12m37s     2843.3    1h23m         6.6
                       R2 2 10    2549.5    2528.7   2545.4   15m33s      202          3   24m04s     2549.4    3h14m         8.1
                                         Table 13: Detailed results for 200-customer Gehring and Homberger
                                         VRPTWinstances of class R2
                        Instance   Initial  Robust              Root              Nodes      Total     Final    Time     Improv.
                                    UB      bound     bound     time     #R1C number         time      UB       PCDU      factor
                       RC1 2 1     3517.0    3459.6   3498.7    4m26s       338        43   40m29s    3516.9   42m10s         1.0
                       RC1 2 2     3221.7    3177.8   3206.1   11m52s       522        17   33m38s    3221.6    3h10m         5.7
                       RC1 2 3     3001.5    2952.1   2982.9   22m40s       630       187   14h41m    3001.4   18h15m         1.2
                       RC1 2 4     2845.3    2814.4   2831.0   26m52s       361        41    4h58m    2845.2    6h23m         1.3
                       RC1 2 5     3325.7    3272.9   3312.7   49m59s       678        15    1h22m    3325.6    2h23m         1.7
                       RC1 2 6     3300.8    3255.3   3295.1   12m30s       468         5   16m35s    3300.7   26m46s         1.6
                       RC1 2 7     3177.9    3114.7   3151.8   17m14s       554       109   10h46m    3177.8   52h20m         4.9
                       RC1 2 8     3060.1    3022.6   3047.4   19m03s       614         5   49m56s    3060.0    2h50m         3.4
                       RC1 2 9     3074.9    3006.6   3035.6   16m42s       464       493     >60h    3074.9     >96h          −
                       RC1 2 10    2990.6    2938.7   2966.4   24m40s       583       683     >60h    2990.6     >96h          −
                                         Table 14: Detailed results for 200-customer Gehring and Homberger
                                         VRPTWinstances of class RC1
                        Instance   Initial  Robust              Root              Nodes      Total     Final     Time     Improv.
                                    UB      bound     bound     time     #R1C number         time       UB       PCDU      factor
                       RC2 2 1     2797.5    2789.4   2797.4    4m11s        38         1    4m11s     2797.4   35m49s         8.6
                       RC2 2 2     2481.7    2469.5   2477.0   19m21s       183         3   39m25s     2481.6    4h50m         7.4
                       RC2 2 3     2227.8    2204.7   2227.7    1h54m       308         1    1h54m     2227.7   13h32m         7.1
                       RC2 2 4     1854.9    1839.7   1848.3    1h33m       196        31   10h52m    1854.8∗     >96h       >8.8
                       RC2 2 5     2493.6    2479.0   2491.4   13m36s       142         1   13m36s     2491.4    1h25m         6.3
                       RC2 2 6     2496.4    2475.6   2495.1   14m09s        83         1   14m09s     2495.1    1h33m         6.6
                       RC2 2 7     2287.8    2271.2   2279.0   17m22s        98        11   59m07s     2287.7    8h11m         8.3
                                                                      35
                       RC2 2 8     2151.3   2140.7   2151.2   29m09s        92         1   29m09s     2151.2   23h05m       47.5
                                                                                                           ∗
                       RC2 2 9     2086.7   2056.5   2071.1    1h54m      240       109    59h29m    2086.6      >96h       >1.6
                       RC2 2 10    1989.3   1953.2   1955.8   51m23s        12      201      >60h     1989.2     >96h         −
                                         Table 15: Detailed results for 200-customer Gehring and Homberger
                                         VRPTWinstances of class RC2
                             Instance  Initial  Robust              Root              Nodes     Total     Final
                                         UB      bound    bound     time    #R1C number          time      UB
                                                                                                               c
                             C1 4 1    7138.9    7138.8   7138.8    1m34s        0         1    1m34s    7138.8
                                                                                                               ∗
                             C1 4 2    7113.2    7095.0   7102.2    6m13s       79         3    7m17s    7113.2
                                                                                                               ∗
                             C1 4 3    6930.0    6919.8   6929.9   12m51s       81         1   12m51s    6929.9
                             C1 4 4    6777.8    6769.6   6777.7   45m22s      118         1   45m22s    6777.7∗
                                                                                                               ∗
                             C1 4 5    7138.9    7138.8   7138.8    1m58s        0         1    1m58s    7138.8
                                                                                                               ∗
                             C1 4 6    7140.2    7140.1   7140.1    2m11s        0         1    2m11s    7140.1
                                                                                                               ∗
                             C1 4 7    7136.3    7135.9   7136.2    2m27s        0         1    2m27s    7136.2
                                                                                                               ∗
                             C1 4 8    7107.1    7030.0   7071.2   13m02s      277        61    2h07m    7083.0
                             C1 4 9    6927.9    6888.3   6927.8   22m43s      355         1   22m43s    6927.8∗
                                                                                                               ∗
                             C1 4 10   6825.5    6798.8   6819.2   44m59s      347        13    1h02m    6825.4
                             c this instance has been solved before by Kallehauge, Larsen, and Madsen (2006)
                                    Table 16: Detailed results for 400-customer Gehring and Homberger
                                    VRPTWinstances of class C1
                            Instance   Initial  Robust              Root              Nodes     Total     Final
                                        UB      bound     bound     time     #R1C number         time      UB
                                                                                                               ∗
                            C2 4 1     4100.4    4088.4   4100.3   15m08s       35         1   15m08s    4100.3
                            C2 4 2     3914.2    3897.5   3914.1   9h39m       283         1    9h39m    3914.1∗
                            C2 4 3     3755.3    3722.7   3740.8  60h00m       566         1     >60h     3755.3
                            C2 4 4     3524.1    3483.3   3498.4   3h00m       288        11     >60h     3524.1
                                                                                                               ∗
                            C2 4 5     3923.3    3919.7   3923.2   23m01s       58         1   23m01s    3923.2
                                                                                                               ∗
                            C2 4 6     3860.2    3843.8   3860.1   39m33s       99         1   39m33s    3860.1
                                                                                                               ∗
                            C2 4 7     3871.0    3861.6   3870.9   29m47s       82         1   29m47s    3870.9
                            C2 4 8     3773.8    3743.4   3770.6   1h11m       397         9    4h29m    3773.7∗
                            C2 4 9     3843.8    3782.0   3815.9   4h09m       542        15     >60h     3843.8
                            C2 4 10    3665.2    3616.9   3656.2   2h33m       682        73     >60h     3665.1
                                    Table 17: Detailed results for 400-customer Gehring and Homberger
                                    VRPTWinstances of class C2
                           Instance   Initial   Robust              Root               Nodes     Total     Final
                                       UB       bound     bound      time    #R1C number         time       UB
                                                                                                                 ∗
                           R1 4 1    10313.9   10243.5   10284.1    4m00s       181        25   16m48s    10305.8
                           R1 4 2      8876.0   8776.2    8834.3   17m52s       534      1683     >60h      8876.0
                           R1 4 3      7794.8   7673.7    7732.2   54m14s       658       327     >60h      7794.8
                           R1 4 4      7281.8   7182.4    7239.2    2h06m      1095       123     >60h      7281.8
                           R1 4 5      9188.7   9082.3    9145.8    6m35s       355      2393     >60h      9188.7
                           R1 4 6      8366.6   8257.8    8314.1   28m04s       596      1139     >60h      8366.6
                           R1 4 7      7609.1   7489.2    7558.6    1h25m      1020       185     >60h      7609.1
                           R1 4 8      7253.5   7148.5    7200.0    1h57m       967       147     >60h      7253.5
                           R1 4 9      8674.8   8545.7    8618.4   13m45s       611      1265     >60h      8674.8
                           R1 4 10     8088.9   7944.9    8024.2   31m57s       782       611     >60h      8088.9
                                    Table 18: Detailed results for 400-customer Gehring and Homberger
                                    VRPTWinstances of class R1
                                                                     36
                             Instance   Initial Robust               Root              Nodes      Total     Final
                                         UB      bound    bound      time    #R1C number          time       UB
                             R2 4 1    7522.1    7485.3   7520.7   42m42s        96          1   42m42s    7520.7∗
                                                                                                                 ∗
                             R2 4 2    6482.9    6466.3   6482.8    1h33m       127          1    1h33m    6482.8
                                                                                                                 ∗
                             R2 4 3    5373.0    5349.3   5372.9    6h18m       333          1    6h18m    5372.9
                             R2 4 4    4213.8    4144.1   4169.8   12h06m      1131         15     >60h     4213.8
                             R2 4 5    6572.1    6498.0   6559.6   10h06m       450          3     >60h     6572.1
                             R2 4 6    5814.6    5763.1   5811.8   24h11m      1423          3     >60h     5814.6
                             R2 4 7    4893.6    4843.2   4878.4   15h39m      1492         11     >60h     4893.6
                             R2 4 8    4001.1    3897.7   3913.9   20h11m       444          9     >60h     4001.1
                                                                                                                 ∗
                             R2 4 9    6070.3    6001.5   6059.4    3h44m       704         25   58h55m    6067.8
                             R2 4 10   5665.1    5561.6   5619.5    4h09m       758         21     >60h     5665.1
                                     Table 19: Detailed results for 400-customer Gehring and Homberger
                                     VRPTWinstances of class R2
                              Instance    Initial  Robust              Root              Nodes     Total   Final
                                           UB      bound     bound     time    #R1C number         time     UB
                              RC1 4 1     8523.0    8368.9   8470.0   16m38s      762       667    >60h    8523.0
                              RC1 4 2     7887.2    7770.3   7843.0   49m29s     1123       197    >60h    7887.2
                              RC1 4 3     7525.2    7423.3   7444.7   44m01s      252       269    >60h    7525.2
                              RC1 4 4     7295.3    7207.8   7242.9   1h43m       805         37   >60h    7295.3
                              RC1 4 5     8152.4    8033.8   8101.5   44m15s     1115         37   >60h    8152.4
                              RC1 4 6     8148.6    8005.9   8089.7   47m39s     1192       127    >60h    8148.6
                              RC1 4 7     7937.0    7830.6   7878.9   48m09s      841       235    >60h    7937.0
                              RC1 4 8     7765.8    7639.3   7679.0   42m19s      574       201    >60h    7765.8
                              RC1 4 9     7724.4    7604.8   7639.1   48m15s      455       209    >60h    7724.4
                              RC1 4 10    7583.2    7479.2   7521.6   1h42m       931         33   >60h    7583.2
                                     Table 20: Detailed results for 400-customer Gehring and Homberger
                                     VRPTWinstances of class RC1
                             Instance   Initial  Robust              Root               Nodes     Total     Final
                                         UB      bound     bound     time     #R1C number          time      UB
                            RC2 4 1     6147.4    6120.1   6146.6    3h18m       238         3    3h37m    6147.3∗
                            RC2 4 2     5407.6    5389.5   5407.5    4h06m       458         1    4h06m    5407.5∗
                            RC2 4 3     4573.1    4549.6   4573.0   35h25m      1294         1   35h25m    4573.0∗
                            RC2 4 4     3598.0    3535.9   3535.9    8h25m         0         5     >60h     3598.0
                            RC2 4 5     5396.7    5363.0   5388.6    4h47m       466         7     >60h     5396.7
                            RC2 4 6     5332.1    5270.9   5308.5    9h04m       738         3     >60h     5332.1
                            RC2 4 7     4987.9    4944.9   4968.6    6h08m       453        19     >60h     4987.9
                            RC2 4 8     4703.2    4602.0   4618.7    4h53m       216        31     >60h     4703.2
                            RC2 4 9     4519.1    4448.9   4457.0    5h35m       278        21     >60h     4519.1
                            RC2 4 10    4252.4    4157.0   4157.0    2h11m         0        83     >60h     4252.4
                                     Table 21: Detailed results for 400-customer Gehring and Homberger
                                     VRPTWinstances of class RC2
                       Inst.   n    m Initial      Robust               Root              Nod.     Total      Final       Time     Impr.
                                           UB       bound     bound      time    #R1C num.         time        UB         CM       factor
                       p08    249    2   4372.90   4294.01   4347.67   49m01s       567      29    5h43m    4372.78∗,a        −       −
                       p09    249    3   3858.80   3798.47   3849.96    1h34m       650      19    2h25m      3858.66∗        −       −
                       p10    249    4   3631.30   3582.48   3626.26   37m26s       522       3   41m46s    3631.11∗,a        −       −
                       p11    249    5   3546.20   3488.64   3540.43   44m15s       597       3   49m46s    3546.06∗,a        −       −
                       p13     80    2   1319.10   1318.95   1318.95         1s       0       1        1s      1318.95       31s    17.5
                       p14     80    2   1360.30   1360.12   1360.12         1s       0       1        1s      1360.12       38s    20.5
                       p16    160    4   2572.40   2572.23   2572.23       12s        0       1       12s      2572.23    8m27s     39.7
                                                                      37
                      p17    160    4   2709.20   2709.09   2709.09      55s        0      1       55s     2709.09    8m07s       8.8
                      p19    240    6   3827.20   3822.92   3827.06    1m25s        0      1    1m25s      3827.06   37m15s      26.3
                      p20    240    6   4058.20   4058.07   4058.07    2m30s        0      1    2m30s      4058.07   38m47s      15.5
                                                                                                                 ∗
                      p22    360    9   5702.30   5693.87   5702.16    2m28s        0      1    2m28s     5702.16         −        −
                                                                                                                 ∗
                      p23    360    9   6078.90   6078.75   6078.75    5m52s        0      1    5m52s     6078.75         −        −
                      a a solution with smaller value is claimed in Escobar et al. (2014),
                        however the authors were not able to communicate it to us
                                            Table 22: Detailed results for Cordeau et al. MDVRP instances of class
                                            “p”
                      Inst.   n    m Initial      Robust              Root              Nod.    Total      Final     Time      Impr.
                                          UB      bound     bound      time    #R1C num.         time       UB        CM       factor
                      pr01     48   4    861.40    861.32    861.32       3s        0      1         3s    861.32        0s       0.03
                      pr02     96   4   1307.50   1287.52   1307.34    4m18s      110      1     4m18s   1307.34∗     >75h    >1042.8
                      pr03   144    4   1803.90   1773.42   1803.80  10m22s       185      1    10m22s    1803.80   31h11m       180.5
                      pr04   192    4   2058.50   2029.87   2058.31  22m52s       327      1    22m52s   2058.31∗     >75h     >196.7
                      pr05   240    4   2331.30   2293.32   2318.80   1h14m       628     27    6h19m    2331.20∗         −         −
                      pr06   288    4   2676.40   2635.08   2662.92   1h18m       522     21    6h39m    2676.30∗         −         −
                      pr07     72   6   1089.70   1085.59   1089.56      17s        0      1        17s   1089.56   18m28s        63.8
                      pr08   144    6   1665.00   1640.18   1664.85    8m42s      105      1     8m42s    1664.85   11h53m        82.0
                      pr09   216    6   2133.30   2109.20   2133.20  23m06s       242      1    23m06s   2133.20∗     >75h     >194.8
                      pr10   288    6   2868.40   2818.03   2850.68   1h40m       583     77   24h06m    2867.26∗         −         −
                                            Table 23: Detailed results for Cordeau et al. MDVRP instances of class
                                            “pr”
                      Instance    n    m Initial      Robust              Root              Nodes     Total      Final
                                             UB       bound     bound     time     #R1C number         time      UB
                                                                                                                      ∗
                      pr01        48    4   1380.90  1377.09   1380.77       19s        0        1       19s   1380.77
                                                                                                                      ∗
                      pr02        96    4   2304.00  2283.37   2303.89    2m51s        23        1    2m51s    2303.89
                      pr03       144    4   2575.50  2538.93   2565.67   19m01s      248         7   24m12s    2574.56∗
                      pr04       192    4   3450.00  3396.73   3432.33   42m22s      453         9    1h47m    3449.84∗
                      pr05       240    4   4377.50  4288.21   4332.64   46m35s      442       217     >60h     4375.67
                      pr06       288    4   4422.20  4326.08   4329.25   21m45s        21      353     >60h     4421.95
                                                                                                                      ∗
                      pr07        72    6   1890.00  1868.89   1889.82    6m30s         0        1    6m30s    1889.82
                      pr08       144    6   2971.20  2933.81   2962.61   25m44s      222         7   32m37s    2969.92∗
                      pr09       216    6   3536.30  3511.38   3527.76    1h00m      239         5    1h03m    3536.20∗
                      pr10       288    6   4639.80  4537.82   4559.48   48m34s      246       297     >60h     4639.80
                                      Table 24: Detailed results for Cordeau and Laporte SDVRP instances
                       Instance   n     Initial  Robust              Root               Nodes     Total      Final
                                         UB      bound     bound      time    #R1C number         time        UB
                                                                                                                   ∗
                       CMT6       50    555.60    540.52    555.43       7s       49         1        7s     555.43
                                                                                                                   ∗
                       CMT7       75    909.80    898.95    909.68       4s       35         1        4s     909.68
                                                                                                                   ∗
                       CMT8      100    866.10    842.15    857.86    6m48s      319        17   54m47s      865.94
                                                                                                                  ∗,b
                       CMT9      150   1162.70   1133.47   1153.37    7m58s      429       447   13h48m    1162.55
                                                                                                                   ∗
                       CMT10     199   1396.00   1368.79   1387.35  16m22s       579       443   17h29m     1395.85
                       CMT13     120   1541.30   1458.00   1475.23  10m39s       281       149     >60h      1541.30
                                                                                                                   ∗
                       CMT14     100    866.50    851.24    866.37  45m22s       318         1   45m22s      866.37
                       b solution with value 1158.41, claimed in Dell’Amico et al. (2016), is infeasible
                        (different rounding convention was used)
                                      Table 25: Detailed results for Christofides et al. DCVRP instances
                                                                    38
                       Instance   n    m Initial     Robust                Root               Nodes      Total      Final
                                             UB       bound      bound      time     #R1C number         time        UB
                                                                                                                          ∗
                       DLP 75     20    3     453      448.43     452.85        0s        6         1        0s     452.85
                       DLP 92     35    3     565      553.05     559.82    4m58s       110         5    9m39s      564.39∗
                       DLP 93     39    3    1037     1011.57    1023.69       12s       46        11    1m39s     1036.99∗
                       DLP 94     46    5    1379     1369.07    1378.25       17s       42         1       17s    1378.25∗
                                                                                                                          ∗
                       DLP 55     56    3   10245   10134.23    10244.34       38s       29         1       38s   10244.34
                                                                                                                          ∗
                       DLP 52     59    3    4028     3912.72    3931.40    2m59s        53        11   12m57s     4027.27
                                                                                                                          ∗
                       DLP 10     69    4    2108     2048.67    2060.75    3m00s        77        13   18m38s     2107.55
                                                                                                                          ∗
                       DLP 39     77    5    2922     2874.88    2902.55    6m03s       302        25   28m47s     2918.87
                                                                                                                          ∗
                       DLP 70     78    4    6685     6561.07    6659.88    5m02s       252         3   13m53s     6684.56
                       DLP 82     79    3    4767     4630.03    4648.96    1m10s       107       123    1h12m     4718.27∗
                       DLP 08     84    3    4592     4569.97    4591.75        2s        0         1        2s    4591.75∗
                                                                                                                          ∗
                       DLP 36     85    6    5685     5610.15    5684.62    1m29s       115         1    1m29s     5684.62
                       DLP 43     86    7    8738     8686.41    8737.02       43s       31         1       43s    8737.02∗
                       DLP 01     92    4    9211     8974.44    9081.63   10m33s       158         3   24m37s     9210.14∗
                                                                                                                          ∗
                       DLP 11     95    4    3368     3288.08    3296.82    3m19s        31         9   20m54s     3367.41
                                      Table 26: Detailed results for Duhamel et al. HFVRP instances with up
                                      to 100 customers
                       Instance    n    m Initial     Robust                Root                Nodes     Total       Final
                                              UB       bound      bound      time     #R1C number          time       UB
                                                                                                                            ∗
                       DLP 90     102    4    2347     2249.36    2257.75    5m05s       136       655   40h29m     2278.05
                       DLP 17     105    3    5363     5278.74    5326.71    2m50s       131         7     3m30s    5362.83∗
                       DLP 84     105    4    7228     7117.02    7142.28    2m02s       136        19   21m01s     7227.88∗
                       DLP 81     106    4   10687    10483.95   10521.23    3m06s       182       313    5h36m    10583.50∗
                       DLP 2B     107    6    8463     8300.92    8332.22    4m17s        37      1639     >60h      8463.00
                       DLP 07     108    4    8090     8009.35    8049.38    3m51s       104        19   12m07s     8071.97∗
                       DLP 87     108    4    3754     3658.33    3692.55    6m32s       236         7   29m51s     3753.87∗
                       DLP 47     111    5   16157    15971.69   16123.03    3m54s       250         5     5m49s   16156.12∗
                       DLP 48     111    5   21310    21041.94   21228.34   19m51s       321         7   28m25s    21257.38∗
                       DLP 61     111    3    7293     6997.61    7027.77    3m15s        33      1435     >60h      7293.00
                                                                                                                            ∗
                       DLP 12     112    4    3544     3410.14    3410.14    1m53s         0        25    1h39m     3543.99
                                                                                                                            ∗
                       DLP 30     112    3    6314     6185.97    6207.60    4m11s       186      1489   31h29m     6278.62
                       DLP 2A     113    6    7794     7708.25    7793.16    1m42s        77         1     1m42s    7793.16∗
                                                                                                                            ∗
                       DLP 53     115    3    6435     6281.51    6376.47   12m26s       209        31    2h14m     6434.83
                       DLP 05     116    5   10877    10764.90   10869.04       29s       30         1       29s   10869.04∗
                       DLP 13     119    5    6697     6618.19    6649.75    5m20s       160      1261     >60h      6696.43
                       DLP 06     121    8   11689    11618.62   11682.98    2m37s        53         1     2m37s   11682.98∗
                       DLP 03     124    4   10710    10635.69   10669.77       55s      106         5     1m13s   10709.66∗
                                                                                                                            ∗
                       DLP 83     124    4   10020     9871.11    9899.78    2m33s       127        59   51m57s    10001.80
                                                                                                                            ∗
                       DLP 68     125    4    8971     8799.96    8852.89    5m39s       192        89    3h00m     8889.03
                       DLP 74     125    5   11587    11543.40   11563.64       41s       78         7     4m18s   11586.58∗
                       DLP 21     126    3    5140     5079.13    5110.52    8m11s       289        11   25m05s     5139.84∗
                                                                                                                            ∗
                       DLP 26     126    5    6434     6352.66    6382.52    6m00s       230       453   10h10m     6406.16
                       DLP 88     127    5   12389    12328.90   12385.74       29s       25         1       29s   12385.74∗
                       DLP 16     129    6    4157     4000.74    4006.42    4m33s        16      1573     >60h      4157.00
                       DLP 51     129    3    7722     7628.81    7666.22   10m11s       123         3   29m17s     7721.47∗
                       DLP 31     131    8    4092     4045.03    4083.80   15m20s       284         5   18m24s     4091.52∗
                       DLP 40     132    5   11119    10974.62   11015.52    2m32s       160       317    2h59m    11056.13∗
                       DLP 89     134    5    7087     6982.53    7023.43    4m11s       239      1027     >60h      7087.00
                       DLP 41     135    7    7598     7444.36    7444.36    4m48s         0      3305     >60h      7598.00
                                                                                                                            ∗
                       DLP 34     136    6    5748     5700.07    5727.33    7m35s       306        27    1h10m     5739.02
                       DLP 60     137    4   17037    16768.33   16934.97    5m40s       285        37   44m38s    17012.42∗
                       DLP 73     137    5   10196    10138.46   10174.15       57s       88         3     2m07s   10195.33∗
                       DLP 28     141    5    5531     5478.74    5499.59    4m24s       208      4705     >60h      5525.90
                       DLP 25     143    6    7207     7030.07    7042.25    5m46s       100       959     >60h      7207.00
                                                                                                                            ∗
                       DLP 85     146    4    8774     8690.09    8726.51    7m27s       295       111    2h40m     8763.90
                                                                      39
                                                                                                                        ∗
                      DLP 79     147    4    7260    7132.58    7165.36    8m22s      187        21    1h13m     7257.97
                      DLP 66     150    4   12784   12484.59   12587.01    8m31s      104       999     >60h     12776.24
                                      Table 27: Detailed results for Duhamel et al. HFVRP instances with
                                      101–150 customers
                      Instance    n    m Initial     Robust               Root               Nodes     Total      Final
                                             UB      bound      bound      time    #R1C number          time       UB
                                                                                                                        ∗
                      DLP 69     152    4    9148    9003.97    9086.90    7m52s      335       147    3h36m     9127.16
                      DLP 76     152    8   11995   11900.23   11933.72    5m28s      212      1195     >60h     11994.22
                      DLP 56     153    4   31031   30571.34   30764.30    8m26s      250      1591   58h50m    30905.95∗
                                                                                                                        ∗
                      DLP 86     153    5    9028    8935.26    8957.90    8m23s      274       249    8h45m     9020.63
                      DLP 37     161    5    6851    6751.15    6787.92    7m57s      354      2017     >60h      6838.72
                      DLP 64     161    3   17136   16552.72   16552.72    6m38s       25       995     >60h     17135.16
                      DLP 24     163    4    9102    8990.07    8990.07    3m26s        0      1907     >60h      9102.00
                      DLP 57     163    4   44782   44302.32   44409.19    8m53s      194      1565     >60h     44782.00
                                                                                                                        ∗
                      DLP 29     164    4    9143    9044.54    9078.84    9m59s      182        43    2h18m     9132.03
                                                                                                                        ∗
                      DLP 09     167    5    7604    7543.04    7563.84   12m52s      274       135    2h16m     7599.72
                      DLP 35     168    6    9556    9492.98    9521.16    2m55s      114         3    3m17s     9522.45∗
                      DLP 45     170    3   10477   10294.91   10343.43    8m34s      124       929     >60h     10477.00
                                                                                                                        ∗
                      DLP 80     171    3    6817    6712.75    6716.88    8m39s       29       219   13h07m     6816.89
                      DLP 44     172    3   12192   11895.60   11895.60   12m31s       19      1187     >60h     12192.00
                      DLP 54     172    4   10352   10089.37   10089.37    7m45s       21      1323     >60h     10352.00
                      DLP 67     172    5   10885   10604.14   10662.94    9m53s      233       325   23h44m    10772.81∗
                      DLP 63     174    5   19952   19670.12   19799.92    8m54s      108        97    5h24m    19890.65∗
                      DLP 14     176    4    5645    5511.85    5511.85    4m37s        0      1023     >60h      5639.98
                      DLP 42     178    7   10818   10615.08   10615.08    7m00s        0       889     >60h     10805.94
                                                                                                                        ∗
                      DLP 02     181    4   11676   11603.82   11632.01    4m27s      104        25    9m34s    11649.81
                      DLP 04     183    4   10749   10582.45   10673.39    9m41s      277       985   13h53m    10714.84∗
                      DLP 95     183    2    6176    6100.98    6119.06    6m53s      290      1709     >60h      6170.20
                                                                                                                        ∗
                      DLP 71     186    3    9835    9711.77    9771.86   10m30s      292        87    4h08m     9798.06
                                                                                                                        ∗
                      DLP 72     186    4    5904    5780.39    5831.66    9m35s      322       365   31h31m     5870.43
                      DLP 50     187    6   12371   12035.29   12035.29    9m56s        0      1521     >60h     12371.00
                      DLP 15     188    7    8221    8083.44    8083.44    3m27s        0       873     >60h      8221.00
                      DLP 33     189    7    9411    9248.07    9283.05    9m51s      135      1129     >60h      9333.39
                      DLP 77     190    3    6917    6821.36    6826.04    7m49s       10      1215     >60h      6917.00
                      DLP 78     190    4    7036    6899.96    6899.96    6m40s        0      1099     >60h      7036.00
                      DLP 59     193    6   14283   13786.96   13786.96   23m42s        0       737     >60h     14283.00
                      DLP 91     196    4    6375    6228.90    6244.50   10m26s      157      1167     >60h      6348.36
                                      Table 28: Detailed results for Duhamel et al. HFVRP instances with
                                      151–200 customers
                      Instance    n    m Initial     Robust               Root               Nodes    Total    Final
                                             UB      bound      bound      time    #R1C number        time      UB
                      DLP 23     203    4    7742    7590.28    7603.76    8m46s       70      1043   >60h     7742.00
                      DLP 38     205    5   11195   11048.66   11092.13   14m28s      375       869   >60h    11195.00
                      DLP 58     220    6   23371   22800.97   22800.97   36m42s       10       969   >60h    23371.00
                      DLP 27     220    5    8423    8315.95    8343.41   10m15s      174       687   >60h     8423.00
                      DLP 65     223    3   13044   12648.64   12648.64   41m17s       24       657   >60h    13044.00
                      DLP 19     224    5   11687   11503.00   11526.84    8m25s       98      1053   >60h    11687.00
                      DLP 62     225    5   23011   22594.36   22645.25   13m36s       47      1047   >60h    22987.90
                      DLP 22     239    2   13069   12923.02   12956.02   13m12s      357      1193   >60h    13050.00
                      DLP 32     244    8    9383    9205.76    9235.38   14m29s      108       695   >60h     9383.00
                      DLP 49     246    8   16182   15681.80   15681.80   15m27s        0       735   >60h    16182.00
                      DLP 46     250    5   24567   23856.71   23856.71   14m14s       21       913   >60h    24567.00
                      DLP 18     256    5    9653    9491.55    9547.80   22m29s      519      1159   >60h     9649.05
                                    Table 29: Detailed results for Duhamel et al. HFVRP instances with
                                    more than 200 customers
                                                                    40