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

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
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
In this work, we tackle the Capacitated Single Allocation
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.
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
and for each pair
When
The mathematical formulation for CSAHLP is:
Equation (5) ensure that a node is assigned to exactly one hub. Equation (6) specifies that exactly
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.
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:
The remaining problem can be separated in two subproblems, denoted as
Decomposing the main problem
A set of
Each
The optimal set of hubs in
This means that we can obtain the solution for
Decomposing the main problem
For each pair
The relaxed problem
The lower bound computation,
We used subgradient optimization to solve the Lagrangean dual problem. At each iteration, we obtain the solution for the relaxed problem
The procedure starts with
For a given vector
To determine the set of
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
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
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 ( The maximum number of iterations is reached. The difference between the upper bound (
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
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:
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
Specifically, each component of the SS works in the following way. The
The
The
The
An
The
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.
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.
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.
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 (
LL small instances results
LL small instances results
The proposed RAMP algorithms were compared with the state-of-the-art approaches for the CSA
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
LT small instances results
TL small instances results
TT small instances results
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 (
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
LL medium instances results
LT medium instances results
TL medium instances results
TT medium instances results
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.
LL large instances results
LT large instances results
TL large instances results
TT large instances results
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
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
Tables 13 and 14 show the results for the small instances (from 10 to 50 nodes).
LL small instances results for the CSA
LT small instances results for the CSA
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 (
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
LL medium instances results for the CSA
LT medium instances results for the CSA
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
LL large instances results for the CSA
LT large instances results for the CSA
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 (
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.
Comparison between parallel RAMP algorithm with the other RAMP approaches
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.
In this paper, three RAMP approaches for solving the CSA
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.
