Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoff

Faldum, Stefan; Machate, Sarah; Gschwind, Timo; Irnich, Stefan Article — Published Version Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a singlesegment tradeoff OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Faldum, Stefan; Machate, Sarah; Gschwind, Timo; Irnich, Stefan (2024) : Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoff, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 46, Iss. 4, pp. 1063-1097, https://doi.org/10.1007/s00291-024-00766-y This Version is available at: https://hdl.handle.net/10419/313820 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2024) 46:1063–1097 https://doi.org/10.1007/s00291-024-00766-y 1 3 ORIGINAL ARTICLE Partial dominance inbranch‑price‑and‑cut algorithms forvehicle routing andscheduling problems withasingle‑segment tradeoff StefanFaldum1 · SarahMachate2· TimoGschwind2 · StefanIrnich1 Received: 5 January 2024 / Accepted: 6 May 2024 / Published online: 26 June 2024 © The Author(s) 2024 Abstract For many variants of vehicle routing and scheduling problems solved by a branchprice-and-cut (BPC) algorithm, the pricing subproblem is an elementary shortestpath problem with resource constraints (SPPRC) typically solved by a dynamic-programming labeling algorithm. Solving the SPPRC subproblems consumes most of the total BPC computation time. Critical to the performance of the labeling algorithms and thus the BPC algorithm as a whole is the use of effective dominance rules. Classical dominance rules rely on a pairwise comparison of labels and have been used in many labeling algorithms. In contrast, partial dominance describes situations where several labels together are needed to dominate another label, which can then be safely discarded. In this work, we consider SPPRCs, where a linear tradeoff describes the relationship between two resources. We derive a unified partial dominance rule to be used in ad hoc labeling algorithms for solving such SPPRCs as well as insights into its practical implementation. We introduce partial dominance for two important variants of the vehicle routing problem, namely the electric vehicle routing problem with time windows with a partial recharge policy and the split-delivery vehicle routing problem with time windows (SDVRPTW). Computational experiments show the effectiveness of the approach, in particular for the SDVRPTW, leading to an average reduction of 20% of the total BPC computation time, with savings of 30% for the more difficult instances requiring more than 600s of computation time. Keywords Branch-price-and-cut· Partial dominance· Column generation· Labeling algorithm· Vehicle routing and scheduling Extended author information available on the last page of the article 1064 S.Faldum et al. 1 3 1 Introduction For many variants of the vehicle routing problem (VRP, Toth and Vigo 2014), branch-and-price (BP, Desaulniers etal. 2005) based algorithms constitute the leading exact solution methodology (Costa etal. 2019). A BP algorithm is a branch-andbound algorithm in which the lower bounds are computed by column generation. Column generation is an iterative procedure that can tackle linear programs containing a huge number of variables. At each iteration, it solves a restricted master problem (RMP) comprising only a subset of the variables of the original linear program and one or several pricing subproblems to dynamically generate missing variables with negative reduced cost or to prove that no such variable exists. Cutting planes are added to strengthen the linear relaxations giving rise to a branch-price-andcut (BPC) algorithm. For details on the theory of BPC, we refer to Barnhart etal. (1998), Lübbecke and Desrosiers (2005). The master program is often an extended set-partitioning or set-covering formulation for selecting the best routes, while the pricing subproblem is an elementary shortest-path problem with resource constraints (SPPRC) typically solved by dynamic-programming labeling algorithms (for an overview of SPPRCs and labeling algorithms, see Irnich and Desaulniers 2005). In a labeling algorithm, partial paths are gradually extended in a network from a given source o to a sink d (the origin and destination depot in the context of VRPs) seeking for a resource feasible minimum-cost o - d -path. The partial paths are represented by labels that store information on the accumulated resource consumption up to the endpoint of the partial paths. Herein, resources are quantities necessary to compute the reduced cost and, e.g., the load onboard and the start of the service, at the end of the partial path. In particular, resources are used to decide on the feasibility of partial paths. The propagation of the labels along the arcs of the network is performed with the help of resource extension functions (REFs, Irnich 2008). Crucial for the performance of a labeling algorithm is the dominance relation between partial paths. The dominance relation is a relation between labels (i.e., partial paths) used to identify and discard those that cannot lead to a better solution of the SPPRC than possible with a known partial path. Dominance is typically realized by comparing the resource values of the labels and avoids the enumeration of all feasible partial paths that can be found in the network. Classical dominance relations that have been used in many labeling algorithms rely on a pairwise comparison of labels. Informally speaking, if one of the labels is worse than the other, it can be safely discarded. Formally, we assume that the network (V,A) with source o∈V and sink d∈V are given. For a partial path p , i.e., an o -i-path ending at some vertex i∈V , any id -path q that provides a feasible o - d -path r=(p,q) is called a feasible extension of p . Now, pairwise dominance between two partial paths can be characterized with the help of feasible extensions as follows: Proposition 1 (Pairwise Dominance) Let p1 and p2 be two different partial paths ending at the same vertex i∈V . If, for each feasible extension q2 of p2 , 1065 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… (i) the path q2 is also a feasible extension of p1 , i.e., r1=(p1,q2) is feasible (ii) or there exists a feasible extension q1 of p1 (the extension q1 is allowed to differ from q2 ) so that r1=(p1,q1) is feasible, and r1 has a smaller or identical reduced cost than r2 , then the partial path p2 is dominated. Because the conditions(i) and(ii) in Proposition1 are difficult to verify for two arbitrary partial paths p1 and p2 , labeling algorithms typically test sufficient conditions, so-called dominance rules. Dominance rules do not directly consider extensions, but they compare the resource values of the labels of p1 and p2 . In contrast to pairwise dominance, partial dominance describes the situation that several labels together are, informally speaking, better than another label which can then be safely discarded. A formal characterization of partial dominance is given in the following proposition. Proposition 2 (Partial Dominance) Let P be a set of partial paths and p2∉P be another partial path all ending at the same vertex i∈V . If, for each feasible extension q2 of p2 , there exists a p1∈P such that the condition(i) or the condition(ii) of Proposition1 is fulfilled and the resulting o - d -path r1 has a smaller or identical reduced cost than r2=(p2,q2), then the partial path p2 is dominated. The notion of partial dominance reflects the concept that any path p1∈P generally fulfills the dominance conditions in Proposition1 only for some extensions q2 of p2 , i.e., p1 partially dominates p2 . Considering all the paths in P together, all extensions q2 of p2 are dominated so that p2 can be discarded. In the VRP literature, partial dominance has been employed in different situations like SPPRCs with a tradeoff between resources, handling relaxations of the elementarity condition in SPPRCs, and other use cases (see Sect.2). The focus of this paper is on partial dominance for SPPRCs with a tradeoff between resources and, in particular, on the most basic type of such a tradeoff, i.e., a linear tradeoff with a single linear piece as depicted in Fig.1. An example of a linear tradeoff can be found in the context of the electric vehicle routing problem with time windows (EVRPTW) with partial recharging (Schneider etal. 2014): Battery electric vehicles have a limited driving range, which can be extended by charging the battery at dedicated recharging stations. The tradeoff is between the amount to be recharged and the time required to do so. Longer charging increases the driving range, but may hinder the timely arrival at later customers due to their service time windows. In Fig.1, the x-axis represents the time when a service can begin, and the y-axis represents the amount of energy that could be feasibly recharged: Being early in the time window [a,b] allows more energy (up to u) to be recharged, while being late limits it (down to l). In general, Fig.1 shows the feasible domain of two resources x and y for a partial path represented by label F . For the resource x , the minimum feasible resource consumption is Fa and the maximum feasible resource consumption is Fb . Likewise, it is Fl and Fu for the resource y . For both resources, smaller values are preferable. 1066 S.Faldum et al. 1 3 The tradeoff function f characterizes the nature of the tradeoff: Whenever we allow resource x to increase by one unit (recall that smaller values are preferable), the consumption of resource y can be decreased by m units, i.e., the slope of f is −m . The contributions of this paper are the following. We provide a formal characterization of linear tradeoffs between resources with a single linear piece within SPPRCs and derive a unified partial dominance rule to be used in ad hoc labeling algorithms for the solution of corresponding SPPRCs as well as insights on its practical implementation. Our results apply to both the elementary and the non-elementary version of the SPPRC. Furthermore, we exemplify the application of partial dominance for two important variants of the VRP with a linear tradeoff in their SPPRC pricing subproblems, namely the EVRPTW with a partial recharge policy and the split-delivery vehicle routing problem with time windows (SDVRPTW). Finally, we report an extensive computational analysis of using partial dominance compared to the classical pairwise dominance for the EVRPTW and the SDVRPTW on their standard benchmarks. The remainder of the paper is structured as follows. In Sect. 2, we categorize different use cases in which partial dominance has been used within SPPRC subproblems and review the corresponding literature. Section3 provides the theoretical analysis of partial dominance for linear tradeoffs between resources. Section4 details its application to the EVRPTW and the SDVRPTW. Our computational study on the EVRPTW and the SDVRPTW is reported in Sect.5. Final conclusions are drawn in Sect.6. 2 Literature review Partial dominance has been used for different types of SPPRC subproblems. We categorize into linear tradeoff functions and non-linear tradeoff functions describing the relationship of two resources, partial dominance in SPPRC with elementarity constraints, and other forms of partial dominance. Fig. 1 Tradeoff with a single linear piece between two resources x and y x y ab u l f S dominated area D(S) m 1 1067 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… Linear Tradeoff Functions First, SPPRC subproblems that have a tradeoff between two resources can benefit from partial dominance. This type of dominance started with the works (Ioachim etal. 1998, 1999) for airplane flight scheduling. In this application, the only resources are time and reduced cost such that a partial path can be completely characterized by a continuous, piecewise linear tradeoff function. The seminal paper of Desaulniers etal. (1998) clarifies when and how such linear tradeoffs between resources result from resource constraints in extensive path-based formulations solved with column-generation algorithms: Resource constraints in the master program referring to resource levels at vertices or at arcs result in linear node/vertex and arc costs. For continuous, piecewise linear tradeoff functions, Desaulniers and Villeneuve (2000) developed an implicit form of partial dominance for the respective SPPRC subproblems: Whenever the minimum of several tradeoff functions of a set of paths is completely below the tradeoff function of another path, this path can be eliminated. Such continuous, piecewise linear tradeoff functions between two resources arise in several vehicle scheduling and routing problems. Examples of this form of partial dominance used for solving SPPRC subproblems are the VRP with soft time windows (Liberatore etal. 2010), the time-window assignment VRP (Spliet and Gabor 2015; Spliet etal. 2018), the active-passive VRP (Tilk et al. 2018), the time-dependent VRP with time windows (VRPTW) (LeraRomero etal. 2020), and the SDVRPTW with linear weight-related cost (Luo etal. 2017). The handling of piecewise defined functions per label is somewhat inconvenient, in particular when the number of pieces is not bounded (by a small instanceindependent number). For the EVRPTW with partial recharges (Desaulniers etal. 2016b) and the SDVRPTW (Desaulniers 2010), there is only one linear piece which includes the case of a single point. The EVRPTW and the SDVRPTW are the two VRP variants that we consider in the computational analysis, see Sect.4. In a follow up publication on a variant of the inventory-routing problem, Desaulniers etal. (2016a) apply similar solution methods, because also this problem can be modeled with REFs with not more than one linear piece. Even if we did not find works suggesting partial dominance for some applications, it should also be applicable when solving SPPRC subproblems of the following problems: the dial-a-ride problem with ride-time constraints (Gschwind and Irnich 2015), the synchronized pickup and delivery problem (Gschwind 2015), the truck-and-trailer VRP with quantity-dependent transfer times (Rothenbächer et al. 2018), and the VRP with partial outsourcing (Baller etal. 2020). This list should not be considered complete. Non-Linear Tradeoff Functions Also non-linear tradeoffs between some resource and reduced cost have been considered. Comparing piecewise defined non-linear tradeoff functions and herewith establishing a partial dominance is more intricate but still beneficial. In the VRPTW with convex inconvenience cost functions (He etal. 2019), a customer-specific tradeoff function is defined over the customer’s time windows. Elementarity Partial dominance improves dominance for relaxations of the elementary SPPRC: For the SPPRC with 2-cycle elimination (Houck etal. 1980; Kohl etal. 1999), i.e., short cycles of the form (i, j, i), two labels that have mutually different 1068 S.Faldum et al. 1 3 predecessor vertices can dominate another label by resource values. For the SPPRC with k-cycle elimination, i.e., all cycles of length up to k are forbidden, Irnich and Villeneuve (2006) generalize this partial dominance. Up to six labels with different predecessor sequences are needed for 3-cycle elimination. For the general case, Irnich and Villeneuve prove that not more than k!(k−1)! different predecessor sequences are needed. For a SPPRC with combined 2-cycle and k-cycle elimination, Bode and Irnich (2014) further generalize the partial dominance. Such a combined cycle elimination occurs in BPC algorithms for the capacitated arc routing problem when branching decisions and k-cycle free subproblems defined on the street network are considered simultaneously. For the SPPRC subproblem of the minimum latency problem, Bulhões etal. (2018) derive a partial dominance for the ng-route relaxation of the subproblem. In this context, a first label that dominates a second label with respect to all resources but not with respect to the ng-route restrictions (it cannot be extended to one or several customers to which the second label can be extended) does however partially dominate the second. This partial dominance results in so-called dominated extensions, i.e., vertices to which an extension of the second label can be safely avoided. Full dominance occurs when a label cannot be extended either due to the set of dominated extensions or due to ng-route restrictions. These ideas were further exploited by Costa etal. (2021) where even stronger arc-ng-route dominance rules were proven in the context of selective pricing (Desaulniers etal. 2019). Other Forms of Partial Dominance We found some works using a partial dominance that does not fall into one of the above categories. For the basic multi-compartment VRP, Heßler and Irnich (2023) use labels that represent partial paths for which (at least) one feasible packing of delivery items into compartment exists. The decision about the concrete packing finally used is, however, postponed until the partial path reaches the destination. In particular, one label generally represents many alternative packings. Partial dominance is used to allow that packings of one label are dominated by some packings of a second label. Two-arc fixing using reduced costs as suggested by Desaulniers etal. (2020) is an acceleration technique for solving SPPRC pricing problems faster without compromising optimality of the overall BPC approach. Sequences of two consecutive arcs that cannot occur in an optimal solution are identified and the labeling algorithm ensures that after traversing the first arc of the sequence, the label is not extended along the second arc. In order to maintain optimality of the pricing, a label must be extended by the information which (second) arcs must not be used for an extension. This information must be taken into account in the dominance. The authors rely on partial dominance, since otherwise the majority of the labels is not comparable with the standard pairwise dominance. 3 Partial dominance forlinear decreasing tradeoff functions In this section, we formally define the linear tradeoff between two resources and describe the basic theory for partial dominance between labels. Furthermore, we address general issues for the application of partial dominance within labeling algorithms for SPPRCs. Finally, we provide some details of our implementations. 1069 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… 3.1 Basic theory We assume that the linear tradeoff exists between two resources with real-valued resource values x and y . For a partial path and its label F , a proper tradeoff can be described by a segment S in ℝ2 with endpoints (Fa ,Fu) and (Fb , Fl) with Fa<Fb and Fu>Fl , see Fig. 1. Formally, the segment is the convex hull of its endpoints, i.e., S= conv ({(Fa , Fu) , (Fb , Fl)}) . The intuitive interpretation of the tradeoff described by the segment is that if resource x is allowed to increase by one unit, the consumption of resource y can be decreased by m=(Fu−Fl)∕(Fb−Fa)>0 units. Every point (x,y) on the segment S can be described with the help of a linear function f∶ ℝ 1 →ℝ 1 defined by Note that we have intentionally defined this underlying function f on the entire real space, and not only on the interval [Fa , Fb] . Moreover, we can also cope with the case of a one-point segment, i.e., that the two endpoints (Fa ,Fu) and (Fb , Fl) are identical, i.e., Fa=Fb and Fl=Fu . In this case, we still use (1) by defining the (negative) slope to be m=1 . With this definition, also the inverse of f is welldefined, it is x=f−1(y)=Fa− 1 ∕m ⋅ (y−Fu) . For both resources, smaller values are preferable so that a combination (x,y) of two resource values (hereafter referred to as a point) dominates (x� ,y�) if x≤x′ and y≤y′ hold. Graphically speaking, a point (x,y) dominates all points that lie on the top right of it. This dominance between points can be extended to sets. In particular, for the segment S , the dominated area is see also Fig.1. 3.1.1 Full dominance We first describe the standard full dominance with respect to the two resources that are traded against each other. Note that a partial path typically has more resources than just these two. As a consequence, the following conditions for full dominance regarding the two resources are only necessary conditions for dominance between labels (see also the dominance for the EVRPTW and the SDVRPTW described in Sects.4.1 and4.2). We assume that two labels F1 and F2 with corresponding segments S1 defined by (Fa 1,Fu 1) and ( F b 1 ,F l 1) and S2 defined by (Fa 2,Fu 2) and ( F b 2 ,F l 2) are given. Label F1 fully dominates F2 if S2⊂D(S1) . An example where S2 lies completely in the dominated area of S1 is illustrated in Fig.2. Full dominance can be verified using the following four conditions, which must all hold true: (1) y=f(x)=Fu−m ⋅ (x−Fa). D(S)={(x� , y�)∈ ℝ 2∶ ∃(x , y)∈S with (x , y) dominates (x� , y�)}, (DC1) Fa 1 ≤ Fa 2, 1070 S.Faldum et al. 1 3 Condition(DC1) compares the minimum x-values and checks whether Fa 1 lies further on the left than Fa 2 . Likewise, condition(DC2) compares the minimum y-values and checks whether Fl 1 is below Fl 2 . Condition (DC3) compares the values of f1 and f2 at x=Fa 2 . Finally, Condition(DC4) compares the values of f1 and f2 at x =F b 2 . The four dominance conditions are visualized in Fig.2. If both segments S1 and S2 consist of a single point each, i.e., Fa 1 =F b 1 and Fa 2 =F b 2 , these conditions collapse into the standard dominance of the form Fa 1 ≤ Fa 2 and Fl 1 ≤F l 2 between independent resources, i.e., (DC1) and (DC2). 3.1.2 Partial dominance We now characterize partial dominance between the two resources for which a tradeoff occurs. Reusing the same notation as in Sect.3.1.1, we define that a label F1 partially dominates F2 if Recalling that full dominance requires S2⊂D(S1) , we speak of a proper partial domination if (2) and S2⊄D(S1) are fulfilled. In the spirit of Proposition2, a set F of labels together dominates a label F2 , if (DC2) Fl 1 ≤F l 2, (DC3) Fu 1−( F a 2− F a 1) ⋅m 1 ≤F u 2, (DC4) Fu 1 −(F b 2 −F a 1 )⋅m 1 ≤F l 2, (2) D( S 1)∩ S 2 ≠ �. (3) S 2⊂ ⋃ F 1 ∈F D(S1) . Fig. 2 Full dominance of segment S1 over S2 x y a2b2 u2 l2 a1b1 u1 l1 S2 S1 (DC1 ) (DC2 ) (DC3 ) (DC4 ) 1077 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… partially dominates S3 from the left, and S2 partially dominates S3 over a central piece. If the labeling algorithm first compares S2 and S3 , it neglects this fact. The subsequent comparison of S1 and S3 results in a partial dominance of S1 over S3 from the left. The resulting set of undominated points comprises more than half of the original segment S3 . If the order of the two pairwise comparisons is swapped, partial dominance from the left of S1 over S3 allows the subsequent partial dominance from the left of S2 over S3 . In comparison, the remaining set of undominated points of S3 is much smaller. (ii) The capability to partially dominate another label can be reduced or lost. Consider the example shown in Fig.4b. It depicts three segments S1 , S2 , and S3 , where segment S2 fully dominates S3 , and segment S1 partially dominates S2 and S3 from the left. If first S1 partially dominates S2 , then S2 is updated to describe the remaining set of undominated points as highlighted by the thick line. Now, the reduced segment S2 only partially dominates S3 from the right. Both S1 and S2 together are needed to completely dominate S3 . Possibility(2) A second type of implementation stores two segments: the initial segment S as well as the remaining set Su of undominated points. We assume that the initial segment is represented by Fa ,Fb ,Fl , and Fu . Storing Su can be accomplished by introducing four additional attributes Fa ,Fb ,Fl , and Fu . Note that the two attributes Fa and Fb are sufficient, because Fu=f(Fa) and Fl=f(Fb) and the function f can be expressed with the original attributes. This type of implementation is denoted double bookkeeping in the following, because it keeps the information about both the largest possible segment for dominating other labels as well as the segment of undominated points that we want to become as small as possible (recall that the label is completely dominated once this set is the empty set). Hence, double bookkeeping overcomes the above disadvantage(ii). However, because the stored information is limited to only two segments, no dominance over central pieces can be performed so that disadvantage(i) remains. Possibility(3) Storing a variable number of segments allows to exactly describe the initial segment S as well as the sets of dominated and undominated points of a partial path resulting from all possible types of partial dominance (PD1–PD6b), in particular including dominance over a central piece. Formally, if partial domination has been performed with a subset F of labels F1∈F , then the set of undominated points is and may consist of up to |F|+1 segments. Alternatively, storing the complement S2 ∩ ⋃F1∈ FD(S 1) , i.e., the set of dominated points, may require representing |F| segments. If S2 is given, dominated points can be reproduced from undominated points, and vice versa. We can formalize the set of undominated points of a partial path with the help of a variable numberK of sub-segments S1,u,…,SK,u with S u= ⋃K k=1 Sk, u . Partial dominance can then be realized similar to possibilities (1) and (2) by gradually reducing the set of undominated points Su . This requires updating all S u 2=S2⧵ ⋃ F1∈ F D(S1 ) 1078 S.Faldum et al. 1 3 sub-segments S1,u 2 ,…,S K,u 2 accordingly. In particular, in each update, some sub-segments may remain unchanged, some sub-segments may become empty sets (and can be eliminated), some sub-segments may be reduced (if dominated from the left or from the right), and some sub-segments may decompose into two new sub-segments (if dominated over central pieces). Overall, this type of representation overcomes both of the above disadvantages(i) and(ii). The drawback is that the number of sub-segments is variable, which is more complex to implement. Even more, it requires the allocation and deallocation of memory during the dominance algorithm slowing down the computational speed in which the dominance algorithm can be completed. Note that the dominance is typically the most time-critical part of a labeling algorithm. We now comment on the two possibilities to represent variable numbers of segments for partial paths. Possibility(a) A first type of implementation maintains the classical one-to-one correspondence between partial paths and labels. All initial and intermediate information about a partial path, its capability to dominate other labels, and its own state of being partially dominated are stored within a single label (the original label created at initialization) whose attributes are updated whenever it is partially dominated by other labels. In particular, in each label the segment S is represented and maintained using the original attributes Fa ,Fb ,Fl , and Fu . Furthermore, the K subsegments ( S k,u ) K k=1 can be described with 4K additional values ( F k,a ,F k,b ,F k,l ,F k,u ) K k=1 (again 2K values (Fk,a , Fk,b) suffice, since Fk,l=f(Fk,b) and Fk,u=f(Fk,a) and f is known). At initialization, the assignments K=1 and S1,u=S have to be made, i.e., F1,a=Fa,F1,b=Fb,F1,l=Fl , and F1,u=Fu . The main advantage of possibility (a) is that all information of a partial path is stored only once (non-redundant, memory efficient). A disadvantage is that it requires a variable-sized representation of the sub-segments of either dominated or undominated points of the segment S . This may be time-critical when labels themselves are stored in dynamically allocated memory and their variable-sized attributes are also stored in dynamically allocated memory. Moreover, the pairwise comparison is more intricate from a implementation point of view. Possibility(b) In contrast, some works mention that they create several labels per partial path when convenient for storing the information about partial domination or in the presence of multiple extensions per arc, e.g., when items can alternatively be loaded in different compartments of a vehicle (Cherkesly and Gschwind 2022; AertsVeenstra etal. 2023). An alternative type of implementation could, for example, use labels like with double bookkeeping in possibility(2). Instead of restricting partial dominance to PD1–PD4, partial dominance over central pieces can be established by creating a new copy F′ 2 of a label F2 whenever two sub-segments are created from one sub-segment of undominated points. One sub-segment is then stored in the original label F2 and the other sub-segment in the new copy F′ 2 . In general, with this implementation, a partial path with set of undominated points S u= ⋃K k=1 Sk, u is represented by K labels, one for each sub-segment ( S k,u ) K k=1 . In the spirit of double 1079 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… bookkeeping, each label maintains the initial segment S using the original attributes Fa ,Fb ,Fl , and Fu and its corresponding sub-segment Sk,u with the additional attributes Fa ,Fb ,Fl , and Fu . 3.3 Implementation details ofour labeling algorithm Concerning possibilities(a) and (b) to represent variable numbers of segments in partial dominance, we see no strong point in possibility(b) except for being rather simple to code. In comparison, possibility(a) allows to keep all information about a partial path within a single label. Regarding the alternatives (1)–(3) to maintain and utilize dominance information, the main question is whether or not partial dominance over a central piece is essential. To answer this question, we recommend to conduct pretests to quantify how often the partial dominance typesPD5, PD6a, and PD6b occur compared to partial dominance from the left and from the right. On the basis of such pretests (see also Sect.4), we decided not to consider partial dominance over a central piece in our BPC algorithms. The additional computational overhead to cope with a variable number of segments is high. In comparison, the impact caused by additional dominance was low, i.e., we did not see a strong reduction in the number of labels and dominance tests when omitting partial dominance over a central piece. It is clear that double bookkeeping, i.e., possibility(2), leads to a stronger dominance compared to possibility (1). The necessary addition of the (often integer) attributes Fa ,Fb ,Fl , and Fu to a label F is rather harmless for a computer implementation; the main effect is a slightly higher memory consumption and, as a consequence, a possible higher number of cache misses. There is one more refinement related to double bookkeeping that we would like to discuss now. Recall that the resources whose dependency is described by the segment are problem-specific. Independent from a specific problem, the segment of a given label Fi referring to a vertex i is typically used to define the segment of an extension to a vertexj represented by label Fj . REFs Refij are used for this purpose (see Sect.4 for examples), i.e., ( F a j ,F b j ,F l j ,F u j )=Refij(F a i ,F b i ,F l i ,F u i) . This offers the opportunity to initialize the set of undominated points Su j for a newly created label Fj based on information about partial dominance of its predecessor Fi . The related attributes are computed with the same REFs as The advantage is that labels Fj with a smaller set of undominated points Su j can be eliminated sooner, i.e., with less applications of partial dominance. In summary, we have chosen possibility(2), i.e., double bookkeeping, together with the refinement that undominated sets of points are propagated with REFs. ( F a j ,F b j ,F l j ,F u j )=Refij(F a i ,F b i ,F l i ,F u i ) . 1080 S.Faldum et al. 1 3 4 Two variants oftheVRPTW In this section, we present two variants of the VRPTW with tradeoff resources and discuss the application as well as specific adaptations of the theory from Sect.3 to these variants. First, we formally define the VRPTW as the base problem of the considered variants and introduce the common notation, followed by a description of the two variants, namely the EVRPTW and the SDVRPTW. For convenience, we use the same notation, e.g., for index sets, for all variants even though their definition may be slightly different. The correct meaning should be clear from the context. We then describe the use of partial dominance within the labeling algorithms to solve the pricing subproblems of column-generation approaches for the EVRPTW and the SDVRPTW. The VRPTW can be defined on a directed graph G=(V,A) . The vertex set V=N∪{o,d} comprises the customer vertices N and two copies o and d of the depot. A travel time tij and routing cost cij are associated with each arc (i,j)∈A . Both travel times and routing costs are assumed to satisfy the triangle inequality. For each vertex i∈V , a non-negative demand qi , a service duration si , and a time window [ei,li] in which the service must start are given. We assume qo=qd=si=si=0 for the depot copies o and d . A fleet K of homogeneous vehicles each with a capacity of Q is available at the common depot to serve the customers. The VRPTW is the problem of finding at most |K| vehicle routes such that the total routing cost is minimized, each customer is served by exactly one route, and each route is feasible, i.e., it is an elementary o - d -path in G satisfying the capacity and time-window constraints. For further details on the VRPTW and its solution by BPC-based approaches, we refer to Costa etal. (2019). The EVRPTW is an extension of the VRPTW that takes into account the limited driving range of electric commercial vehicles and the possibility of recharging the vehicle’s battery en route at recharging stations. We consider two variants of the EVRPTW that employ a so-called partial recharging policy where any amount of energy can be recharged when visiting a recharging station. The two variants differ in the number of allowed recharges per route: at most a single (S) or multiple (M) recharges are allowed. They are referred to as EVRPTWS and EVRPTW-M, respectively, in the following. To model these EVRPTW variants, the set R of recharging stations can be added to the vertex set V , i.e., V=N∪{o,d}∪R . Each vehicle in the homogeneous fleet is equipped with an electric battery of maximum capacity B . Moreover, each arc (i,j)∈A is associated with an energy consumption bij . As described by Desaulniers etal. (2016b), we assume that the battery capacity and the energy consumptions are given in recharging time units so that, e.g., B equals the time to fully recharge a completely empty battery. In particular, there is a one-to-one relationship between the recharging duration and the amount of recharged energy, i.e., recharging for Δ units of time increases the state of charge (SoC) by exactly Δ units. A route is feasible in the EVRPTW, if it is feasible for the underlying VRPTW (timing constraints now include also recharging times) and the SoC is never negative or 1081 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… greater than the battery’s capacity B . In addition, the number of recharges per route must comply with the recharging policy (S or M). Also the EVRPTW has the objective of minimizing the total routing cost. A detailed description of the considered EVRPTW variants and corresponding BPC algorithms for their solution can be found in Desaulniers etal. (2016b), Desaulniers etal. (2020) and Duman etal. (2021). The SDVRPTW is a relaxation of the VRPTW in which customers may be visited more than once, i.e., the customer demands can be satisfied through multiple visits by different vehicles. This also allows finding feasible solutions to instances with customer demands qn>Q . Contrary to the VRPTW, a route in the SDVRPTW is not only characterized by a sequence of customers but also by a corresponding delivery pattern 𝜌 which specifies the quantities d𝜌n delivered to each customer n visited on the route. A route is capacity-feasible if the sum the quantities d𝜌n does not exceed the vehicle capacity Q . Each customer’s demand must be fulfilled by the sum of received delivery quantities of all routes. Again, the objective is the minimization of the total routing cost. Desaulniers (2010) proposed a BPC approach to the SDVRPTW in which only routes with extreme delivery pattern have to be explicitly considered. In an extreme delivery pattern, only one customer n receives a split delivery, i.e., 0<d𝜌n<qn . All other customers receive either a zero delivery ( d𝜌n=0 ) or a full delivery ( d𝜌n=qi ). Routes with general delivery patterns are considered implicitly in the RMP by convex combinations of routes with extreme delivery patterns. For details we refer to Desaulniers (2010), Archetti etal. (2011). 4.1 Labeling withpartial dominance fortheEVRPTW We now show how partial dominance can be used in the labeling algorithm proposed by Desaulniers etal. (2016b) to solve the elementary SPPRC pricing problem of the EVRPTW. After visiting a recharging station, there is a tradeoff between time and SoC: the more energy to charge, the later the time, but the higher the SoC. Since the amount to be recharged, i.e., the recharging duration, depends on the part of the partial path after this recharging station, it can only be determined a posteriori. Consequently, the labels must maintain the relevant tradeoff segment of feasible times, which implies different recharging durations and achievable SoCs. If no recharging station has been visited on the partial path, there is no tradeoff, i.e., the segment reduces to a single point. For the sake of brevity, we only briefly discuss the resources and dominance rules used in the original algorithm. We also limit the presentation to the forward part of the labeling, since the backward labeling is similar. For more details on the original labeling algorithm, see Desaulniers etal. (2016b). A partial path p starting at the origin depot o and ending at vertex i∈V is represented by a label Fi =(Fcost i ,Fload i ,(F cust n i ) n∈N ,Frch i ,FtMin i ,FtMax i ,FrtMax i) . The 6+|N| components of the label have the following meaning: Fcost i : the reduced cost of path p ; 1082 S.Faldum et al. 1 3 Fload i : the accumulated customer demands along path p ; Fcustn i : for each n∈N , the number of times customer n has been visited along path p ; Frch i : the number of recharges performed along path p ; FtMin i : the earliest service start time at vertexi assuming that, if a recharging station is visited prior toi along p , a minimum recharge that ensures battery feasibility up toi has been performed; FtMax i : the earliest service start time at vertex i assuming that, if a recharging station is visited prior to i along p , a maximum recharge respecting time-window feasibility up toi has been performed; FrtMax i : with the artificial assumption that recharging is possible at all vertices, FrtMax denotes the maximum possible recharging duration at vertexi assuming that, if a recharging station is visited prior toi along p , a minimum recharge that ensures battery feasibility up to i has been performed. Note that this assumption is used only to propagate the information along the path, but a real recharge never occurs at a customer. To simplify the notation, we omit the index i of the residing vertex so that we write, e.g., Fcost instead of Fcost i . Instead of modeling the SoC directly, Desaulniers etal. implicitly represented it by the maximum feasible additional recharging duration FrtMax (= maximum feasible amount of energy to be recharged) with respect to the earliest service start time FtMin at the current vertex. With this representation, for both tradeoff resources time and maximum possible recharging duration, smaller values are preferable. Therefore, the theory of Sect.3 is immediately applicable to realize partial dominance. Moreover, by the above definition of the battery related data (capacity, consumption, and recharging rate), the negative slope of all tradeoff functions is m=1 , which simplifies the representation and dominance conditions. As a result, so that only the three attributes FtMin , FtMax , FrtMax are needed to describe the tradeoff and the corresponding segment. The classical dominance rule of Desaulniers etal. (2016b) for pairwise dominance is as follows. Let F1 and F2 be two labels representing partial paths ending at the same vertex i . Label F1 dominates F2 , if Fa =F tMin , F b=FtMax , Fl=FrtMax −(FtMax −FtMin) , F u =F rtMax , 1083 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… In the EVRPTW-S, Frch 1 ≤F rch 2 is additionally required. Since segments have identical slope with m1=m2=1 , conditions (DC1)–(DC3) imply condition (DC4). Alternatively, one could require conditions(DC1), (DC2), and(DC4), which imply condition(DC3). Having identical slopes also simplifies partial dominance between two tradeoff segments. First, the two segments can never have a proper intersection (see Sect.3.1.2) meaning that only PD1 and PD3 are relevant (recall that we do not employ partial dominance over a central piece). Second, also the identification of them is simplified. For PD1, conditions(DC1) and(DC3) are fulfilled (implying (DC4)), while condition(DC2) is violated. For PD3, conditions(DC2) and(DC3) are fulfilled (implying (DC4)), while condition(DC1) is violated. Furthermore, the determination of the undominated points is simplified (see Table 2), since the tradeoff function and its inverse are identical with (negative) slopes given by m=1 . Finally, for time windows and travel times defined by integer values, all battery related data can also be assumed to be integer. Thus, the feasible domains of the tradeoff resources time and SoC can be reduced to integers, and rounding can be applied to the segments in partial dominance as described in Sect.3.1.2. The integer assumption is satisfied for the standard benchmark instances of the EVRPTW used in the computational experiments presented in Sect.5. 4.2 Labeling withpartial dominance fortheSDVRPTW In the following, we detail the application of partial dominance to the labeling algorithm of Desaulniers (2010) for pricing routes and associated extreme delivery patterns for the SDVRPTW. Here, the pricing subproblem is an elementary SPPRC combined with the linear relaxation of a bounded knapsack problem. Since there is a dual price for each unit to be delivered to a customer, there is a tradeoff between the two resources vehicle load and reduced cost: The question of how much to deliver to the (unique) customer receiving a split delivery is, in turn, the question of how much to earn from each unit delivered. Similar to the recharging duration in the EVRPTW, the quantity to be delivered is not known when visiting the split customer. Therefore, the label represents this tradeoff with a segment indicating the possible vehicle load (implying the delivery quantity to the split customer) and the achievable reduced cost. If no split delivery has been made along a partial path, there is no tradeoff, resulting in a single-point segment. For brevity, we only present the attributes of a label and the dominance rules of the original algorithm only for the case of forward labeling (backward labeling is F cost 1≤F cost 2, Fload 1≤Fload 2, Fcustn 1≤Fcustn 2∀n∈N , and (DC 1 ) – (DC 3 ) . 1084 S.Faldum et al. 1 3 symmetric with respect to the tradeoff). A partial path p from source o to a vertex i∈V is represented by a label Fi =(Fcost i ,Ftime i ,Fload i ,(F cust n i ) n∈N ,F split i ,FsMax i ,Fs𝜋 i) with 6+|N| components defined as follows: Fcost i : the reduced cost of path p without the cost for a potential split delivery; Ftime i : the earliest service start time at vertex i ; Fload i : the accumulated customer demands of full deliveries along path p ; Fcustn i : for each n∈N , the number of times customern has been visited along path p ; Fsplit i : binary indicator whether or not a split delivery has occurred on path p ; FsMax i : the maximum quantity that can be delivered to the split delivery customer on path p ; Fs𝜋 i : dual price per unit delivered to the split delivery customer on path p . Smaller values are preferable for both tradeoff resources load and reduced cost. As a result, the theory of Sect.3 is also applicable here, and the segment describing the tradeoff in the SDVRPTW is defined by which are given by the four components Fload , Fcost , FsMax , and Fs𝜋 where the latter describes the negative slope m . However, unlike for the EVRPTW, the negative slopes given by m=Fs𝜋 are generally different for different labels so that a proper intersection is possible. Consequently, no direct simplifications can be made. The classical rule of Desaulniers (2010) for pairwise dominance is as follows: Let F1 and F2 be two labels representing partial paths ending at the same vertex i , then label F1 dominates F2 , if Fa =F load , F b=Fload +FsMax , Fl=Fcost −FsMaxFs𝜋 , F u =F cost , F time 1≤F time 2, Fsplit 1≤Fsplit 2, Fcustn 1≤Fcustn 2∀n∈N , and (DC1)–(DC4). 1085 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… For partial dominance between labels, all types PD1–PD6b are relevant. Finally, it is known that, for each SDVRPTW instance, there exists an optimal solution in which all delivery quantities are integer, under the precondition that all demand values and the vehicle capacity are integer (Archetti etal. 2006). The integer assumption is satisfied for the standard benchmark instances used in Sect.5, so that rounding is applicable as described in Sect.3.1.2. 5 Computational results In this section, we report an extensive computational study of partial dominance within the BPC algorithms for the EVRPTW and the SDVRPTW. The two BPC algorithms were implemented in C++ and compiled into 64-bit single-thread code with MS Visual Studio 2019. CPLEX 20.10 with default parameters (except for the time limit and allowing only a single thread) was used to reoptimize the RMPs. All computations were performed on the high performance computing cluster Elwetritsch of the RPTU Kaiserslautern-Landau, consisting of several Intel Xeon Gold 6126 processors running at 2.60GHz. Note that the performance of a single thread on the cluster is comparable to that of a standard desktop processor. 5.1 BPC algorithms The BPC algorithms for the EVRPTW and the SDVRPTW share the same code basis, which is adapted to each of the problem variants. The base code uses several acceleration techniques that are well established in the literature. For the EVRPTW, the computational setup of the BPC algorithm is completely identical to that used in Desaulniers etal. (2020). For the SDVRPTW, a modified setup seems more favorable. Both computational setups are summarized below. Pricing To speed up the pricing, we apply bidirectional labeling with a dynamic half-way point using the time as the monotone resource (Tilk et al. 2017), i.e., FtMin for the EVRPTW and Ftime for the SDVRPTW. Furthermore, instead of solving the strongly NP -hard elementary versions of the SPPRCs, we rely on the wellknown ng-path relaxations of them (Baldacci etal. 2011). In our implementation, the neighborhood sizes are set to 14 (EVRPTW) and 4 (SDVRPTW). In addition, we use the concept of unreachable customers who cannot be reached due to their resource levels (Feillet etal. 2004). We use pricing heuristics based on families of arc-reduced networks as proposed by Desaulniers etal. (2008), where the networks have a limited number of incoming and outgoing arcs for each customer vertex. The number of arcs chosen in our implementation are 2, 5, 10, 15 (EVRPTW) and 3, 10 (SDVRPTW). For the SDVRPTW, we additionally consider another heuristic pricing strategy that only allows full deliveries and zero deliveries to customers, i.e., split deliveries are disregarded, resulting in an SPPRC without tradeoffs. The latter strategy is combined with the arc-reduced networks. Finally, our labeling algorithms are based on a bucket-based implementation using a one-dimensional bucketing on the time resource (Sadykov etal. 2021). 1086 S.Faldum et al. 1 3 Valid Inequalities To strengthen the linear relaxation of the master program, rounded capacity inequalities (RCIs, Naddef 2002) and subset-row inequalities (SRIs, Jepsen etal. 2008) are added as two families of valid inequalities. Violated inequalities are separated only at the root node (level zero) for the EVRPTW and up to level one of the search tree for the SDVRPTW. For the SDVRPTW, additional inequalities that upper bound the flow by one on every pair of anti-parallel customer arcs are also dynamically added (see Desaulniers 2010,Corollary 2, Eq.(7), and Sect.5.2.2). The separation procedures add inequalities to the RMP only if they are violated by at least0.05. RCIs are robust cuts because their dual prices can be incorporated by modifying the reduced cost of the associated arcs; they do not change the structure of the pricing problem. For the SDVRPTW, RCIs are critical to the overall performance of our BPC algorithm and are, therefore, extensively separated using the extended and greedy shrinking heuristics of Ralphs etal. (2003), the route-based algorithm of Archetti etal. (2011) for the SDVRPTW, and using an exact mixed-integer programming (MIP) formulation following the ideas of Martinelli etal. (2013). The route-based algorithm is invoked only when the shrinking heuristics fail to find a violated RCI. Similarly, the MIP is only used if the route-based algorithm also fails to identify a violated RCI. To avoid prohibitively long computation times, CPLEX is given a hard time limit of 10s for solving the MIP. For the EVRPTW, RCIs are less important and only the shrinking heuristics are used. SRIs are non-robust cuts so that, for each active SRI, an additional resource needs to be added in the labeling algorithms making the pricing problem more difficult to solve. Therefore, we use the limited memory variant of the SRIs as proposed by Pecin etal. (2017a). Furthermore, as done in most works, we limit ourselves to SRIs with row sets of size three. Our implementation uses the same separation algorithm and vertex memory as presented by Pecin etal. (2017b). Branching Branching is necessary to finally ensure integer solutions. For the EVRPTW, we use the hierarchical branching scheme of Desaulniers etal. (2016b), i.e., we branch on (i)the total number of routes, (ii)the total number of recharges, (iii)the total number of recharges at a recharging station, and (iv)the total flow on an arc. For the SDVRPTW, we use the scheme of Desaulniers (2010), i.e., we branch on (i)the total number of routes, (ii)the total number of visits to a customer, (iii)the total flow on an arc, and (iv)whether two arcs are used in succession. On all levels, we select a branching variable with fractional value closest to0.5. The search tree is explored using a best-bound first node selection strategy. For the SDVRPTW, we additionally apply strong branching as follows. In each node of the search tree, a set of branching candidates is selected by considering a given number of branching variables with the largest fractional values. For each candidate, a rough evaluation of both child nodes is performed by solving the RMP with the corresponding branching constraint without any column generation. The most promising candidate is selected according to the product rule proposed by Achterberg (2007). At the root node, the maximum size of the candidate set is 15, and the size of the candidate set decreases by two for each level of the search tree. However, the minimum size of the candidate set is five. Note that this implementation of 1093 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… application of partial dominance has been exemplified for two variants of the EVRPTW with a partial recharge policy and the SDVRPTW, two important variants of VRP. Computational results on standard benchmark instances for the considered problems have revealed the following main insights. On a per pricing problem basis, i.e., on truly identical instances of SPPRCs, we have found that the labeling algorithms applying partial dominance never performed worse than their counterparts with classical pairwise dominance. Furthermore, partial dominance has proved more beneficial for the pricing problems of the more difficult EVRPTW and SDVRPTW instances. It has also proved more beneficial for the EP instances rather than for heuristic pricing iterations on reduced networks. Overall, for the SDVRPTW, average speedups of up to 40% (EPs of the more difficult instances) could be realized by using partial dominance. For the two EVRPTW variants, savings were much smaller. This behavior can be explained by the fact that much less labels actually show a tradeoff in the EVRPTW variants (33% and 46%) compared to 62% in the SDVRPTW. Such a straightforward analysis can, thus, help to a priori estimate a potential gain from implementing partial dominance. We leave it to future research to conduct related experiments for other problems with a linear tradeoff and a single segment, such as the dial-a-ride problem with ride-time constraints, the synchronized pickup and delivery problem, the truck-and-trailer VRP with quantity-dependent transfer times, and the VRP with partial outsourcing (see Sect.2). In addition, the consideration of nonlinear tradeoffs may be the next step in generalizing partial dominance. The latter is relevant, e.g., for more realistic charging functions for battery electric vehicles. Finally, we have found that the results for the individual pricing instances do translate also to an improvement of an overall BPC, which employs many wellestablished acceleration techniques and whose performance is influenced also by many other effects that are not immediately related to the solution of the pricing problems. Again, these benefits are substantial for the SDVRPTW while they are rather minor for the EVRPTW. Future research could consider non-linear tradeoffs and more than one segment, for which the categorization as well as the computer implementation become much more complicated. Table 4 Data to Fig.5a for the EVRPTW-S All pricing problems (AP) Exact pricing problems (EP) Comp Labels Dominance Time Labels Dominance Time time ≥ #Instances AP-L AP-D AP-T EP-L EP-D EP-T 0 168 0.9957 0.9948 0.9739 0.9880 0.9704 0.9875 1 148 0.9955 0.9944 0.9751 0.9870 0.9672 0.9859 10 98 0.9954 0.9938 0.9786 0.9852 0.9564 0.9819 60 64 0.9956 0.9938 0.9795 0.9830 0.9456 0.9729 100 55 0.9960 0.9939 0.9802 0.9835 0.9432 0.9701 600 29 0.9961 0.9934 0.9753 0.9812 0.9319 0.9501 1200 25 0.9969 0.9937 0.9728 0.9835 0.9274 0.9525 1800 22 0.9970 0.9937 0.9699 0.9824 0.9226 0.9393 3600 19 0.9972 0.9940 0.9710 0.9839 0.9265 0.9413 1094 S.Faldum et al. 1 3 Appendix In Tables4, 5, and 6, we provide the underlying values to Fig.5. For the solutions of the root node, we distinguish two cases: we aggregate over all pricing problems (AP) solved or only the exact pricing problems (EP) defined over the full network. The tables display the geometric mean of ratios of the number of created labels (-L), the number of dominance tests (-D), and the solution time (-T) in seconds. In addition, we filter results according to different total computation times in seconds. The column #Instances gives the corresponding number of instances. Table 4 provides the values for the EVRPTW-S, Table5 for the EVRPTW-M, and Table6 for the SDVRPTW. Acknowledgements This research was supported by the Deutsche Forschungsgemeinschaft (DFG) under Grants GS83/1-1 and IR122/10-1 of Project418727865. This support is gratefully acknowledged. Table 5 Data to Fig.5b for the EVRPTW-M All pricing problems (AP) Exact pricing problems (EP) Comp Labels Dominance Time Labels Dominance Time time ≥ #Instances AP-L AP-D AP-T EP-L EP-D EP-T 0 168 0.9943 0.9926 0.9671 0.9860 0.9574 0.9603 1 156 0.9942 0.9923 0.9683 0.9853 0.9545 0.9583 10 113 0.9938 0.9915 0.9710 0.9830 0.9427 0.9470 60 71 0.9939 0.9908 0.9708 0.9795 0.9250 0.9331 100 65 0.9941 0.9907 0.9714 0.9797 0.9227 0.9310 600 43 0.9950 0.9907 0.9682 0.9811 0.9141 0.9181 1200 31 0.9952 0.9907 0.9639 0.9802 0.9078 0.9015 1800 28 0.9957 0.9908 0.9617 0.9827 0.9059 0.9019 3600 24 0.9956 0.9909 0.9604 0.9818 0.9039 0.9037 Table 6 Data to Fig.5c for the SDVRPTW All pricing problems (AP) Exact pricing problems (EP) Comp Labels Dominance Time Labels Dominance Time time ≥ #Instances AP-L AP-D AP-T EP-L EP-D EP-T 0 504 0.8302 0.6793 0.8059 0.7817 0.6250 0.7093 1 362 0.8245 0.6587 0.7882 0.7709 0.5974 0.6795 10 207 0.8080 0.6217 0.7555 0.7519 0.5567 0.6350 60 122 0.7945 0.5953 0.7297 0.7404 0.5334 0.6077 100 97 0.7886 0.5835 0.7190 0.7318 0.5208 0.5957 600 49 0.7706 0.5536 0.6898 0.7302 0.5154 0.5897 1200 34 0.7678 0.5506 0.6857 0.7339 0.5240 0.5979 1800 29 0.7628 0.5444 0.6807 0.7374 0.5284 0.6026 3600 21 0.7445 0.5191 0.6578 0.7293 0.5175 0.5938 1095 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… Funding Open Access funding enabled and organized by Projekt DEAL. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/ licenses/by/4.0/. References Achterberg T (2007) Constraint integer programming. Ph.D. thesis, Technische Universität Berlin, Fakultät II—Mathematik und Naturwissenschaften, Berlin, Germany Aerts-Veenstra M, Cherkesly M, Gschwind T (2023) A unified branch-price-and-cut algorithm for multicompartment pickup and delivery problems. Les Cahiers du GERAD G-2023-26, Groupe d’études et de recherche en analyse des décisions, GERAD, Montréal QC H3T 2A7, Canada Archetti C, Speranza MG, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1):64–73 Archetti C, Bouchard M, Desaulniers G (2011) Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transp Sci 45(3):285–298 Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper Res 59(5):1269–1283 Baller AC, Dabia S, Dullaert WEH, Vigo D (2020) The vehicle routing problem with partial outsourcing. Transp Sci 54(4):1034–1052 Barnhart C, Johnson E, Nemhauser G, Savelsbergh M, Vance P (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3):316–329 Bianchessi N, Irnich S (2019) Branch-and-cut for the split delivery vehicle routing problem with time windows. Transp Sci 53(2):442–462 Bode C, Irnich S (2014) The shortest-path problem with resource constraints with (k,2) -loop elimination and its application to the capacitated arc-routing problem. Eur J Oper Res 238(2):415–426 Bulhões T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the minimum latency problem. Comput Oper Res 93:66–78 Cherkesly M, Gschwind T (2022) The pickup and delivery problem with time windows, multiple stacks, and handling operations. Eur J Oper Res 301(2):647–666 Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transp Sci 53(4):946–985 Costa L, Contardo C, Desaulniers G, Pecin D (2021) Selective arc-ng pricing for vehicle routing. Int Trans Oper Res 28(5):2633–2690 Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper Res 58(1):179–192 Desaulniers G, Villeneuve D (2000) The shortest path problem with time windows and linear waiting costs. Transp Sci 34(3):312–319 Desaulniers G, Desrosiers J, Loachim I, Solomon MM, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Crainic TG, Laporte G (eds) Fleet management and logistics. Springer, Cham, pp 57–93 Desaulniers G, Desrosiers J, Solomon M (eds) (2005) Column generation. Springer, New York Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k -path inequalities for the vehicle routing problem with time windows. Transp Sci 42(3):387–404 Desaulniers G, Rakke JG, Coelho LC (2016) A branch-price-and-cut algorithm for the inventory-routing problem. Transp Sci 50(3):1060–1076 Desaulniers G, Errico F, Irnich S, Schneider M (2016) Exact algorithms for electric vehicle-routing problems with time windows. Oper Res 64(6):1388–1405 1096 S.Faldum et al. 1 3 Desaulniers G, Pecin D, Contardo C (2019) Selective pricing in branch-price-and-cut algorithms for vehicle routing. EURO J Transp Logist 8:147–168 Desaulniers G, Gschwind T, Irnich S (2020) Variable fixing for two-arc sequences in branch-price-andcut algorithms on path-based models. Transp Sci 54(5):1170–1188 Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201–213 Duman EN, Taş D, Çatay B (2021) Branch-and-price-and-cut methods for the electric vehicle routing problem with time windows. Int J Prod Res 60(17):5332–5353 Feillet D, Dejax P, Gendreau M, Guéguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems. Networks 44(3):216–229 Gschwind T (2015) A comparison of column-generation approaches to the synchronized pickup and delivery problem. Eur J Oper Res 247(1):60–71 Gschwind T, Irnich S (2015) Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transp Sci 49(2):335–354 He Q, Irnich S, Song Y (2019) Branch-and-cut-and-price for the vehicle routing problem with time windows and convex node costs. Transp Sci 53(5):1409–1426 Heßler K, Irnich S (2023) Partial dominance in branch-price-and-cut for the basic multi-compartment vehicle routing problem. INFORMS J Comput 35(1):50–65 Houck D, Picard J, Queyranne M, Vemuganti R (1980) The travelling salesman problem as a constrained shortest path problem: theory and computational experience. Opsearch 17:93–109 Ioachim I, Gélinas S, Desrosiers J, Soumis F (1998) A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31:193–204 Ioachim I, Desrosiers J, Soumis F, Bélanger N (1999) Fleet assignment and routing with schedule synchronization constraints. Eur J Oper Res 119(1):75–90 Irnich S (2008) Resource extension functions: properties, inversion, and generalization to segments. OR Spectrum 30(1):113–148 Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M (eds) Column generation. Springer, New York, pp 33–65 Irnich S, Villeneuve D (2006) The shortest path problem with resource constraints and k -cycle elimination for k≥3 . INFORMS J Comput 18(3):391–406 Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehiclerouting problem with time windows. Oper Res 56(2):497–511 Kohl N, Desrosiers J, Madsen O, Solomon M, Soumis F (1999) 2 -path cuts for the vehicle routing problem with time windows. Transp Sci 33(1):101–116 Lera-Romero G, Miranda Bront JJ, Soulignac FJ (2020) Linear edge costs and labeling algorithms: the case of the time-dependent vehicle routing problem with time windows. Networks 76(1):24–53 Liberatore F, Righini G, Salani M (2010) A column generation algorithm for the vehicle routing problem with soft time windows. 4OR 9(1):49–82 Luo Z, Qin H, Zhu W, Lim A (2017) Branch and price and cut for the split-delivery vehicle routing problem with time windows and linear weight-related cost. Transp Sci 51(2):668–687 Lübbecke M, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007–1023 Martinelli R, Poggi M, Subramanian A (2013) Improved bounds for large scale capacitated arc routing problem. Comput Oper Res 40(8):2145–2160 Naddef D (2002) Polyhedral theory. In: Gutin G, Punnen A (eds) The traveling salesman problem and its variations, volume12 of combinatorial optimization, chapter2. Kluwer, Dordrecht, pp 29–116 Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math Program Comput 9(1):61–100 Pecin D, Contardo C, Desaulniers G, Uchoa E (2017) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J Comput 29(3):489–502 Ralphs T, Kopman L, Pulleyblank W, Trotter L (2003) On the capacitated vehicle routing problem. Math Program 94(2–3):343–359 Rothenbächer A-K, Drexl M, Irnich S (2018) Branch-and-price-and-cut for the truck-and-trailer routing problem with time windows. Transp Sci 52(5):1174–1190 Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph–based labeling algorithm with application to vehicle routing. Transp Sci 55(1):4–28 Schneider M, Stenger A, Goeke D (2014) The electric vehicle-routing problem with time windows and recharging stations. Transp Sci 48(4):500–520 1097 1 3 Partial dominance inbranch‑price‑and‑cut algorithms for… Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265 Spliet R, Gabor AF (2015) The time window assignment vehicle routing problem. Transp Sci 49(4):721–731 Spliet R, Dabia S, Van Woensel T (2018) The time window assignment vehicle routing problem with time-dependent travel times. Transp Sci 52(2):261–276 Tilk C, Rothenbächer A-K, Gschwind T, Irnich S (2017) Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster. Eur J Oper Res 261(2):530–539 Tilk C, Bianchessi N, Drexl M, Irnich S, Meisel F (2018) Branch-and-price-and-cut for the active-passive vehicle-routing problem. Transp Sci 52(2):300–319 Toth P, Vigo D (eds) (2014) Vehicle routing: problems, methods, and applications. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Authors and Affiliations StefanFaldum1 · SarahMachate2· TimoGschwind2 · StefanIrnich1 * Timo Gschwind [email protected] Stefan Faldum stf[email protected] Sarah Machate [email protected] Stefan Irnich irnic[email protected] 1 Chair ofLogistics Management, Gutenberg School ofManagement andEconomics, Johannes Gutenberg University Mainz, Jakob-Welder-Weg 9, 55128Mainz, Germany 2 Chair ofLogistics, School ofBusiness andEconomics, RPTU Kaiserlautern-Landau, Gottlieb-Daimler-Straße 42, 67663Kaiserlautern, Germany