Mike Hewitt
email: mhewitt3@luc.edu

Fabien Lehuédé
email: fabien.lehuede@imt-atlantique.fr

The Service Network Scheduling Problem

We consider the optimization problem of determining schedules for shipments on known paths within a terminal network in order to minimize vehicle transportation costs. We refer to this problem as the Service Network Scheduling Problem and present two mixed integer programming formulations of that problem. The first is based on the classical idea of a time-expanded network. The second formulation is new and is based on sets of shipment consolidations. We show both analytically and computationally that the consolidation-based formulation can be the superior of the two, but that its enumerative nature renders it ineffective for instances with large numbers of shipments. Thus, we also present a column generation-based algorithm for solving the consolidation-based formulation that relies on solving relaxations that are integer programs. We demonstrate the superior performance of this algorithm with a computational study wherein we compare it against applications of state-ofthe-art approaches from the literature.

Introduction

Consolidation carriers are transportation companies that transport shipments that are small relative to vehicle capacity. Consolidation carrier is an umbrella term that covers companies participating in one (or both) of the Less-than-truckload (LTL) freight and small package/parcel industries. Both industries are large; in the United States the LTL industry was reported to be $46 billion in 2021 (Schulz 2021) while UPS reported $69.44 billion in revenue from its US and international small package operations in 2020 (UPS 2021). Many of these companies execute very large scale operations. For example, UPS reports delivering 6.3 billion packages in 2020 (UPS 2021).

As transportation exhibits economies of scale, profitability for such carriers is driven by consolidation. Specifically, dispatching vehicles that transport multiple shipments, each potentially associated with a different customer. Such consolidation is typically enabled by routing shipments on paths through a network of terminals as opposed to directly from customer origin to destination, as is often done in full truckload transportation. For large-scale operations, small percentage improvements in consolidation (typically measured by vehicle utilization) can lead to significant reductions in transportation costs.

Among the decisions that are taken by carriers to plan their network, a path has to be determined for each shipment. A path is defined by the sequence of terminals it visits, with the sequence beginning at the origin terminal for the shipment and ending at its destination terminal. Then, a schedule has to be determined for the path of each shipment. This schedule determines the time at which each leg of the path is executed. Finally, transportation moves of capacitated vehicles are planned to operate these transportation legs. Transportation moves executed by a vehicle incur a cost that is independent of the shipments it transports. Achieving high levels of consolidation of shipments in vehicles, and low transportation costs, requires determining paths for shipments through such networks, and schedules for those paths, that enable multiple shipments to dispatch on the same transportation move at the same time. The determination of such paths and schedules can often be assisted by solving some variant of the Scheduled Service Network Design Problem (SSNDP) [START_REF] Crainic | Service network design in freight transportation[END_REF][START_REF] Jarrah | Large-scale, less-than-truckload service network design[END_REF][START_REF] Zhu | Scheduled service network design for freight rail transportation[END_REF], Boland et al. 2017a,b, Hewitt 2019, Hewitt et al. 2019[START_REF] Marshall | Interval-based dynamic discretization discovery for solving the continuous-time service network design problem[END_REF].

We consider the case of a LTL freight transportation carrier that is reluctant to frequently changing shipment paths. Generally speaking, consistency in operations reduces complexity and errors and increases service quality. More specifically, the determination of shipment paths in a network can then trigger additional planning processes such as the assignment of shipment destination terminals to outbound doors in a cross-dock. Changing paths may necessitate changing these assignments. Some terminals may be equipped with information systems that facilitate changing these assignments with few subsequent operational errors. Others may not, in which case frequent changes may lead to shipments being loaded into vehicles at the wrong outbound door. Maintaining shipment paths, and hence door assignments, does leave flexibility with respect to the dispatch times of vehicles (scheduling of paths), especially if it allows to reduce the number of vehicle moves and transportation costs.

Hence, after solving a SSNDP based on a forecast, the carrier seeks to keep shipment paths constant over some planning horizon (e.g. a week), in order to maintain consistency with the operations that support the execution of those paths. However, in the near-term when more accurate estimates of shipment volumes are known, the schedules of those path are adjusted to maximize consolidation. Thus, we consider the problem of optimally determining shipment path schedules in order to minimize total vehicle transportation costs. We refer to this problem as the Service Network Scheduling Problem (SNSP).

To summarize, both the SSNDP and SNSP determine the number of vehicles to be dispatched on each transportation leg and the times of those dispatches. The SSNDP also determines a path and schedule for each commodity on the network. The SNSP keeps the paths taken by each commodity fixed and designs a new schedule for those paths. The SNSP can be seen as an operational adjustment of a load plan generated by solving a SSNDP at a tactical level. In addition to being relevant to practice, the SNSP can also appear as a subproblem of exact or heuristic algorithms for solving the SSNDP.

We propose two mixed integer programming formulations of the SNSP. The first is based on the classical idea of a time-expanded network (Ford andFulkerson 1958, 1962). The second is based on enumerations of consolidations of shipments, wherein a consolidation of shipments represents a set of shipments that are transported on the same move at the same time. We prove the equivalence of the formulations. We also show both analytically and computationally that the consolidation-based formulation can be the stronger of the two, but that its enumerative nature renders it computationally ineffective for instances based on large numbers of shipments.

Thus, we present an algorithm for solving the consolidation-based formulation that does not enumerate sets of consolidations a priori, but instead dynamically in the course of its execution. Clearly, one framework for such an algorithm is Branch-and-Price [START_REF] Barnhart | Branchand-price: Column generation for solving huge integer programs[END_REF][START_REF] Desaulniers | Column generation[END_REF]). As such an algorithm involves solving linear relaxations of a formulation, many of the technical advancements of today's solvers at solving integer programs is lost. We present an algorithm that operates in a fashion that is similar to Branch-and-Price, in that at each iteration it solves an optimization problem and then uses information from the solution to that problem to determine variables to add to the optimization problem. It differs from Branch-and-Price in that the optimization problem solved at an iteration is an integer program that is formulated in such a manner as to be a relaxation of the original problem. We refer to this algorithm as IP -ColGen, or, Integer Programming-based Column Generation. The idea of Integral Column Generation has been applied to other transportation applications [START_REF] Tahir | An improved integral column generation algorithm using machine learning for aircrew pairing[END_REF]. We prove the correctness of this algorithm and demonstrate with a computational study based on a US-based LTL carrier its ability to solve instances derived from real-world operations in much less time than applications of state-of-the-art methods from the literature.

We believe this paper presents multiple contributions to the literature on optimizing freight transportation. First, to the best of our knowledge, this is the first paper to study the SNSP. Second, we present a consolidation-based formulation of the SNSP that is new to the literature and computationally superior to an approach based on classical techniques. Third, we present an algorithm for solving this consolidation-based formulation that is very effective computationally in comparison to state-of-the-art methods.

The rest of this paper is organized as follows. Section (2) discusses literature relevant to the problem we consider. Section (3) describes the planning problem we consider in greater detail and presents two mixed integer programming formulations of that problem. Section (3.4) presents a comparison of the two formulations. Section (4) presents an algorithm for solving the consolidation-based formulation while Section (5) presents a computational analysis of the performance of the proposed algorithm with other methods. Section (6) concludes the paper and outlines future research directions extending the ideas presented in this paper.

Literature review

Much of the academic literature relevant to planning freight transportation operations in a terminal network focuses on determining paths and schedules by solving some variant of the Scheduled Service Network Design Problem (SSNDP) [START_REF] Crainic | Service network design in freight transportation[END_REF][START_REF] Jarrah | Large-scale, less-than-truckload service network design[END_REF][START_REF] Zhu | Scheduled service network design for freight rail transportation[END_REF], Boland et al. 2017a,b, Hewitt 2019, Hewitt et al. 2019[START_REF] Marshall | Interval-based dynamic discretization discovery for solving the continuous-time service network design problem[END_REF]. A related problem, the Service Network Design Problem (SNDP) determines shipment paths but not schedules [START_REF] Wieberneit | Service network design for freight transportation: a review[END_REF][START_REF] Andersen | Service network design with asset management: Formulations and comparative analyses[END_REF][START_REF] Andersen | Branch and price for service network design with asset management constraints[END_REF], Chouman and Crainic to appear, Baubaid et al. 2020). Both the SSNDP and SNDP have primarily been used to plan long haul freight operations.

The literature typically views solving the SSNDP (and SNDP) as part of a tactical planning process, meaning shipment paths and schedules are presumed fixed over some medium-term planning horizon [START_REF] Jarrah | Large-scale, less-than-truckload service network design[END_REF][START_REF] Erera | Improved load plan design through integer programming based local search[END_REF][START_REF] Zhu | Scheduled service network design for freight rail transportation[END_REF]. Some literature [START_REF] Gabriel | Service network design models for two-tier city logistics[END_REF][START_REF] Oskar Scherr | Service network design with mixed autonomous fleets[END_REF], 2020) considers the applicability of these problems to urban logistics. Some literature [START_REF] Andersen | Service network design with asset management: Formulations and comparative analyses[END_REF][START_REF] Andersen | Branch and price for service network design with asset management constraints[END_REF], Crainic et al. 2014, Hewitt et al. 2019) expands the decision-making of the SSNDP to include asset management considerations regarding vehicles such as the need to move a vehicle empty to position it for a future move. As the SNSP focuses only on scheduling paths, it considers a subset of the decisions prescribed by the SSNDP.

If one views vehicle transportation moves as machines, the SNSP is similar in nature to a Flow Shop Scheduling Problem (FSSP) [START_REF] Pinedo | Scheduling[END_REF]. However, in the FSSP the number of machines is given, whereas our problem seeks to minimize an objective that is a function of the number of machines used. The formulation we propose for the SNSP is similar in spirit to the optimization problem solved in Dynamic Discretization Discovery (Boland et al. (2017a)) to verify whether a given set of commodity paths and consolidations of commodities on arcs of those paths is feasible. It is also similar in spirit to the extended formulation of the Generalized Assignment Problem (GAP) presented in [START_REF] Savelsbergh | A branch-and-price algorithm for the generalized assignment problem[END_REF]. It is different in that the SNSP involves scheduling a sequence of activities (e.g. vehicle and shipment dispatches).

The algorithm we propose for solving the SNSP follows a classical framework wherein a relaxation of the problem is iteratively solved and refined until a solution to the relaxation is feasible (and hence optimal) to the original problem. Examples of applications of this framework include cutting plane algorithms such as Benders decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF]Branch-and-Cut (Nemhauser and[START_REF] George | Integer and combinatorial optimization[END_REF]. The algorithm we propose is similar to Branch-and-Price [START_REF] Barnhart | Branchand-price: Column generation for solving huge integer programs[END_REF][START_REF] Desaulniers | Column generation[END_REF] in that it solves an optimization problem that is formulated (in most iterations) over a subset of the variables in the original problem. The algorithm we propose is different from Branch-and-Price in that the optimization problem it solves is an integer program that is formulated to be a relaxation of the original problem. In this way, it is similar to the Dynamic Discretization Discovery (DDD) algorithm proposed in (Boland et al. 2017a)). The algorithm we propose is different from DDD in that the domains of the decision variables remain constant throughout its execution. It is also similar to Integral Column Generation [START_REF] Rönnberg | Column generation in the integral simplex method[END_REF], 2014[START_REF] Tahir | Integral column generation for the set partitioning problem[END_REF], 2021[START_REF] Tahir | Integral column generation for set partitioning problems with side constraints[END_REF]. It is different in that it is not based on simplex-type pivots.

Problem description and mathematical programming formulations

In this section, we first present a description of the transportation problem we seek to solve as well as modeling constructs and notation common to the two mixed integer programming formulations of that problem we propose. We then present those formulations. We finish with an analysis of the relative strength of the two formulations.

Problem description and mathematical notation

We consider a company that transports shipments from customer origin to customer destination. The transportation network of the company can be defined by a directed graph D = (N , A), where N is a set of nodes that model terminals in the network and A is a set of arcs that model transportation moves within that network. Formally, the set A consists of pairs (i, j), i, j ∈ N that model physical travel from terminal i to terminal j. We consider that the network is operated by a homogeneous fleet of vehicles with identical capacities, speed and cost. Associated with each arc (i, j) ∈ A is a travel time denoted by τ ij , a per-vehicle capacity denoted by u ij , and a per-vehicle cost denoted by f ij . We presume that each shipment is associated with a commodity k ∈ K, with K the set of all shipments/commodities that must be routed through the network. Associated with each commodity k ∈ K is an origin terminal, o k , and destination terminal, d k . We let e k denote the earliest time at which commodity k is available at its origin terminal, o k , and l k denote the latest time at which k can be delivered to its destination terminal, d k . Lastly, associated with commodity k is the shipment size denoted q k , quoted in the same unit as the vehicle capacity u ij , (i, j) ∈ A associated with arcs.

In the problem we study, we presume a single path is given for each shipment. We let

p k = v k 1 , ..., v k r k
represent the sequence of nodes from N in the path of commodity k ∈ K, with v k 1 = o k and v k r k = d k . We let P = ∪ k∈K p k denote the set of all such shipment paths.

We seek to schedule the dispatch time of each shipment on each move in its path, and schedule vehicle dispatches on moves to support shipment dispatches. We presume that a shipment must dispatch entirely at the same time on each move in its path. More specifically, the problem seeks to determine the times at which each shipment dispatches on each of the moves on its path, while ensuring that those dispatch times agree with the shipment earliest available and latest due times, and the travel times for those moves. In addition, the problem determines the dispatch times of vehicles with sufficient capacity to transport those shipments. We presume that the time horizon during which commodity paths are to be fixed can be discretized according to a time step (of e.g. 15 minutes) for which prescribed decisions can be executed. The objective is to minimize the total transportation cost associated with the vehicle moves needed to transport a known set of shipments over a fixed planning horizon. We refer to this problem as the Service Network Scheduling Problem (SNSP).

As complementary notation, for each commodity k ∈ K we let the node set N k ⊆ N contain the nodes v k i in that path and the arc set A k ⊆ A contain the arcs (v k i , v k i+1 ) in that path. We also let K ij = {k ∈ K : (i, j) ∈ A k } denote the set of commodities with a path that contains arc (i, j) ∈ A. Lastly, we note that given the path p k and earliest available and latest due times e k , l k for commodity k, one can derive a time window [α k v , β k v ] during which k can be at each node v in its path. Having defined notation that is common to our two formulations of the SNSP, we next present a mixed integer programming formulation that is based on a time-expanded network.

Time-expanded network formulation

For this formulation, we presume a discretization of time, T = {1, . . . , T }, of a planning horizon that is T periods long. We model shipment and vehicle movements in both space and time with the directed network D T = (N T , A T ∪ H T ). Here, N T consists of nodes of the form (i, t), i ∈ N , t ∈ T , that model actions that occur at terminal i during the time period represented by t. The set A T consists of arcs of the form ((i, t), (j, t ′ )), (i, t), (j, t ′ ) ∈ N T , i ̸ = j, t ′ = min(t ′′ ∈ τ |t ′′ -t ≥ τ ij ) and model traveling from terminal i at time t to arrive at terminal j at time t ′ . The set H T consists of arcs of the form ((i, t), (i, t + 1)), (i, t), (i, t + 1) ∈ N T and model waiting at terminal i from time t to time t + 1. Like above, we let the sets

N k T = {(i, t) ∈ N T : i ∈ N k }, A k T = {((i, t), (j, t ′ )) ∈ A T : (i, j) ∈ A k }
, and H k T = {((i, t), (i, t + 1)) ∈ H T : i ∈ N k } denote the portions of the time-expanded network that can be used by commodity k.

With this notation, we let the binary decision variable

x ktt ′ ij indicate whether commodity k ∈ K uses arc ((i, t), (j, t ′ )) ∈ A k T ∪ H k T .
We let the integer decision variable y tt ′ ij indicate the number of vehicles that move on arc ((i, t), (j, t ′ )) ∈ A k T . The time-expanded network formulation of the SNSP based on the network D T , that we refer to as TEN-SNSP (D T ), follows.

z TEN (D T ) = minimize ((i,t),(j,t ′ ))∈A T f ij y tt ′ ij (1) subject to ((i,t),(j,t ′ ))∈A k T ∪H k T x ktt ′ ij - ((j,t ′ ),(i,t))∈A k T ∪H k T x kt ′ t ji =      1 if (i, t) = (o k , e k ) -1 if (i, t) = (d k , l k ) 0 otherwise. ∀k ∈ K, ∀(i, t) ∈ N k T (2) k∈K:((i,t),(j,t ′ ))∈A k T q k x ktt ′ ij ≤ u ij y tt ′ ij ∀((i, t), (j, t ′ )) ∈ A T , (3)
x ktt ′ ij ∈ {0, 1} ∀((i, t), (j, t ′ )) ∈ A k T ∪ H k T , k ∈ K, (4)
y tt ′ ij ∈ N ∀((i, t), (j, t ′ )) ∈ A T . (5)
The objective (1) seeks to minimize the total costs associated with vehicle movements. Constraints (2) are standard flow conservation constraints, ensuring that each commodity departs its origin terminal at its earliest available time and arrives at its destination terminal at its latest due time. Constraints (3) ensure sufficient vehicle capacity is scheduled to support shipment movements. Constraints ( 4) and ( 5) define the decision variables and their domains. We note that the existence of a single path, p k , on which commodity k may be routed is reflected in the domains defined in constraints (4). One of the primary computational challenges associated with solving such a formulation is the size of the complete time-expanded network, D T , and the resulting number of decision variables in the model. However, similar to what was shown in Proposition 1 of Boland et al. (2017a) for the Scheduled Service Network Design Problem, a reduced time-expanded network D R T that consists of a well-chosen subset of points (i, t) ∈ N T can be formed such that the optimal solution of the formulation TEN-SNSP (D R T ) is also an optimal solution to TEN-SNSP (D T ). We restate this Proposition, albeit stated in terms of the SNSP below.

Proposition 1. Consider a time-expanded network D R T based on a set N R T that contains nodes of the form (o k , e k ) or (v k j , e k + j-1 i=1 τ v k i v k i+1 ), j = 2, . . . , r k , ∀k ∈ K and arc sets A R T , H R
T constructed accordingly. An optimal solution to the TEN-SNSP(D T ) can be determined by formulating and solving TEN-SNSP(D R T ).

Proposition 1 states that if the network is defined for a subset of nodes that represent terminals at times that are the earliest at which some commodity could reach that terminal, then it is sufficient to find the optimal solution to the SNSP.

We can also strengthen the formulation TEN-SNSP (D T ) with valid inequalities similar to the Arc-Time-Window inequalities presented in [START_REF] Hewitt | Enhanced dynamic discretization discovery for the continuous time load plan design problem[END_REF]. To define these inequalities, we let q ij = k∈Kij q k denote the total size of all commodities whose path includes arc (i, j). Then, we must have

t,t ′ ∈T :((i,t),(j,t ′ ))∈A T y tt ′ ij ≥ ⌈ q ij u ij ⌉ ∀(i, j) ∈ A. (6)
We refer to these inequalities as Agg-Arc-Capacity inequalities. Proposition 1 enables the TEN-SNSP (D T ) to be formulated in a static manner, albeit with a reduced node set. That formulation can then be strengthened with the Agg-Arc-Capacity inequalities. However, it is fairly easy to see that the Dynamic Discretization Discovery algorithmic framework presented in Boland et al. (2017a), and enhanced in [START_REF] Hewitt | Enhanced dynamic discretization discovery for the continuous time load plan design problem[END_REF], can be applied with nearly no modification to solve the SNSP.

Consolidation-based formulation

We next present a formulation of the SNSP that is based on sets of possible consolidations on each arc, (i, j) ∈ A. After presenting the formulation, we prove its equivalence to TEN-SNSP (D T ).

To define the formulation we let

C ij = {C 1 , . . . , C nij }, C g ⊆ K ij ∀g = 1, . . . , n ij
, denote all sets of commodities that can dispatch on arc (i, j) at the same time. Recalling that [α k i , β k i ] denotes the time window during which commodity k must depart from node i, we have that

C g = {k g 1 , . . . , k g mg } ∈ C ij ∀g = 1, . . . , n ij if and only if ∩ mg q=1 [α kq i , β kq i ] ̸ = ∅.
In words, a consolidation is feasible on an arc if and only if the time windows for all commodities in that consolidation overlap in at least one time point. That said, C ij also contains all singleton sets. Namely, if k ∈ K ij , then there exists g ∈ [1, n ij ] such that C g = {k}. In addition, we let C = ∪ (i,j)∈A C ij . Throughout this paper we will refer to "consolidation C g " as shorthand for the set of commodities {k g 1 , . . . , k g mg } contained in that consolidation. Regarding data elements associated with these consolidation sets, we let the attribute

ϕ k C ∈ {0, 1}, k ∈ K, C ∈ C represent whether k ∈ C. We also let s C = ⌈ k∈C q k uij ⌉ represent the number of vehicles needed on arc (i, j) ∈ A to transport consolidation C ∈ C ij .
To model the SNSP, we let the binary variable w C indicate whether the consolidation consisting of commodities in set C ∈ C ij traveling together on arc (i, j) ∈ A is chosen. Note this choice implies that the commodities must dispatch at the same time. We let the integer variable y ij represent the number of vehicles that dispatch on arc (i, j) ∈ A. We let the decision variables

γ k v k i v k i+1 , i = 1, . . . , r k -1 prescribe
the time at which commodity k dispatches on the arc (v k i , v k i+1 ), i = 1, . . . , r k -1 on its path. With these sets and decision variables, we define the optimization problem Cons-SNSP(C), as

z Cons (C) = minimize (i,j)∈A f ij y ij (7) subject to C∈Cij ϕ k C w C = 1 ∀k ∈ K, (i, j) ∈ A k , ( 8
) C∈Cij s C w C ≤ y ij ∀(i, j) ∈ A, (9)
γ k ij -γ k ′ ij ≤ M kk ′ i (1 - C∈Cij ϕ k C ϕ k ′ C w C ) ∀(i, j) ∈ A, k, k ′ ∈ K ij , (10)
γ k v k i v k i+1 + τ v k i v k i+1 ≤ γ k v k i+1 v k i+2 ∀k ∈ K, i = 1, . . . , r k -2, ( 11
)
α v k i ≤ γ k v k i v k i+1 ≤ β v k i ∀k ∈ K, i = 1, . . . , r k -1, ( 12
)
γ k v k i v k i+1 ∈ N ∀(v k i , v k i+1 ) ∈ p k , k ∈ K, (13)
w C ∈ {0, 1} ∀C ∈ C, (14)
y ij ∈ N ∀(i, j) ∈ A. ( 15
)
The objective seeks to minimize the total costs associated with vehicle moves that transport consolidations of shipments. Constraints (8) ensure that a consolidation is chosen for each commodity on each arc in its path. Constraints (9) ensure that sufficient capacity is paid for on each arc to support the consolidations chosen for that arc. Constraints (10) ensure that all commodities in the consolidation chosen for an arc dispatch at the same time. Constraints (11) ensure that the dispatch times for arcs on the path of a commodity agree with their travel times. Constraints (12) ensure the dispatch time decision variables occur within the corresponding time windows. Constraints ( 13), ( 14), and (15) define the decision variables and their domains.

While the big-M value in constraints (10) may lead to a weak formulation, the formulation can be tightened without rendering any solutions infeasible by setting

M kk ′ i = β k i -α k ′ i .
Lastly, we note that we can strengthen the Cons-SNSP(C) formulation with the inequality y ij ≥ ⌈ qij uij ⌉, ∀(i, j) ∈ A, which is analogous to the Agg-Arc-Capacity inequality for the TEN-SNSP(D T ).

Solving the proposed consolidation-based formulation will yield the same optimal objective function value as the time-expanded network-based formulation. More precisely, we have the following theorem. Its proof can be found in Appendix A.

Theorem 1. z TEN (D T ) = z Cons (C).
We note that if all travel times, τ, and commodity early, e, and late times, l, are integral the constraints (13) can be relaxed to allow the γ variables to take on fractional values. This can be seen by first observing that any solution with fractional values for some γ variables can be converted to another feasible solution of Cons-SNSP(C) with integral values for all γ variables through rounding. Second, as the γ variables do not appear in the objective, this rounding does not change the objective function value of the solution.

Lastly, we provide an example of the data derived to formulate the Cons-SNSP(C).

Example 1. Figure 1 illustrates a network, N , with four nodes and three arcs. All arcs have a travel time of one. Three commodities are to be routed through this network. Solid arrows in the figure indicate arcs in A, while dashed arrows indicate the origin and destination terminals for each commodity. Table 1 presents data regarding each commodity, including its origin and destination terminals, its early and late times, its path, its size quoted as a fraction of vehicle capacity, and its time window at each terminal on its path. The time windows identified in Table 1 for each commodity at each of the nodes a, b, and c (if applicable) are derived from that commodity's early and late times, knowledge of the path it must take, and travel times on arcs in that path.

To construct the consolidation-based formulation, we enumerate all possible consolidations on arcs (a, b), (b, c), and (c, d) given the time windows at nodes a, b, and c identified in Table 1. In addition to displaying them in Figure 1 below each arc, we list them in Table 2 along with other attributes of each consolidation.

The SNSP formulation for this example is detailed in Appendix B.

τ ab = f ab = 1 τ bc = f bc = 1 d τ cd = f cd = 1 k = 1,e 1 = 1,l 1 = 5 k = 2,e 2 = 4,l 2 = 7 k = 3,e 3 = 1,l 3 = 7 𝒞 ab = {{1}, {3}, {1,3}} 𝒞 bc = {{1}, {2}, {3}, {1,3}, {2,3}} 𝒞 cd = {{2}, {3}, {2,3}} Figure 1: Network N and commodities K in Example 1 Table 1: Commodity attributes in Example 1 Time windows k o k d k e k l k p k q k [α k a , β k a ] [α k b , β k b ] [α k c , β k c ] a c 1 4 a → b → c 0.75 1,2 2,3 - b d 4 7 b → c → d 0.55 - 4,5 5,6 a d 1 7 a → b → c → d 0.65 1,4 2,5 3,6 Table 2: Consolidations C Arc C k∈Cij q k s Cij a → b C 1 ab = {1} 0.75 1 a → b C 2 ab = {3} 0.65 1 a → b C 3 ab = {1, 3} 1.40 2 b → c C 1 bc = {1} 0.75 1 b → c C 2 bc = {2} 0.55 1 b → c C 3 bc = {3} 0.65 1 b → c C 4 bc = {1, 3} 1.40 2 b → c C 5 bc = {2, 3} 1.20 2 c → d C 1 cd = {2} 0.55 1 c → d C 2 cd = {3} 0.65 1 c → d C 3 cd = {2, 3} 1.20 2

Analytical comparison of formulations

We next compare the linear relaxations of each formulation. More specifically, we prove in Theorem 2 that solving the linear relaxation of TEN-SNSP(D T ) can not yield a larger bound than solving the linear relaxation of Cons-SNSP(C).

Theorem 2. Given the definitions of D T and C in Theorem 1, let LP-TEN and LP-Cons be the linear relaxations of problems TEN-SNSP(D T ) and Cons-SNSP(C). Let z ⋆ LP-TEN and z ⋆ LP-Cons be the objective function values of optimal solutions for each problem. Then z ⋆ LP-TEN ≤ z ⋆ LP-Cons .

Proof. We first consider LP-TEN and an optimal solution (x * , y * ) to that linear program. As LP-TEN is a minimization problem, in the absence of ( 6), the objective of LP-TEN implies that y * tt

′ ij = k∈K:((i,t),(j,t ′ ))∈A k T q k x * ktt ′ ij uij .
Relatedly, for a given (i, j) ∈ A we have that

((i,t),(j,t ′ ))∈A k T y * tt ′ ij = ((i,t),(j,t ′ ))∈A k T k∈K:((i,t),(j,t ′ ))∈A k T q k x * ktt ′ ij uij = k∈K:((i,t),(j,t ′ ))∈A k T q k uij ((i,t),(j,t ′ ))∈A k T x * ktt ′ ij = k∈K:((i,t),(j,t ′ ))∈A k T q k uij .
The last equality is due to the flow balance constraints (2) and the presumption that (i, j) is in the path already specified for each commodity k ∈ K ij . As ⌈x⌉ ≥ x ∀x ∈ ℜ, when ( 6) is included in the formulation we have

((i,t),(j,t ′ ))∈A k T y * tt ′ ij = ⌈ qij uij ⌉. Thus, we have z ⋆ LP-TEN = (i,j)∈A f ij ⌈ q ij u ij ⌉. (16)
Next, we consider LP-Cons, a single arc (i, j) ∈ A such that

K ij ̸ = ∅, and the constraints C∈Cij ϕ k C w C = 1, ∀k ∈ K ij (constraints (8) in the formulation). Summing constraints (8) over k ∈ K ij we have k∈Kij C∈Cij ϕ k C w C = C∈Cij |C|w C = |K ij |. As |C| ≤ |K ij | we have C∈Cij |C| |Kij | w C = 1 and thus C∈Cij w C ≥ 1. From constraints (9) we have that y ij ≥ C∈Cij s C w C = C∈Cij ⌈ k∈C q k uij ⌉w C . Thus, as ⌈x⌉ + ⌈y⌉ ≥ ⌈x + y⌉ and C∈Cij w C ≥ 1 we have that y ij ≥ ⌈ qij uij ⌉. As such, all solutions to LP-Cons satisfy y ij ≥ ⌈ qij uij ⌉ and thus z ⋆ LP-Cons ≥ (i,j)∈A f ij ⌈ qij uij ⌉ = z ⋆ LP-TEN .
In addition, there are also instances wherein z ⋆ LP-Cons > z ⋆ LP-TEN . For example, consider an instance of the LP-TEN derived from Example 1. In addition to constraints (6), which reflect the vehicle capacity needed when all three commodities dispatch at the same time, one can examine the time windows at b for commodities 1 and 3 to derive that y 23 bc + y 34 bc ≥ 1 and y 45 bc + y 56 bc ≥ 1. We illustrate in Figure 2a an optimal solution to this linear program, including these two additional inequalities. Recalling that in this example f ij = 1, ∀(i, j) ∈ A, we see that z ⋆ LP-TEN = 6. We illustrate an optimal solution to the corresponding formulation of the LP-Cons on a time-expanded network in Figure 2b. We first note that the w variables naturally take on binary values in this solution. In addition, as the s C coefficients associated with these variables are derived from applying the ⌈•⌉ operator, the solution to this linear program better approximates the vehicle capacity needed. More precisely, we have y ab = 2, y bc = 3, and y cd = 2. Thus, we have z ⋆ LP-Cons = 7 > 6 = z ⋆ LP-TEN . In addition, as the values of all decision variables in the solution to LP-Cons fall within the domains required by the Cons-SNSP(C), the solution is also the optimal solution to Cons-SNSP(C). The analysis in Section 3.4 suggests that Cons-SNSP(C) is the stronger formulation of the two proposed in Section 3 for the SNSP. However, its enumerative nature of is likely to lead to computational challenges when solving larger instances of the formulation. As such, in this section we present an algorithm for solving the Cons-SNSP(C) that does not enumerate the set C a priori, but instead dynamically in the course of its execution. In this section, we present an algorithm that at each iteration solves a relaxation of the original problem and then uses information from the solution to that relaxation to determine variables to add to the relaxation.

w {1,3} = 1 w {2} = 1 w {2,3} = 1 s {1,3} = 2 s {1,3} = 2 s {2} = 1 s {2,3} = 2 y ab = 2 y bc = 3 y cd = 2 (b) LP-Cons
In this section, we first present the relaxation the algorithm solves. We then illustrate with an example why it is a relaxation as well as formally prove this claim. We then outline the reasons why solutions to that relaxation may not be feasible for the Cons-SNSP(C) and how the algorithm chooses to strengthen the relaxation to render such solutions infeasible. We finish with a formal description of the algorithm and a proof of its correctness.

Relaxation of Cons-SNSP(C)

In this section, we present an integer program that is similar in form to Cons-SNSP(C), but defined over only a subset of C. Yet, the integer program is a relaxation of Cons-SNSP(C). We conclude this section with a proof of this claim.

This formulation is defined on subsets,

C ij = {C 1 , . . . , C n ij } ⊆ C ij , n ij ≤ n ij of the potential consoli- dations for each arc (i, j) ∈ A. We note that while C g ∈ C ij , it is not necessarily the case that C g = C g , wherein C g ∈ C ij .
As in the presentation of Cons-SNSP(C), we let C = ∪ (i,j)∈A C ij . The formulation is defined with the same y ij and γ k

v k i v k i+1
variables as in Cons-SNSP(C). The binary variables w C are defined as above, albeit only over the consolidations in sets C ij . The values ϕ k C are also defined as above. However, the values s C are defined differently from the values s C used to formulate the Cons-SNSP(C). Specifically, they are defined as

s C = s C if ∀C ′ ⊆ C, C ′ ∈ C ij , min C ′ ⊆C:C ′ ̸ ∈C ij s C ′ o.w. (17)
The if portion of equation ( 17) tests whether every subset of C is an element of C ij . In this case, the vehicle capacity associated with C in Rel-Cons-SNSP(C) is the actual capacity needed to transport the commodities of C. When this condition is not satisfied, s C is set to require the least vehicle capacity required of any subset of C that is not an element of C ij . As a result, the calculation of s C ensures that the number of vehicles needed to transport consolidation C is no greater than the number needed by any subset of C that is not currently considered by the relaxation. Note, (17

) implies that s C ≤ s C .
This definition is illustrated on the following example.

Example 2. We focus on a single arc (i, j) and four commodities with a path that contains that arc (e.g. K ij = {1, 2, 3, 4}). Data for this example is provided in Tables 3,4, and 5. Table 3 lists each commodity k ∈ K ij and its size, q k . Table 4 lists each of the possible consolidations of those commodities on arc (i, j), along with its total size and the number of vehicles it requires. We note that the set of maximal consolidations is

C max ij = {{1, 2, 3}, {1, 3, 4}, {1, 4}, {3, 4}}.
Table 5 provides a subset of these consolidations that can be used when formulating Rel-Cons-SNSP(C). We note that each of the maximal consolidations in Table 4 is listed in Table 5.

With these sets and decision variables we define the following optimization problem, which we refer to as Rel-Cons-SNSP(C).

z Rel-Cons (C) = minimize (i,j)∈A f ij y ij
C s C 1,2,3 1 1,3,4 1 1,4 1 3,4 1 1 1 2 1 3 1 4 1 subject to C∈Cij ϕ k C w C ≥ 1 ∀k ∈ K, (i, j) ∈ A k , ( 18
) C∈Cij s C w C ≤ y ij ∀(i, j) ∈ A, (19)
γ k ij -γ k ′ ij ≤ M (1 -ϕ C k ϕ C k ′ w C ) ∀(i, j) ∈ A, C ∈ C ij , k, k ′ ∈ K ij such that C \ {k}, C \ {k ′ } ∈ C ij , (20)
γ k v k i v k i+1 + τ v k i v k i+1 ≤ γ v k i+1 v k i+2 ∀k ∈ K, i = 1, . . . , r k -2, (21)
α v k i ≤ γ k v k i v k i+1 ≤ β v k i ∀k ∈ K, i = 1, . . . , r k , (22)
γ k v k i v k i+1 ∈ N ∀(v k i , v k i+1 ) ∈ p k , k ∈ K, (23)
w C ∈ {0, 1} ∀(i, j) ∈ A, C ∈ C ij , (24)
y ij ∈ N ∀(i, j) ∈ A (25)
Many of the constraints defining Rel-Cons-SNSP(C) are the same as those defining Cons-SNSP(C). The constraints that differ are constraints (18), ( 19), and (20). Constraints (18) ensure a commodity appears in at least one chosen consolidation for each arc in its path. Constraints (19) are of the same form as constraints (9) of Cons-SNSP(C) only with the coefficients s C . Constraints (20) ensure that two commodities dispatch on an arc at the same time under two conditions: (1) a consolidation is chosen for that arc that contains those two commodities, and, (2) for each commodity the set C also contains that consolidation without that commodity. The first condition is similar in spirit to what defines constraints (10) of Cons-SNSP(C). The second plays a role in ensuring Rel-Cons-SNSP(C) is a relaxation, as we will next see.

When Rel-Cons-SNSP(C) is defined with the appropriate set C (e.g. using the algorithms proposed in Section 4.2), it can be shown to be a relaxation of Cons-SNSP(C). To be more precise, we let C max ij denote the set of maximal consolidations on arc (i, j) ∈ A. Formally, the consolidation C ∈ C max ij if and only if there does not exist C ′ ∈ C ij and C ⊂ C ′ . We later prove that Rel-Cons-SNSP(C) is a relaxation when formulated with a consolidation set for each arc that contains all the maximal consolidations for that arc. More precisely, when formulated with sets C ij such that ∀C ∈ C max ij , C ∈ C ij . The proof of this statement involves showing that any solution to Cons-SNSP(C) can be used to construct a solution to the Rel-Cons-SNSP(C) of equal objective function value. However, before formally proving this result we illustrate why Rel-Cons-SNSP(C) is a relaxation in the case of Example 2.

Example 3. (continued from Example 2) Consider a solution ( w, γ, ȳ) to Cons-SNSP(C) that involves the consolidations {1, 2} and {3, 4}. Namely, w{1,2} = w{3,4} = 1. This in turn requires γ1 ij = γ2 ij and

γ3 ij = γ4 ij . Suppose that γ1 ij = γ2 ij = 1 and γ3 ij = γ4 ij = 3.
Collectively, these two consolidations require two vehicles to travel on arc (i, j) (i.e. ȳij = 2). We will use this solution to construct a solution (w, γ, y) to the Rel-Cons-SNSP(C) of equal objective function value.

We start by setting y ij = ȳij = 2. Thus, the constructed solution uses the same amount of vehicle capacity and the objective function values of the solution to the Cons-SNSP(C) and the constructed solution will be the same. We next set γ k ij = γk ij , k = 1, 2, 3, 4. In words, commodities dispatch at the same times in the two solutions.

Regarding the w variables, for each consolidation chosen in the solution to the Cons-SNSP(C) we identify a corresponding consolidation to be chosen in the solution to the Rel-Cons-SNSP(C). First, we consider consolidation {3, 4}, as w{3,4} = 1. As {3, 4} ∈ C ij , we set w {3,4} = 1. We next consider consolidation {1, 2}, as w{1,2} = 1. Here, we observe that {1, 2} ̸ ∈ C ij and thus we identify the minimal consolidation in C ij that contains {1, 2}. That such a consolidation exists is guaranteed as C ij contains the maximal consolidations {1, 2, 3}, {1, 3, 4}, {1, 4}, {3, 4}. In this case, {1, 2, 3} is the minimal consolidation containing {1, 2} and we set w {1,2,3} = 1.

We next discuss why this solution is feasible for the Rel-Cons-SNSP(C). We note that while commodity 3 appears in two chosen consolidations, constraints (18) are defined in such a manner that this is feasible. Next, we note that given the sizes of the commodities in the consolidations {1, 2, 3} and {3, 4} they collectively require three vehicles (s {1,2,3} = 2, s {3,4} = 1). However, because the consolidation {1, 2} is not present in C ij , Rel-Cons-SNSP(C) is formulated with s {1,2,3} = 1.

Thus, for constraints (19) we have s {1,2,3} w {1,2,3} + s {3,4} w {3,4} = 1 + 1 = 2 = y ij and the constraint is satisfied.

We next consider constraints (20). Note these constraints are defined for a pair of commodities k, k ′ and a given consolidation C only if the relaxation considers the consolidations C \ {k} and C \ {k ′ } (i.e. they are in C ij ). Regarding the chosen consolidation {3, 4} we note that as C ij contains the consolidations {3} and {4} then the constraint is defined for commodities 3 and 4 and consolidation {3, 4}. Given that 20) is not defined for commodities 2 and 3. Thus, w {1,2,3} can take on the value 1 even though γ 3 ij ̸ = γ 2 ij . Like vehicle capacity, constraints (20) are defined based on the recognition that consolidation {1, 2, 3} may serve as a proxy for consolidations it contains that are not represented in C. When it does, not all commodities in that consolidation are required to dispatch at the same time.

γ 3 ij = γ3 ij = γ4 ij = γ 4 ij , the constraint is satisfied. While w {1,2,3} = 1, as consolidation {1, 2} is not contained in C ij , constraint (
Lastly, we note that as the commodities dispatch at the same time in the two solutions, the γ variables satisfy constraints ( 21), ( 22), and ( 23) of the Rel-Cons-SNSP(C) because the γ variables satisfy the analogous constraints in the Cons-SNSP(C). Similarly, the domain constraints ( 24) and ( 25) are clearly satisfied.

This example illustrates the logic of the proof of the following result.

Theorem 3. Consider the directed network D and commodity set K.

Let C ij = {C 1 , . . . , C n ij } ⊆ C ij , n ij ≤ n ij and C = ∪ (i,j)∈A C ij . If for each arc (i, j) ∈ A the set C ij contains all maximal consolida- tions (e.g. ∀C ∈ C max ij , C ∈ C ij ), then z Rel-Cons (C) ≤ z Cons (C).
Proof. Consider a feasible solution (γ, w, ȳ) of Cons-SNSP(C). We will show that this solution can be used to construct a feasible solution (γ, w, y) of Rel-Cons-SNSP(C) of the same objective function value.

First, we set y = ȳ and γ = γ. Next, Rel-min . Such a set C Rel-min must exist as either C Cons is maximal, contradicting a premise of the theorem, or is contained in a maximal consolidation that is a member of the set C max ij . If there is more than one such minimal set, one is chosen at random. We then set w C Rel-min = 1. Next, ∀C ′ ∈ C ij such that we have not yet set w C ′ = 1 we set w C ′ = 0. Observe that by construction, each consolidation C Cons chosen in the solution to Cons-SNSP(C) is mapped to a single consolidation C Rel ∈ C ij such that w C Rel = 1. However, the mapping is not oneto-one. There may be multiple consolidations C Cons chosen in the solution to Cons -SN DP (C) that map to the same C Rel ∈ C ij and such that w C Rel = 1.

∀(i, j) ∈ A, consider all sets C Cons ∈ C ij such that wC Cons = 1. If ∃C Rel ∈ C ij such that C Rel = C Cons , then set w C Rel = 1. If such a set C Rel does not exist then let C Rel-min denote a minimal set in C ij such that C Cons ⊆ C
We next show that (γ, w, y) satisfy constraints ( 18) -( 25). Regarding constraints (18) we first recall that the values w satisfy constraints (8), meaning that for each k ∈ K, (i, j) ∈ A k , ∃C ∈ C ij such that k ∈ C and wC = 1. Next, we note that by construction, for each C ∈ C ij such that wC = 1 there is at least one C Rel ∈ C ij , C ⊆ C Rel , such that w C Rel = 1. Thus, we can conclude that for each k ∈ K, (i, j) ∈ A k , ∃C Rel such that k ∈ C Rel and w C Rel = 1. Thus, constraints (18) are satisfied. Next,consider constraints (19). We observe that as the values ( w, ȳ) satisfy constraints (9) we have that C∈Cij s C wC ≤ ȳij . For a given C Cons such that wC Cons = 1, we consider the corresponding set C Rel ∈ C ij such that w C Rel = 1 and the value s C Rel . Recalling equation ( 17) that determines the values s C we consider two cases. The first case is when C Cons ⊂ C Rel . In this case, we must have that

C Cons ̸ ∈ C ij and s C Rel = min C ′ ⊆C Rel :C ′ ̸ ∈C ij s C ′ ≤ s C Cons . The second case is when C Cons = C Rel . In this case, we have s C Rel ≤ s C Rel = s C Cons . As a result, we have y ij = ȳij ≥ C∈Cij s C wC ≥ C∈C ij s C w C and constraints (19) are satisfied.
Next, we consider constraints (20). We consider the set C Rel ∈ C ij such that w C Rel = 1 and pairs of commodities k, k ′ ∈ C Rel such that constraints (20) are defined. We have w C Rel = 1 because ∃C Cons ∈ C ij , C Cons ⊆ C Rel , such that wC Cons = 1. Because constraints (20) are defined and C Rel is chosen to be the minimal set that contains C Cons we must have k, k ′ ∈ C Cons . Thus, we must have γk ij = γk ′ ij as γ satisfy constraints (10). Given that γ = γ we have that γ satisfy constraints (20). Lastly, as γ satisfy constraints ( 11) and ( 12) and γ = γ, γ satisfy constraints ( 21) and ( 22). Clearly, (γ, w, y) satisfy the domain constraints ( 23),( 24), and (25).

Thus, (γ, w, y) is a feasible solution to Rel-Cons-SNSP(C) and as y = ȳ the objective values of (γ, w, y) and (γ, w, ȳ) in the respective optimization problems are the same. As every feasible solution to Cons-SNSP(C) can be mapped to a feasible solution of Rel-Cons-SNSP(C) of the same cost, we have that Rel-Cons-SNSP(C) is a relaxation of Cons-SNSP(C).

In summary, there are three characteristics of the formulation that render it a relaxation, assuming a suitable set C as indicated in Theorem 3. The first is that constraints (18) allow a commodity to appear in more than one consolidation on an arc in its path. The second is that the computation of s C may underestimate the number of vehicles required to transport a consolidation. The third is that potentially defining constraints (20) over subsets of pairs of commodities in a consolidation allows for two commodities to appear in a chosen consolidation on an arc but dispatch at different times.

Refining the relaxation with additional consolidations

As seen in the previous section, there are three characteristics of Rel-Cons-SNSP(C) that make it a relaxation of Cons-SNSP(C), even though it may not consider the entire set of consolidations C. Relatedly, there are three corresponding attributes of a solution (γ, w, y) to Rel-Cons-SNSP(C) that can render it infeasible for Cons-SNSP(C). We next discuss for each attribute the method that is executed to add consolidations to C to render such a solution infeasible when Rel-Cons-SNSP(C) is next solved. We note that two of the methods rely on first finding the power set, P(C ij ), of commodities in a consolidation, C ij , for an arc. Method 1: Insufficient capacity installed on an arc: Given equation ( 17) we know that s C ≤ s C . As such, while we must have y ij ≥ C∈C ij s C w C , we may also have

C∈C ij s C w C > y ij .
In other words, because Rel-Cons-SNSP(C) may under-estimate the number of vehicles needed to transport a consolidation on an arc, its solution may prescribe too few vehicles for the consolidations chosen for that arc.

In this case, for each C ∈ C ij such that s C < s C and w C = 1 we add sufficient missing consolidations in P(C ij ) to C ij to ensure that after doing so s C increases by at least one vehicle. More precisely, if s t C is the value at iteration t then the method identifies all C ⊂ C such that C ̸ ∈ C ij and s C ≤ s t C + 1 and adds those consolidations to C ij . After doing so, s t+1 C ≥ s t C + 1. Alternately, we could add all missing consolidations in P(C), leaving s t+1 C = s C for each such C. In either case, when Rel-Cons-SNSP(C) is next solved, the values (w, y) in the current solution no longer satisfy y ij ≥ C∈C ij s C w C . Returning to our example above, we have that y ij = 2, but s {3,4} = 1 and s {1,2,3} = 2. As such, we have s {1,2,3} w {1,2,3} + s {3,4} w {3,4} = 2 + 1 = 3 > y ij . As it is consolidation {1, 2, 3} such that s {1,2,3} < s {1,2,3} , the method adds consolidations {1, 2}, {1, 3}, and {2, 3} to C ij to increase s {1,2,3} to 2. Method 2: Commodity appears in multiple consolidations on an arc: Consider a commodity k and arc (i, j)

∈ A k such that ∃C g , C h ∈ C ij , w C g = w C h = 1, and k ∈ C g ∩ C h .
In other words, the commodity k appears in multiple chosen consolidations for the same arc. Such values would cause w to violate constraints (8) of Cons-SNSP(C). The method for handling such a solution is based on the following proposition which identifies how such a solution can be transformed to another solution that is feasible to the relaxation, of equal or lesser objective function value, and with fewer violations of constraints (8).

Proposition 2. Suppose C ∈ C ij such that ∀C d ⊆ C, C d ∈ C ij . Any solution (γ, w, y) to Rel-Cons-SNSP(C) such that w C g = w C h = 1, C g , C h ⊆ C ij and C g ∩ C h ̸ = ∅ can be transformed to another feasible so- lution (γ ′ , w ′ , y ′ ) of equal or lesser objective function value such that for all C m , C n ⊆ C ij wherein w ′ C m = w ′ C n = 1, we have C m ∩ C n = ∅.
Proof. Let C int = C g ∩ C h denote the consolidation containing the commodities that participate in both chosen consolidations. Because we have

∀C d ⊆ C, C d ∈ C ij , we have s C g = s C g and s C h = s C h . Thus, we have y ij ≥ s C g + s C h = ⌈ k∈C g \C int q k + k∈C int q k uij ⌉ + ⌈ k∈C h \C int q k + k∈C int q k uij ⌉ ≥ ⌈ k∈C g \C int q k + k∈C int q k uij ⌉ + ⌈ k∈C h \C int q k uij ⌉.
Because we have

∀C d ⊆ C, C d ∈ C ij we have that C h \ C int ∈ C ij .
Thus, the variable w C h \C int is defined for Rel -Cons -Sched(C) and setting w C h = 0, w uC h \C int = 1 and setting remaining variables to their values in (γ, w, y) yields a feasible solution of equal or lesser objective function value and one fewer violation of constraints (8).

Thus, when we encounter such a solution to the Rel-Cons-SNSP(C) we construct the set

C u-gh = C g ∪ C h . If we have C m ∈ C ij , ∀C m ⊆ C u-gh
we construct the alternative feasible solution as in the proof of Proposition 2. Otherwise, we create all missing consolidations in P(C u-gh ) and add them to C ij .

Returning to our example, we have C g = {1, 2, 3} and C h = {3, 4} and thus C u-gh ij = {1, 2, 3, 4}. The method would then add the consolidations {1, 2}, {1, 3}, and {2, 3} to C ij . Method 3: Pair of commodities in chosen consolidation but dispatch at different times: Consider an arc (i, j) ∈ A and consolidation

C ∈ C ij such that w C = 1. Next, suppose there exist commodities k, k ′ ∈ C such that γ k ij ̸ = γ k ′ ij , causing w Cij , γ k ij , and γ k ′ ij to violate constraints (10) of Cons-SNSP(C). Given the definition of constraints (20) in Rel-Cons-SNSP(C), we must have either C \ k ̸ ∈ C ij , or C \ k ′ ̸ ∈ C ij ,
or both. Such a solution can be rendered infeasible for Rel-Cons-SNSP(C) by adding to C ij whichever of the consolidations C \ k, C \ k ′ are missing.

Returning to our example, we see that w {1,2,3} = 1 but γ 1 ij = γ 2 ij = 1 and γ 3 ij = 3. This is feasible for Rel-Cons-SNSP(C) because consolidations {1, 2, 3} \ {3} = {1, 2} and {1, 2, 3} \ {2} = {1, 3} are not contained in C ij and thus constraints (20) are not present in Rel-Cons-SNSP(C). Thus, the method would add consolidations {1, 2} and {1, 3} to C ij .

Algorithm description and proof of correctness

In this section, we present a formal description of the algorithm we propose for solving Cons-SNSP(C), which we refer to as IP -ColGen. We note that we include in the description some steps that are not necessary for its correctness, but speed up its convergence. For example, at each iteration, the algorithm solves Cons-SNSP(C) to heuristically generate a primal solution. In addition, by ensuring that C ij contains both maximal consolidations and singletons, the Cons-SNSP(C) solved at an iteration is guaranteed to be feasible. We note that through a tuning exercise we determined that performing the refinement methods in the order Method 3, Method 1, and then Method 2 lead to the best performance of the algorithm.

In the interest of brevity, we do not provide a detailed description of how Step 6 of IP -ColGen is performed. However, we note that identifying aspects of a solution (γ, w, y) to the relaxation that render it infeasible for Cons-SNSP(C) can be done via simple inspection. For example, checking to see whether constraints (8) are satisfied can be done by looking at all consolidations C g , C h ∈ C ij such that w C g = w C h = 1 and checking that their intersection is empty. Checking whether constraints (9) are satisfied can be done by computing C∈Cij s C w C and observing whether it exceeds the value y ij . Finally, checking whether constraints (10) are satisfied can be done by looking at all consolidations C ∈ C ij such that w C = 1 and all commodities k, k ′ ∈ C and checking whether γ k ij = γ k ′ ij . We next prove the correctness of IP -ColGen.

Proposition 3. IP -ColGen is guaranteed to terminate with an optimal solution to Cons-SNSP(C) in a finite number of iterations. Stop. Current best primal solution is ϵ-optimal. 17:

end if 18: end while Proof. As Rel-Cons-SNSP(C) is a relaxation of Cons-SNSP(C) any optimal solution to Rel-Cons-SNSP(C) that is feasible for Cons-SNSP(C) is also optimal for Cons-SNSP(C). However, when an optimal solution to Rel-Cons-SNSP(C) is not feasible for Cons-SNSP(C), at least one of Steps 10, 11, or 12 of IP -ColGen will add a consolidation to C. As consolidations are never removed from C and C is finite, IP -ColGen must ultimately produce a set C that is equal to C.

When C = C, we have s C = s C ∀(i, j) ∈ A, C ∈ C. We also have constraints ( 20) defined for all k, k ′ ∈ C, (i, j) ∈ A, C ∈ C. Finally, as noted in Proposition (2), any solution to Rel-Cons-SNSP(C) such that a commodity participates in multiple consolidations on a given arc can be transformed to another feasible solution of equal or lesser objective function value where this does not occur. As such, any optimal solution to Rel-Cons-SNSP(C) is either feasible and optimal for Cons-SNSP(C), or can be converted to a feasible and optimal solution for Cons-SNSP(C).

Other enhancements

In this section, we identify other enhancements to IP -ColGen that computational experiments indicated improved its performance. These enhancements involve adding additional consolidations to C at an iteration above and beyond what is necessary for its correctness. Adding consolidations based on commodities that dispatch at the same time: We recall that in a solution to Rel-Cons-SNSP(C) we may have w C = 1 for consolidation C but not all commodities k ∈ C dispatch at the same time. In this case, we partition C into sets of commodities that dispatch at the same time in the solution and add a consolidation to C ij for each set of commodities that is not in C ij . More precisely, we add sets

C g , g = 1, . . . , n ij such that C = ∪ n ij g=1 C g , C g ∩ C h = ∅, g = 1, . . . , n ij -1, h = g + 1, . . . , n ij and γ k ij = γ k" ij ∀k, k ′ ∈ C g ij .
In this case, we add to C ij the sets C g that it does not currently contain. Returning to our example, we have w {1,2,3} = 1 but γ 1 ij = γ 2 ij = 1 and γ 3 ij = 3. As commodities 1 and 2 dispatch together in this solution and {1, 2} ̸ ∈ C ij , the method would add consolidation {1, 2} to C ij . Adding missing subset consolidations: Recalling the computation of s C in equation ( 17), we see that when adding consolidation C to C ij we will have s C < s C if there exists a subset consolidation,

C ′ ⊆ C, such that C ′ ̸ ∈ C ij and s C ′ < s C . Thus, we add to C ij all consolidations C ′ ⊆ C such that |C ′ | ≤ κ and C ′ ̸ ∈ C ij .
Here, κ is an algorithm parameter. able to solve every instance. We also see that both dynamic methods are able to solve every instance. In addition, of the two dynamic methods, IP -ColGen does so in less than a third of the time required by DDD-SNSP.

We next report in Table 7 the average times to completion for each method and each number of commodities in an instance. We see that for every number of commodities, IP -ColGen requires the least time to finish. For instances with 250 commodities or fewer, Cons-SNSP(C) is the second fastest method. However, for instances with more than 250 commodities, DDD-SNSP is the second fastest method. We also see that the time required by Cons-SNSP(C) rises dramatically as the number of commodities in an instance increases. Not surprisingly, this can be attributed to the need to enumerate all possible consolidations of commodities in order to formulate Cons-SNSP(C). We study the effort associated with this enumeration in Table 8. This table reports, by number of commodities in an instance, the percentage of instances wherein all consolidations could be enumerated within the two hour time limit. It also reports the average time needed for the enumeration when it could be completed within the two hour limit. We see a general rise in the average time needed by the enumeration as the number of commodities in an instance increases. For the 300 and 350 commodity instances, we observe that it is impossible to enumerate all consolidations for the instances with the widest delivery windows. For the 450 and 500 commodity instances, the feasible consolidations could be enumerated only for the narrowest delivery window setting. However, Table 7 indicates that formulating and solving the Cons-SNSP(C) can be computationally effective when the number of commodities in an instance is not too large. To understand why, we formulated and solved the linear relaxations associated with the two static methods. We compare the objective function value, z Meth LP , of the linear relaxation associated with method Meth (e.g. Cons -SN SP (C)) with the objective function value, z Cons (C), of the optimal solution to the integer program Cons-SNSP(C). We report in Table 9 averages of the gap (z Cons (C) -z Meth LP )/z Cons (C) and the time required to formulate and solve linear relaxations. We note we only consider instances wherein the set C could be enumerated and the resulting linear programming relaxation of Cons-SNSP(C) solved in the two hours time limit. We see that solving the Cons-SNSP(C) yields a much stronger lower bound than the linear relaxation of TEN-SNSP(D R T ). However, it also takes much more time to solve. Note that the time recorded for solving the linear programming relaxation of Cons-SNSP(C) includes the time needed to enumerate the consolidations needed by the formulation. We next turn our attention to the two dynamic methods. Another parameter defining an instance is the number of hours added to the delivery window offered by the carrier. To understand the impact of this parameter value on the performance of the two dynamic methods we report in Table 10 the average time to termination, averaged over instances with the same number of additional hours.

We see that the behavior of DDD-SNSP and IP -ColGen differs with respect to this parameter. Specifically, for IP -ColGen the time it requires to solve an instance increases in the number of hours added to a delivery window. However, for DDD-SNSP, the time (mostly) decreases. That the time required by IP -ColGen increases is likely due to the fact that the wider the delivery windows the greater the number of consolidations that the algorithm may need to consider. On the other hand, DDD-SNSP requires fewer iterations when the delivery windows are wide. Next, we analyze in Table 11 the performance of IP -ColGen in more detail. In column "# Iterations" of Table 11 we report the average number of iterations IP -ColGen executed before termination. We also report in Table 11 the quality of the first lower bound and primal solution produced by IP -ColGen. Specifically, if lb f irst is the lower bound derived from solving Rel-Cons-SNSP(C) in the first iteration and ub last is the upper bound reported at its termination then we measure the quality of the initial lower bound with the gap (ub last -lb f irst )/ub last . With lb last and ub f irst defined similarly, we measure the quality of the initial upper bound produced by IP -ColGen with the gap (ub f irst -lb last )/ub f irst . We first observe that IP -ColGen is able to produce a provably optimal solution in a small number of iterations. This is likely because the quality of the initial lower and upper bounds IP -ColGen produces are quite high, with the lower bound of slightly higher quality than the upper bound. On average, after its first iteration IP -ColGen has found a primal solution and dual bound that together yield an optimality gap of 0.85%.

Conclusion and future work

In this paper, we present two mixed integer programming (MIP) formulations of a scheduling problem that can be solved to plan the operations of freight transportation carriers. More specifically, carriers that transport shipments that are small relative to vehicle capacity. Given these small sizes, the carriers seek to route and schedule shipments through a terminal network such that they may consolidate, i.e. be transported by the same vehicle. The literature generally views determining routes and schedules as a tactical planning problem, with most papers on this topic discussing some variant of the Scheduled Service Network Design Problem (SSNDP). We consider a more operational problem wherein shipment paths have already been determined and thus it is the shipment and vehicle schedules that need to be optimized. We call this problem the Service Network Scheduling Problem (SNSP).

One of the MIP formulations is based on the idea of a time-expanded network. The other is based on enumerating all sets of shipments that can dispatch at the same time when traveling from one terminal to the next (i.e. "consolidations."). With a computational study we show that when enumerating all such sets is not too time-consuming, solving the consolidation-based formulation was much more effective. This is in part because its linear programming relaxation provides a much stronger lower bound on the objective function value of the optimal solution to the integer program. However, for instances with larger sets of shipments, the enumerative nature of the consolidation-based formulation renders it computationally ineffective.

We also propose an algorithm for solving the consolidation-based formulation without generating all sets of consolidations a priori. The algorithm instead generates these sets dynamically and follows an algorithmic strategy that is similar in spirit to Branch-and-Price, but solves optimization problems at iterations that are integer programs instead of linear programs. We prove the correctness of this algorithm and with an extensive computational study illustrate its superior performance to the previously presented methods as well as a state-of-the-art benchmark from the literature, Dynamic Discretization Discovery.

Regarding future work, a Branch-and-Price-based algorithm for the problem is likely worth developing, potentially in the context of a hybrid method that alternates between Branch-and-Price and the method we propose in this paper. Solution methods can also be developed for other planning problems encountered by consolidation carriers that rely on solving the SNSP as a subroutine. Heuristics for the SSNDP could be developed that evaluate a neighboring solution by first routing commodity flows in the terminal network and then scheduling them via the SNSP. Given that heuristics often perform best when solution evaluation is fast, executing just the first iteration of IP -ColGen may be an effective strategy, particularly given the computational results that indicate the high quality of the primal solution and dual bound produced at the first iterations of IP -ColGen.

The consolidation-based formulation and algorithm proposed in this paper can be adapted/incorporated into exact methods for the SSNDP. For example, solving a hybrid formulation wherein some arcs in the network are modeled on a time-expanded network and others are modeled as in the Cons-SNSP(C) may be computationally effective. Such a formulation may be particularly appropriate for carriers that operate networks that have a hub-and-spoke-type structure, with spokes connecting to few hubs. With such a network, it is not uncommon for all potential paths for a shipment that originates at a spoke to first move to the same hub. Thus, the arc that models this first move is amenable to the consolidationbased formulation of the Cons-SNSP(C). A similar observation can be made regarding shipments that are destined for a common spoke.

B Cons-SNSP(C) formulation for Example 1

Given the consolidations enumerated in Table 4, the Cons-SNSP(C) formulation for Example 1 is below.

z Cons (C) = minimize f ab y ab + f bc y bc + f cd y cd subject to

w C 1 ab + w C 3 ab = 1, w C 2 ab + w C 3 ab = 1, w C 1 bc + w C 4 bc = 1, w C 2 bc + w C 5 bc = 1, w C 3 bc + w C 4 bc = 1, w C 1 cd + w C 3 cd = 1, w C 2 cd + w C 3 cd = 1, w C 1 ab + w C 2 ab + 2w C 3 ab ≤ y ab , w C 1 bc + w C 2 bc + w C 3 bc + 2w C 4 bc + w C 5 bc ≤ y bc , w C 1 cd + w C 2 cd + w C 3 cd ≤ y cd , γ 1 ab -γ 3 ab ≤ 1(1 -w C 3 ab ), γ 3 ab -γ 1 ab ≤ 4(1 -w C 3 ab ), γ 1 bc -γ 3 bc ≤ 2(1 -w C 4 bc ), γ 3 bc -γ 1 bc ≤ 3(1 -w C 4 bc ), γ 2 bc -γ 3 bc ≤ 3(1 -w C 5 bc ), γ 3 bc -γ 2 bc ≤ 1(1 -w C 5 bc ), γ 2 cd -γ 3 cd ≤ 3(1 -w C 3 bc ), γ 3 cd -γ 2 cd ≤ 1(1 -w C 3 cd ), γ 1 ab + 1 ≤ γ 1 bc , γ 2 bc + 1 ≤ γ 2 cd , γ 3 ab + 1 ≤ γ 3 bc , γ 3 bc + 1 ≤ γ 3 cd , 1 ≤ γ 1 ab ≤ 2, 2 ≤ γ 1 bc ≤ 4, 4 ≤ γ 2 bc ≤ 5, 5 ≤ γ 2 cd ≤ 6, 1 ≤ γ 3 ab ≤ 4, 2 ≤ γ 3 bc ≤ 5, 3 ≤ γ 3 cd ≤ 6,

Figure 2 :4

 2 Figure 2: Optimal linear relaxation solutions for Example 1

Algorithm 1

 1 IP-ColGenInput: Time limit τ , Optimality tolerance ϵ Input: Flat network D = (N , A), commodity set K 1: for all (i, j) ∈ A do 2:Set C ij = C max ij∪ k∈Kij {k} {Initialize consolidation set for each arc with maximal consolidations and singletons} 3: end for 4: while not solved and elapsed time < τ do 5: Solve Rel-Cons-SNSP(C) for dual bound lb Cons 6: Determine whether solution to Rel -Cons -SN DP (C) is feasible for Cons-SNSP(C) Add consolidations to C via Method 3 to rectify consolidated commodities that dispatch at different times 11: Add consolidations to C via Method 1 to rectify insufficient capacity 12: Add consolidations to C via Method 2 to rectify commodities that appear in multiple consolidations 13: end if 14: Solve Cons-SNSP(C) for primal bound ub Cons 15:if (ub Cons -lb Cons )/ub Cons < ϵ then 16:

Table 3 :

 3 Commodities K ij and their sizes

			Table 4: Possible consolida-
			tions, C ij			Table 5: Subset of consolida-
			C	k∈C q k	s C	tions, C ij
			1,2,3	1.20	2.00
			1,3,4	1.20	2.00
	Commodity k 1 2 3 4	q k 0.80 0.20 0.20 0.20	1,2 1,3 1,4 2,3 3,4 1	1.00 1.00 1.00 0.40 0.40 1.00	1.00 1.00 1.00 1.00 1.00 1.00
			2	1.00	1.00
			3	1.00	1.00
			4	1.00	1.00

Table 7 :

 7 Average time to termination (seconds)

	Static	Dynamic

Table 8 :

 8 Effort to enumerate consolidations

	|K|	100	150	200	250	300	350	400	450	500	Average
	% instances 100.00% 100.00% 100.00% 100.00% 75.00% 75.00% 100.00% 25.00%	25.00%	77.78%
	Time (sec.)	0.09	0.36	1.75	3.56	6.58	67.76	583.30	232.15	3,143.07	212.66

Table 9 :

 9 Strength of LP bound and time to solve LP, averaged over all instances

		Reduced T-E Network + Agg-Arc-Capacity Cons-SNSP(C)
	Gap with best IP sol'n	5.23%	1.64%
	Time (sec.) to solve LP	186.10	1,047.20

Table 10 :

 10 Average time to termination, by number of additional hours in delivery window

	Hours added
	to delivery window IP -ColGen DDD-SNSP
	0	11.59	125.07
	3	24.12	90.18
	6	22.97	86.6
	9	54.91	88.69

Table 11 :

 11 Performance of IP -ColGen in detail

	# Commodities Iterations Quality init. LB Quality init. UB
	100	1	0.22%	0.22%
	150	1	0.24%	0.24%
	200	1	0.09%	0.09%
	250	1	0.41%	0.41%
	300	1.25	0.30%	0.60%
	350	1.25	0.69%	0.84%
	400	2	0.98%	1.06%
	450	1.75	1.30%	1.26%
	500	3.25	1.39%	1.13%
	Average	1.5	0.63%	0.65%

  w C 1 ab , w C 2 ab , w C 3 ab , w C 1 bc , w C 2 bc , w C 3 bc , w C 4 bc , w C 5 bc , w C 1 cd , w C 2 cd , w C 3 cd ∈ {0, 1}, y ab , y bc , y cd ∈ Z.

Aknowledgment

We would like to acknowledge the support of a 2018 Cross Regional Grant from the INFORMS Transportation Science & Logistics Society.

Computational analysis

In this computational study we compare four methods for solving the SNSP. The first two methods are static in that they involve instantiating a mixed integer programming formulation of the SNSP that is then solved. The first, labeled Cons-SNSP(C), consists of enumerating the set C and solving the resulting consolidation-based formulation, Cons-SNSP(C). The second, labeled "Reduced T-E Network + Agg-Arc-Capacity" consists of generating a reduced time-expanded network D R T as described in Proposition 1 and then solving the resulting TEN-SNSP(D R T ) formulation, albeit strengthened with the Agg-Arc-Capacity inequalities (6). The second two methods are dynamic, in that they involve iteratively solving integer programs that are modified at each iteration in a manner that guarantees their solution will ultimately produce a provably optimal solution. More precisely, the third method is to solve the Cons-SNSP(C) with the IP -ColGen approach described in Section 4. The fourth, labeled "DDD-SNSP," is to solve the TEN-SNSP(D T ) with the enhanced dynamic discretization discovery algorithm of [START_REF] Hewitt | Enhanced dynamic discretization discovery for the continuous time load plan design problem[END_REF]. We first describe the experimental setting underlying the computational analysis and then the results of those experiments.

Computational setting

To perform our computational analysis, we generated a set of instances based on a portion of the network of a United States-based LTL carrier. Specifically, we considered a portion of the network that consists of 25 terminals (e.g. |N | = 25) and 530 physical moves between terminals (e.g. |A| = 530). Cost, capacity, and travel time data were provided by the carrier. In addition, the carrier provided a load plan that prescribed paths through the terminal network for pairs of terminals (o, d) ∈ N based on their customer base at the time. We randomly generated instances that vary in the number of commodities (100,150,200,250,300,350,400,450, and 500) and the width l k -e k of the delivery window of each commodity. Specifically, we considered four widths, with the first corresponding to the delivery window quoted by the carrier. The remaining three consist of the length of that path (in time) plus three, six, or nine hours. For each of the nine numbers of commodities and four delivery window widths, we generated five instances. When doing so, the size of each commodity was randomly drawn from distributions fit to carrier historical data of shipment sizes. In total, our instance set consists of 225 instances.

All experiments were run on a computer equipped with 64 Intel Xeon Gold 6130 CPU processors operating at 2.10GHz and running the Ubuntu distribution of the Linux operating system. The DDD approach was implemented in C++, which solved optimization models with CPLEX 12.10 (Studio-CPLEX 2013). For the other approaches, the formulations and code to instantiate them were implemented in Python 3.7 (VanRossum and Drake 2010). For those approaches, optimization models were solved with CPLEX 12.10 (Studio-CPLEX 2013). All code was run for two hours, or, 7,200 seconds. All optimization models were solved to a 1% tolerance. MIPs solved in the course of executing IP -ColGen were solved with the same limits. When executing IP -ColGen a limit of 5,000 was placed on the total number of consolidations added to C at an iteration. The parameter κ for that algorithm was given the value 7. The values of 5,000 and 7 were determined through a parameter tuning exercise. All times reported are in seconds.

Computational results

We first compare the four methods on two dimensions: (1) the percentage of instances the method could solve within the 7,200 second time limit, and, (2) the average time the method needed to terminate. We report these percentages and times to termination, averaged over all instances, in Table 6. We see that of the two static methods, solving the consolidation-based formulation enabled the largest percentage of instances to be solved and required less time to do so. However, neither static method is

A Proof of Theorem 1

We next provide a formal proof that solving the consolidation-based formulation yields the same optimal objective function value as solving the time expanded-network based formulation.

Proof. We begin by showing that any solution (x T EN , y T EN ) to TEN-SNSP(D T ) can be transformed to a solution (γ Cons , w Cons , y Cons ) of Cons-SNSP(C) of equal cost. First, for each k ∈ K and arc ((i, t), (j,

Given that D T is constructed such that when ((i, t), (j, t ′ )) ∈ A T , t ′ ≥ t + τ ij and the presence of the flow balance constraints (2) in TEN-SNSP(D T ), these γ kCons ij values satisfy constraints (11), ( 12), and (13) of Cons-SNSP(C). Regarding vehicle moves, for all (i, j) ∈ A, let y Cons ij = ((i,t),(j,t ′ ))∈A T y tt ′ T EN ij . Clearly, the values y Cons ij satisfy constraints (15). We next consider constraints (8) of Cons-SNSP(C). Consider a given (i, j) ∈ A and times t, t ′ such that ((i, t), (j, t ′ )) ∈ A T and ∃k ∈ K ij such that x ktt ′ T EN ij = 1. For such a t, consider the maximal set of commodities

As all the time windows for commodities in K t ij overlap in the time t, there must exist a set

Note that because the values x ktt ′ T EN ij satisfy the flow balance constraints (2) in TEN-SNSP(D T ) associated with nodes of the form (i, •) ∈ N T , there is exactly one t such that

More generally, because the values x ktt ′ T EN ij satisfy the flow balance constraints (2) in TEN-SNSP(D T ), for a given k and arc (i, j) in its path there must be a single t such that x ktt ′ T EN ij = 1. Hence, these w Cons values satisfy constraints (8) of Cons-SNSP(C).

Similarly, note that by the construction of the variable values

As (x T EN , y T EN ) is feasible for TEN-SNSP(D T ) we have

and constraints (9) are satisfied. Set the value of all (γ Cons , w Cons , y Cons ) variables not already given a value to zero. The resulting values (γ Cons , w Cons , y Cons ) are feasible for Cons-SNSP(C) and have objective function value (i,j)∈A f ij y Cons ij = (i,j)∈A f ij ((i,t),(j,t ′ ))∈A T y tt ′ T EN ij . In the second part of the proof, let us consider a solution (γ Cons , w Cons , y Cons ) to Cons-SNSP(C). We show that it can be transformed to a feasible solution of the TEN-SNSP(D T ). Consider a given k ∈ K and dispatch variable values γ kCons

and for all i = 1, . . . , r k -1 find the smallest

Note such a t ′ must exist by construction of D T and because the variable values γ Cons satisfy constraints (11) and ( 12) of Cons-SNSP(C). Set

the values of some variables

associated with waiting arcs ((v i+1 , t), (v i+1 , t + 1)) ∈ H T will have to be set to 1 as well. A similar statement holds when Next, consider an arc (i, j) ∈ A and consolidation

Note that, because the variable values γ Cons , w Cons satisfy constraints (10), we have

s Cij for the smallest t ′ such that ((i, t), (j, t ′ )) ∈ A T . Such a t ′ must exist by construction of D T . The values y tt ′ T EN ij satisfy the domain constraints (5) of TEN-SNSP(D T ). Recalling that s Cij = ⌈ k∈Cij q k /u ij ⌉, we have that

and the values (x T EN , y T EN ) satisfy constraints (3). Set all variables y tt ′ T EN ij not already given a value to zero. The resulting variable values (x T EN , y T EN ) are feasible for TEN-SNSP(D T ) with objective value ((i,t),(j,t ′ ))∈A T f ij y tt ′ T EN ij = (i,j)∈A f ij t∈T C q ij ∈Cij (t) s C q ij = (i,j)∈A f ij y ij . We have that any feasible solution to TEN-SNSP(D T ) can be converted to a feasible solution of Cons-SNSP(C) with the same objective value and vice versa. Thus, z T EN (D T ) = z Cons (C).