Theoretical Paper

Introduction

This paper proposes a branch-and-price algorithm as an exact algorithm for the cross-docking supply chain network design problem (CDSCNDP) introduced by Sung and Song (2003). The problem (CDSCNDP) is concerned with optimally locating cross-docking (CD) centres and allocating vehicles for direct transportation services from the associated origin node to the associated CD centre or from the associated CD centre to the associated destination node so as to satisfy a given set of freight demands at minimum cost subject to the associated service (delivery) time restriction. Each freight demand is assumed to be delivered through just one CD centre (where operations including sorting and consolidating are handled) located between origin and destination nodes. Thus, it can be checked at a pre-processing stage whether each demanded freight can be delivered through some CD centre within the associated delivery time limit or not. This will be discussed more in the next section. Moreover, it is assumed that two types of vehicles are available in the network and that one of the types has the smaller capacity than the other type. The vehicle cost of the smaller type is assumed to be less than that of the other type, while being larger in the vehicle cost per unit capacity than that of the other type.

As discussed in Sung and Song (2003), the problem (CDSCNDP) is different from many ordinary network design problems including hub networks design problems (Campbell, 1994; Aykin, 1995; Sung and Jin, 2001), less-than-truck-load (LTL) transportation networks design problems (Powell, 1986; Powell and Sheffi, 1989; Crainic and Jacques, 1992; Akyilmaz, 1994; Farvolden and Powell, 1994) and air networks design problems for express shipment delivery (Barnhart and Schneur, 1996; Kim et al, 1999; Armacost et al, 2002) in the sense that it considers the integrated issue incorporating discrete transportation units (vehicles) and service time restrictions explicitly as well as facility location and vehicle allocation.

The expected contributions of this paper can be specified as follows:

• It presents an exact algorithm. An exact algorithm is necessary for the following reasons even if the problem was proven to be NP-hard in Sung and Song (2003). First, the problem (CDSCNDP) is concerned with decisions on the strategic and tactical levels of system designs including facility location and investment on vehicles so that it may be desirable to find an optimal solution. Second, an exact algorithm may provide a strong basis to evaluate the performance of any other heuristics for the problem (CDSCNDP). In other words, the proposed exact algorithm may be used as an effective strategic planning tool for small-scale problem instances. It may also be used as an evaluation basis for any existing heuristics or those to be developed for large-scale problem instances as well.
• Some of the solution properties characterized in this paper can also be used for deriving any efficient local search heuristics with the move operation (neighbourhood search operation) of modifying assignment of some freight demands from current CD centres to other CD centres. The move operation, denoted by MOVE_MD, is easy to use, referring to Sung and Song (2003). As the operation MOVE_MD is performed, the delivery quantity associated with each direct service can be updated. Therewith, the contribution of the operation MOVE_MD to the objective total cost can be computed by finding how many vehicles are needed for the direct services modified by the operation, which corresponds to solving vehicle allocation problems associated with the modified direct services. This implies that the efficiency of such a local search heuristic is dependent on how efficiently the vehicle allocation problems can be solved. In order to solve the vehicle allocation problems, several solution properties were characterized in Sung and Song (2003). In this connection, more efficient solution properties are characterized in this paper.

The remainder of this paper is organized as follows. The next section presents the path-based formulation derived in Sung and Song (2003), and also derives a set-partitioning-based formulation for the problem (CDSCNDP). It is shown that the proposed set-partitioning-based formulation (SPBF) can be used to derive a better lower bound than the existing path-based formulation. Next, we follow-up with a section that characterizes some solution properties that are used to derive a branch-and-price algorithm based on the SPBF. The penultimate section presents the computational results to evaluate the performance of the derived algorithm and the contribution of the solution properties in improving the efficiency of the aforementioned local search heuristics. Finally, the last section makes concluding remarks.

Problem formulations

Path-based formulation

For the problem (CDSCNDP), a path-based formulation was derived in Sung and Song (2003) by use of the following notation.

Sets

I

set of origin nodes (terminals representing manufactures and suppliers)

J

set of destination nodes (terminals representing retailers and customers)

K

set of intermediate nodes (terminals representing CD centres)

V

set of all nodes, V=IJK

E_IN

set of edges (representing potential direct services) from origin nodes to intermediate nodes, that is E_IN={e=(i,k)|iI,kK}

E_OUT

set of edges (representing potential direct services) from intermediate nodes to destination nodes, that is E_OUT={e=(k,j)|kK,jJ}

E

set of all edges, that is E=E_INE_OUT

Q

set of freight demands each of which is represented by an ordered pair of two nodes (i,j), where i and j denote the associated origin node and the associated destination node, respectively

Q_k

set of freight demands that can be transported through the intermediated node (CD centre) k

Parameters

f_k

setup cost of the intermediate node (CD centre) k

h_ik¹,h_ik²,h_kj¹,h_kj²

unit vehicle costs of type-1 and type-2 vehicles for each direct service (i,k)E_IN and (k,j)E_OUT, respectively (h_ik¹<h_ik² and h_kj¹<h_kj²)

₁,₂

capacities of type-1 and type-2 vehicles, respectively (₁<₂andh_e¹/₁>h_e²/₂)

t_ik,t_kj

transportation time required for each direct service (i,k)E_IN and (k,j)E_OUT, respectively

p_k

handling (sorting and consolidating) time at the intermediate node k

d_ij

quantity of freight demand (i,j)Q

TL_ij

delivery time limit for freight demand (i,j)Q

Decision variables

Y_ik,Z_ik,Y_kj,Z_kj

numbers of type-1 and type-2 vehicles allocated for each direct service (i,k)E_IN and (k,j)E_OUT, respectively

X_ij^k

1 if the freight demand (i,j)Q is transported through the intermediate node kK;
0 otherwise

W_k

1 if the CD centre k is established located);
0 otherwise

For notational convenience, notation (or subscript) e and (i,k) (or (k,j)) will be used alternately to denote the associated edge, and q and (i,j) will be used alternately to denote the associated freight demand. The two terms 'edge' and 'direct service' will also be used alternatively.

Formulation (PBF):

The objective function (1) represents the two major cost functions including the cost of locating CD centres and the cost of allocating any vehicles for the associated direct services. Constraints (2) represent the situation where all the freight demands have to be serviced. Constraints (3) and (4) require that the total amount of demands transported through any direct service should not exceed the total capacity of any allocated vehicles. Constraints (5) represent the condition that freight demand (i,j) may be consolidated at the intermediate node k if and only if the associated CD centre is located at the node. Note that constraints (5) can be replaced with the following constraints (5') which are the disaggregated version of the constraints (5).

The aggregated constraints (5) are weaker than the disaggregated constraints (5') so that in order to find a better lower bound, it is necessary to replace constraints (5) with constraints (5') even though it may require more time to solve the associated LP relaxations because of the larger number of constraints (Sung and Song, 2003). The service time restrictions can be satisfied with only the X-variables X_ij^k in the formulation (PBF) such that for each freight demand (i,j), the sum of transportation times between nodes and handling time at an intermediate node k does not exceed the predefined time limit TL_ij (t_ik+p_k+t_kjTL_ij) (Sung and Song, 2003). Thus, the set Q_k can be identified at a pre-processing stage. Under the assumption that each freight demand is transported through a single path, the X-variables X_ij^k have binary values.

Set-partitioning-based formulation

In this section, a set-partitioning-based formulation (SPBF) is derived for the problem (CDSCNDP). Such SPBFs have been considered for various problems including vehicle routing problem with time windows (Desrochers et al, 1992), generalized assignment problem (Cattrysse et al, 1994; Savelsbergh, 1997) and p-median problem (Garfinkel et al, 1974).

For the formulation, the following notation will be used in addition.

Sets

Q_ik

set of freight demands that can be transported from node i to node k, Q_ik={(i',j)Q_k|i'=i}

Q_kj

set of freight demands that can be transported from node k to node j, Q_kj={(i,j')Q_k|j'=j}

_IN^ik

set of freight demands to be transported and the associated vehicle allocation on the edge from origin node i to intermediate node k (ie set of integral points consisting of X, Y and Z variables feasible to the associated vehicle capacity constraint (3) on the edge),

_OUT^kj

set of freight demands to be transported and the associated vehicle allocation on the edge from intermediate node k to destination node j (ie set of integral points consisting of X, Y and Z variables feasible to the associated vehicle capacity constraint (4) on the edge),

Q_ik(r),Q_kj(s)

set of freight demand corresponding to r_IN^ik and s_OUT^kj, respectively

Parameters

c_r^ik

vehicle allocation cost induced by r=(X,Y_ik,Z_ik)_IN^ik, c_r^ik=h_ik¹Y_ik+h_ik²Z_ik

c_s^kj

vehicle allocation cost induced by s=(X,Y_kj,Z_kj)_OUT^kj, c_s^kj=h_kj¹Y_kj+h_kj²Z_kj

Decision variables

_r^ik

1 if the associated freight demands with r_IN^ik is transported by the associated vehicles;
0 otherwise

_s^kj

1 if the associated freight demands with s_OUT^kj is transported by the associated vehicles;
0 otherwise

W_k

1 if the CD centre k is established;
0 otherwise

Note that Q_k=_iI Q_ik=_jJ Q_kj.

Formulation (SPBF):

The objective function (7) is equivalent to the objective function (1) in the (PBF). Constraints (8) and constraints (11) are equivalent to constraints (2) and constraints (5) in (PBF), respectively. Constraints (9) mean that at most one set of freight demands associated with variable _r^ik is delivered for direct service (i,k), and constraints (10) mean that at most one set of freight demands associated with variable _s^kj is delivered for direct service (k,j). In a similar approach to constraints (5) in the (PBF), constraints (11) can be replaced with constraints (11') which are the disaggregated version of constraints (11).

Note that the variables _r^ik and _s^kj are defined to satisfy the constraints (3) and (4), respectively.

A set of valid inequalities to the formulation (PBF) has been derived and used in Sung and Song (2003) to propose a cutting plane scheme based on the set of valid inequalities so as to obtain a stronger lower bound than that obtained from the LP relaxation of the formulation (PBF). The set of valid inequalities represents a set of Chvátal–Gomory valid inequalities for the convex hull of _IN^ik (or _OUT^kj). However, only for a subset of the inequalities with some coefficient fixed, separation algorithm was derived to find out any violated constraints from a current solution in the work. Therefore, the associated convex hull of _IN^ik (or _OUT^kj) may not be described well.

Now, denote by LB1, LB2 and LB3, the lower bounds obtained from the LP relaxation of the formulation (PBF), the cutting plane scheme proposed by Sung and Song (2003) and the LP relaxation of the formulation (SPBF) presented in this paper, respectively.

Property 1

The following relation holds:

Proof

The relation LB1LB2 is obvious. The proof for the relation LB2LB3 can be made by showing that the formulation (SPBF) can be derived via Dantzig–Wolfe decomposition of the following formulation (VPBF). The formulation (VPBF) can, however, be derived from the formulation (PBF) by introducing a set of variables equivalent to the set of variables X_ij^k and adding a set of constraints .

Formulation (VPBF):

The lower bound obtained from the LP relaxation of the formulation (VPBF) is denoted by LB1'. Obviously, LB1' is equal to LB1. Now, Dantzig–Wolfe decomposition of the formulation (VPBF) is made as follows. Assume that the set _IN^ik={(X,Y_ik,Z_ik)B^|Q_ik| Z₊ Z₊|_(i,j)Qik d_ijX_ij^k₁Y_ik+₂Z_ik} contains points (r^ik)'s. For notational convenience, r will be used instead of r^ik. Then, it follows that

where x_r^ik, y_r^ik and z_r^ik are the incidence vector of Q_ik(r)Q (x_r^ik being composed of x_jr^ik's having 0–1 incidence values in the associated position), the number of type-1 vehicles to deliver Q_ik(r), and the number of type-2 vehicles to deliver Q_ik(r), respectively. Similarly, assume that the set

contains points (s^kj)'s. For notational convenience, s will be used instead of s^kj. Then, it follows that

where x_s^kj, y_s^kj and z_s^kj are the incidence vector of Q_kj(s)Q (x_s^kj being composed of (x_is^kj)'s having 0–1 incidence values in the associated position), the number of type-1 vehicles to deliver Q_kj(s), and the number of type-2 vehicles to deliver Q_kj(s), respectively. Recall the relations c_r^ik=h_ik¹y_r^ik+h_ik²z_r^ik and c_s^kj=h_kj¹y_s^kj+h_kj²z_s^kj. Now, let us replace the variables X_ij^k, Y_ik, Z_ik, , Y_kj, Z_kj with the variables x_jr^ik, y_r^ik, z_r^ik, _r^ik, x_is^kj, y_s^kj,z_s^kj and _s^kj. Then, the terms _rIN^ik x_jr^ik_r^ik and _sOUT^kj x_is^kj_s^kj can be represented by _{{rIN^ik|(i,j)Qik(r)}r}^ik and _{{sOUT^kj|(i,j)Qkj(s)} s}^kj, respectively. However, if the sets Q_ik(r) and Q_kj(s) are empty, then the associated variables _r^ik and _s^kj, respectively, are not necessary to generate for solving the problem (CDSCNDP), so that the relations _rIN^ikr^ik=1 and _{sOUT^kj s}^kj=1 can be rewritten as the relations _{rIN^ik r}^ik1 and _sOUT^kj1, respectively. Therewith, the formulation (VPBF) can be transformed to the proposed formulation (SPBF) by Dantzig–Wolfe decomposition. Because the separation algorithm proposed by Sung and Song (2003) is not an exact separation algorithm for the convex hull of _IN^ik (or _OUT^kj), the associated lower bound, LB2, is equal to or lower than that obtained from the LP relaxation of the above Dantzig–Wolfe decomposition being equivalent to the proposed formulation (SPBF), LB3.

Property 1 implies that a stronger lower bound for the problem (CDSCNDP) can be obtained from the LP relaxation of the proposed formulation (SPBF), which is very desirable to derive an exact algorithm for the problem. Note that a similar property to Property 1 can be derived in the situation where the aggregated constraints (5) and (11) are replaced with the disaggregated constraints (5') and (11'), respectively.

Solution approach

The proposed formulation (SPBF) may have a huge number of variables because the variables _r^ik and _s^kj are associated with various subsets of freight demand sets Q_ik and Q_kj, respectively. In spite of that, a small subset of all the variables is required to find an optimal solution. To exploit this aspect, the column generation technique is used to generate such required variables in this paper. Specifically, a branch-and-price algorithm for the problem (CDSCNDP) is derived based on the formulation (SPBF) with the column generation technique applied throughout the associated branch-and-bound tree.

Consider the LP relaxation of the proposed formulation (SPBF), which will be called the 'master problem', denoted by (SPBF_MP). Denote by (SPBF_RMP) a 'restricted master problem' containing only a subset of all the variables of the master problem (SPBF_MP).

Initial restricted master problem

The initial restricted master problem used in the proposed algorithm includes all the W variables, (W_k)'s, and a subset of all the -variables. The -variables, (_r^ik)'s and (_s^kj)'s, to be included in the initial restricted master problem are generated as follows. First, for each freight demand, the cheapest path to make its delivery is found. Second, once all such cheapest paths are found in association with all the given freight demands, the set of freight demands to be delivered for each direct service can be identified from among all the cheapest paths associated with the direct service. Third, for each direct service associated with only a non-empty set of freight demands, the corresponding variables _r^ik and _s^kj are generated and added to the initial restricted master problem. Then, the vehicle cost c_r^ik (or c_s^kj) associated with _r^ik (or _s^kj) can be computed by finding how many vehicles are needed to deliver the associated freight demands at minimum vehicle cost.

To calculate the number of vehicles at minimum vehicle cost, the next section characterizes several solution properties and proposes an associated efficient calculation procedure.

Calculating the number of vehicles for direct service

Suppose that a set of freight demands to be delivered for direct service e is determined, denoted by Q(e). Then, the problem to calculate the number of vehicles at minimum vehicle cost for the delivery can be defined as follows:

Problem CNV(e):

Let D(e)=_(i,j)Q(e) d_ij, Y_e^max=D(e)/₁ and Z_e^max=D(e)/₂. Then, the problem CNV(e) needs to be solved to construct the initial restricted master problem, and to reduce the size of the pricing problems of generating -variables, (_r^ik)'s and (_s^kj)'s, that will be fully explained in the next section.

Moreover, the problem CNV(e) shall be solved in local search heuristics using the operation MOVE_MD for the problem (CDSCNDP). As mentioned earlier, the contribution of the operation MOVE_MD to the objective total cost can be measured by finding how many vehicles are needed for the direct services in association with the modified delivery quantity due to the operation, which corresponds to solving the problem CNV(e)'s associated with the modified direct services. This implies that the efficiency of such a local search heuristic is dependent on how efficiently the problem CNV(e) can be solved.

In order to solve the problem CNV(e), several solution properties were characterized in Sung and Song (2003). In this connection, more efficient solution properties are characterized in this section.

Property 2

(Referring to Sung and Song, 2003) Given Z_e=m(0mZ_e^max), (D(e)-m₂)/₁ and (Z_e^maxY_e^max-mY_e^max)/Z_e^max are derived as lower and upper bounds of Y-variable Y_e, respectively.

By use of Property 2, the number of vehicles to transport D(e) for direct service e at minimum vehicle cost could be determined by comparing the combinations of (Y_e,Z_e)'s, which results in the number _m=0^Z_emax{(Z_e^maxY_e^max-mY_e^max)/Z_e^max-(D(e)-m₂)/₁+1}. The above combinations have been compared in Sung and Song (2003) to solve the problem CNV(e).

Property 3

Given Z_e=m(0mZ_e^max), the optimal number of type-1 vehicles, Y_e, is (D(e)-m₂)/₁.

Proof

It is obvious, because a solution (D(e)-m₂)/₁ is the minimum number of type-1 vehicles to satisfy (22).

Property 3 obviously dominates over Property 2, so that it is enough to compare Z_e^max+1 combinations of (Y_e,Z_e)'s in total.

To obtain an optimal (Y_e,Z_e) for the problem CNV(e) more efficiently, some more properties are to be characterized. Let , R_e=₁Y_e+₂Z_e-D(e) and C_e=h_e¹Y_e+h_e²Z_e. Note that if is given, the associated Y_e, Z_e, R_e and C_e can be obtained easily. The associated Y_e, Z_e, R_e and C_e with are denoted by , , and throughout this paper, respectively. Also, given D(e), the associated Y_e, Z_e, R_e, C_e and with an optimal solution for the problem CNV(e) are denoted by Y_e^*|_D(e), Z_e^*|_D(e), R_e^*|_D(e), C_e^*|_D(e) and , respectively.

Property 4

Given and , it holds that if r₁r₂, then ₁<₂, where (r₁,₁) and (r₂,₂) are the values of (R_e,C_e) associated with and , respectively.

Proof

Denote by (y₁,z₁) and (y₂,z₂) the values of (Y_e,Z_e) associated with and , respectively. Then,

Corollary 5

If R_e associated with is 0, then it is unnecessary to consider the associated solutions for the problem CNV(e) with .

Proof

It is obvious by Property 4.

Property 4 and Corollary 5 can be used as dominance relations for solving the problem CNV(e) efficiently.

Property 6

If (₂ mod ₁) is 0 (ie ₂ being a multiple of ₁), then is either 0 or 1.

Proof

Let D(e)=₂k+A where kZ₊ and A=(D(e) mod ₂). For n(1nZ_e^max), , since ₂ mod ₁=0. By Property 4, dominates over . Thereupon, is either 0 or 1.

Property 6 implies that the problem CNV(e) can be solved in O(1)-bounded operations when (₂ mod ₁) is 0 as a special case. A similar result was characterized in Sung and Song (2003). For general cases, the following properties are characterized.

Property 7

With the values D(e)=₂k+A>₁₂ where k{₁,₁+1,...} and A=(D(e) mod ₂), is periodic in starting at 1 with the period ₁.

Proof

This can be made by showing , where 0<n<n+₁Z_e^max. since . Also, since and ₂₁ mod ₁=0. Thus, .

According to Property 3, the problem CNV(e) can be solved by comparing Z_e^max+1 solutions. Note that Z_e^max gets larger as D(e) increases and it can be much larger than ₁ for some D(e). Property 7 implies that the problem CNV(e) can be solved by comparing at most ₁+1 solutions for any arbitrary case. Thereupon, the problem CNV(e) can be solved by comparing Z_e^max+1 solutions when D(e) is small such that Z_e^max<₁ (by Property 3), and comparing ₁+1 solutions when D(e) is large such that Z_e^max₁ (by Property 7).

The periodic characteristics presented in Property 7 seem to provide a motivation to characterize more solution properties to solve the problem CNV(e) effectively. Accordingly, the following solution properties are characterized such that as D(e) increases, the associated optimal solutions to the problem CNV(e) also have periodic characteristics. To implement the solution properties, a preprocessing procedure is derived to keep some information corresponding to one period at a cost of a small computation load and memory consumption. After the preprocessing procedure, the problem CNV(e) can be solved with any given D(e) in O(1)-bounded operations.

Property 8

With the values D(e)=k₂ (kZ₊), the following relations hold:

Proof

It is easy to see that . Thus, the conclusion can be made by Corollary 5.

Property 9

With the values D(e)₁>0 and D(e)₂=D(e)₁+k₂>0 (kZ), the following relations hold:

Proof

It is obvious by the definition of .

Corollary 10

With the values D(e)₁(₁-1)₂+l (l{1,...,₂-1}) and D(e)₂=D(e)₁+k₂ (kZ₊), the following relations hold:

Proof

This can be proved by showing . By Property 7, (Y_e^*|_D(e)2,Z_e^*|_D(e)2) can be obtained by comparing ₁+1 solutions associated with . For , it is easy to see that is greater than exactly by the amount kh_e² as shown in Property 9. Thus, .

Let for the given values D(e) ((₁-1)₂+1D(e)₁₂-1) and m (0m₁).

Corollary 11

With the values D(e)₁(₁-1)₂+l (l{1,...,₂-1}) and D(e)₂=D(e)₁-k₂>0 (kZ₊), the following relations hold:

where with m=Z_e^max|_D(e)2=₁-k.

Proof

This can be proved by showing . By Property 3, (Y_e^*|_D(e)2,Z_e^*|_D(e)2) can be obtained by comparing Z_e^max|_D(e)2+1 solutions associated with . For , it is easy to see that is less than exactly by the amount kh_e² as shown in Property 9, Thus, .

In order to implement the results of Corollary 10 and Corollary 11, all the data , , , , for (₁-1)₂+1D(e)₁₂-1, 0n₁) are required. Once all the required data are found, the problem CNV(e) can be solved with any freight demand quantity for the associated direct service e in O(1)-bounded operations by use of Property 8, Corollaries 10 and 11. The procedure for solving the problem CNV(e), denoted by PROC_CNV, is then derived as follows.

Procedure PROC_CNV:

The demand quantity to be delivered for direct service e is given as D(e)=_(i,j)Q(e) d_ij. Let k=D(e)/₂-(₁-1) and l=D(e) mod ₂. Then, the optimal solution (Y_e^*|_D(e),Z_e^*|_D(e)) and the optimal cost C_e^*|_D(e) can be determined as in the following situations.

The step of calculating all required data needs to be implemented as a preprocessing step in O((₂-1)(₁+1))-bounded operations and memory by the definitions of the required data, which may be time-consuming though. However, the PROC_CNV may be beneficial in the aspect of efficiency for both the proposed branch-and-proce algorithm and the local search heuristics using the operation MOVE_MD because they may require a lot of the problem CNV(e)'s to be solved iteratively.

In the case of the proposed branch-and-proce algorithm, to reduce the size of the pricing problems of generating -variables, (_r^ik)'s and (_s^kj)'s, that will be presented in the next section in detail, it is necessary to know the upper bound on the number of each vehicle type when demand quantity to be delivered is an arbitrary value within some bounds, but not a given value as in the problem CNV(e). The upper bounds can be found by consecutively repeating the procedure that D(e) is fixed each time at a value within the bounds and then the associated problem CNV(e) is solved whenever it is necessary to solve the pricing problem. However, the method requires multiple number of the repetitive problems CNV(e)'s to be solved for the single pricing problem. Futhermore, it is necessary to solve a number of such pricing problems. Therefore, a lot of such repetitive problems CNV(e)'s need to be solved in the proposed branch-and-price algorithm.

Similarly, in the case of local search heuristics using the operation MOVE_MD, a lot of repetitive problems CNV(e)'s need to be solved. This is because the operation MOVE_MD is often required to be performed many times for solving the problem (CDSCNDP) in such a local search heuristic. By the way, it is necessary to evaluate the contribution of each move operation MOVE_MD to the objective total cost, for which it needs to solve the problems CNV(e)'s associated with the modified direct services by the operation.

Pricing problem

This section considers two types of pricing problems to generate -variables: one for _r^ik_IN^ik, denoted by (PP_ik) and the other for _s^kj_OUT^kj, denoted by (PP_kj). Let _ij^PAR (unrestricted), _ik^IN(0), _kj^OUT(0), _ijk^LOC(0) and _ijk^F (unrestricted) be the optimal values of the dual variables for constraints (8), (9), (10), (11') and (12) in the current formulation (SPBF_RMP), respectively. The reduced cost of variable _r^ik_IN^ik and the reduced cost of variable _s^kj_OUT^kj are given as follows:

Recall that x_jr^ik and x_is^kj are 0–1 incidence parameters indicating whether demand (i,j) is included in the sets Q_ik(r) and Q_kj(s) or not, respectively, when the proposed formulation (SPBF) is derived by Dantzig–Wolfe decomposition (as presented in the proof of Property 1). However, in the pricing problems, x_jr^ik and x_is^kj are 0–1 decision variables indicating whether demand (i,j) is included in the sets Q_ik(r) and Q_kj(s) (x_jr^ik or x_is^kj=1) or not (x_jr^ik or x_is^kj=0), respectively. Then, the pricing problem (PP_ik) can be derived as follows:

Problem (PP_ik):

Similarly, the pricing problem (PP_kj) can be formulated by replacing the objective cost function , and variables Y_ik,Z_ik and x_jr^ik in the problem (PP_ik) with , and Y_kj, Z_kj and x_is^kj, respectively. If a variable _r^ik_IN^ik (or _s^kj_OUT^kj) with negative reduced cost is obtained from (PP_ik) (or (PP_kj)), the variable is added to the current formulation (SPBF_RMP).

Some of x_jr^ik-variables in the problem (PP_ik) and some of x_is^kj-variables in the problem (PP_kj) can be fixed as in the following property so as to reduce the size of the pricing problems.

Property 12

1. If (_ij^PAR+_ijk^LOC+_ijk^F)0 for some j in the problem (PP_ik), then there is an optimal solution with x_jr^ik=0;
2. If (_ij^PAR+_ijk^LOC+_ijk^F)C_ij^*|_D(e)=dij for some j in the problem (PP_ik), then there is an optimal solution with x_jr^ik=1;
3. If (-_ijk^F)0 for some i in the problem (PP_kj), then there is an optimal solution with x_is^kj=0;
4. If (-_ijk^F)C_ij^*|_D(e)=dij for some i in the problem (PP_kj), then there is an optimal solution with x_is^kj=1.

Proof

For the proof of (a), let us compare the situations of x_jr^ik=1 and x_jr^ik=0 for some j such that (_ij^PAR+_ijk^LOC+_ijk^F)0 in the problem (PP_ik). The value of the objective function (23) for the former case cannot be smaller than that for the latter case, because the coefficient of the variable in (23) is non-negative. Also, the former case makes the constraint (24) tighter than the latter case. Therefore, the former case cannot give a better solution than the latter case. The proofs for (b), (c) and (d) can be made similarly by comparing the situations of x_jr^ik (or x_is^kj)=1 and x_jr^ik (or x_is^kj)=0 in the same manner as in the proof of (a).

Let be a subset of the set Q_e (the associated Q_ik or Q_kj) such that (_ij^PAR+_ijk^LOC+_ijk^F)0 in the problem (PP_ik) (ie satisfying the statement (a) in Property 12) or (-_ijk^F)0 in the problem (PP_kj) (ie satisfying the statement (c) in Property 12) for . Also, let be a subset of the set Q_e (the associated Q_ik or Q_kj) such that (_ij^PAR+_ijk^LOC+_ijk^F)C_ij^*|_D(e)=dij in the problem (PP_ik) (ie satisfying the statement (b) in Property 12) or (-_ijk^F)C_ij^*