Primal-dual algorithms for the Capacitated Single Allocation p -Hub Location Problem

Abstract

The Hub Location Problems (HLP) have gathered great interest due to the complexity and to the many applications in industry such as aviation, public transportation, telecommunications, among others. The HLP have many variants regarding allocation (single or multiple) and capacity (uncapacitated or capacitated). This paper presents a variant of the HLP, encompassing single allocation with capacity constraints. The Capacitated Single Allocation p-Hub Location Problem (CSApHLP) objective consists on determine the set of $p$ hubs in a network that minimizes the total cost of allocating all the non-hub nodes to the $p$ hubs. In this work, it is proposed a sophisticated RAMP approach (PD-RAMP) to improve the results obtained previously by the simple version (Dual-RAMP). Thus, a parallel implementation is conducted to assess the effectiveness of a parallel RAMP model applied to the CSApHLP. The first algorithm, the sequential PD-RAMP, incorporates Dual-RAMP with a Scatter Search procedure to create a Primal-Dual RAMP approach. The second algorithm, the parallel PD-RAMP, also take advantage of the dual and primal, parallelizing the primal side of the problem and interconnecting both sides as it is expected in the RAMP sequential algorithm. The quality of the results carried out on a standard testbed shows that the PD-RAMP approach managed to improve the state-of-the-art algorithms for the CSApHLP.

Keywords

Parallel algorithm CSApHLP RAMP lagrangean relaxation

ï»¿

1. Introduction

The problem of locating hubs is commonly found in transport and telecommunication networks. This is an NP-hard [1] combinatorial optimization problem that occurs in several practical circumstances, such as in air transport, postal delivery services, emergency response services (e.g. firefighters), in the location of communication antennas, supply of supermarkets, among many others [2, 3, 4, 5]. The decision on the location of hubs and the network nodes that will be allocated to each one of them depends on the number of hubs needed, the demand of each node, the existence or not of capacity of the hubs, as well as other factors to be considered.

Hub Location Problems (HLP) and its variants have received a lot of interest in the last decades, with a great number of algorithmic approaches. Regarding its variants, two possibilities can be derived regarding the allocation: single or multiple allocation. In single allocation, a non-hub node is allocated to exactly one hub and in multiple allocation, the same non-hub node can be allocated to more than one hub. Being the allocation single or multiple, HLP variants can be divided according to the existence of capacity on the hub. Generically, the objective of the HLP is to select the nodes to act as hubs and also to determine how to allocate the non-hub nodes to the hubs so that the total cost of the network is minimized [6].

Many papers in the literature have addressed the HLP and its variants. For the uncapacitated single and multiple allocation $p$ -hub median problems (USApHMP and UMApHMP, respectively), a few articles can be found in the literature. O’kelly [1] presented this problem and produce the first quadratic mathematical formulation. The author also presented two solutions design and described some computational results considering pre-defined open hubs. Ernst and Krishnamoorthy [7, 8] proposed exact and heuristic methods for solving both USApHMP and UMApHMP, and created new datasets for these problems. Klincewicz [9] presented and compared several interchange heuristics. Campbell [10] shoed integer formulations for single and multiple $p$ -hub median problems (uncapacitated versions) and also presented two heuristics designs to tackle these problems. Matos et al. [11] introduced a primal-dual algorithm to solve the UMAHLP reporting state-of-the-art results for standard datasets. Later, the same authors presented another primal-dual algorithm [12], incorporating the lagrangean relaxation technique into the dual side of the problem. They succeeded to improve the results previously reported.

Some approaches in the literature that work with the capacitated version can be found in the work of Perez et al. [13], where he introduces a hybrid GRASP-Path Relinking approach, in which the GRASP procedure is used to construct the population of the Path Relinking [14]. They presented results for standard datasets and solved instances up to 100 nodes with values of $p$ between 2 and 20. Stanimirović [15] produced a Genetic Algorithm with excellent results for small, medium and large instances in the literature.

In this work, we tackle the Capacitated Single Allocation $p$ -Hub Location Problem (CSApHLP), a version of the HLP that considers the fixed cost to open a hub in a specific location. The first paper addressing the CSApHLP is due to Lu and Ting [16]. They produced a Lagrangean Relaxation procedure with subgradient optimization. The technique used consists of dividing the problem formulation into two subproblems, as in Contreras et al. [17], obtaining the $Z$ space variables and the $X$ space variables subproblems. They solved the $Z$ space variables subproblem using the Gurobi solver and the assignment problems of the $X$ space variables subproblem with a simple procedure that finds the shortest path between nodes. The authors presented computational results for the AP dataset and solved instances up to 50 nodes with $p=$ 2, 3, 4, 5. Ting et al. [18] developed a reactive GRASP providing computational results on a standard dataset of instances with up to 50 nodes and for $p=$ 2, 3, 4, 5. More recently, Matos et al. [19] introduced a RAMP approach to the CSApHLP. This approach relies on the interconnection between primal and dual sides of the problem. In the primal side a simple improvement method was used and the lagrangean relaxation procedure explored the dual side of the problem. Matos et al. also introduced the first test results for instances with more than 50 nodes. The proposed algorithm produced results for instances up to 200 nodes (the largest in the literature) with $p=$ 2, 3, 4, 5.

In this paper, we propose sequential and parallel RAMP implementations for solving the CSApHLP. This work is an extension of the one presented in [19] and as it will be shown, both implementations managed to improve the best-known results for this problem.

The remainder of this paper is organized as follows. In Section 2, a mathematical programming formulation is proposed for the CSApHLP. Later, in Section 3, the first heuristic approach and its methodology are described. Then, in Section 4, a parallel RAMP implementation is explained. The results of the computational experiments performed are presented and analyzed in Section 5. The paper closes with some conclusions taken from the work done.

2. Mathematical model

Following the formulation given by Contreras et al. [2] (in which it is considered a fixed set of mandatory open hubs), a possible formulation is given. Let $G=(N,A)$ be a complete graph where $N=\{1,2,\ldots,n\}$ is a set of nodes that represent origins/destinations and can be defined as hubs. Let $w_{ij}$ be the flow between $i$ and $j$ , $O_{i}={\mathop{\sum}\limits_{j\in N}}w_{ij}$ the outgoing flow from node $i{\in}N$ , and $D={\mathop{\sum}\limits_{i\in N}}O_{i}$ the total flow generated in the graph. For each node $i\in N$ , let $b_{i}$ denote the capacity and $f_{i}$ the fixed set-up cost of hub $i$ . The capacity of a hub represents an upper bound on the total incoming flow that can be processed in the hub. Thus, it refers to the sum of the flow generated at the nodes that are assigned to the hub. The distance between nodes $i$ and $j$ is assumed to satisfy the triangle inequality and is denoted by $d_{ij}$ . These distances will be used as a measure of the per-unit flow transportation costs along with the links of the graph. They are weighted by some discount factors, denoted by $\chi$ , $\alpha$ and $\delta$ , to represent the collection, transfer, and distribution costs per unit of flow, respectively. Each node can only be assigned to one hub since the problem defines the allocation as single. The goal is to choose a set of $p$ nodes to define as hubs that minimize the total cost of assigning all the other nodes to the selected $p$ hubs, satisfying the hubs capacity constraints. The total cost of routing the flow along the path $i-j-k-m$ (these are the paths between origin-destination pairs, where $i$ and $j$ represents the origin and destination, respectively, and $k$ and $m$ are the hubs to which $i$ and $j$ are allocated, respectively) is given by:

$\displaystyle F_{\textit{ijkm}}=w_{ij}(\chi d_{ik}+\alpha d_{km}+\delta d_{mj})$ (1)

and for each pair $i$ , $k\in N$ we have the following sets of decision variables (representing the connection between the node and the hub):

$\displaystyle Z_{ik}=\left\{\begin{array}[]{l}1\text{ if node }i\text{ is % connected to hub }k;\\ {0\text{ otherwise}.}\\ \end{array}\right.$ (2)

When $i=k$ , variable $Z_{kk}$ represents the definition (or not) of a hub at node $k$ . The $Z$ variables will be referred to as location/allocation variables. We define an additional set of binary variables that represent the amount of flow through each link of the graph. For each $i,j,k,m\in N$ let the existence of flow be defined by:

$\displaystyle X_{\textit{ijkm}}=\left\{\begin{array}[]{l}1\textit{ if flow % from }i\text{ to }j\text{ goes via hubs }k\\ \text{and }m;\\ {0\text{ otherwise}.}\\ \end{array}\right.$ (3)

The mathematical formulation for CSAHLP is:

$\displaystyle\min{\mathop{\sum}\limits_{k\in N}}f_{k}Z_{kk}+{\mathop{\sum}% \limits_{i\in N}}{\mathop{\sum}\limits_{j\in N}}{\mathop{\sum}\limits_{k\in N}% }{\mathop{\sum}\limits_{m\in N}}$ (4) $\displaystyle F_{\textit{ijkm}}X_{\textit{ijkm}}$ s.t. $\displaystyle{\mathop{\sum}\limits_{k\in N}}{\mathop{\sum}\limits_{m\in N}}X_{% \textit{ijkm}}=1\forall i,j\in N$ (5) $\displaystyle{\mathop{\sum}\limits_{k\in N}}Z_{kk}=p$ (6) $\displaystyle Z_{ik}\leqslant Z_{kk}\forall i,k\in N$ (7) $\displaystyle{\mathop{\sum}\limits_{m\in N}}X_{\textit{ijkm}}=Z_{ik}\forall i,% j,k\in N$ (8) $\displaystyle{\mathop{\sum}\limits_{k\in N}}X_{\textit{ijkm}}=Z_{jm}\forall i,% j,m\in N$ (9) $\displaystyle{\mathop{\sum}\limits_{i\in N}}O_{i}z_{ik}\leqslant b_{k}Z_{kk}% \forall k\in N$ (10) $\displaystyle{\mathop{\sum}\limits_{k\in N}}b_{k}Z_{kk}\geqslant D$ (11) $\displaystyle Z_{ik}\in\{0,1\}\forall i,k\in N$ (12) $\displaystyle X_{\textit{ijkm}}\in\{0,1\}\forall i,j,k,m\in N$ (13)

Equation (5) ensure that a node is assigned to exactly one hub. Equation (6) specifies that exactly $p$ nodes are chosen to act as hubs, whereas Eq. (7) impose that no node is assigned to a node that is not a hub. Equation (8) state that if node $i$ is assigned to hub $k$ then all the flow from node $i$ to any other (fixed) node $j$ must go through some other hub $m$ . Equation (9) have a similar interpretation for the flow arriving to a node $j$ assigned to hub $m$ from some node $i$ . Equation (10) ensure that the overall incoming flow of nodes assigned to a hub does not exceed its capacity. Equation (11) is the aggregated demand constraint. Note that satisfying this constraint is a necessary condition for the feasibility of the location/allocation vectors, which can be derived by adding up all Eq. (10) and considering Eqs (5) and (8). Equation (11) is redundant for the formulation, as mentioned by Contreras et al. [17], but I choose also to include it in the model in order to strengthen the relaxation.

3. RAMP Algorithms for the CSA

{\it p}

HLP

Relaxation Adaptive Memory Programming (RAMP) is a primal-dual metaheuristic framework proposed by Rego [20] in 2005. The term primal refers to the original problem and corresponding solutions space. On the other hand, the term dual refers generically to the dual problem of a mathematical relaxation of the original problem. RAMP approach aims to gather information of the primal-dual relationship of a combinatorial optimization problem, driving the search based on adaptive memory principles, a concept similar to the one used in some research techniques such as Tabu and Path Relinking [21, 22]. In more simple forms (Dual-RAMP), the method explores more intensively the dual side of the problem and in more sophisticated level (the PD-RAMP), the method integrates the Dual-RAMP approach with more advanced strategies to exploit primal-dual relationships more extensively. RAMP algorithm can be seen as an incremental process, starting with simple forms (or levels) of the method, and going to successively more complex forms, adjusting the design of the algorithm according to the analysis of the results of the previous implementation, attempting to achieve the best possible results.

RAMP has proved extremely effective in finding optimal and near-optimal solutions for a variety of combinatorial optimization problems, competing with state-of-the-art algorithmic approaches. In simple forms of the method, this approach successful introduced algorithms to solve some Facility Location Problems [23, 24] or to solve some HLP [11, 19]. In sophisticated forms of the RAMP methodology, we can find some algorithms that manage to introduced excellent computational results [25, 26].

In the next section, we present the sequential PD-RAMP implementation for solving the CSApHLP. The RAMP algorithm starts with a Dual-RAMP (based on the work previously done by Matos et al. [19]) approach that combines a Lagrangean Relaxation [16] with a Subgradient Procedure on the dual side and an Improvement Method on the primal side. Next, a PD-RAMP approach is implemented, that incorporates Dual-RAMP with an evolutionary procedure (Scatter Search) aiming to intensify the search in the primal side. With the useful combination of dual and primal solutions, this approach manages to achieve excellent results for small, medium and large instances, demonstrating the advantages of the RAMP framework.

3.1 Dual method

The algorithm uses Lagrangean Relaxation to explore the dual side of the problem based on the work of Contreras et al. [17] applied to the CSAHLP. The Dual Method explores the dual solutions space by solving the relaxed problem with subgradient optimization. At each iteration, a Projection Method is used to project the dual solution to the primal solutions space, followed by an Improvement Method that tries to improve the projected solution.

If we relax Eqs (8) and (9), we obtain the following optimization problem:

$\displaystyle L(u,v)=\min{\mathop{\sum}\limits_{k\in N}}f_{k}Z_{kk}+{\mathop{% \sum}\limits_{i\in N}}{\mathop{\sum}\limits_{j\in N}}{\mathop{\sum}\limits_{k% \in N}}{\mathop{\sum}\limits_{m\in N}}$ $\displaystyle F_{\textit{ijkm}}X_{\textit{ijkm}}+{\mathop{\sum}\limits_{i\in N% }}{\mathop{\sum}\limits_{j\in N}}{\mathop{\sum}\limits_{k\in N}}u_{\textit{ijk}}$ $\displaystyle\left({\mathop{\sum}\limits_{m\in N}}X_{\textit{ijkm}}-Z_{ik}% \right)+{\mathop{\sum}\limits_{i\in N}}{\mathop{\sum}\limits_{j\in N}}{\mathop% {\sum}\limits_{m\in N}}v_{\textit{ijm}}$ $\displaystyle\left({\mathop{\sum}\limits_{m\in N}}X_{\textit{ijkm}}-Z_{jm}\right)$ (14) s.t. $\displaystyle(5),(6),(7),(8),(11),(12)\text{and}(13)$

The remaining problem can be separated in two subproblems, denoted as $L_{Z}(u,v)$ and $L_{X}(u,v)$ , for $Z$ space variables and for $X$ space variables, respectively.

Decomposing the main problem $L(u,v)$ in respect to the of $Z$ space variables, results in the following subproblem:

$\displaystyle L_{Z}(u,v)=\min{\mathop{\sum}\limits_{k\in N}}f_{k}Z_{kk}-{% \mathop{\sum}\limits_{i\in N}}{\mathop{\sum}\limits_{k\in N}}$ (15) $\displaystyle\left({\mathop{\sum}\limits_{j\in N}}(u_{\textit{ijk}}+v_{\textit% {jik}})\right)Z_{ik}$ $\displaystyle\text{s.t.}{\mathop{\sum}\limits_{k\in N}}Z_{kk}=p$ (16) $\displaystyle Z_{ik}\leqslant Z_{kk}\forall i,k\in N$ (17) $\displaystyle{\mathop{\sum}\limits_{i\in N}}O_{i}z_{ik}\leqslant b_{k}Z_{kk}% \forall k\in N$ (18) $\displaystyle{\mathop{\sum}\limits_{k\in N}}b_{k}Z_{kk}\geqslant D$ (19) $\displaystyle Z_{ik}\in\{0,1\}\forall i,k\in N$ (20)

A set of $p$ hubs to be open $(Z_{kk}=p)$ and the allocation of the remaining nodes to the open hubs $(Z_{ik}=1,i\neq k)$ constitute a solution for $L_{Z}(u,v)$ . As mention by Contreras et al. [17] a feasible solution for this subproblem does not require that nodes be assigned to just one open hub. This means that we can have nodes that are not assigned to any hub, or nodes that are assigned to more than one open hub. If a hub is in $k\in N$ , so that $Z_{kk}=1$ , the remaining nodes that will be assigned to hub $k$ can be identified by solving the following binary knapsack problem:

$\displaystyle KP_{k}=\min{\mathop{\sum}\limits_{i\neq k}}\left({\mathop{\sum}% \limits_{j}}(u_{\textit{ijk}}+v_{\textit{jik}})\right)Z_{ik}$ (21) s.t. $\displaystyle{\mathop{\sum}\limits_{i\neq k}}O_{i}z_{ik}\leqslant(b_{k}-O_{k})% \forall k\in N$ (22) $\displaystyle Z_{ik}\in\{0,1\}\forall i,k\in N,i\neq k$ (23)

Each $KP_{k}$ is a binary knapsack problem that evaluates the maximum profit of opening a hub at node $k$ with respect to the profit coefficients ${\mathop{\sum}\limits_{j}}(u_{\textit{ijk}}+v_{\textit{jik}})$ . Equation (22) represent the capacity of hub $k$ that is available for the rest of the nodes, when it is open.

The optimal set of hubs in $L_{Z}(u,v)$ can be obtained by solving the problem:

$\displaystyle L_{Z}(u,v)=\min{\mathop{\sum}\limits_{k\in N}}$ (24) $\displaystyle\left(f_{k}-{\mathop{\sum}\limits_{j\in N}}(u_{\textit{kjk}}+v_{% \textit{jkk}})-KP_{k}\right)Z_{kk}$ s.t. $\displaystyle{\mathop{\sum}\limits_{k\in N}}b_{k}Z_{kk}\geqslant D$ (25) $\displaystyle Z_{kk}\in\{0,1\}\forall k\in N$ (26)

This means that we can obtain the solution for $L_{Z}(u,v)$ by solving a series of $|N|+1$ knapsack problems. To achieve this, I used the approach of Contreras et al. [17] and the algorithm proposed by Martello et al. [27]. As it requires $p$ hubs to be open as stated by Eq. (16), and Contreras et al. Lagrangean Relaxation does not consider that, we force $L_{Z}(u,v)$ to open the required number of hubs. To select the hubs to be opened the nodes are ordered by decreasing value of the profit given by Eqs (21) to (23).

Decomposing the main problem $L(u,v)$ in respect to the of $X$ space variables, results in the following subproblem:

$\displaystyle L_{X}(u,v)=\min{\mathop{\sum}\limits_{i\in N}}{\mathop{\sum}% \limits_{j\in N}}{\mathop{\sum}\limits_{k\in N}}{\mathop{\sum}\limits_{m\in N}}$ (27) $\displaystyle(F_{\textit{ijkm}}+u_{\textit{ijk}}+v_{\textit{ijm}})X_{\textit{% ijkm}}$ s.t. $\displaystyle{\mathop{\sum}\limits_{k\in N}}{\mathop{\sum}\limits_{m\in N}}X_{% \textit{ijkm}}=1\forall i,j\in N$ (28) $\displaystyle X_{\textit{ijkm}}\in\{0,1\}\forall i,j,k,m\in N$ (29)

$L_{X}(u,v)$ is evidently a semi-assignment problem, hence for each pair $(i,j)$ , it can be decomposed into $(N-1)^{2}$ independent semi-assignment problems of the following form:

$\displaystyle\textit{SAP}_{ij}=\min{\mathop{\sum}\limits_{k\in N}}{\mathop{% \sum}\limits_{m\in N}}$ (30) $\displaystyle(F_{\textit{ijkm}}+u_{\textit{ijk}}+v_{\textit{ijm}})X_{\textit{% ijkm}}$ s.t. $\displaystyle{\mathop{\sum}\limits_{k\in N}}{\mathop{\sum}\limits_{m\in N}}X_{% \textit{ijkm}}=1$ (31) $\displaystyle X_{\textit{ijkm}}\in\{0,1\}\forall k,m\in N$ (32)

For each pair $(i,j)$ , the $\textit{SAP}_{ij}$ can be solved by using the following rule:

$\displaystyle X_{\textit{ijwl}}=1\quad\text{for }$ (33) $\displaystyle F_{\textit{ijwl}}=\min\{F_{\textit{ijkm}}+u_{\textit{ijk}}+v_{% \textit{ijm}}|k,m\in N\}$ $\displaystyle X_{\textit{ijkm}}=0\quad\text{Otherwise}$ (34)

The relaxed problem $L(u,v)$ can be obtained by the sum of the two subproblems, one for each space variables, as already shown:

$\displaystyle L(u,v)=L_{Z}(u,v)+L_{X}(u,v)$ (35)

The lower bound computation, $Z_{D}$ will be:

$\displaystyle Z_{D}=\max_{u,v}L(u,v)$ (36)

We used subgradient optimization to solve the Lagrangean dual problem. At each iteration, we obtain the solution for the relaxed problem $L(u,v)$ , project it to the primal solutions space through a Projection Method followed by an Improvement Method.

The procedure starts with $Z_{D}=0$ (the lower bound), an initial value for $Z_{UB}$ (the upper bound that we will see in the Primal Method) and the Lagrangean multipliers $\lambda_{u,v}=0$ . The agility parameter $\pi$ is initialized with the value 2, it is divided by 2 every 25 consecutive iterations without improving $Z_{D}$ , and it is reset to the original value every 100 iterations to decrease the step size ( $\Delta$ ). The step size ( $\Delta$ ) is calculated as follows:

$\displaystyle\Delta=\frac{\pi(Z_{UB}-L(u,v))}{||\delta||}$ (37)

For a given vector $(u,v)$ , let $z(u,v)$ , and $x(u,v)$ be the optimal solution to $L(u,v)$ . Then, a subgradient $\delta(u,v)$ of $L(u,v)$ , is given by:

$\displaystyle\delta(u,v)=\left(\left({\mathop{\sum}\limits_{m}}X_{\textit{ijkm% }}(u)-Z_{ik}\right)_{i,j,k}\right.,$ (38) $\displaystyle\left.\left({\mathop{\sum}\limits_{m}}X_{\textit{ijkm}}(u)-Z_{jm}% \right)_{i,j,m}\right)$

To determine the set of $\lambda_{u,v}$ multipliers that maximizes the Lagrangean function $L(u,v)$ , the subgradient method needs to generate new sequences of multipliers, one for each iteration of the Lagrangean Relaxation:

$\displaystyle\lambda_{u,v}^{\textit{iter}+1}=\lambda_{u,v}+\Delta\delta(u,v)$ (39)

3.2 Primal method

The Dual-RAMP algorithm starts the primal exploration with an Improvement Method that tries to improve the primal feasible solution provided by the Dual Method. Sometimes a feasible solution is not reached at the end of the dual search, so I use a simple method to ensure feasibility. This method is divided in two stages. In the first stage, the Projection Method tries to open hubs. If it fails to open at least one hub, then it chooses to open the hub with the highest supply (and all the nodes are assigned to it). The second stage assumes that the Projection Method opens at least the required number of $p$ hubs. If not, it opens hubs until the required number of $p$ hubs are met. After that, the solution requires that all nodes be allocated to open hubs without violating their capacity. This is accomplished by the following procedure:

Turn solution feasible Procedure

1.
Let HList be the set of hubs opened by the Projection Method 2.
Let $\textit{DemandList}[h]$ be the set of all nodes allocated to hub $h\in\textit{HList}$ ordered by ascending order of demand
3.
for every $h$ $\in\textit{HList}$ do
4.
while ( ${\it h}_{{\it\textit{supply}}}<0$ )
5.
deallocate tail node $n\in\textit{DemandList}[h]_{\textit{tail}}$
6.
let $\textit{CostList}[n]$ be the set of all nodes ordered by ascending order of cost regarding node n
7.
for every $m\in\textit{CostList}[n]$ do
8.
If $m\in\textit{HList}$ and $m_{\textit{capacity}}\geqslant n_{\textit{demand}}$ then
9.
Include $n$ in $\textit{DemandList}[m]$
10.
end if
11.
end for
12.
if $n$ cannot be allocated to one of HList
13.
set $n\in\textit{HList}$
14.
end if
15.
Update supply and demand for all hubs and nodes
16.
end while
17.
end for

After assuring feasibility, the Dual-RAMP algorithm proceeds with the Improvement Method that considers the shift, swap, and close classic neighborhood structures:

•

Shift (nodes): the shift procedure shifts nodes from one open hub to another, until no more improvement can be made to the objective function. Basically (for every node), the procedure tries to improve the objective function by shifting a node from one open hub to another.

•

Swap (nodes): the swap procedure swaps nodes from open hubs until no more improvement can be made to the objective function. For every node, this procedure analysis the benefit of swapping two nodes assigned to two different hubs and does the swapping if it improves the objective function.

•

Swap (hubs): the swap procedure swaps open hubs until no more improvement can be made to the objective function. For every hub, this procedure analysis the gain of swapping two open hubs and does the swapping (by reassigning all the nodes from one open hub to the other) if it improves the objective function.

•

Close (hubs): The procedure (Turn Solution Feasible) that transforms a projected solution into a feasible one may open more hubs than necessary. As we need to open exactly $p$ hubs, we verify, at each iteration, if the number of hubs differs from $p$ and close a hub when necessary. Closing a hub involves looking for the best gain in closing an open hub (from the set of open hubs) and reassigning all the nodes to the remaining open hubs based on minimum distances.

The improvement method performs the procedures (Shift-nodes, Swap-nodes, Swap-hubs, and Close-hubs), one at a time, until no improvement to the objective function is possible.

The Dual-RAMP algorithm continues alternating between the dual and the primal solutions spaces until one of the four stopping criteria is achieved:

The agility parameter is less than 0.005.

The norm ( $||\delta||$ ) reaches the value 0.

The maximum number of iterations is reached.

The difference between the upper bound ( $Z_{UB}$ ) and lower bound ( $Z_{D}$ ) is less than 1.

As described in the beginning of this section, the RAMP framework can be implemented incrementally, starting with a straightforward Dual-RAMP approach, and progressively evolving into more complex versions.

Although the simplest version of the framework (Dual-RAMP) produced extremely competitive results, it was decided to implement a more sophisticated RAMP algorithm for the solution of the CSA $p$ HLP, to assess if it could produce even better results. This new approach (PD-RAMP) uses the same dualization and Improvement Method as the Dual-RAMP algorithm.

In PD-RAMP (Primal-Dual RAMP), advanced strategies are integrated, allowing a wider search of the primal solutions space. Primal and dual solutions are evolutionarily, using a common reference set that is updated by both primal and dual solutions until no more combined (new) solutions can incorporate the reference set.

The RAMP framework relies on the fact that it can incorporate different methods, as components, for building more advanced search strategies. In his paper, Rego [20] presents the general PD-RAMP framework, suggesting Scatter Search (SS) as a possible example for the main component of the primal search, among other approaches. I chose Scatter Search as the evolutionary approach for the basis of the PD-RAMP Primal Method. The applied SS is based on the procedure proposed by Laguna e Martí [28]. The Primal-Dual approach uses information provided by the dual method to generate an initial population of solutions to be used by the SS procedure. This SS procedure is divided into the following methods:

Scatter Search Procedure

Initial Phase 2.

Generate initial population (Reference Set)

Apply improvement method

Apply Reference Set update method

Scatter Search Phase

while (new solutions are generated in Reference Set)

Apply subset generation method

Apply solutions combination method

Apply improvement method

10.

Apply Reference Set update method

11.

end while

Figure 1.

PD-RAMP algorithm overview.

The PD-RAMP algorithm starts by populating the pool of solutions with solutions obtained by solving the relaxed problem. The dual solutions are subjected to a Projection Method, that projects them to the primal solutions space, where they are improved using an Improvement Method. Next, the solutions are submitted to a Reference Set Update Method that analyzes (according to the quality or diversification criteria) if they can be included in the Reference Set. Then, the Subset Generation Method creates three sets of solutions (coming from the Reference Set) to be combined by the Combination Method. The objective is to generate new solutions, aiming to explore new regions of the solutions space that traditionally are not explored. An Improvement Method improves the solution provided by the Combination Method and the improved solution is included in the Solutions Pool.

Figure 1 illustrates the general PD-RAMP model for solving the CSA $p$ HLP.

Specifically, each component of the SS works in the following way. The Solutions Pool is composed of improved solutions coming from the Projection Method. These diversified solutions are ordered according to quality (increasing order of the objective function value). Every solution has an id that identifies the iteration that produced that solution.

The Reference Set (RefSet) is composed by $S$ solutions and is divided into three subsets ( $S_{1},S_{2},S_{3}\in S$ ). The Reference Set Update Method populates these subsets as follows. The first subset, $S_{1}$ , has a maximum of two solutions that are considered the best ones (the elite solutions) in terms of the objective function value. The second subset, $S_{2}$ , contains elite and diversified solutions, up to a maximum of three. The remaining solutions (up to five) are in $S_{3}$ and are classified as diversified and the worst in terms of quality.

The Subset Generation Method operates on the reference set to produce subsets of solutions that will serve as the basis for the Combination Method. The typical implementation of this method is to generate all possible pairs of solutions that contain at least one new solution in all the reference set, although the generation of larger subsets can be considered. A solution is considered new if it has not yet been subjected to the Combination Method. In the proposed algorithm, the subset randomly chooses (between zero and the algorithm’s iteration) a maximum of five solutions from the Reference Set.

The Combination Method combines solutions, two by two, based on a threshold given by the objective function value of each solution. When it finds the same open hubs in both solutions, and one of the solutions have a threshold value higher than a predefined one, then that hub will be opened in the new combined solution. This is based on the idea that choosing open hubs that belong to better solutions (in terms of the objective function value) is more likely to generate elite solutions.

An Improvement Method (the same used by Dual-RAMP) tries to improve each solution produced by the Combination Method and includes the resulting solution in the Solutions Pool.

The Reference Set Update Method is called again to replace old solutions with new improved solutions and populate the Reference Set as previously explained.

The PD-RAMP algorithm alternates between the dual and primal methods until they fail to improve the best solution found. In addition to the stopping criteria of Dual-RAMP, PD-RAMP stops whenever no new solutions are included in the Reference Set.

The next section presents a design and analysis of a parallel algorithm for the CSApHLP. It is worth mentioning that the primal-dual scheme such as the RAMP framework is a flexible approach for applying the paradigm of parallelization. The motivation for its use is that few approaches exist in the literature that explores primal-dual parallel algorithms. It will be shown that a parallel implementation not only was used to reduce computational times but also to achieve an even better solution than the ones obtained in a sequential manner.

4. Parallel RAMP approach for the CSApHLP

Parallel metaheuristics arise in operation research as a way of obtaining short computational times, and at the same time, searching for solutions in regions that have not yet been searched, in the hope of being able to find even better solutions [29, 30, 31]. The main idea of the parallel scheme is to use several processes to execute some part of the problem concurrently, making this scheme attractive when solving complex problems. Regarding the HLP and its variants, some few algorithms in the literature take advantage of a parallel approach. Carvalho et al. [32] present a parallel heuristic for the single allocation hub location problem. Their approach introduces a cooperative design with the combination of multiple parallel iterated local search procedures together with Path-Relinking. The algorithm manages to tackle instances up to 3038 nodes. Benaini et al. [33] proposed a parallel Genetic Algorithm implemented on GPU using CUDA framework. They present computational results on randomly generated instances up to 6000 nodes. Matos et al. [25] proposed the first parallel RAMP model for the Capacitated Facility Location Problem (CFLP). In this parallel implementation of a RAMP algorithm for the CFLP, the parallel part of the algorithm took place in the primal method allowing a large decrease in computational time.

Primal-dual algorithms and evolutionary orpopulation-based algorithms (e.g., Genetic Algorithms, Scatter Search, Particle Swarm Optimization, etc.), in addition to being able to face complex problems, have the necessary characteristics for the use of parallel processing, due to the natural parallelism of several phases that involves these evolutionary algorithms’ strategy. Combining their evolutionary schemes with the power of parallel processing, these parallel algorithms seek to obtain greater efficiency in their executions, when compared to the sequential ones.

As already seen in Section 3, RAMP framework takes advantage of the exploration of the primal and dual side of the problem. This primal-dual metaheuristic-based framework is very suitable to use parallel processing in one or both phases (sides). Due to its flexibility, the RAMP framework suggests that a parallel implementation of the algorithm will produce excellent results improving the ones obtained in a sequential faction. Whether it is a simple version or the most complex (Dual-RAMP or a PD-RAMP, respectively), the number of different components of the algorithm can be decomposed and explored with the use of parallelization [25].

The first parallel approach using RAMP framework was introduced by Matos et al. [25] and applied to the CFLP. The sequential algorithm produced excellent results but for large instances, the projection method (method responsible to transform a dual solution into the primal solution space) and the improvement method showed a lot of computational effort to achieve a primal solution, due to the successive calls to the transportation problem. So, was natural to choose the primal side to employ parallelism. So, the improvement method was parallelized, taking advantage of the processing power to reduce the time needed to project dual solutions into the primal solution space and the following method improvement method. It was decided, in a first phase, to apply to the CSApHLP, the same parallel approach applied to the CFLP and analyze the effect on the results.

The parallel approach for the CSApHLP starts with the obtention of an upper bound to start the Lagrangean relaxation with a single thread. Then the projection method projects the dual solution into the primal solution space and then all the threads begin the Improvement Method. The Projection Method and the Improvement Method were already described in the previous section. A solutions pool is responsible for storing primal solutions. During the running process of the algorithm, the thread responsible for the Dual Method will generate primal solutions that will be inserted into this solutions pool, after being subjected to the Projection Method. If a solution already exists in the solution pool, it is discarded, since it has already been visited, i.e., an improvement method has already been triggered for this solution. The algorithm continues in one single thread through the SS procedure with the methods refset update, subset generation and combination, while the other threads are responsible for improving the solutions.

As the dual-phase and subsequent projection method are very fast, it will generate primal solutions to a new pool of pending solutions. These primal solutions and solutions coming from the combination method will populate this new pool of pending solutions. Next, the improvement method will process in parallel solutions from this pending pool of solutions. The number of solutions in the pending solutions pool is limited to 25 and if no solutions are found in this pool, all threads wait for a solution to emerge in this pool. In all our computational tests and tuning, we do not encounter a situation where the pending solutions pool stayed empty. As mentioned, the dual method is a fast procedure and although only one thread handles its execution, many solutions are always generated into this pool of pending solutions. The next figure (Fig. 2) illustrates a general overview of the parallel RAMP approach for the CSApHLP.

Figure 2.

Parallel PD-RAMP algorithm overview.

It is important to emphasize that a lock in the parallel processing is made whenever an improved solution or primal solution is taken from the projection method, improving the best-known solution found so far, in respect of the objective value. So, the process stops momentarily, and the dual method is updated, by obtaining a new upper bound and the recalculation of the associated Lagrangean multipliers. The algorithm continues, by producing primal feasible solutions (through the dual phase) and combined solutions (in primal phase) to populate the pending solutions pool. Threads execute concurrently the Improvement Method, improving these solutions and updating the dual method with new data if a better solution is found. The stopping criteria are the same as the sequential implementation.

5. Computational results

In this section, we describe the application of the algorithm, the data sets that were used and the results obtained in a series of experimentations.

Both algorithms (sequential and parallel) were coded in C programming language and run on an Intel Pentium I7 2.40 GHz (for sequential execution, only one processor was used and for the parallel version of the algorithm 6 threads were used) with 8 GB RAM under Ubuntu operating system.

We have run our algorithm on standard AP (Australia Post) instances that result from the mail flows in an Australian city and contain up to 200 nodes. These instances are available at Beasley’s OR-Library [34] and were introduced by Ernst and Krishnamoorthy [35]. The flow is asymmetric ( $W_{ij}\neq W_{ji}$ ) and the ratios are defined as $\chi=3,\alpha=0.75$ and $\delta=2$ . The dataset has 56 instances grouped by size (small, medium, and large) and with two different types of hubs setup costs and capacities. We have tight (T) setup costs, when the cost increases with the amount of flow generated in the node, and loose (L) setup costs, when the instances do not have this characteristic (the tight setup costs are supposed to be more difficult to solve). As for hubs capacities, we have a similar representation, depending on how tightly (T) or loosely (L) constrained the instances are. Each group consists of four instances that correspond to all four possible combinations of setup costs and capacities (LL, LT, TL or TT). The fixed number of open hubs, $p$ , varies from 2 to 5 and for some instances we have $p>2$ . More detailed information about the instances can be found in Ernst and Krishnamoorthy [35] or Contreras et al. [17].

Table 1
LL small instances results

Nodes	$p$	$Z^{*}$	RG		LR		Dual-RAMP		PD-RAMP
			GAP	CPU	GAP	CPU	GAP	CPU	GAP	CPU
10	2	230008.5	0.00	0.2	0.00	25.28	0.00	0.01	0.00	0.01
	3	224250.1	0.00	0.1	0.00	2.32	0.00	0.01	0.00	0.01
	4	229172.6	0.00	0.1	0.00	2.31	0.00	0.01	0.00	0.01
	5	239292.3	0.00	0.1	0.00	1.28	0.00	0.01	0.00	0.01
20	2	234691.0	0.00	0.4	0.00	79.23	0.00	0.09	0.00	0.08
	3	239444.2	0.00	0.2	0.00	35.54	0.00	0.16	0.00	0.15
	4	251939.7	0.00	0.3	0.00	38.8	0.00	0.29	0.00	0.28
	5	266745.2	0.00	0.3	0.00	15.18	0.00	0.14	0.00	0.17
25	2	238978.0	0.00	0.6	0.00	190.4	0.00	0.37	0.00	0.47
	3	242437.2	0.00	0.4	0.20	132.3	0.00	1.20	0.00	1.31
	4	252716.6	0.00	0.5	0.00	64.91	0.00	1.16	0.00	1.33
	5	263518.3	0.00	0.6	0.00	74.68	0.00	0.81	0.00	1.00
40	2	241955.71 ${}^{\text{a}}$	0.00	0.6	0.00	18.97	0.00	7.51	0.00	1.29
	3	–	–	–	–	–	–	6.26	0.00	1.39
	4	–	–	–	–	–	–	8.33	0.00	1.44
	5	–	–	–	–	–	–	6.32	0.00	6.45
50	2	238520.59	0.00	0.8	0.00	564.4	0.00	16.90	0.00	19.70
	3	–	–	–	–	–	–	18.20	0.00	21.35
	4	–	–	–	–	–	–	18.50	0.00	22.16
	5	–	–	–	–	–	–	17.30	0.00	23.74
Average 1			0.00	0.35	0.02	88.97	0.00	2.05	0.00	1.84
Average 2			–	–	–	–	–	5.18	0.00	5.12

The proposed RAMP algorithms were compared with the state-of-the-art approaches for the CSA $p$ HLP: a Reactive GRASP (RG) [18] and a Lagrangean Relaxation approach (LR) [16]. The Dual-RAMP algorithm [19] was compared with all approaches while PD-RAMP was compared directly with Dual-RAMP. All tables show the average percent deviation from the optimal/best-known solutions (GAP) and the associated computational time (CPU) in seconds. I used the optimal/best-known solutions reported by Lu et al. [18] (the authors used the GUROBI solver when possible and for the best-known solutions – marked with “ ${}^{\text{a}}$ ” in the tables – they used the values provided by Ernst and Krishnamoorthy [35]).

The first four tables (Tables 1 to 4) summarize the results for all small AP data instances grouped by type (LL, LT, TL or TT) and size (from 10 to 50 nodes). The “Gap” column was computed as $(UB-Z^{*})/UB*100$ ( $Z^{*}$ is the optimal/best-known solution) and the “CPU” column shows the computational time (in seconds) needed to achieve the $U B$ . PD-RAMP’s “Gap” and “CPU” results are calculated the same way, except when no $Z^{*}$ value is provided, in which case “GAP” was computed considering the “ $U B$ ” value obtained by Dual-RAMP (in these cases the symbol “–” was inserted for Dual-RAMP and only reported the “Gap” value for PD-RAMP). Columns “Nodes” and “ $p$ ” indicate the instances size and number of fixed hubs ( $p$ has a range from 2 to 5). LT and TT instances with $\textit{nodes}>=25$ and $p=2$ cannot be solve, since the demand is higher than the capacity of the required number of hubs. The RG and the LR algorithms do not provide results for all the small AP data set (“–” means that no solution is available), nevertheless, I report results for both RAMP versions. “Average 1” specifies the average results for the instances tested by all the algorithms and “Average 2” considers all instances results for both RAMP approaches.

Table 2

LT small instances results

Nodes	$p$	$Z^{*}$	RG		LR		Dual-RAMP		PD-RAMP
			GAP	CPU	GAP	CPU	GAP	CPU	GAP	CPU
10	2	256048.6	0.00	0.00	0.00	46.87	0.00	0.01	0.00	0.01
	3	252973.6	0.00	0.00	0.00	137.65	0.00	0.02	0.00	0.02
	4	250992.3	0.00	0.00	0.00	22.91	0.00	0.01	0.00	0.01
	5	261451.2	0.00	0.03	0.00	38.59	0.00	0.02	0.00	0.02
20	2	253517.4	0.00	0.05	2.99	316.97	0.00	0.42	0.00	0.55
	3	257247.7	0.00	0.24	0.14	18.39	0.00	0.57	0.00	0.62
	4	260678.9	0.00	0.20	0.00	280.05	0.00	0.29	0.00	0.36
	5	274975.4	0.00	0.21	0.00	217.75	0.00	0.46	0.00	0.59
25	3	276372.5	0.00	0.44	0.00	1494.3	0.00	1.02	0.00	1.26
	4	278235.0	0.00	0.42	0.00	1862.9	0.00	1.18	0.00	1.08
	5	284952.6	0.00	0.43	0.00	377.67	0.00	1.28	0.00	1.36
40	3	272218.32 ${}^{\text{a}}$	0.00	1.19	5.36	289.24	0.00	7.25	0.00	8.38
	4	–	–	–	–	–	–	7.72	0.00	9.02
	5	–	–	–	–	–	–	7.82	0.00	9.97
50	3	–	–	–	–	–	–	17.36	0.00	19.27
	4	272897.49	0.91	2.01	6.3	49.98	0.00	17.87	0.00	21.65
	5	–	–	–	–	–	–	19.05	0.00	23.06
Average 1			0.07	0.40	1.14	396.41	0.00	2.34	0.00	2.76
Average 2			–	–	–	–	–	4.84	0.00	5.72

Table 3

TL small instances results

Nodes	$p$	$Z^{*}$	RG		LR		Dual-RAMP		PD-RAMP
			GAP	CPU	GAP	CPU	GAP	CPU	GAP	CPU
10	2	264544.0	0.00	0.2	0.00	12.59	0.00	0.01	0.00	0.01
	3	263399.9	0.00	0.2	0.00	2.44	0.00	0.01	0.00	0.01
	4	269074.3	0.00	0	0.00	0.72	0.00	0.01	0.00	0.01
	5	281327.3	0.00	0.1	0.00	0.3	0.00	0.01	0.00	0.01
20	2	271128.2	0.00	0.7	0.00	54.09	0.00	0.15	0.00	0.13
	3	281304.8	0.00	0.3	0.4	29.51	0.00	0.17	0.00	0.23
	4	295223.9	0.00	0.3	0.00	22.98	0.00	0.40	0.00	0.42
	5	310122.8	0.00	0.4	0.00	3.5	0.00	0.17	0.00	0.30
25	2	310317.6	0.00	0.5	0.00	113.4	0.00	0.38	0.00	0.41
	3	328092.6	0.00	0.3	0.00	90.56	0.00	1.25	0.00	1.26
	4	347416.8	0.00	0.5	0.00	74.59	0.00	1.35	0.00	1.34
	5	368288.6	0.00	0.5	0.1	31.63	0.00	0.45	0.00	0.63
40	2	298919.01 ${}^{\text{a}}$	0.00	0.6	0.00	231.1	0.00	7.20	0.00	8.60
	3	–	–	–	–	–	–	3.96	0.00	7.78
	4	–	–	–	–	–	–	4.92	0.00	6.61
	5	–	–	–	–	–	–	5.81	0.00	9.05
50	2	319015.77	0.00	1.3	0.00	381.8	0.00	17.40	0.00	19.55
	3	–	–	–	–	–	–	13.40	0.00	19.66
	4	–	–	–	–	–	–	9.62	0.00	18.26
	5	–	–	–	–	–	–	17.80	0.00	21.50
Average 1			0.00	0.42	0.04	74.95	0.00	2.07	0.00	2.35
Average 2			–	–	–	–	–	4.22	0.00	5.79

Table 4

TT small instances results

Nodes	$p$	$Z^{*}$	RG		LR		Dual-RAMP		PD-RAMP
			GAP	CPU	GAP	CPU	GAP	CPU	GAP	CPU
10	2	264544.0	0.00	0.01	0.00	2.22	0.00	0.01	0.00	0.01
	3	263399.9	0.00	0.03	0.00	2.25	0.00	0.01	0.00	0.01
	4	269074.3	0.00	0.00	0.00	0.48	0.00	0.01	0.00	0.01
	5	281327.3	0.00	0.07	0.00	0.28	0.00	0.01	0.00	0.01
20	2	329068.6	0.00	0.01	9.8	54.97	0.00	0.53	0.00	0.56
	3	296035.4	0.00	0.25	0.00	70.67	0.00	0.17	0.00	0.21
	4	306296.3	0.00	0.28	0.00	9.25	0.00	0.12	0.00	0.10
	5	325568.5	0.00	0.32	0.58	10.97	0.00	0.11	0.00	0.11
25	3	348369.1	0.00	0.33	0.00	99.59	0.00	1.18	0.00	1.29
	4	369576.8	0.00	0.47	0.00	67.05	0.00	1.21	0.00	1.39
	5	391996.5	0.00	0.47	0.00	38.47	0.00	1.25	0.00	1.44
40	3	354874.10 ${}^{\text{a}}$	1.15	1.16	4.66	190.96	0.80	7.25	0.00	8.02
	4	–	–	–	–	–	–	7.34	0.00	8.85
	5	–	–	–	–	–	–	7.48	0.00	9.00
50	3	–	–	–	–	–	–	17.18	$-$ 1.22	18.74
	4	417440.99	0.86	2.45	10.1	28.55	0.40	18.30	0.08	19.82
	5	–	–	–	–	–	–	18.47	$-$ 2.22	21.61
Average 1			0.15	0.45	1.93	44.29	0.10	2.32	0.01	2.54
Average 2			–	–	–	–	–	4.74	$-$ 0.20	5.36

Both RAMP approaches managed to achieve excellent quality results for all small instances, clearly outperforming the other two algorithms. PD-RAMP produced a 0.01% average deviation from the optimal/best-Known solutions in reduced computational times. Dual-RAMP achieved all optimal solutions, except for instances 40TT ( $p=3$ ) and 50TT ( $p=4$ ), providing a “Gap” of 0.84% and 0.44%, respectively. PD-RAMP was able to achieve better results than Dual-RAMP, only failing optimality for one instance, the 50TT ( $p=4$ ), and significantly improving the corresponding Dual-RAMP result.

The next four tables (Tables 5 to 8) show the results for the medium instances (from 60 to 100 nodes) for which no solution is available in the literature. As far as I know, these are the first results reported for these CSA $p$ HLP instances. The LT and TT instances with $p=2$ cannot be solved, due to insufficient hubs capacity to fulfil all nodes demand. In these tables, we can see a direct comparison between Dual-RAMP and PD-RAMP. The “ $U B$ ” column displays the best upper bound achieved by Dual-RAMP and the “Gap” column was computed as ( $UB-Z^{*})/UB*100$ , where $Z^{*}$ corresponds to the “ $U B$ ” value provided by Dual-RAMP.

Table 5

LL medium instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
60	2	225917.16	34.12	0.00	39.25
	3	230862.05	35.53	0.00	42.97
	4	237439.83	35.84	0.00	44.19
	5	245404.58	36.09	0.00	44.55
70	2	236900.33	61.95	$-$ 0.04	70.59
	3	238666.31	63.16	0.00	77.94
	4	245426.59	64.93	$-$ 0.72	82.91
	5	255221.64	65.07	0.00	87.19
75	2	239130.75	81.50	$-$ 0.46	93.36
	3	245441.67	79.90	$-$ 0.37	99.62
	4	253886.67	84.33	0.00	110.77
	5	269010.34	87.12	$-$ 1.5	120,00
90	2	224195.69	90.04	0.00	196.07
	3	228453.02	87.18	0.00	212.60
	4	240898.81	83.50	$-$ 1.18	226.67
	5	250477.88	91.20	0.00	230.22
100	2	250508.59	83.50	0.00	103.30
	3	246713.95	90.20	0.00	114,11
	4	255507.17	86.50	0.00	125,22
	5	271650.28	97.17	$-$ 1.33	133,87
Average			90.62	$-$ 0.29	112.77

Table 6

LT medium instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
60	3	269921.0	34.74	0.33	40.14
	4	257854.6	36.12	$-$ 1.46	44.52
	5	263252.9	38.07	$-$ 0.15	46.94
70	3	257763.6	61.5	0.00	68.86
	4	258028.3	63.25	$-$ 0.39	79.17
	5	263814.9	65.13	$-$ 0.18	83.41
75	3	256188.1	81.31	0.00	91.30
	4	259940.9	85.3	0.00	99.60
	5	273778.8	88.42	0.27	108.66
90	3	249050.7	160.8	0.12	203.17
	4	249609.9	166.4	0.16	220.70
	5	261319.4	169	$-$ 0.24	221.76
100	3	269819.0	96.69	$-$ 3.86	102.97
	4	270439.6	96.26	$-$ 1.81	111.98
	5	278304.3	100.5	$-$ 0.57	125.44
Average			89.56	$-$ 0.52	109.91

Table 7

TL medium instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
60	2	252496.7	35.03	0.00	39.75
	3	263732.0	35.16	0.00	40.09
	4	281642.9	34.6	0.00	41.45
	5	302844.4	34.9	0.00	42.04
70	2	271283.8	61.11	0.00	71.26
	3	283507.3	61.51	0.00	76.01
	4	303373.2	63.08	0.00	79.88
	5	326569.3	65.02	0.00	81.30
75	2	303363.50	73.52	0.00	91.98
	3	306864.30	82.47	$-$ 0.42	93.29
	4	325114.40	84.67	$-$ 0.14	100.63
	5	344063.10	83.72	0.00	106.04
90	2	298956.20	86.50	0.01	188.31
	3	281919.20	84.36	$-$ 0.03	203.98
	4	286717.60	82.50	0.00	208.97
	5	309330.50	88.40	0.00	213.46
100	2	385234.80	91.10	$-$ 5.90	104.22
	3	365648.66	86.20	0.60	113.20
	4	389885.91	81.20	$-$ 2.05	129.76
	5	410317.28	90.52	$-$ 0.04	133.94
Average			70.28	$-$ 0.40	107.98

Table 8

TT medium instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
60	3	351669	34.43	$-$ 0.03	39.15
	4	359255.7	34.69	0.06	41.81
	5	373591.4	34.99	0.01	42.40
70	3	457218.5	62.08	0.08	67.11
	4	387397.9	64.77	0.00	74.84
	5	408468.3	65.54	$-$ 0.39	78.76
75	3	372936.1	81.24	0.00	89.32
	4	347371.5	84.88	$-$ 0.05	94.15
	5	363528.7	86.75	$-$ 0.02	102.31
90	3	396614.3	162.8	$-$ 0.16	184.19
	4	349092.1	166.4	$-$ 3.20	208.12
	5	357883.9	170.2	$-$ 1.70	217.81
100	3	576133.3	94.93	$-$ 7.05	103.54
	4	491686.4	99.42	$-$ 2.40	111.53
	5	488904.6	104.1	3.22	123.05
Average			76.37	$-$ 0.78	105.21

The PD-RAMP algorithm managed to find better solutions than Dual-RAMP with a slightly higher computational effort (as expected) due to the intensification of the primal side exploration. Nevertheless, the increase in solutions quality clearly compensates for the higher computational times.

Tables 9 to 12 summarize the results for the largest instances (from 125 to 200 nodes) for which, as far as I know, there are no solutions available in the literature.

Table 9

LL large instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
125	2	243092.5	259.93	$-$ 0.27	270.16
	3	240667.7	255.01	$-$ 0.32	290.52
	4	250668.3	258.07	$-$ 2.19	313.79
	5	264679.1	262.53	$-$ 3.47	332.16
150	2	234765.4	469.05	0.00	486.16
	3	238348.8	477.72	$-$ 0.29	550.29
	4	244912.6	483.46	$-$ 0.19	596.85
	5	258623.2	493.84	$-$ 1.33	650.66
175	2	230477.10	885.90	$-$ 0.44	1017.01
	3	229743.70	899.59	$-$ 1.07	912.97
	4	239710.90	906.06	$-$ 0.74	1043.93
	5	252320.40	916.23	0.00	1096.70
200	2	249971.02	1149.26	$-$ 4.34	1220.94
	3	231069.52	1170.69	0.00	1302.51
	4	236508.92	1185.55	$-$ 0.61	1341.37
	5	249619.03	1191.76	$-$ 0.33	1454.80
Average			704.04	$-$ 0.97	805.05

Table 10

LT large instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
125	3	270569.7	251.76	0.13	271.09
	4	261564.5	257.92	$-$ 4.09	295.61
	5	257604.6	265.17	$-$ 0.02	302.73
150	3	293488.5	469.52	$-$ 4.04	500.27
	4	252894.3	478.72	$-$ 0.40	521.29
	5	260356.8	494.02	$-$ 1.32	561.96
175	3	261998.7	880.29	0.00	875.85
	4	256940.3	906.39	$-$ 1.99	956.27
	5	263236.8	919.34	$-$ 0.93	1049.41
200	3	292306.9	1163.4	$-$ 5.35	1185.94
	4	277819.9	1173.5	$-$ 2.95	1323.78
	5	283591.1	1209.7	$-$ 0.89	1393.36
Average			705.81	$-$ 1.82	769.80

Table 11

TL large instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
125	2	264860.9	252.08	$-$ 7.45	263.52
	3	265706	254.11	$-$ 1.81	280.43
	4	280483.8	258.84	0.00	295.59
	5	313370.8	262.36	$-$ 3.05	306.81
150	2	279501.9	469.06	$-$ 3.53	499.52
	3	263356.2	476.72	0.00	532.79
	4	277607.2	480.93	$-$ 1.37	569.20
	5	297615.9	487.43	$-$ 2.90	602.54
175	2	246381.63	881.91	0.00	905.77
	3	255948.78	889.43	$-$ 0.66	968.92
	4	270384.16	900.02	$-$ 1.82	1062.50
	5	288107.16	917.62	$-$ 2.25	1129.04
200	2	290393.53	1155.55	$-$ 2.69	1202.00
	3	288963.38	1175.50	$-$ 5.68	1251.73
	4	296948.19	1137.30	$-$ 3.03	1380.06
	5	298996.53	1173.99	$-$ 0.48	1455.20
Average			698.30	$-$ 2.29	794.10

Table 12

TT large instances results

Nodes	$p$	Dual-RAMP		PD-RAMP
		UB	CPU	GAP	CPU
125	3	353995.8	251.19	$-$ 11.06	264.07
	4	326708.6	258.51	$-$ 11.17	288.93
	5	329872.1	261.5	$-$ 5.11	306.32
150	3	339679.9	473.88	$-$ 0.02	499.50
	4	328340.9	484.97	1.38	530.81
	5	378218.8	492.4	$-$ 10.43	580.13
175	3	339850.4	895.99	$-$ 6.87	933.67
	4	337573	889.42	$-$ 5.63	985.66
	5	335327.2	909.64	$-$ 0.93	1062.69
200	3	514873.6	1158.2	$-$ 0.54	1162.09
	4	334586.9	1179.4	$-$ 13.16	1325.22
	5	328327.2	1195.4	$-$ 10.44	1410.41
Average			704.21	$-$ 6.16	779.12

For the largest instances in the literature, PD-RAMP produced better results than Dual-RAMP in almost every instance (and for all combinations of size and type). The intensive exploration of the primal side with the use of Scatter Search, led to an average increase in the computational effort of 10%, which is perfectly acceptable considering the gains in quality. In conclusion, the significant improvement in solutions quality with reduced computational times renders PD-RAMP the best RAMP approach.

Tables 13 to 18 show the results for the CSA $p$ HLP in which no fixed costs are considered (in the literature, this problem is usually refered as CSA $p$ HMP – “M” stands for “Median”). I decided to test the PD-RAMP algorithm on this problem, but it is important to notice that the CSA $p$ HMP is a different problem, since the sum ${\mathop{\sum}\limits_{k\in N}}f_{k}Z_{kk}$ is removed from the objective function formulation. The aim of the present study was addressing the CSA $p$ HLP, nevertheless, I wanted to see how PD-RAMP would perform against other approaches specially designed for the CSA $p$ HMP.

Only the PD-RAMP was compared with a Genetic Algorithm proposed by Stanimirović (GA) [15] since the hybrid GRASP-Path Relinking algorithm proposed by Perez et al. [13] assumes different parameters for the discount factor, that are not provided by the author, and thus it cannot be compared in terms of the objective function value. It was used the same instances previously described for the CSA $p$ HLP with the slight difference that it is not necessary to address TL and TT instances, since they are the same as LL and LT (when the fixed costs associated with the hubs are ignored), respectively. In addition, new fixed number of hubs ( $p\in\{10,15,20\}$ ) were used for some instance sizes, to allow a direct comparison with the GA algorithm. GA reports an average “Gap” value obtained after 20 runs on each instance. The proposed algorithm obtained the reported solutions with only a single run.

Tables 13 and 14 show the results for the small instances (from 10 to 50 nodes).

Table 13

LL small instances results for the CSA $p$ HMP

Nodes	$p$	GA		PD-RAMP
		GAP	CPU	GAP	CPU
10	2	0.00	0.37	0.00	0.01
	3	0.00	0.50	0.00	0.06
	4	0.00	0.52	0.00	0.02
	5	0.00	0.64	0.00	0.01
20	2	–	–	0.00	0.11
	3	0.00	0.99	0.00	0.20
	4	0.00	1.08	0.00	0.42
	5	0.00	1.49	0.00	0.66
25	2	0.01	1.93	0.00	0.26
	3	0.00	0.84	0.00	0.81
	4	0.00	1.32	0.00	0.43
	5	0.14	1.56	0.00	1.43
	10	0.01	1.98	0.00	1.37
40	2	0.00	2.64	0.00	2.03
	3	0.00	1.50	0.00	8.32
	4	0.00	2.48	0.12	9.05
	5	0.00	3.22	0.00	9.35
	10	0.01	3.74	0.00	10.09
50	2	0.05	5.40	0.00	9.56
	3	0.00	2.28	0.00	19.24
	4	0.00	3.64	0.00	21.43
	5	0.00	4.22	0.00	23.64
	10	0.05	5.11	0.00	23.37
Average		0.02	2.35	0.005	7.23

Table 14

LT small instances results for the CSA $p$ HMP

Nodes	$p$	GA		PD-RAMP
		GAP	CPU	GAP	CPU
10	2	0.00	0.36	0.00	0.01
	3	0.00	0.49	0.00	0.02
	4	0.00	0.51	0.00	0.01
	5	0.00	0.67	0.00	0.02
20	2	0.00	0.00	0.00	0.59
	3	0.50	0.98	0.00	0.63
	4	0.00	1.03	0.00	0.17
	5	0.00	1.26	0.00	0.12
25	2	0.00	1.70	0.00	0.20
	3	0.52	1.14	0.00	1.26
	4	0.22	1.39	0.17	1.35
	5	0.39	1.99	0.00	0.22
	10	0.00	2.24	0.00	1.43
40	2	5.38	1.95	0.00	7.98
	3	0.00	2.85	0.00	8.74
	4	0.11	3.29	0.00	9.38
	5	0.07	5.45	0.00	10.12
	10	1.13	3.11	0.00	18.89
50	2	0.65	5.13	0.00	20.75
	3	0.08	5.17	0.00	22.84
	4	0.35	8.17	0.00	29.42
	5	0.00	0.36	0.00	0.01
	10	0.00	0.49	0.00	0.02
Average		0.45	2.32	0.008	6.38

For the small instances, PD-RAMP achieved almost every optimal solution with a single run, obtaining average “Gap” values of 0.005% and 0.008% for the LL and LT instances, respectively. PD-RAMP only failed to find the optimal solution for instances 25LT ( $p=4$ ) and 40LL ( $p=4$ ) obtaining a deviation from the optimal solution of 0.12% and 0.17%, respectively. In terms of computational time, no direct comparison can be made due to the use of different machines, but nonetheless, the PD-RAMP algorithm takes slightly longer to return the solutions. If we consider the best upper bound found within the 20 runs for each instance, GA achieved every optimal solution, except for 20LT ( $p=2$ ), for which GA could not produce any solutions. Nevertheless, PD-RAMP outperformed the GA approach, considering that it only took a single run to produce these high-quality results.

The next two tables (Tables 15 and 16) show the results for the medium instances (from 60 to 100 nodes). GA only provides results for the 100 nodes instances and for the LT instances it does not report results for $p=3$ . The results for the PD-RAMP algorithm are presented on all instances and, as far as I know, the solutions provided for instances with up to 90 nodes are the first in the literature for the CSA $p$ HMP. The “Gap” column was computed as ( $U B$ – B ${}^{*}$ )/ $UB\ast 100$ (B ${}^{*}$ is the best solution provided by Stanimirović [15] within 20 runs of the GA algorithm) and the “Best $U B$ ” column displays the best upper bound achieved by the PD-RAMP algorithm.

Table 15

LL medium instances results for the CSA $p$ HMP

Nodes	$p$	GA		PD-RAMP
		GAP	CPU	GAP/Best $U B$	CPU
60	2	–	–	180651.08	38.57
	3	–	–	163305.23	42.41
	4	–	–	146874.91	47.94
	5	–	–	133203.48	51.15
70	2	–	–	185676.61	69.20
	3	–	–	165027.38	78.07
	4	–	–	146717.19	87.96
	5	–	–	136903.77	92.88
75	2	–	–	186520.73	96.62
	3	–	–	165129.27	105.83
	4	–	–	151754.89	122.20
	5	–	–	139666.64	133.14
	10	–	–	179889.58	186.81
90	2	–	–	160735.81	208.59
	3	–	–	145427.11	237.21
	4	–	–	136089.58	253.30
	5	–	–	180651.08	238.57
100	2	0.04	9.24	0.00	100.11
	3	0.01	16.60	0.00	112.65
	4	0.01	16.57	0.00	125.46
	5	0.09	18.87	0.04	140.23
	10	0.35	29.53	0.56	234.45
	15	0.57	36.09	2.40	488.25
	20	0.61	43.29	2.03	598.53
Average		0.24	24.31	0.72	257.10

Table 16

LT medium instances results for the CSA $p$ HMP

Nodes	$p$	GA		PD-RAMP
		GAP	CPU	GAP/Best UB	CPU
60	3	–	–	182418.19	39.00
	4	–	–	152147.27	42.81
	5	–	–	138173.05	46.36
70	3	–	–	177547.09	23.48
	4	–	–	152934.38	66.85
	5	–	–	140011.56	83.13
75	3	–	–	174932.08	92.81
	4	–	–	150761.66	98.61
	5	–	–	139786.94	106.01
90	3	–	–	181171.91	185.77
	4	–	–	152525.38	203.40
	5	–	–	139943.44	216.20
100	3	–	–	180294.08	99.43
	4	0.49	15.50	1.22	109.35
	5	0.72	21.67	1.32	116.05
	10	1.19	32.12	1.02	411.25
	15	0.60	34.64	1.43	421.25
	20	0.69	42.90	3.61	600.15
Average		0.74	29.37	1.72	331.61

For the medium instances, PD-RAMP did not achieve the same quality results as for the small instances. Specifically, for the 100 nodes LL instances, the proposed algorithm obtained an average “Gap” value of 0.72% in 257.10 seconds, and for the 100 nodes LT instances, PD-RAMP achieved an average “Gap” value of 1.72% in 331.61 seconds. For these instances, the GA approach outperformed PD-RAMP.

The last two tables (Tables 17 and 18) show the results for the large instances (from 125 to 200 nodes). GA only provides results for the 200 nodes instances and for the LT instances it does not report results for $p=3$ . For the PD-RAMP algorithm results are displayed on all instances and, as far as I know, the solutions presented for instances with up to 175 nodes are the first in the literature for the CSA $p$ HMP.

Table 17

LL large instances results for the CSA $p$ HMP

Nodes	$p$	GA		PD-RAMP
		GAP	CPU	GAP	CPU
125	2	–	–	180941.19	261.01
	3	–	–	161117.13	287.60
	4	–	–	146173.13	316.56
	5	–	–	137372.63	348.36
150	2	–	–	180898.78	479.64
	3	–	–	161490.34	527.37
	4	–	–	146521.23	581.72
	5	–	–	138648.61	635.23
175	2	–	–	182292.72	899.39
	3	–	–	162584.63	985.85
	4	–	–	147361.13	1067.90
	5	–	–	139998.38	1163.57
200	2	0.02	58.92	2.59	1173.88
	3	0.00	93.14	1.66	1258.73
	4	0.02	107.52	0.01	1359.09
	5	0.26	118.70	$-$ 0.06	1454.15
	10	0.86	183.00	1.55	1521.13
	15	0.61	223.73	3.05	1912.52
	20	0.55	261.82	1.93	1984.52
Average		0.33	149.55	1.53	1523.43

Table 18

LT large instances results for the CSA $p$ HMP

Nodes	$p$	GA		PD-RAMP
		GAP	CPU	GAP	CPU
125	3	–	–	177984.23	253.61
	4	–	–	157683.70	277.96
	5	–	–	144252.77	299.48
150	3	–	–	214943.67	465.35
	4	–	–	157954.09	500.39
	5	–	–	142694.05	547.63
175	3	–	–	188608.69	876.53
	4	–	–	153247.48	961.22
	5	–	–	142119.25	1032.05
200	3	–	–	182663.67	1169.53
	4	0.37	115.71	$-$ 0.47	1242.40
	5	1.70	139.99	$-$ 0.03	1407.18
	10	2.51	204.92	0.74	1545.54
	15	1.38	223.06	2.54	1635.45
	20	1.04	260.03	4.96	1895.22
Average		1.40	188.74	1.55	1545.16

PD-RAMP required a significantly greater computational effort to solve the largest instances in the literature for this version of the Hub Location Problem. Nevertheless, the PD-RAMP algorithm managed to achieve new best-known solutions for instances 200LL ( $p=5$ ), 200LT ( $p=4$ ) and 200LT ( $p=5$ ) with an upper bound of 140472.73, 157422.16 and 143377.67, respectively.

Table 19 presents and compares the average results of sequential (Dual-RAMP and PD-RAMP) and parallel RAMP algorithms for the small, medium, and large AP instances. Column GAP and CPU indicate the average percent deviation from the optimal/best-known solutions (GAP) and the associated computational time (CPU) in seconds. The GAP column in the Parallel RAMP algorithm, was calculated as the average percent deviation from the results obtained by PD-RAMP algorithm.

Table 19

Comparison between parallel RAMP algorithm with the other RAMP approaches

Instances		Dual-RAMP	PD-RAMP		Parallel RAMP
		CPU	GAP	CPU	GAP	CPU
Small	LL	5.18	0.00	5.12	0.00	2.15
	LT	4.84	0.00	5.72	0.00	3.11
	TL	4.22	0.00	5.79	0.00	2.22
	TT	4.74	$-$ 0.20	5.36	0.00	1.89
Medium	LL	90.62	$-$ 0.29	112.77	0.00	55.65
	LT	89.56	$-$ 0.52	109.91	0.00	44.12
	TL	70.28	$-$ 0.4	107.98	0.00	60.52
	TT	76.37	$-$ 0.78	105.21	0.00	65.98
Large	LL	704.04	$-$ 0.97	805.05	0.00	333.48
	LT	705.81	$-$ 1.82	769.80	0.00	299.89
	TL	698.30	$-$ 2.29	794.10	0.00	278.42
	TT	704.21	$-$ 6.16	779.12	0.00	300.75
Average		263.18	$-$ 1.12	300.49	0.00	120.68

From the table above it is clear that the parallel approach found the same solutions as the sequential PD-RAMP algorithm. In terms of computational time, there is no comparison to be made. However, we can verify the advantage of the parallel algorithm when compared to the sequential approach.

All the RAMP approaches, whether it is the sequential or the parallel RAMP algorithm, demonstrated to be very efficient for the solution of the CSApHLP, effectively obtaining excellent quality solutions on the well-known instances available in the literature.

6. Conclusions

In this paper, three RAMP approaches for solving the CSA $p$ HLP are presented. A Dual-RAMP algorithm (that combines Lagrangean Relaxation with subgradient optimization and local search), a PD-RAMP algorithm (that integrates the Dual-RAMP algorithm with a Scatter Search procedure to intensify the search on the primal side of the problem) and finally, a Parallel RAMP algorithm, that includes the sequential approach and solves concurrently the primal method of the PD-RAMP algorithm. In this parallel approach, one thread is responsible to compute and project the dual solution into the primal solution space. A pending solutions pool is responsible for storing all primal and combined solutions. All other threads are responsible for improving the solutions in this solutions pool, always maintaining the best solution found in terms of the objective function.

Once again, the RAMP framework on its primal-dual interconnection proved to be very effective for solving the CSApHLP. The use and combination of information taken by mathematical relaxation in the dual-side together with some adaptive memory programming in the primal-side make the problem easier to solve, obtaining very competitive results for a wide class of HLP. Extensive tests on the standard AP dataset were made to access the performance of all algorithms. Compared with the best-known algorithm in the literature, our approach exhibits excellent results, outperforming the current state-of-the-art algorithms for this problem.

Further directions of research comprising the sequential and parallel RAMP approach can be drawn. The results obtained with the simple and sophisticated RAMP algorithm suggests the creation of different variants and algorithms to tackle other HLP.

Footnotes

Acknowledgments

This work has been supported by national funds through FCT – Fundação para a Ciência e Tecnologia through project UIDB/04728/2020.

References

O’Kelly

M.E.

, A quadratic integer program for the location of interacting hub facilities, Eur. J. Oper. Res 32 (1987), 393–404. doi: 10.1016/S0377-2217(87)80007-3.

Farahani

R.Z.

Hekmatfar

Arabani

A.B.

and Nikbakhsh

, Hub location problems: A review of models, classification, solution techniques, and applications, Comput. Ind. Eng 64 (2013), 1096–1109. doi: 10.1016/j.cie.2013.01.012.

Alumur

and Kara

B.Y.

, Network hub location problems: The state of the art, Eur. J. Oper. Res 190 (2008), 1–21. doi: 10.1016/j.ejor.2007.06.008.

O’Kelly

M.E.

and Miller

H.J.

, The hub network design problem: A review and synthesis, J. Transp. Geogr 2 (1994), 31–40. doi: 10.1016/0966-6923(94)90032-9.

O’Kelly

M.E.

Bryan

Skorin-Kapov

and Skorin-Kapov

, Hub network design with single and multiple allocation: A computational study, Locat. Sci 4 (1996), 125–138. doi: 10.1016/S0966-8349(96)00015-0.

Campbell

J.F.

, A survey of network hub location, Stud. Locat. Anal 6 (1994), 31–49.

Ernst

A.T.

and Krishnamoorthy

, Efficient algorithms for the uncapacitated single allocation p-hub median problem, Locat. Sci 4 (1996), 139–154.

Ernst

A.T.

and Krishnamoorthy

, Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem, Eur. J. Oper. Res 104 (1998), 100–112. doi: 10.1016/S0377-2217(96)00340-2.

Klincewicz

J.G.

, Theory and methodology: Heuristics for the p-hub location problem, Eur. J. Oper. Res 53 (1991), 25–37.

10.

Campbell

J.F.

, Hub location and the p-hub median problem, Oper. Res 44 (1996), 923–935. doi: 10.1287/opre.44.6.923.

11.

Matos

Maia

and Gamboa

, Improving Traditional Dual Ascent Algorithm for the Uncapacitated Multiple Allocation Hub Location Problem: A RAMP Approach, in: 2019, pp. 243–253. doi: 10.1007/978-3-030-13709-0_20.

12.

Matos

Maia

and Gamboa

, A Simple Dual-RAMP Algorithm for the Uncapacitated Multiple Allocation Hub Location Problem, in: Adv. Intell. Syst. Comput., Valencia, Spain, 2020, pp. 331–339. doi: 10.1007/978-3-030-14347-3_32.

13.

Pérez

Almeida

and Marcos Moreno-Vega

, A hybrid GRASP-Path Relinking algorithm for the capacitated p-Hub median problem, in: Lect. Notes Comput. Sci., 2005, pp. 142–153.

14.

Feo

and Resende

, Greedy randomized adaptive search procedures, J. Glob. Optim 134 (1995), 109–134. http://www.springerlink.com/index/m57h74q0805g1l43.pdf (accessed May 20, 2013).

15.

Stanimirović

, A genetic algorithm approach for the capacitated single allocation p-hub median problem, in: Comput. Informatics, 2010, pp. 117–132.

16.

Ting

C.-J.

and Lu

K.-R.

, Lagrangian relaxation for the capacitated single allocation p-hub median problem, J. East. Asia Soc. Transp. Stud 10 (2013), 851–863. doi: 10.11175/easts.10.851.

17.

Contreras

Díaz

J.A.

and Fernández

, Lagrangean relaxation for the capacitated hub location problem with single assignment, OR Spectr 31 (2009), 483–505. doi: 10.1007/s00291-008-0159-y.

18.

Ting

and Wu

, Reactive GRASP for the capacitated single allocation p-hub median problem, J. East. Asia Soc. Transp. Stud 11 (2015), 819–833. doi: 10.11175/easts.11.819.

19.

Matos

, RAMP for the Capacitated Single Allocation p-Hub Location Problem, in: 21th Int. Conf. Hybrid Intell. Syst. (HIS 2021), 2022, pp. 205–214. doi: 10.1007/978-3-030-96305-7_19.

20.

Rego

, RAMP: A new metaheuristic framework for combinatorial optimization, in: Rego

and Alidaee

(Eds.), Metaheuristic Optim. via Mem. Evol. Tabu Search Scatt. Search, Kluwer Academic Publishers, 2005, pp. 441–460. http://www.springerlink.com/index/U6HT8486772950N7.pdf (accessed July 27, 2012).

21.

Glover

Laguna

and Martí

, Fundamentals of scatter search and path relinking, Control Cybern 29 (2000), 652–684. http://leeds-faculty.colorado.edu/Laguna/articles/ss3.pdf (accessed October 11, 2012).

22.

Glover

and Laguna

, Tabu Search, 1997. doi: 10.1007/978-1-4615-6089-0.

23.

Matos

Oliveira

Ó.

and Gamboa

, A Simple Dual-RAMP Algorithm for the Capacitated Facility Location Problem, in: Learn. Intell. Optim., 2020, pp. 1–13. doi: 10.1007/978-3-030-38629-0_20.

24.

Oliveira

Ó.

Matos

and Gamboa

, A dual RAMP algorithm for single source capacitated facility location problems, Ann. Math. Artif. Intell, 2021. doi: 10.1007/s10472-021-09756-0.

25.

Matos

Oliveira

Ó.

and Gamboa

, RAMP algorithms for the capacitated facility location problem, Ann. Math. Artif. Intell, 2021. doi: 10.1007/s10472-021-09757-z.

26.

Oliveira

Ó.

Matos

and Gamboa

, A RAMP Algorithm for Large-Scale Single Source Capacitated Facility Location Problems, in: Lect. Notes Comput. Sci. (Including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 2020, pp. 171–183. doi: 10.1007/978-3-030-38629-0_14.

27.

Martello

Pisinger

Toth

Martello

Pisinger

and Toth

, New trends in exact algorithms for the 0–1 knapsack problem, Eur. J. Oper. Res 123 (2000), 325–332. doi: 10.1016/S0377-2217(99)00260-X.

28.

Laguna

and Marti

, Scatter search: Methodology and implementations in C, Oper. Res. Comput. Sci. Interfaces Ser 24 (2003), 1–283. doi: 10.1007/978-1-4615-0337-8.

29.

Crainic

and Toulouse

, Parallel strategies for meta-heuristics, in: Glover

and Kochenberger

(Eds.), Handb. Metaheuristics, Kluwer Academic Publishers, 2003, pp. 475–514. doi: 10.1007/0-306-48056-5_17 (accessed June 26, 2013).

30.

Alba

, Parallel Metaheuristics: A New Class of Algorithms, 2005. doi: 10.1002/0471739383.

31.

Alba

and Luque

, Evaluation of parallel metaheuristics, Lect. Notes Comput. Sci, 2006. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.184.8185&rep=rep1&type=pdf (accessed June 26, 2013).

32.

de Carvalho

Saraiva de Camargo

Xavier Martins

and Rezende Saldanha

, A parallel heuristics for the single allocation hub location problem, IEEE Lat. Am. Trans 15 (2017), 1278–1285. doi: 10.1109/TLA.2017.7959347.

33.

Benaini

Berrajaa

Boukachour

and Oudani

, Solving the Uncapacitated Single Allocation p-Hub Median Problem on GPU, 2017. http://arxiv.org/abs/1704.06258.

34.

Beasley

, OR-Library: Distributing test problems by electronic mail, J. Oper. Res. Soc 65 (1990), 1069–1072. http://www.jstor.org/stable/10.2307/2582903 (accessed October 11, 2012).

35.

Ernst

A.T.

and Krishnamoorthy

, Solution algorithms for the capacitated single allocation hub location problem, Ann. Oper. Res 86 (1999), 141–159. doi: 10.1023/A:1018994432663.

Primal-dual algorithms for the Capacitated Single Allocation p -Hub Location Problem

Abstract

Keywords

1. Introduction

2. Mathematical model

3.1 Dual method

Table 1 LL small instances results

Footnotes

Acknowledgments

References

Table 1
LL small instances results