New complexity results for the p-hub median problem

Abstract

Using transportation mode and flow dependent cost structures on the classical p-hub median problems affects the shape of its linear cost function. While there is a vast literature about the classical problem, the studies with cost structures different than linear functions are rare. In this study, several cost structures such as all unit discount model, modified all unit discount model, car load discount model and container cost structures, which are especially useful in freight transportation, are considered. It is shown that some easy classical problems become NP-hard when the linearity of the cost functions is lost.

1 Introduction

In the real life flow of people, commodities, information, energy, etc. between many origin–destination (O–D) pairs may be observed. A many-to-many distribution system deals with transportations between many origins and many destinations. In such a distribution system, transportation through indirect paths based on consolidation of flows on common links can often be preferred to direct transports because of economies of scale. The beginning node of such a common link on a network acts as a consolidation center of flows and the ending node of the link acts as a dissemination center of flows. Center nodes are called “hub” and non-hub nodes are called “spoke”.

Let G = (N, E) be a connected graph where N = {1, 2,…, n} is the set of nodes, E is the set of edges, and P be the set of p hubs. The p-hub median problem (p-HMP) is to find $P \subseteq N$ and paths of the flows between the O–D pairs such that the total transportation cost is minimized subject to the constraints: (i) 1 or 2 of hubs operates between any O–D pair, (ii) the flows between hubs are direct and (iii) flow between any O–D pair uses a single path.

If all flows from and to a spoke are restricted to be sent and received through a single hub the problem is then called the single-allocation p-hub median problem (p-SHMP). If there is no such a restriction the problem is then called the multiple-allocation p-hub median problem (p-MHMP).

If the locations of the hubs are given, the remaining part of the problem is called as the allocation problem. According to the allocation type, the problems are called as the multiple-allocation p-hub allocation problem (p-MHAP) and the single-allocation p-hub allocation problem (p-SHAP).

Figure 1 shows a solution of a 3-SHMP with 9 nodes. In this solution, nodes 3, 7 and 8 are selected as the hubs. The others are spokes. Nodes 1, 2 and 6 are assigned to hub 3, node 4 is assigned to hub 7, and nodes 5 and 9 are assigned to hub 8. As an example, the flow from node 1 to node 9 follows the path 1 → 3→8 → 9.

Fig. 1

A solution of a 3-SHMP with 9 nodes

The total transportation cost consists of the cost occurred between spokes and hubs, and between hubs. Let Q_ij be the amount of the total flow from node i to node j and C_ij(Q_ij) be the total transportation cost of this flow. Most studies in the literature assume C_ij(Q_ij) as a linear function of Q_ij, i.e., C_ij(Q_ij) = c_ij*Q_ij where c_ij is unit transportation cost from node i to node j. Discount factor α (0 ≤ α ≤ 1) is used on the inter-hub links in order to incorporate economies of scale into the models. If node k and node m are hubs then C_km(Q_km) = α*c_km*Q_km. Let w_ij be the amount of flow from node i to node j.

The mathematical model of the (classical) p-MHMP is given below (Campbell 1992).

$$ \hbox{min} \;TC = \sum\limits_{i \in N} {\sum\limits_{k \in N} {\sum\limits_{m \in N} {\sum\limits_{{j \in N - \{ i\} }} {w_{ij} (c_{ik} + \alpha \cdot c_{km} + c_{mj} )x_{ikmj} } } } } $$

(1)

$$ \begin{aligned} & s.t. \\ & \sum\limits_{k \in N} {\sum\limits_{m \in N} {x_{ikmj} = 1} \quad \forall i,j \in N|i \ne j} \\ \end{aligned} $$

(2)

$$ x_{ikmj} \le y_{kk} \quad \forall i,j,k,m \in N|i \ne j $$

(3)

$$ x_{ikmj} \le y_{mm} \quad \forall i,j,k,m \in N|i \ne j $$

(4)

$$ \sum\limits_{k \in N} {y_{kk} = p} $$

(5)

$$ x_{ikmj} \ge 0\quad \forall i,j,k,m \in N|i \ne j $$

(6)

$$ y_{kk} \in \{ 0,1\} \quad \forall k \in N $$

(7)

In this model, decision variable x_ikmj is the fraction of the flow from node i to node j that follows the path i → k → m → j. y_kk is 1 if node k is selected as a hub and 0 otherwise. Objective function (1) is the minimization of the total transportation cost which is a linear function of the transportation amounts. Constraint (2) ensures that all the flows between all O–D pairs are transported. Constraints (3) and (4) guarantee that flow between any O–D pair can be sent or received via only the nodes selected as hub. Constraint (6) ensures that p nodes are selected as hub.

The mathematical model of the (classical) p-SHMP is given below (Skorin-Kapov et al. 1996).

$$ \begin{aligned} & {\text{Min}}\left( 1 \right) \\ & s.t. \\ & \left( 5 \right) - \left( 7 \right) \\ & \sum\limits_{m \in N} {x_{ikmj} = y_{ik} } \quad \forall i,j,k \in N|i \ne j \\ \end{aligned} $$

(8)

$$ \sum\limits_{k \in N} {x_{ikmj} = y_{jm} } \quad \forall i,j,m \in N|i \ne j $$

(9)

$$ \sum\limits_{k \in N} {y_{ik} = 1} \quad \forall i \in N $$

(10)

$$ y_{ik} \le y_{kk} \quad \forall i,k \in N $$

(11)

In this model, the new decision variable y_ik is a binary variable which is 1 if node i is allocated to hub k and 0 otherwise. The other decision variables are the same with the ones in the previous model. Constraints (8) and (9) ensure that each node sends and receives all of its flows using the hub that it is allocated to. Constraint (10) guarantees that each node is allocated to a single hub. Constraint (11) allows any node to be allocated to a node if it is selected as a hub.

Note that even if x_ikmj variables are not defined as binary variables in these models, in the optimal solutions they are 0 or 1 valued. This property is not guaranteed by these models if some non-linear cost structures are used. i.e., Constraint (iii) in the problem definition can be violated if these models are used with some non-linear cost structures. Some part of the flow from an origin to a destination may follow a path and some other parts of it may follow some other paths. Moreover, when the origin or the destination of a flow is a hub constraint (ii) in the problem definition can be violated by the first model if some non-linear cost functions are used. In a solution of that model, a hub node may send or receive its own flow via some other hubs as if itself is a spoke. Let’s assume k, m, t and j as four nodes in N, and k, m and t are selected as hub in a solution. Let’s consider the flow w_kj. Normally, according to constraint (ii) in the problem definition, w_kj may follow a path like k → m → j (in this case x_kkmj must be 1). But if a non-linear cost structure is used it may follow a path like k → t → m → j (in this case x_ktmj will be 1) in the optimal solution of the first model. In this path node k and node m are hubs but the transportation between them is not direct. The reason behind such a strange solution may be the effort of increasing the total flow sent from hub t to hub m in order to obtain a higher cost discount there. In the second model constraint (11) cuts such solutions. These risks related with the use of the above models are not valid for the problems with linear cost functions of the flow amounts [objective function (1) in the models]. Mathematical models of the (general cost) p-MHMP and (general cost) p-SHMP are developed considering these mentioned matters and they are presented below.

The mathematical model of the (general cost) p-MHMP is given below.

$$ \begin{aligned} \hbox{min} \;TC &= \sum\limits_{i \in N} {\sum\limits_{k \in N} {C_{ik} \left( {\sum\limits_{m \in N} {\sum\limits_{{j \in N - \{ i\} }} {w_{ij} x_{ikmj} } } } \right)} } + \sum\limits_{k \in N} {\sum\limits_{m \in N} {C_{km} \left( {\sum\limits_{i \in N} {\sum\limits_{{j \in N - \{ i\} }} {w_{ij} x_{ikmj} } } } \right)} } \\ & \quad + \sum\limits_{m \in N} {\sum\limits_{j \in N} {C_{mj} \left( {\sum\limits_{{i \in N - \{ j\} }} {\sum\limits_{k \in N} {w_{ij} x_{ikmj} } } } \right)} } \\ \end{aligned} $$

(12)

$$ \begin{aligned} & s.t. \\ & \left( 2 \right), \, \left( 5 \right), \, \left( 7 \right), \, \left( {11} \right) \\ & x_{ikmj} \le y_{ik} \quad \forall i,k,m,j \in N|i \ne j \\ \end{aligned} $$

(13)

$$ x_{ikmj} \le y_{jm} \quad \forall i,k,m,j \in N|i \ne j $$

(14)

$$ y_{km} \le 1 - y_{kk} \quad \forall k,m \in N|k \ne m $$

(15)

$$ x_{ikmj} \in \{ 0,1\} \quad \forall i,k,m,j \in N|i \ne j $$

(16)

In this model, objective function (12) is the minimization of the total transportation cost which is a general function of the transportation amounts. Constraints (13) and (14) ensure that each node sends and receives its flows using the hubs that it is allocated to. Constraint (15) guarantees that if a node is selected as a hub then it sends and receives all of its flows via itself. Constraint (16) prevents fractional transportations of flows via different paths between the O–D pairs.

In the above model of (Skorin-Kapov et al. 1996), replacing objective function (1) with (12) and constraint (6) with (16) is enough to obtain the mathematical model of the (general cost) p-SHMP.

The first study that we have found about “hub” concept belongs to Minas and Mitten (1958). They assume one “central” and a number of “outlying” terminals and define the central terminal as the “hub” of the system. There are commodity flows between the terminals but the flows are forced to be transported by trucks via the hub, i.e., direct transportations between the “outlying” terminals (spokes) are forbidden. They consider the truck scheduling problem. Then, perhaps the first article on the hub location problem is Goldman (1969). O’Kelly (1987) presents the first mathematical model of the problem. Then the problem becomes one of the most studied location problems. Several versions and extensions of the problem are considered in the literature. There are some studies like Aykin (1995) and O’Kelly (1992) considering the continuous version of the problem in which hubs can be located at all points on a plane, they are not restricted by the nodes of a graph. Several studies such as Yaman and Carello (2005), and Costa et al. (2008) consider capacitated hub location problems. Some recent studies like Alamur et al. (2016) consider dynamic version of the problem. In some studies like Çetiner et al. (2010) transportation in routs between hubs and spokes is considered instead of direct transportation. The p-hub center problem, the hub set covering problem and the p-hub maximal covering problem can be given as some other versions of the hub location problem. More information on the literature can be found in the review studies of Campbell et al. (2002), Alamur and Kara (2008), Campbell and O’Kelly (2012), and Farahani et al. (2013).

To the best of our knowledge there are three studies on the complexity of the (classical) p-hub median problem with flow independent costs. Sohn and Park (1997) show that the p-SHMP is polynomially solvable if p = 2. They show that the 2-SHAP reduces to the polynomially solvable min-cut problem. Then the 2-SHMP is solved by solving the corresponding min-cut problems for each of the C(n 2) alternative locations of hubs.

Sohn and Park (1998) show that the p-MHMP is polynomially solvable for a fixed p. For a given P the allocation part of the p-MHMP is to find the least costly path via the given hubs for each O–D pair, i.e., $\mathop {\hbox{min} }\limits_{k,m \in P} \{ c_{ik} + \alpha c_{km} + c_{mj} \}$ for all $i,j \in N$. For an O–D pair this path can be found using shortest path algorithms. Thus the allocation part of the p-MHMP can be solved in O(pn²) by running Floyd’s shortest path algorithm iteratively for each O–D pair. Ultimately, the p-MHMP can be solved polynomially for fixed p by repeating this method for each of the C(n p) alternative locations of hubs.

Kara (1999) shows that the p-SHMP is NP-hard when p ≥ 3. For a given hub locations, the allocation part of the problem is equivalent to the NP-hard multi-processor assignment problem. Since the multi-processor assignment problem has polynomially solvable special cases the allocation part of the problem is then polynomially solvable, for instance, if the flows form a k-tree over the set of nodes.

There are several studies like O’Kelly and Bryan (1998), Bryan (1998), Klincewicz (2002), Horner and O’Kelly (2001), Kimms (2005), Racunicam and Wynter (2005), and Cunha and Silva (2007) that consider transportation mode options and flow dependent cost structures, but there is no known result about complexity of these problems. In this study we consider linear costs between spokes and hubs, and non-linear costs between hubs. We consider four different non-linear cost functions between the hubs which are especially useful in freight transportation and show that all of the corresponding p-MHAP, p-MHMP, p-SHAP, and p-SHMP are NP-hard even p = 2.

In Sect. 2, the all unit discount cost structure is considered. The structure is explained and NP-hardness proofs of the problems are given. Similar to the organization of Sect. 2, the modified all unit discount cost structure, car load discount cost structure and container cost structure are considered in Sects. 3, 4 and 5, respectively. The study is concluded and future study issues are explained in Sect. 6.

2 All unit discount cost structure

There may be different transportation mode alternatives such as air, rail and land transportation between the hubs. Suppose that each mode has a different unit transportation cost that is pertinent within specified load bounds. If there are two or more discount options, the lower bound of a lower unit transportation cost determines the upper bound of a higher unit transportation cost.

Let α_km(Q) be the discount factor applied to the freight of Q units transported from hub k to hub m. In all unit discount cost structure, the same discount factor is applied to every units of Q within corresponding load bounds and it is determined as follows.

$$ \alpha_{km} (Q) = \left\{ {\begin{array}{*{20}l} {\alpha_{1} } \hfill & {0 < Q < LB_{2} } \hfill \\ {\alpha_{2} } \hfill & {LB_{2} \le Q < LB_{3} } \hfill \\ : \hfill & : \hfill \\ {\alpha_{L} } \hfill & {LB_{L} \le Q} \hfill \\ \end{array} } \right. $$

where $1 \ge \, \alpha_{1} > \, \alpha_{2} > \cdots > \, \alpha_{L} > 0$, LB_l is the lower bound for load level l and L denotes the number of discount factor options or load levels specified. Let d_ij be the distance between nodes i and j. Then the total transportation cost of Q units from hub k to hub m is: $C_{km} \left( Q \right)_{{}} = \, \alpha_{km} \left( Q \right)*Q*d_{km}$. Figure 2 shows the shape of C_km(Q) for the all-unit-discount model.

Fig. 2

All unit discount model

Theorem 1

The 2-MHAP with all unit discount cost in two levels is NP-hard.

Proof

We show that the binary knapsack problem is polynomially reducible to the 2-MHAP with all unit discount cost even if L = 2.

Consider an instance of the binary knapsack problem as given below.

$$ \begin{aligned} & \hbox{min} \sum\limits_{i \in R} {f_{i} } x_{i} \\ & s.t. \\ & \sum\limits_{i \in R} {g_{i} x_{i} } \ge U \\ & x_{i} \in \{ 0,1\} \quad \forall i \in R = \{ 1, \, 2, \, \ldots , \, n\} \\ \end{aligned} $$

where $f_{i}$ and $g_{i}$ are positive integers for all $i \in R$, and $\sum\limits_{i \in R} {g_{i} } > U$.

Let $a = \mathop {\hbox{max} }\limits_{i \in R} \left\{ {\frac{{f_{i} }}{{g_{i} }}} \right\}$, $b = \mathop {\hbox{min} }\limits_{i \in R} \left\{ {\frac{{f_{i} }}{{g_{i} }}} \right\}$ and $r = \frac{1}{2}(a + b)$.

Consider the following instance of the 2-MHAP with all unit discount cost and L = 2. Let N (N = R) be the set of spokes and k and m ($k,m \notin N$) be the fixed hubs. Let

$$ \begin{aligned} & d_{km} = \frac{1}{2}a + r \\ & d_{ik} = r\quad \forall i \in N \\ & d_{im} = r + \frac{{f_{i} }}{{g_{i} }} - \frac{1}{2}b\quad \forall i \in N \\ & d_{ij} = d_{ji} \quad \forall i,j \in N \cup \{ k,m\} \\ & w_{mk} = \frac{{\sum\limits_{i \in R} {f_{i} } }}{{(\alpha_{1} - \alpha_{2} )d_{km} }} + 1 \\ & w_{km} = 0 \\ & w_{ik} = \, g_{i} \quad \forall i \in N \\ & w_{im} = \, w_{mk} + g_{i} \quad \forall i \in N \\ & w_{ij} = 0\quad \forall i \in N \cup \{ k,m\} ,j \in N \\ & \alpha_{(Q)} = \left\{ {\begin{array}{*{20}l} {\alpha_{1} } \hfill & {0 < Q < w_{mk} + U} \hfill \\ {\alpha_{2} } \hfill & {Q \ge w_{mk} + U} \hfill \\ \end{array} } \right. \\ & {\text{where}}\;\alpha_{1} = \frac{a}{2a + b} \;{\text{and}}\;\alpha_{2} = \frac{b}{2a + b}. \\ \end{aligned} $$

Note that, in such a setting, triangular inequalities for distances are always satisfied. Let transportation costs between the nodes be equal to the distances. There is a discount only on the edge between hub nodes k and m.

Now we will show that we solve the above hub allocation problem if and only if we can solve the above knapsack problem.

For the load to be sent from spoke i to m, w_im, the transportation path is either i → m or i → k → m. Although the unit transportation cost on the second path is based on the total load to be sent on this path, the unit costs can be specified as d_im and (d_ik + α₂d_km), respectively, assuming that the discount level on the path from k to m is the best option, i.e., α₂. Note that $\sum\nolimits_{i \in N} {w_{im} } = nw_{mk} + \sum\nolimits_{i \in R} {g_{i} } \ge w_{mk} + U$, therefore, there is enough loads to achieve the option α₂ for the flow from k to m. Since the unit transportation cost of the second path is smaller than the first one for all $i \in N$, all these loads follow the second path in the optimal solution.

Note that the load w_mk is shipped from m to k. For the load from spoke i to k the two paths that may be followed are i → k and i → m → k. Let S be the set of spokes that their loads follow the second path. There may be two cases:

• (i) $\sum\nolimits_{i \in S} {w_{ik} } < U$

  In this case, because $w_{mk} + \sum\nolimits_{i \in S} {w_{ik} } = w_{mk} + \sum\nolimits_{i \in S} {g_{i} } < w_{mk} + U$, the discount level on the path from m to k is α₁. The total transportation cost of the flows to hub k is then,

  $$ \begin{aligned} cost_{1} (S) &= \alpha_{1} w_{mk} d_{mk} + \sum\limits_{i \in S} {w_{ik} \cdot (d_{im} + \alpha_{1} d_{mk} )} + \sum\limits_{i \in N/S} {w_{ik} d_{ik} } \\ &= \frac{{\alpha_{1} }}{{\alpha_{1} - \alpha_{2} }}\sum\limits_{i \in N} {f_{i} } + \frac{a}{2} + r\sum\limits_{i \in N} {g_{i} } + \sum\limits_{i \in S} {f_{i} } + \frac{a - b}{2}\sum\limits_{i \in S} {g_{i} } \\ &= \frac{a}{a - b}\sum\limits_{i \in R} {f_{i} } + \frac{a}{2} + \frac{a + b}{2}\sum\limits_{i \in R} {g_{i} } + \sum\limits_{i \in S} {f_{i} } + \frac{a - b}{2}\sum\limits_{i \in S} {g_{i} } \\ \end{aligned} $$

• (ii) $\sum\limits_{i \in S} {w_{ik} } \ge U$

  In this case, because $w_{mk} + \sum\limits_{i \in S} {w_{ik} } = w_{mk} + \sum\limits_{i \in S} {g_{i} } \ge w_{mk} + U$ the discount level on the path from m to k is α₂. The total transportation cost of the flows to hub k is then,

  $$ \begin{aligned} cost_{2} (S) &= \alpha_{2} w_{mk} d_{mk} + \sum\limits_{i \in S} {w_{ik} \cdot (d_{im} + \alpha_{2} d_{mk} )} + \sum\limits_{i \in N/S} {w_{ik} d_{ik} } \\ &= \frac{{\alpha_{2} }}{{\alpha_{1} - \alpha_{2} }}\sum\limits_{i \in N} {f_{i} } + \frac{b}{2} + r\sum\limits_{i \in N} {g_{i} } + \sum\limits_{i \in S} {f_{i} } \\ &= \frac{b}{a - b}\sum\limits_{i \in R} {f_{i} } + \frac{b}{2} + \frac{a + b}{2}\sum\limits_{i \in R} {g_{i} } + \sum\limits_{i \in S} {f_{i} } \\ \end{aligned} $$

Note that, cost₁(S) is minimized if $S = \varphi$ and it is equal to

$$ bestcost_{1} = \frac{{\alpha_{1} }}{{\alpha_{1} - \alpha_{2} }}\sum\limits_{i \in R} {f_{i} } + \frac{a}{2} + r\sum\limits_{i \in R} {g_{i} } = \frac{a}{a - b}\sum\limits_{i \in R} {f_{i} } + \frac{a}{2} + \frac{a + b}{2}\sum\limits_{i \in R} {g_{i} } $$

On the other hand, cost₂(S) is maximized if S = N and it is equal to

$$ worstcost_{2} = \frac{{\alpha_{2} }}{{\alpha_{1} - \alpha_{2} }}\sum\limits_{i \in R} {f_{i} } + \frac{b}{2} + r\sum\limits_{i \in R} {g_{i} } + \sum\limits_{i \in R} {f_{i} } = \frac{b}{a - b}\sum\limits_{i \in R} {f_{i} } + \frac{b}{2} + \frac{a + b}{2}\sum\limits_{i \in R} {g_{i} } + \sum\limits_{i \in R} {f_{i} } $$

Since (bestcost₁ − worstcost₂) = (a − b)/2 ≥ 0, any solution that belongs to the first case is always worse than the one that belongs to the second case. So, the optimal solution belongs to the second case. The problem is then to find $S \subseteq N$ such that $\sum\nolimits_{i \in S} {w_{ik} } \ge U$ and cost₂(S) is minimized. Because the first three components of cost₂(S) are constant the problem is equivalent to the knapsack problem given above. So, we solve this instance of the 2-MHAP with all unit discount cost if and only if we can solve the above knapsack problem. Because the knapsack problem is NP-hard then the 2-MHAP with all unit discount cost in two levels is NP-hard. □

Theorem 2

The 2-SHAP with all unit discount cost in two levels is NP-hard.

Proof

Changing w_im = 0 for all $i \in N$ in the proof of Theorem 1 proves Theorem 2. Because when w_im = 0 for all $i \in N$, the problem is to determine the flow amount w_ik that follows the path i → k or the path i → m → k, which is equivalent to determining the hub that spoke i is assigned to. In the proof of Theorem 1 it has been shown that this problem is NP-hard. □

Theorem 3

The 2-MHMP with all unit discount cost in two levels is NP-hard.

Proof

Direct result of Theorem 1. □

Theorem 4

The 2-SHMP with all unit discount cost in two levels is NP-hard.

Proof

Direct result of Theorem 2. □

3 Modified all unit discount (shipping Q but declaring LB_{i + 1}) cost structure

This structure is useful if the firm is a customer of another trucking firm. In all unit discount cost structure the total cost decreases when the total quantity passes to the next interval. In order not to give more money the firm can declare that the total amount of the freight is equal to the lower bound of the next interval if the total cost is higher than the one with the true cost level. In this case the total transportation cost of Q units from hub k to hub m is:

$$ C_{km} (Q) = \left\{ {\begin{array}{*{20}l} {\alpha_{n} Qd_{km} } \hfill & {\quad for\quad LB_{n} \le Q \le (\alpha_{n + 1} /\alpha_{n} )LB_{n + 1} } \hfill & {and\quad n = 1, \ldots ,L - 1} \hfill \\ {\alpha_{n + 1} LB_{n + 1} d_{km} } \hfill & {\quad for\quad (\alpha_{n + 1} /\alpha_{n} )LB_{n + 1} \le Q \le LB_{n + 1} } \hfill & {and\quad n = 1, \ldots ,L - 1 } \hfill \\ {\alpha_{L} Qd_{km} } \hfill & {\quad for\quad LB_{L} \le Q} \hfill & {} \hfill \\ \end{array} } \right. $$

Figure 3 shows the shape of C_km(Q) for the modified-all-unit-discount model.

Fig. 3

Modified all unit discount model

Theorem 5

The 2-MHAP with modified all unit discount cost in two levels is NP-hard.

Proof

We show that the binary knapsack problem is polynomially reducible to the 2-MHAP with modified all unit discount cost even if L = 2.

Consider an instance of the binary knapsack problem as given below.

$$ \begin{aligned} & \hbox{max} \sum\limits_{i \in R} {f_{i} } x_{i} \\ & s.t. \\ & \sum\limits_{i \in R} {g_{i} x_{i} } \le U \\ & x_{i} \in \{ 0,1\} \quad \forall i \in R = \{ 1,2, \ldots ,n\} \\ \end{aligned} $$

where $\sum\nolimits_{i \in R} {g_{i} } > U$, U is a positive integer, and 0 < g_i ≤ U and integer, and $f_{i} > 0$ for all $i \in R$.

Consider the following instance of the 2-MHAP with modified all unit discount cost and L = 2. Let N (N = R) be the set of spokes and k and m ($k,m \notin N$) be the fixed hubs. Let

$$ \begin{aligned} & D = \sum\limits_{i \in R} {g_{i} } \\ & d_{ik} = \sum\limits_{j \in R} {f_{j} } \quad \forall i \in N \\ & d_{km} = 2\sum\limits_{i \in R} {f_{i} } \\ & d_{im} = d_{ik} + \frac{{f_{i} }}{{g_{i} }}\quad \forall i \in N \\ & d_{ij} = d_{ji} \quad \forall i,j \in N \cup \{ k,m\} \\ & w_{im} = g_{i} \quad \forall i \in N \\ & w_{ik} = 1\quad \forall i \in N \\ & w_{km} = D \\ & w_{mk} = 0 \\ & w_{ij} = 0\quad \forall i \in N \cup \{ k,m\} ,j \in N \\ & \alpha_{(Q)} = \left\{ {\begin{array}{*{20}c} {\alpha_{1} } & {0 < Q < D + U} \\ {\alpha_{2} } & {Q \ge D + U} \\ \end{array} } \right. \\ & {\text{where}}\;\alpha_{1} = \frac{(D + U)}{2D}\; {\text{and}}\;\alpha_{2} = \frac{1}{2}. \\ \end{aligned} $$

Note that, in such a setting, triangular inequalities for distances are always satisfied. Also it is satisfied that 0 < α₂ < α₁ < 1 since D > U. Let transportation costs between the nodes be equal to the distances. There is a discount only on the edge between hub nodes k and m.

Now we will show that we solve the above hub allocation problem if and only if we can solve the above knapsack problem.

Because d_im > d_ik, the path i → k is always cheaper than the path i → m → k even if the transportation cost from hub m to hub k is nil. Therefore, the load from spoke i to hub k, w_ik, follows the path i → k in the optimal solution.

According to the above settings, when the total flow from k to m is less than or equal to D discount factor will be α₁. When it is between D and (D + U) the total cost of this transportation will be constant as α₁*d_km*D. When it is more than (D + U) the discount factor α₂ will be applied. Since k and m are hubs w_km follows the path k → m. Because w_km = D for some additional flows (up to D + U) the transportation cost from k to m is zero. Because $D + U < w_{km} + \sum\nolimits_{i \in N} {w_{im} }$ only some part of $\sum\nolimits_{i \in N} {w_{im} }$ may be transported from k to m with zero transportation cost.

When the transportation cost from k to m is zero, the unit transportation cost of the path i → k → m is equal to d_ik. For the amount of flows that exceeds (D + U), the unit transportation cost per unit distance from k to m is α₂. Then the unit transportation cost on the same path is d_ik + α₂d_km. If any load w_im follows the path i → m, then the unit transportation cost is d_im. Since d_ik < d_im < d_ik + α₂d_km any load w_im will follow the path i → k → m if the transportation cost from k to m is zero. If this cost is α₂ then it will follow the path i → m. So the problem is to determine the amount of load to be sent using either the path i → k → m or the path i → m. Let S be the set of spokes that their loads follow the first path. There may be two cases:

• (i) $\sum\nolimits_{i \in S} {w_{im} } \le U$

  The total transportation cost of the flows to hub m is then,

  $$ \begin{aligned} cost_{1} (S) &= \sum\limits_{i \in S} {w_{im} d_{ik} } + \sum\limits_{i \in N/S} {w_{im} d_{im} } + \alpha_{1} w_{km} d_{km} \\ &= \sum\limits_{i \in N} {g_{i} } d_{ik} + \sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } + \alpha_{1} Dd_{km} \\ &= \left( {2\sum\limits_{i \in R} {g_{i} + U + 1} } \right)\sum\limits_{i \in R} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ \end{aligned} $$

• (ii) $\sum\nolimits_{i \in S} {w_{im} } > U$

  The total transportation cost of the flows to hub m is,

  $$ \begin{aligned} cost_{2} (S) &= \sum\limits_{i \in S} {w_{im} d_{ik} } + \sum\limits_{i \in N/S} {w_{im} d_{im} } + \left( {\sum\limits_{i \in S} {w_{im} } - U} \right)\sum\limits_{i \in N} {f_{i} } + \alpha_{1} w_{km} d_{km} \\ &= \sum\limits_{i \in N} {g_{i} d_{ik} } + \sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } + \left( {\sum\limits_{i \in S} {g_{i} } - U} \right)\sum\limits_{i \in N} {f_{i} } + \alpha_{1} Dd_{km} \\ &= \left( {2\sum\limits_{i \in R} {g_{i} } + \sum\limits_{i \in S} {g_{i} } + 1} \right)\sum\limits_{i \in R} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ \end{aligned} $$

Note that, cost₁(S) is maximized if $S = \varphi$ and it is equal to

$$ worstcost_{1} = \left( {2\sum\limits_{i \in R} {g_{i} + U + 1} } \right)\sum\limits_{i \in R} {f_{i} } . $$

On the other hand, cost₂(S) is minimized when $\sum\nolimits_{i \in S} {w_{im} }$ is close to U. Because $w_{im} = g_{i}$ for all $i \in N$ and g_i values and U are integer, this summation may be at least (U + 1). In this case cost₂(S) is equal to

$$ bestcost_{2} (S) = \left( {2\sum\limits_{i \in R} {g_{i} + U + 1} } \right)\sum\limits_{i \in R} {f_{i} } + \sum\limits_{i \in R\backslash S} {f_{i} } . $$

For any solution verifying (ii), transportation cost is more than the cost of any solution belongs to case (i). So, the optimal solution belongs to the first case. The problem is then to find $S \subseteq N$ such that $\sum\limits_{i \in S} {w_{im} } \le U$ and cost₁(S) is minimized. Because the first component of cost₁(S) is constant the problem is equivalent to the knapsack problem given above. So, we solve this instance of the 2-MHAP with modified all unit discount cost if and only if we can solve the above knapsack problem. Because the knapsack problem is NP-hard then the 2-MHAP with modified all unit discount cost in two levels is NP-hard. □

Theorem 6

The 2-SHAP with modified all unit discount cost in two levels is NP-hard.

Proof

Changing w_ik = 0 for all $i \in N$ in the proof of Theorem 5 proves Theorem 6. Because when w_ik = 0 for all $i \in N$, the problem is to determine the amount of flow from N that follows the path i → m or the path i → k → m, which is equivalent to determining the hub that spoke i is assigned to. In the proof of Theorem 5, it has been shown that this problem is NP-hard. □

Theorem 7

The 2-MHMP with modified all unit discount cost in two levels is NP-hard.

Proof

Direct result of Theorem 5. □

Theorem 8

The 2-SHMP with modified all unit discount cost in two levels is NP-hard.

Proof

Direct result of Theorem 6. □

4 Car (truck) load discount cost structure

This cost model is also useful if the firm is a customer of a truck carrier firm. There are 2 well known pricing policies of truck carriers: Truck Load (TL) policy and Less than Truck Load (LTL) policy. Let C be the load capacity of a truck. In the TL policy, the truck carrier allocates (or rents) a truck to the customer with a cost (let’s say H). Whatever the load amount of the customer is it pays this cost of a full truck. Paying the full truck cost is unnecessarily expensive for the customer when its load is not high enough. This time the customer wants to pay an amount of money which is based on the amount of the load. In this case the truck carrier applies LTL policy: a unit transportation cost (let it be α) is applied on each unit of the load. In this policy the carrier does not allocate the truck to a single customer. It can carry load of some other customers together using the same truck. But it is not sure that it can find some other customers and earn as much as H. As a result of this risk, the truck carrier applies a more expensive unit transportation cost for small amount of loads. If the load of the customer is low then it prefers to pay according to LTL policy. Up to some load level (let’s say D) which is less than C, the total cost of the transportation to the customer is less than H. When the load exceeds D paying according to LTL policy becomes more expensive than H because of more expensive unit transportation cost of the LTL policy. So, when its load amount is between D and C, the customer prefers to rent the truck with the cost of H. If its load amount is more than C, then the customer rents a truck and applies the same strategy for the rest of its load considering second truck, and so on.

In this case the total transportation cost of Q units from hub k to hub m is:

$$ C_{km} (Q) = \left\{ {\begin{array}{*{20}l} {\left[ {\alpha D\left\lfloor {\frac{Q}{C}} \right\rfloor + \alpha \left( {Q - C\left\lfloor {\frac{Q}{C}} \right\rfloor } \right)} \right]d_{km} } \hfill & { \, C\left\lfloor {\frac{Q}{C}} \right\rfloor \le Q \le C\left\lfloor {\frac{Q}{C}} \right\rfloor + D} \hfill \\ {\alpha D\left\lceil {\frac{Q}{C}} \right\rceil d_{km} } \hfill & { \, C\left\lfloor {\frac{Q}{C}} \right\rfloor + D \le Q \le C\left\lceil {\frac{Q}{C}} \right\rceil } \hfill \\ \end{array} } \right. $$

Figure 4 shows the shape of C_km(Q) for the car (truck) load discount model.

Fig. 4

Car load discount model

Theorem 9

The 2-MHAP with car load discount cost is NP-hard.

Proof

We show that the binary knapsack problem is polynomially reducible to the 2-MHAP with car load discount cost.

Consider an instance of the binary knapsack problem as given below.

$$ \begin{aligned} & \hbox{max} \sum\limits_{i \in R} {f_{i} } x_{i} \\ & s.t. \\ & \sum\limits_{i \in R} {g_{i} x_{i} } \le U \\ & x_{i} \in \{ 0,1\} \quad \forall i \in R = \{ 1,2, \ldots ,n\} \\ \end{aligned} $$

where $\sum\nolimits_{i \in R} {g_{i} } > U$, U is a positive integer, 0 < g_i ≤ U and integer, $f_{i} > 0$ for all $i \in R$.

Consider the following instance of the 2-MHAP with car load discount cost. Let N (Nv= R) be the set of spokes and k and m ($k,m \notin N$) be the fixed hubs. Let

$$ \begin{aligned} & D = \sum\limits_{i \in R} {g_{i} } \\ & C = \sum\limits_{i \in R} {g_{i} + U} \\ & d_{ik} = \sum\limits_{j \in R} {f_{j} } \quad \forall i \in N \\ & d_{im} = d_{ik} + \frac{{f_{i} }}{{g_{i} }}\quad \forall i \in N \\ & d_{km} = 2\sum\limits_{i \in R} {f_{i} } \\ & d_{ij} = d_{ji} \quad \forall i,j \in N \cup \{ k,m\} \\ & \alpha = \frac{1}{2} \\ & w_{im} = g_{i} \quad \forall i \in N \\ & w_{ik} = 1\quad \forall i \in N \\ & w_{ij} = 0\quad \forall i \in N \cup \{ k,m\} ,j \in N \\ & w_{km} = D \\ & w_{mk} = 0 \\ \end{aligned} $$

Note that, in such a setting, triangular inequalities for distances are always satisfied. Let transportation costs between the nodes be equal to the distances. There is a discount only on the edge between hub nodes k and m.

Now we will show that we solve the above hub allocation problem if and only if we can solve the above knapsack problem.

Because d_im > d_ik, the path i → k is always cheaper than the path i → m → k even if the transportation cost from hub m to hub k is zero. So the load from spoke i to hub k follows the path i → k at the optimal solution.

Because k and m are hubs, w_km follows the path k → m. Since w_km = D for some additional flows (up to C) the transportation cost from k to m is zero. Because $C < w_{km} + \sum\nolimits_{i \in N} {w_{im} \le C + D}$ only some amount of load $\sum\nolimits_{i \in N} {w_{im} }$ may be transported from k to m with zero transportation cost.

When the transportation cost from k to m is zero the unit transportation cost on the path i → k → m is equal to d_ik. For the amount of flow that exceeds C, the unit transportation cost per unit distance from k to m is α. The unit transportation cost on the same path is d_ik + αd_km. If any load w_im follows the path i → m, then the unit transportation cost is d_im. Since d_ik < d_im < d_ik + αd_km, any load w_im will follow the path i → k → m if the transportation cost from k to m is zero. If this cost is α then it will follow the path i → m. So the problem is about to find out the amount of the load to be sent using either the path i → k → m or the path i → m. Let S be the set of spokes that their loads follow the first path. There may be two cases:

• (i) $\sum\nolimits_{i \in S} {w_{im} } \le U$

  The total transportation cost of the flows to hub m is then,

  $$ \begin{aligned} cost_{1} (S) &= \sum\limits_{i \in S} {w_{im} d_{ik} } + \sum\limits_{i \in N/S} {w_{im} d_{im} } + \alpha d_{km} w_{km} \\ &= \sum\limits_{i \in N} {g_{i} } d_{ik} + \sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } + \sum\limits_{i \in N} {g_{i} \sum\limits_{i \in N} {f_{i} } } \\ &= \left( {2\sum\limits_{i \in R} {g_{i} } + 1} \right)\sum\limits_{i \in R} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ \end{aligned} $$

• (ii) $\sum\limits_{i \in S} {w_{im} } > U$

  The total transportation cost of the flows to hub m is then,

  $$ \begin{aligned} cost_{2} (S) &= \sum\limits_{i \in S} {w_{im} d_{ik} } + \sum\limits_{i \in N/S} {w_{im} d_{im} } + \left( {\sum\limits_{i \in S} {w_{im} } - U} \right)\sum\limits_{i \in N} {f_{i} } + \alpha d_{km} w_{km} \\ &= \sum\limits_{i \in N} {w_{im} d_{ik} } + \sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } + \left( {\sum\limits_{i \in S} {w_{im} } - U} \right)\sum\limits_{i \in N} {f_{i} } + \sum\limits_{i \in N} {g_{i} \sum\limits_{i \in N} {f_{i} } } \\ &= \left( {2\sum\limits_{i \in R} {g_{i} } + \sum\limits_{i \in S} {g_{i} } + 1 - U} \right)\sum\limits_{i \in R} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ \end{aligned} $$

Note that, cost₁(S) is maximized if $S = \varphi$ and it is equal to

$$ worstcost_{1} = (2\sum\limits_{i \in R} {g_{i} } + 1)\sum\limits_{i \in R} {f_{i} } . $$

On the other hand, cost₂(S) is minimized when $\sum\limits_{i \in S} {w_{im} }$ is close to U. Because $w_{im} = g_{i}$ for all $i \in N$ and g_i values and U are integer this summation may be at least (U + 1). In this case cost₂(S) is equal to

$$ bestcost_{2} (S) = \left( {2\sum\limits_{i \in R} {g_{i} } + 1} \right)\sum\limits_{i \in N} {f_{i} } + \sum\limits_{i \in R\backslash S} {f_{i} } . $$

Since (bestcost₂(S)-worstcost₁) > 0, any solution that belongs to the second case is always worse than the one that belongs to the first case. So, the optimal solution belongs to the first case. The problem is then to find $S \subseteq N$ such that $\sum\limits_{i \in S} {w_{im} } \le U$ and cost₁(S) is minimized. Because the first component of cost₁(S) is constant the problem is equivalent to the knapsack problem given above. So, we solve this instance of the 2-MHAP with car load discount cost if and only if we can solve the above knapsack problem. Because the given knapsack problem is NP-hard then the 2-MHAP with car load discount cost is NP-hard. □

Theorem 10

The 2-SHAP with car load discount cost is NP-hard.

Proof

Changing w_ik = 0 for all $i \in N$ in the proof of Theorem 9 proves Theorem 10. When w_ik = 0 for all $i \in N$, the problem is to determine the amount of load from N that follows the path i → m or the path i → k → m, which is equivalent to determining the hub that spoke i is assigned to. In the proof of Theorem 9, it has been shown that this problem is NP-hard. □

Theorem 11

The 2-MHMP with car load discount cost is NP-hard.

Proof

Direct result of Theorem 9. □

Theorem 12

The 2-SHMP with car load discount cost is NP-hard.

Proof

Direct result of Theorem 10. □

5 Container cost structure

This cost structure is not a quantity discount cost structure, i.e. average unit transportation cost per unit distance may increase when the quantity increases. This cost function may be used on inter-hub links if the average transportation cost per unit distance is smaller than the one of between spoke and hub links. This cost function is useful for the firm that uses its own vehicles or it is a customer of another transportation firm. In this cost structure transportations are made with containers (or trucks) and a fixed charge (A) occurs when a new container is added and there is a unit variable transportation cost (α). Each container has capacity C. When the amount of the flow between hubs k and m is Q then the total transportation cost is

$$ C_{km} (Q) = A\left\lceil {\frac{Q}{C}} \right\rceil + \alpha Qd_{km} $$

Figure 5 shows the shape of C_km(Q) for the container cost model.

Fig. 5

Container based cost

Theorem 13

The 2-MHAP with container cost is NP-hard.

Proof

We show that the binary knapsack problem is polynomially reducible to the 2-MHAP with container cost.

Consider an instance of the binary knapsack problem as given below.

$$ \begin{aligned} & \hbox{max} \sum\limits_{i \in R} {f_{i} } x_{i} \\ & s.t. \\ & \sum\limits_{i \in R} {g_{i} x_{i} } \le U \\ & x_{i} \in \{ 0,1\} \quad \forall i \in R = \{ 1,2, \ldots ,n\} \\ \end{aligned} $$

where $\sum\limits_{i \in R} {g_{i} } > U$, 0 < g_i ≤ U, $f_{i} > 0$ for all $i \in R$.

Consider the following instance of the 2-MHAP with container cost. Let N (N = R) be the set of spokes and k and m ($k,m \notin N$) be the fixed hubs. Let

$$ \begin{aligned} & C = w_{km} + U \\ & A = 2\sum\limits_{i \in R} {f_{i} } \\ & \alpha : {\text{any}}\;{\text{value}}\;{\text{in}}\;{\text{the}}\;{\text{interval}}\;\left[ {0, \hbox{min} \left\{ {\frac{{w_{km} - A}}{{w_{km} }},\frac{C - 2A}{C}} \right\}} \right) \\ & d_{ik} = 1 + \mathop {\hbox{max} }\limits_{i \in R} \left\{ {\frac{{f_{i} }}{{g_{i} }}} \right\}\quad \forall i \in N \\ & d_{km} = \frac{{2\mathop {\hbox{max} }\limits_{i \in R} \left\{ {\frac{{f_{i} }}{{g_{i} }}} \right\}}}{1 - \alpha } \\ & d_{im} = d_{ik} + \frac{{f_{i} }}{{g_{i} }} + \alpha d_{km} \quad \forall i \in N \\ & d_{ij} = d_{ji} \quad \forall i,j \in N \cup \{ k,m\} \\ & w_{im} = g_{i} \quad \forall i \in N \\ & w_{ik} = 1\quad \forall i \in N \\ & w_{km} = \hbox{max} \left\{ {4\sum\limits_{i \in R} {f_{i} } ,2\sum\limits_{i \in R} {g_{i} } } \right\} \\ & w_{ij} = 0\quad \forall i \in N \cup \{ k,m\} ,j \in N \\ & w_{mk} = 0 \\ \end{aligned} $$

Triangular inequalities are always satisfied for distances. Note that unit transportation cost per unit distance between the hubs is always smaller than the one between spokes and hubs, which is 1, for $Q \ge w_{km}$.

Now we will show that we solve the above hub allocation problem if and only if we can solve the above knapsack problem.

Because d_im > d_ik, the path i → k is always cheaper than the path i → m → k. Then the loads from spokes to hub k follow the path i → k at the optimal solution.

Because of the direct transportation between hubs and there is a load to be sent from k to m, w_km, at least one truck (container) must be sent from k to m. So the problem is to find out the amount to be sent through the path i → m or the path i → k → m. Let S be the set of spokes that their loads follow the second path. There may be two cases:

• (i) $\sum\limits_{i \in S} {w_{im} } \le U$

  The total cost of transportation to hub m is,

  $$ \begin{aligned} cost_{1} (S) & = A\left\lceil {\frac{{w_{km} + \sum\limits_{i \in S} {w_{im} } }}{C}} \right\rceil + \alpha w_{km} d_{km} + \sum\limits_{i \in S} {w_{im} d_{ik} } + \sum\limits_{i \in S} {w_{im} \alpha d_{km} } + \sum\limits_{i \in N/S} {w_{im} d_{im} } \\ & = A + \alpha w_{km} d_{km} + \sum\limits_{i \in N} {g_{i} d_{ik} } + \alpha d_{km} \sum\limits_{i \in N} {g_{i} } + \sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ \end{aligned} $$

• (ii) $\sum\limits_{i \in S} {w_{im} } > U$

  The total cost of transportation to hub m is,

  $$ \begin{aligned} cost_{2} (S) & = A\left\lceil {\frac{{w_{km} + \sum\limits_{i \in S} {w_{im} } }}{C}} \right\rceil + \alpha w_{km} d_{km} \\ &\quad + \sum\limits_{i \in S} {w_{im} d_{ik} } + \sum\limits_{i \in S} {w_{im} \alpha d_{km} } + \sum\limits_{i \in N/S} {w_{im} d_{im} } \\ & = A\left\lceil {\frac{{\sum\limits_{i \in S} {w_{im} } - U}}{C}} \right\rceil + A + \alpha w_{km} d_{km} + \sum\limits_{i \in N} {g_{i} d_{ik} } + \alpha d_{km} \sum\limits_{i \in N} {g_{i} }\\ &\quad + \sum\limits_{i \in N} {f_{i} } + 2\sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ & = A\left\lceil {\frac{{\sum\limits_{i \in S} {g_{i} } - U}}{{\hbox{max} \left\{ {4\sum\limits_{i \in R} {f_{i} } ,2\sum\limits_{i \in R} {g_{i} } } \right\} + U}}} \right\rceil + A + \alpha w_{km} d_{km}\\ &\quad + \sum\limits_{i \in N} {g_{i} d_{ik} } + \alpha d_{km} \sum\limits_{i \in N} {g_{i} } + \sum\limits_{i \in N} {f_{i} } + 2\sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ & = A + A + \alpha w_{km} d_{km} + \sum\limits_{i \in N} {g_{i} d_{ik} } + \alpha d_{km} \sum\limits_{i \in N} {g_{i} } + \sum\limits_{i \in N} {f_{i} } + 2\sum\limits_{i \in N} {f_{i} } - \sum\limits_{i \in S} {f_{i} } \\ \end{aligned} $$

Note that, cost₁(S) is maximized if $S = \varphi$ and it is equal to

$$ worstcost_{1} = A + \alpha w_{km} d_{km} + \sum\limits_{i \in N} {g_{i} d_{ik} } + \alpha d_{km} \sum\limits_{i \in N} {g_{i} } + \sum\limits_{i \in N} {f_{i} } . $$

On the other hand, cost₂(S) is minimized when S = N. In this case cost₂(S) is equal to

$$ bestcost_{2} = A + A + \alpha w_{km} d_{km} + \sum\limits_{i \in N} {g_{i} d_{ik} } + \alpha d_{km} \sum\limits_{i \in N} {g_{i} } + \sum\limits_{i \in N} {f_{i} } + \sum\limits_{i \in N} {f_{i} } . $$

Since (bestcost₂ − worstcost₁) > 0, any solution that belongs to the second case is always worse than the one that belongs to the first case. So, the optimal solution belongs to the first case. The problem is then to find $S \subseteq N$ such that $\sum\limits_{i \in S} {w_{im} } \le U$ and cost₁(S) is minimized. Because only the last component of cost₁(S) is constant and $w_{im} = g_{i}$ for all $i \in N$, the problem is equivalent to the knapsack problem given above. So, we solve this instance of the 2-MHAP with container cost if and only if we can solve the above knapsack problem. Because the given knapsack problem is NP-hard then the 2-MHAP with container cost is NP-hard. □

Theorem 14

The 2-SHAP with container cost is NP-hard.

Proof

Changing w_ik = 0 for all $i \in N$ in the proof of Theorem 13 proves Theorem 14. Because when w_ik = 0 for all $i \in N$, the problem is to determine the amount of load from N that follows the path i → m or the path i → k → m, which is equivalent to determining the hub that spoke i is assigned to. In the proof of Theorem 13, it has been shown that this problem is NP-hard. □

Theorem 15

The 2-MHMP with container cost is NP-hard.

Proof

Direct result of Theorem 13. □

Theorem 16

The 2-SHMP with container cost is NP-hard.

Proof

Direct result of Theorem 14. □

6 Conclusion and future study issues

In this study, we analyzed the complexity of the p-hub median problems with some non-linear cost structures. We showed that when the transportation cost between spokes and hubs is linear and the one between hubs is one of all unit discount, modified all unit discount, truck load discount and container cost structures, the p-hub allocation problem is NP-hard even p = 2 for both single allocation and multiple allocation models. These results imply that the p-hub median problem is NP-hard for given cases and if the transportation costs between spokes and hubs are non-linear the problems are again NP-hard.

In producing our complexity results, we have shown that the knapsack problem is polynomially reducible to our problems. Then we should be able to develop a general DP based solution algorithm that runs in pseudo polynomial time to solve these restricted problems. Unfortunately, our first attempt in this regard was not successful. If we could not develop such an algorithm then we need to show that the problems are NP-hard in the strong sense. Otherwise, we need to check whether the problems with p = 3 and/or L = 3 are pseudo polynomially solvable or NP-hard in the strong sense. One another well-known and useful discount model in transportation is the incremental (or progressive) discount model which has a piecewise-linear concave total cost function of the transportation amount Q. Unfortunately, despite our long efforts we could not be successful in proving the complexity of the problems with this cost structure. These issues can be considered as a subject of some future research studies.