# Capacitated single assignment hub location problem with modular link capacities

Corberán Á., Peiró J., Campos V., Glover F., Martí R. (2014)

Optsicom project, University of Valencia (Spain)

# Problem Description

The capacitated single assignment hub location problem with modular link capacities is a variant of the classical hub location problem in which the cost of using edges is not linear but stepwise, and the hubs are restricted in terms of transit capacity rather than in the incoming traffic. This problem was introduced by Yaman and Carello (Yaman and Carello, 2005) and treated by a branch-and-cut and a tabu search metaheuristic. We propose a metaheuristic algorithm based on strategic oscillation, a methodology originally introduced in the context of tabu search. Our method incorporates several designs for constructive and destructive algorithms, together with associated local search procedures, to balance diversification and intensification for an efficient search. Computational results on a large set of instances show that, in contrast to exact methods that can only solve small instances optimally, our metaheuristic is able to find high-quality solutions on larger instances in short computing times. In addition, the new method, which joins tabu search strategies with strategic oscillation, outperforms the previous tabu search implementation.

In mathematical terms, given a network *G* with a set of nodes *V* and a set of edges *E*,
let *t _{ij}* be the amount of traffic to be transported from node

*i*to node

*j*, where

*t*=0 for any node

_{ij}*i*.

Each node *i* is either a terminal node or a hub node (*terminal* and *hub* for short).
A terminal can only be assigned to a single hub. A hub is assigned to itself.
The hubs and the adges among them define a complete subgraph. Opening a hub at node *i* has a
fixed installation cost of *C _{ii}*. Each hub

*i*has a capacity

*Q*limiting the total amount of traffic transitiing through

^{h}*i*.

There are two types of edges between nodes: edges of the first type are used to connect terminals with hubs,
and we call them access edges. Let *m _{i}* be the number of access edges needed to route the
incoming and outgoing traffic at node

*i*. The cost of installing

*m*edges between terminal

_{i}*i*and hub

*k*is denoted by

*C*. Edges of the second type are used to transfer traffics between hubs, and we call them backbone edges. Each backbone edge has a maximum traffic capacity of

_{ik}*Q*(in each direction). If nodes

^{b}*k*and

*l*are hubs, the amount of traffic on arc (

*k*,

*l*), denoted as

*z*, is the traffic that has to be transported from nodes assigned to

_{kl}*k*to nodes assigned to

*l*. The capacity

*Q*of a given edge

^{b}*kl*cannot be less than the maximum traffic on its corresponding arcs (

*k*,

*l*) and (

*l*,

*k*), and the cost of installing te edge is denoted by

*R*.

_{kl}The following variables (Yaman and Carello, 2005) are defined in order to provide the mathematical programming model shown below:
The assignment variable *x _{ik}* is equal to 1 if terminal

*i*is assigned to hub

*k*, and 0 otherwise. If node

*i*receives a hub, then

*x*takes value 1.

_{ii}*z*is the traffic on an arc (

_{kl}*k*,

*l*) and

*w*is the number of copies of the edge

_{kl}*kl*.

The problem is formulated (Yaman and Carello, 2005) as:

# State of the Art Methods

A metaheursitic and a branch-and-cut algorithm were proposed in (Yaman and Carello, 2005).
The metaheuristic consists of a tabu search (TS) to solve the hub location subproblem and a local search for
assigning terminals to hubs. The solution provided by the metaheuristic is used as an initial upper bound in
the branch-and-cut algorithm and to limit the number of variables considered by the exact method.
In addition to the best solution, the metaheuristic produces also a subset of nodes that represents,
in a sense, the best potential locations for the hubs. The hubs selected in the best solution belong to this subset,
as well as the two other hubs which appear most often in the best solutions found by the metaheuristic.
This set is called the *concentration set*. The resulting reduced problem, where hubs can be chosen
only among the nodes of the concentration set, is called the *concentrated problem*, and is the problem
solved using the branch-and-cut method.

A strategic oscillation algorithm that incorporates several designs for constructive and destructive phases, making use of tabu search memory structures together with associated local search procedures.

# Instances

We have tested our algorithms on three sets of instances:

- The
**CAB**(Civil Aviation Board) data set. It is based on airline passenger flows between some important cities in the United States. It consists of a data file, presented by O’Kelly in 1987, with the distances and flows of a 25 nodes graph. - The
**AP**(Australian Post) data set. It is based on real data from the Australian postal service and was presented by Ernst and Krishnamoorthy in 1996. The size of the original data file is 200 nodes. Smaller instances can be obtained using a code from ORLIB. As with CAB, many authors have generated different instances from the original file. - The
**USA423**data set. Introduced by (Peiró, Corberán, and Martí, 2014) and based on real airline data. It consists of a data file concerning 423 cities in the United States, where real distances and passenger flows for an accumulated 3 months period are considered.

You can download the instances here.

# Computational Experience

We performed extensive computational experiments with 150 instances. The best values for the instances can be downloaded here.

# References

- Alumur, S., and Kara, B. Y. Network hub location problems: The state of the art. European Journal of Operational Research 190, 1 (2008), 1–21.
- Beasley, J. E. OR-library: distributing test problems by electronic mail. Journal of the Operational Research Society 41, 11 (1990), 1069–1072.
- Campbell, J. F., Ernst, A. T., and Krishnamoorthy, M.Hub location problems. In Facility location: Applications and theory, Z. Drezner and H. Hammacher, Eds. Springer, 2002, pp. 373–407.
- Campbell, J. F., and O'Kelly, M. E. Twenty-five years of hub location research. Transportation Science 46, 2 (2012), 153–169.
- Ernst, A. T., and Krishnamoorthy, M. Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Science 4, 3 (1996), 139–154.
- Fanjul-Peyroa, L., and Ruiz, R. Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research 207, 1 (2010), 55–69.
- Farahani, R. Z., and Hekmatfar, M. Facilities location: Concepts, models, algorithms and case studies. Springer-Verlag, 2009.
- Glover, F. Heuristics for integer programming using surrogate constraints. Decision Sciences 8, 1 (1977), 156–166.
- Glover, F., and Laguna, M. Tabu search. Kluwer, Norwell, MA, 1997.
- Ilić, A., D. Urosević, J. Brimberg, and N. Mladenović. 2010. A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem. European Journal of Operational Research 206, no. 2: 289-300.
- Jacobs, L., and Brusco, M. A local-search heuristic for large set-covering problems. Naval Research Logistics 42, 7 (1995), 1129–1140.
- Lozano, M., Molina, D., and Garcia-Martinez, C. Iterated greedy for the maximum diversity problem. European Journal of Operational Research 214, 1 (2011), 31–38.
- Melo, M. T., Nickel, S., and Saldanha da Gama, F. Facility location and supply chain management - a review. European Journal of Operational Research 196, 2 (2009), 401–412.
- Nickel, S., and Puerto, J. Location Theory: A unified approach. Springer, 2005.
- O'Kelly, M. E. 1987. A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research 32, no. 3: 393-404.
- Peiro, J., Corberan, A., and Marti, R. GRASP for the uncapacitated r-allocation p-hub median problem. Computers & Operations Research 43, 1 (2014), 50–60.
- ReVelle, C., and Eiselt, H. Location analysis: A synthesis and survey. European Journal of Operational Research 165, 1 (2005), 1–19.
- ReVelle, C., Eiselt, H., and Daskin, M. A bibliography for some fundamental problem categories in discrete location science. European Journal of Operational Research 184, 3 (2008), 817–848.
- Ruiz, R., and Stutzle, T. An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research 187, 3 (2008), 1143–1159.
- Yaman, H. Concentrator Location in Telecommunication Networks. PhD thesis, Universit ́e Libre de Bruxelles, Brussels, Belgium, Dec 2002.
- Yaman, H., and Carello, G. Solving the hub location problem with modular link capacities. Computers & Operations Research 32, 12 (2005), 3227–3245.
- Ying, K., and Cheng, H. Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic. Expert Systems with Applications 37, 4 (2010), 2848–2852.