A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

Abstract

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.

Introduction

The hub allocation problem is concerned with allocating hub facilities in order to route the traffic between origin–destination pairs. In single allocation all the incoming and outgoing flow of every location is routed through a single hub. A general survey of different hub location problems can be found in Alumur and Kara (2008). The uncapacitated single allocation p-hub median problem (USApHMP for short) was first formulated by O’Kelly (1987) as an integer quadratic program.

There are n locations (or nodes) in the plane with corresponding x and y coordinates. Let $D_{i\text{,}j}$ be the Euclidean distance between locations i and j. For every pair of nodes i and j there is an amount of flow $W_{i\text{,}j}⩾0$ that needs to be transferred from i to j. Note that $D_{i\text{,}i}=0$, but $W_{i\text{,}i}$ should be strictly greater than zero. Due to metric properties, matrix D is symmetric, but matrix W is not symmetric in general. We have to choose p hubs among these n locations, where p is given. Let N be the set of all locations, and H be the set of hubs. Every non-hub node $v\in N⧹H$ is assigned to a single hub $h\in H$. Direct transportation between non-hub nodes is not allowed. The objective of the uncapacitated single allocation p-hub median problem is to minimize the overall flow cost in a network.

Parameters $\chi \text{,}\alpha$ and $\delta$ are unit rates for collection (origin–hub), transfer (hub–hub) and distribution (hub–destination), respectively. Generally, $\alpha$ is used as a discount factor to provide reduced unit costs on arcs between hubs, so $\alpha <\chi$ and $\alpha <\delta$. The problem can be rewritten as:

$$\min \sum _{i=1}^n\sum _{j=1}^n{W}_{i\text{,}j}(\chi D_{i\text{,}h[i]}+\alpha D_{h[i]\text{,}h[j]}+\delta D_{h[j]\text{,}j})\text{.}$$

O’Kelly (1987) formulated the single allocation p-hub median problem as a quadratic integer program.

Let $X_{\mathit{ij}}$ variables be defined as:

$$X_{\mathit{ij}}=\left\{\begin{array}{cc}1\text{,}\hfill & \text{Location}i\text{is}\text{assigned}\text{to}\text{hub}(\text{location})j\text{,}\hfill \\ 0\text{,}\hfill & \text{otherwise}.\hfill \end{array}\right.$$

Then, the uncapacitated single allocation p-hub median problem can be defined as follows:

$$\min \sum _{i=1}^n\sum _{j=1}^n{W}_{\mathit{ij}}\left(\chi \sum _{k=1}^n{X}_{\mathit{ik}}{D}_{\mathit{ik}}+\delta \sum _{m=1}^n{X}_{\mathit{jm}}{D}_{\mathit{jm}}+\alpha \sum _{k=1}^n\sum _{m=1}^n{X}_{\mathit{ik}}{X}_{\mathit{jm}}{D}_{\mathit{km}}\right)\text{,}$$

such that

$$(n-p+1)X_{\mathit{jj}}-\sum _{i=1}^n{X}_{\mathit{ij}}⩾0\text{,}j=1\text{,}\dots \text{,}n\text{,}$$

$$\sum _{j=1}^n{X}_{\mathit{ij}}=1\text{,}i=1\text{,}\dots \text{,}n\text{,}$$

$$\sum _{j=1}^n{X}_{\mathit{jj}}=p\text{,}$$

$$X_{\mathit{ij}}\in \{0\text{,}1\}\text{for}\text{all}i\text{,}j\text{.}$$

Constraints (3) ensure that nonhub nodes are assigned only to hub nodes. Constraints (4) ensure that each node can be assigned to one and only one node. Constraint 5 ensures that exactly p hubs are located.

Campbell (1991) formulated the p-hub median problem as follows:

$$\min \sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n\sum _{m=1}^n{W}_{\mathit{ij}}{X}_{\mathit{ijkm}}(\chi D_{\mathit{ik}}+\alpha D_{\mathit{km}}+\delta D_{\mathit{mj}})\text{,}$$

such that

$$\sum _{k=1}^n\sum _{m=1}^n{X}_{\mathit{ijkm}}=1\text{forall}i\text{,}j\text{,}$$

$$X_{\mathit{ijkm}}⩽Y_k\text{for}\text{all}i\text{,}j\text{,}k\text{,}m\text{,}$$

$$X_{\mathit{ijkm}}⩽Y_m\text{for}\text{all}i\text{,}j\text{,}k\text{,}m\text{,}$$

$$\sum _{k=1}^n{Y}_k=p\text{,}$$

$$X_{\mathit{ijkm}}\text{,}{Y}_k\in \{0\text{,}1\}\text{for}\text{all}i\text{,}j\text{,}k\text{,}m$$

and this formulation may be transformed into following

$$\min \sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n\sum _{m=1}^n{W}_{\mathit{ij}}{X}_{\mathit{ijkm}}(\chi D_{\mathit{ik}}+\alpha D_{\mathit{km}}+\delta D_{\mathit{mj}})$$

such that

$$\sum _{k=1}^n\sum _{m=1}^n{X}_{\mathit{ijkm}}=1\text{for}\text{all}i\text{,}j\text{,}$$

$$\sum _{k=1}^n{Y}_k=p\text{,}$$

$$Z_{\mathit{ik}}⩽Y_k\text{for}\text{all}i\text{,}k\text{,}$$

$$2X_{\mathit{ijkm}}⩽Z_{\mathit{ik}}+Z_{\mathit{jm}}\text{for}\text{all}i\text{,}j\text{,}k\text{,}m\text{,}$$

$$X_{\mathit{ijkm}}\text{,}{Z}_{\mathit{ik}}\text{,}{Y}_k\in \{0\text{,}1\}\text{for}\text{all}i\text{,}j\text{,}k\text{,}m\text{.}$$

The quadratic programming formulation is very difficult to solve; whereas the linear programming formulation has many variables and constraints (the number of variables and constraints is $O(n^4)$).

USApHMP belongs to the class of NP hard problems. Even when the set of hubs is given, the assignment sub-problem of optimal allocation of non-hub nodes to hubs is also NP hard (Love et al., 1996). Therefore, when the size of a problem becomes large, we have to apply heuristic solution approaches.

Several heuristics have been proposed for the p-hub median problem. The first method by O’Kelly (1987) is based on exhaustive search for all possible choices of p hub locations. In the first assignment method HEUR1, every location is assigned to the nearest hub, while the second HEUR2 assigns every non-hub to the nearest or the second nearest hub. Klincewicz (1991) developed an exchange heuristic based on local improvement considering both the single and double exchange procedures. His comparison showed that these heuristics are superior to the heuristics proposed by O’Kelly (1987). Klincewicz (1992) presented a tabu search and a greedy randomized search procedure GRASP heuristic. He considered the traffic among the hubs in addition to the distance criteria and also proposed an associated clustering heuristic. A cluster represents one hub with all locations assigned to it. A simulated annealing (SA) approach is described by Ernst and Krishnamoorthy (1996). It starts with a randomly generated solution and uses a simple geometric cooling regime with two types of transitions to generate neighborhood solutions:

• Change the allocation of a randomly chosen non-hub node to a different cluster.

• Change the location of a hub within a randomly chosen cluster to a different node in the cluster; if the cluster contains only a single node-then replace this hub with a random non-hub node.

A version of tabu search, called TABUHUB, is developed by Skorin-Kapov and Skorin-Kapov (1994). The method treats equally the problem of locating hub facilities, as well as the problem of allocating nodes to exactly one hub. The neighborhood of a feasible solution contains solutions whose set of hubs differs in exactly one node, regardless of the allocation of non-hub nodes. A tabu search strategy is applied on both levels to deal with the local optimality problem. The tabu list records all pairs (h, q)-single location exchange when hub h is replaced with non-hub q.

Pérez–Pérez et al., 2004, Pérez–Pérez et al., 2007 proposed a hybrid algorithm that combines Variable neighborhood search and Path relinking heuristics, named VNS–PR. A feasible solution is represented by an array with n elements, where the first p elements are indexes of hub locations and the second part indicates allocation of non-hub nodes. In this approach, VNS is used for populating the initial set of elite solutions for the PR method. The path relinking paradigm, like VNS, uses systematic neighborhood based strategies to explore the feasible region. PR exploits a mechanism for combining solutions and creating new sets that at each step seeks to incorporate attractive attributes from both parents. The distance function defined in this paper is the linear combination of the number of different hubs and the number of nodes with different assignments in two solutions. Hybrid VNS–PR improves the results of TABUHUB and SA both in quality of the solutions and in run times as shown in computational results in Pérez–Pérez et al. (2007).

Two genetic algorithm (GAHUB1 and GAHUB2) approaches are proposed by Kratica et al. (2007). The objective function is evaluated by summing all distances multiplied with corresponding flows and parameters. Both methods use fine-grained tournament selection FGTS, caching techniques, elitism and the idea of frozen bits to increase the diversity of solutions. Arranging located hubs in non-decreasing order of their distances from each non-hub node directs GA to the promising search regions. Solution representation for GAHUB1 is similar as in VNS–PR, but it can contain some duplicates and indexes are resolved during the execution of the algorithm. The crossover operator is performed with double one-point crossover, while the mutation operator changes randomly selected bits in the genetic code. The second approach GAHUB2 uses the first bit of the assignment array for representing whether the current location is a hub or not. Standard operators are modified in order to preserve exactly p hubs. The numerical experiments show that both metaheuristics are robust and efficient in solving USApHMP. GAHUB2 reaches or improves all best-known solutions on both CAB (Civil Aeronautics Board) and AP (Australia Post) instances, while the running time is close to the SA method and significantly slower than VNS–PR.

Ernst and Krishnamoorthy (1998) proposed a branch-and-bound algorithm which solves shortest-path problems to obtain lower bounds. Unlike the traditional branch-and-bound algorithms, their algorithm does not start with a single root node, but with a set of root nodes. They tested the effectiveness of this algorithm on the CAB and AP data sets, and observed that this new algorithm is very efficient for small values of p. The authors solved problems with 100 nodes and with p = 2 and p = 3 in approximately 228 and 2629 s respectively. However, they were still unable to solve problems with 100 nodes when p > 3 in a reasonable amount of computational time.

Wolf and Merz (2007) investigate optimization problems connected with topology construction in Peer-to-Peer systems. A possible solution of scalability of P2P networks is introducing super-peers that act as servers, and each common peer is attached to exactly one super-peer, which constitutes its link to the remainder of the network. The only difference between this problem and USApHMP is the super-peer degree restriction. The number x of common peers assigned to a super-peer is limited by

$$⌊\frac{p}{2}⌋⩽x⩽2p\text{,}$$

while we assume that every super-peer is assigned to itself. The authors present a super-peer selection heuristic, based on evolutionary algorithms and local search. After each step of the evolutionary algorithm, a local search is applied to further improve the current solution; they use three different neighborhoods: replacing the super-peer (in one cluster), swapping two peers (while exchanging assigned super-peers) and reassigning a peer to another super-peer. Mutation is done by swapping two random peers. This heuristic uses a population of only one individual, since there is no need for recombination. This approach improved some of the largest instances in the well known Australia Post data set.

Note that in the new instances prepared for the super-peer selection problem, the value of all three scaling parameters $\alpha \text{,}\delta$ and $\chi$ is set to one, and the amount of flow between all pairs of locations $(W_{\mathit{ij}})$ is also set to one. But this is not crucial, and the proposed heuristic may be applied for arbitrary values of these parameters.

Variable neighborhood search (VNS) is a metaheuristic proposed by Mladenović and Hansen (1997). Local search proceeds from an initial solution and using a sequence of local changes, improves the value of the objective function until a local optimum is found. VNS systematically exploits the idea of change of neighborhood during the search in a dynamic way. To construct different neighborhood structures and to perform a systematic search, one needs to supply the solution space with some (Quasi)-metrics and then induce neighborhoods from them.

In this paper, we develop two General VNS (GVNS) heuristics for solving the stated p-hub median problem. These heuristics differ in the local search step. The first uses a standard Sequential Variable neighborhood descent (VND); the other uses our proposed Nested VND. Three local search neighborhoods (Allocate, Alternate and our new Locate neighborhood) are examined in the Sequential and Nested VND. Note that two of the neighborhood structures, Allocate and Alternate, are the same as the Reassign and Replace neighborhoods in Wolf and Merz (2007), while the third is different. Moreover, Wolf and Merz (2007) refers to its solution approach as an evolutionary algorithm when in effect they are using in alternate terminology a General VNS with Sequential VND and backward shaking (Hansen and Mladenović, 2001a, Hansen and Mladenović, 2001b, Hansen and Mladenović, 2003, Hansen et al., 2008a) (which they call the mutation operator).

The rest of the paper is organized as follows: In Section 2 we provide the detailed rules of our two General VNS (GVNS) heuristics for solving the USApHMP. This includes a description of the new neighborhood Structure locate and the new Nested VND strategy, both of which are found to be highly effective in the local search step. The GVNS is also applied after a modification to the related super-peer selection problem. Section 3 gives a summary of computational results on several problem instances from the literature, and Section 4 concludes the paper.