The capacitated single-allocation p-hub location routing problem: a Lagrangian relaxation and a hyper-heuristic approach

Given a graph G, a fixed integer p, as the number of hub nodes to be installed, \(\Gamma\) as the minimum number of spoke nodes to be allocated to each hub node, C as the capacity of each feeder route, \(w_{ij}\) as the demand of flow to be transferred/transported from i to j and \(t_{ij}\) as the cost of traveling between every two nodes i and j, which is assumed, in this study, as the time needed to travel between nodes i and j. We also introduce \(d_i\) as the load of transporter after leaving node i on a spoke-level route (the load at arrival minus the total demand of i from every other node plus the total supply of i to every other node). We seek to construct from the scratch a hub-and-spoke network, which consists of a complete hub-level subgraph with p hub nodes and p spoke-level directed cyclic routes, each of which composed of a hub node and all the spoke nodes allocated to it. The hub-level network is a complete subgraph where pair of connected hubs have a bidirectional link. The objective function of our problem is minimizing the total transit time composed of transportation time plus transhipment time in the whole network, provided that the total volume of flow on a spoke-level arc does not violate the capacity of the transporter on it, given a homogenous fleet of transporters.

This problem is a special case of the Bounded Cardinality Capacitated Hub Routing Problem (BCCHRP) proposed in Gelareh et al. (2015) in which the lower and upper bounds on the number of hub nodes coincide. We refer to this problem as Capacitated Single-Allocation p-Hub Location Routing Problem (CSApHLRP).

Figure 1 represents a solution for an instance with \(|V|=n=19\) nodes and \(p=4\) fully interconnected hub nodes. Nodes 2, 3, 8, and 13 represent hubs, while all the remaining nodes are spoke nodes. One observes that each hub together with spoke nodes allocated to it forms a direct cycle. In this solution, four cycles are defined as follows: (i) \(2\rightarrow 1\rightarrow 0\rightarrow 2\), (ii) \(3\rightarrow 4\rightarrow 5\rightarrow 6\rightarrow 7\rightarrow 3\), (iii) \(8\rightarrow 9\rightarrow 10\rightarrow 11\rightarrow 12\rightarrow 8\) and, (iv) \(13\rightarrow 14\rightarrow 15\rightarrow 16\rightarrow 17\rightarrow 18\rightarrow 13\).

In this work, we are focusing on a problem that fits within the category of capacitated single-allocation hub location problems (CSAHLP). In the following, we review some of the related works in the literature with a particular emphasis on the single-allocation scheme and exogenous number of hubs in modeling and (meta)heuristic approaches in solution methods. The references brought here are sorted by publication year.

Rabbani and Kazemi (2015) proposed a genetic algorithm and a simulated annealing for solving an un-capacitated multiple allocation p-hub center problem.

Simulated annealing (SA) and iterated local search (ILS) were proposed by Zarandi et al. (2015) to solve single-allocation hub median problem.

The un-capacitated p-Hub location problem wherein each spoke node should be connected to exactly r hubs (where r is a predefined fixed number) is studied by Peiró et al. (2014). The authors proposed a GRASP algorithm to solve the problem.

Rodríguez-Martín et al. (2014) proposed a Mixed Integer Programming (MIP) formulation and a branch-and-cut algorithm for the hub location and routing problem. In this study, the single-allocation scheme is considered where the capacity constraint is defined in terms of number of spokes per route, and the number of hub nodes is considered as a fixed parameter.

A Multiple Ant Colony Optimization (MACO) algorithm is proposed by Ting and Chen (2013) to solve the capacitated single-allocation hub location problem. In this study, the problem is decomposed into two subproblems: (1) the facility location problem and (2) the multiple depot vehicle routing problem. The two subproblems are treated together within MACO where collaboration of colonies is operated by interchanging information through pheromone renewing the chosen location and costumer assignment.

Gelareh et al. (2013) proposed an MIP formulation for the hub-and-spoke network design problem and fleet deployment of liner shipping, to minimize weighted sum of transit times while considering fixed deployment costs. The proposed MIP is based on a 4-index formulation of HLPs and allocated spokes forming directed cycles (the so-called string) to hubs. Note that, in this work, the fleet of vessels defining the capacity of strings are to be determined from a given heterogenous fleet.

Another VNS is proposed by Jarboui et al. (2013) for the un-capacitated single-allocation hub location problem.

Kratica et al. (2012) proposed a genetic algorithm (GA) for solving an un-capacitated multiple allocation hub location problem. In this study, binary encoding and genetic operators are employed, while the run time is optimized using a caching technique.

Ilić et al. (2010) investigate the Un-capacitated single-allocation p-hub median problem. In this work, a Variable Neighborhood Search (VNS) is considered where a variable neighborhood descent (VND)-based local search using three different neighborhood structures is proposed.

Another simulated annealing for single-allocation capacitated hub location problem was proposed by Yu et al. (2010), given that routes and hubs were constrained by capacity.

Correia et al. (2009) proposed an MIP formulation for the single-allocation hub location problem where capacity on hubs is not an exogenous value, but it is a variable with discrete choices of value. Several variants of this problem have been studied in the literature, such as capacitated and un-capacitated for the single-allocation problem (Correia et al. 2009), and capacitated flow splitting for the multiple allocation one (Campbell et al. 2007).

Randall (2008) proposed an ant colony meta-heuristic optimization algorithm to solve the capacitated single-allocation hub location problem. In this work, four variations of ant colony optimisation meta-heuristic are developed to explore different construction modeling choices.

A heuristic based on (GA) is proposed by Stanimirovic (2008) to solve un-capacitated multiple allocation p-hub median problem. This GA uses binary representation of the solutions. A mutation operator with frozen bits and a caching technique has been employed to solve the problem.

As a relevant work, Ge et al. (2007) investigate the Un-capacitated Single-Allocation p-Hub Location problem. In this study, the authors aim at locating p hub nodes in the network and allocating non-hub nodes to the hubs under the single-allocation scheme where the main objective is to minimize the transportation cost.

Ebery et al. (2000) proposed an MIP formulation and a heuristic for capacitated multiple allocation hub location problem. They hybrid method that combines evolutionary algorithm (EA) with a branch-and-bound algorithm (B&B) to solve a capacitated multiple allocation hub location problem. In this work, the proposed EA selects the set of hubs, while B&B continues with the allocation part of the problem by allocating the non-hubs to the located hubs.

A two-phase tabu search algorithm considering location as the first phase and routing as the second phase with short-term memory is investigated by Tuzun and Burke (1999), to solve capacitated hub location problem considering single-allocation scheme.

Abdinnour-Helm (1998) developed a hybrid method based on combination of genetic algorithm and tabu search to solve an un-capacitated hub location problem with single-allocation scheme. A Genetic Algorithm is used to choose hubs, while a Tabu Search is used to assign spokes to the located hubs.

An application of the p-median Problem is addressed by Rolland et al. (1997). They proposed a tabu search algorithm employing short-term and long-term memory technics, as well as a strategic oscillation for random tabu list sizes.

Klincewicz (1992) studied the p-hub location problem, and to avoid local optima in p-hub location problem, they proposed two meta-heuristics: a tabu search and a GRASP algorithm. The objective of this work is to minimize the total costs of sending traffic over the links. In the proposed two algorithms, local search procedure is based on the two-exchange neighborhood structure.

The work presented in this paper has some similarities with the work presented in Rodríguez-Martín et al. (2014). However, our work is distinguished from Rodríguez-Martín et al. (2014), as follows: in Rodríguez-Martín et al. (2014), the objective function is only to minimize the total transportation cost, while in here, we also considered time as the transshipment cost. In the former, the spoke-level routes are undirected, while we consider direction for the network, such that flow on the spoke-level route circulates in only one direction. Finally, in Rodríguez-Martín et al. (2014), the capacity is defined as the maximum number of spokes along a spoke-level route (the number of physical ports on a machine, as a constraint in telecommunication), while we define it as the volume of flow circulating on a spoke-level route that needs to respect the capacity of transporters available on it.

Our work is also distinguished from the work presented in Gelareh et al. (2015), by the fact that we do not consider any upper/lower bound on the number of hubs. Rather, we assume a fixed cardinally (p) as an exogenous parameter.

To the best of our knowledge, so far, the non-exact methods applied to solve variants of hub location problem were either a meta-heuristic algorithm or a classic heuristic algorithm.

Table 1 summarizes some key features in closely related contributions.

This work has initially been inspired from an application in the distribution chain of pharmaceutical products. Assume we have a chain of consumers in a number of different pharmacies, while a company is to deliver their demand. Local pharmacies are able to store a small amount of products which are more demanded; however, this usually happens that they receive a new prescription which is not available in their stock. Thus, they need to order it and the maximum delay to deliver the ordered prescription needs to be short (for formal situations, no more than a day). What the pharmacies need per day is usually in a reasonably moderate amount, and consequently, a truck is enough to serve quite a few number of pharmacies in a tour every morning. The aim is at designing a service network meeting the criteria while optimizing the time and resource consumption.

This work contributes to the state-of-the-arts as follows: In addition to presenting a mathematical model and identifying several classes of valid inequalities and the respective separation routines, we propose a tailored relax-and-cut algorithm based on the Lagrangian relaxation technique. The primal/dual information (such as Lagrangian multipliers and reduced cost of spoke-level variables), which are accumulated during the iterations of solving Lagrangian dual, are exploited to guide the heuristic algorithms of our hyper-heuristic framework. The proposed hyper-heuristic algorithm is comprised of a portfolio of low-level heuristics (some of which are using the Lagrangian relaxation information) and a heuristic selection method that learns—in the course of process—how to dynamically replace the selected heuristic among the existing heuristics aiming at reaching a higher likelihood of success and improvement. The latter is, in fact, a reinforcement learning method that has been inspired from the concept of association rules in the business data-mining world. We are unaware of any similar work in the literature and, to the best of our knowledge, this is the first work tackling a variant of hub location problems using a hyper-heuristic approach (that, in particular, exploits Lagrangian relaxation information and data-mining knowledge).

The remainder of this paper is organized as follows: In Sect. 2, we present the mathematical model based on the model presented in Gelareh et al. (2015). Then, Sect. 3 is divided into three parts. In the first part, a Lagrangian relaxation algorithm and several classes of valid inequalities are proposed for the problem. In the second part of this section, a hyper-heuristic solution approach and its components exploiting information of Lagrangian dual are presented. In the third part, the overall algorithm and some separation routines for the identified valid inequalities are proposed to be used in a relax-and-cut algorithm. Computational experiments are reported in Sect. 4. Finally, in Sect. 5, we conclude our work and present the possible future work.

Lagrangian relaxation for solving (mixed) integer programming problems was first proposed in Geoffrion (1974), Geoffrion and Bride (1978) and later in Fisher (1981, 2004). The idea behind this method is to relax complicating constraints by penalizing the objective function upon violation of these constraints. The relaxed problem normally has a special structure and can be solved more efficiently comparing the original problem (see Guignard 2003 for a comprehensive survey of the method.).

Three well-known methods are commonly practiced in the literature for solving the Lagrangian dual problem. The oldest and most well-known one is the subgradient method as an iterative method for solving convex minimization problems. The subgradient method was originally proposed in the 60s in the former Soviet Union. Almost at the same time, a very similar method has been proposed in Held and Karp (1971) for solving traveling salesman problem. Later, Lemarechal (1975) proposed the well-known bundle methods as an extension to the simple subgradient. The volume algorithm was later proposed in Barahona and Anbil (2000) as a method which simultaneously produces a primal feasible solution and a dual bound for the problem. A further analysis of volume algorithm and its relation with bundle method has been studied in Bahiense et al. (2002).

Several variants of the subgradient-based methods have been proposed in the literature. Here, based on some observations from our preliminary computational experiments, we opted to use the well-known bundle method of Frangioni (1995) and the corresponding code (publicly available).

We opted to relax constraints (6), (7), (8), (9), and (15) in the Lagrangian fashion. Let \(u^1_{ij}, u^2_{ij}\) and \(u^4_{ij}\) for all \(i, j \in V, i \ne j\), and \(u^3_{ijkl}\) and \(u^5_{ijkl}\) for all \(i, j, k, l \in V\), while \(i \ne j\) and \(k \ne l\) be the Lagrangian multipliers corresponding to (6), (7), (8), (9), and (15) constraints. By doing so, the dual information is going to be retrieved from the coefficients of \(r_{ij}\) and \(z_{ij}\) variables. A solution to such a Lagrangian relaxation, which is a lower bound to the initial model, partially describes the network design and route structures. The dual information can be used to either construct a partially feasible solution or, in general, to guide some of the heuristics in our hyper-heuristic framework. This is called a warm start for a heuristic/huper-heuristic algorithm.

In fact, this relaxation has been chosen among four different scenarios some of which could result in a decomposable subproblem. However, our extensive initial computational experiments find this relaxation as the best trade-off between the quality of bound and computational intractability, among others:

Hyper-heuristics may be seen as a generalization of (meta-)heuristics and an easier way for categorize a large body of literature of heuristics and meta-heuristics that was rather difficult to classify previously. A significant part of the optimization literature is devoted to the use of a given Meta-heuristic (or a hybrid scheme) to solve the problem and often a comparison among a bunch of such methods is presented in different articles. According to Burke et al. (2009), hyper-heuristic is a search methodology or learning mechanism to select or generate heuristics to solve a specific combinatorial problem, while, in this work, we deal with the class of heuristic selection hyper-heuristics (the notion of heuristics to choose heuristics in the context of combinatorial optimisation). Cowling et al. (2001) focuses on the strategies for systematic alternation among different low-level heuristics in different steps of the search (e.g., supported by learning mechanisms). This kind of hyper-heuristic is considered as a high-level approach that, given a problem and a number of low-level heuristics, can select and apply a suitable low-level heuristic at each iteration (Burke et al. 2003).

Using a combination of an operator (low-level heuristic) selection vector and a solution acceptance criterion, a hyper-heuristic must offer a ’good’ solution (when exists), within an unseen low-level problem domain (Marshall et al. 2015). Figure 2 depicts a general structure of a hyper-heuristic.

It must be noted that in a meta-heuristic, one conducts a search in the space of feasible solutions, while, in a hyper-heuristic, the search is carried out over the space of heuristic algorithms (Burke et al. 2003). Our goal here is to select the best series (not necessarily a sequence) of (meta-)heuristics to be applied to obtain high-quality solution(s).

Hyper-heuristics have been successfully applied to solve various problems in routing and scheduling (see Danach et al. 2015a, b; Monemi et al. 2015; Marshall et al. 2014; Garrido and Riff 2010; Garrido and Castro 2012), scheduling (see Ahmed et al. 2015; Zheng et al. 2015; Aron et al. 2015), and bin packing (see Sim et al. 2015; Beyaz et al. 2015; Ross et al. 2002) among others.

Özcan et al. (2012) categorizes such methods as in the following: (i) Purely Random selection that consists of randomly selecting a low-level heuristic from among a set of existing heuristics (see also Özcan and Kheiri 2012), (ii) Random Descent selection that randomly selects a low-level-heuristic and applies it until the solution in hand is improved (see Kendall and Mohamad 2004 as an example of such a selection strategy). (iii) Random Permutation Descent selection that randomly selects a set of low-level-heuristics, and applies them in a circular manner. It then applies the first heuristic until a worsening move is hit. The next heuristics are applied on a cyclic manner (see Özcan and Kheiri 2012; Cowling et al. 2001; Burke and Soubeiga 2003). (iv) Greedy selection applies all low-level heuristics separately at each iteration and chooses the one that generates the best cost (see Cowling et al. 2002, 2001; Özcan and Kheiri 2012 as examples of this strategy). (v) Peckish selection follows the same strategy as the greedy selection, but a subset of low-level heuristics is considered instead of all low-level heuristics (see Cowling and Chakhlevitch 2003, 2007) and, (vi) Reinforcement Learning heuristic selection is based on a reward value for each heuristic. Such type of reward that represents its historical performance has been considered by Özcan et al. (2012), Drake et al. (2015), and Aron et al. (2015).

Our approach falls within the category of reinforcement learning methods and has been inspired from the concept of association rules in the business data-mining world (Aguinis et al. 2012). By the definition of Burke et al. (2010), our approach: (1) is a heuristic-selection type (as opposed to heuristic-generation type), (2) applies an online learning, and (3) is a hybrid construction–perturbation heuristic.

The overall flow of algorithm is described in the following: first, an initial solution is constructed using a constructive heuristic. Then, through a learning process, the hyper-heuristic proposes a series of perturbation, constructive, and/or improvement heuristics to improve the solution.

An acceptance criterion then decides on the transition from the current state (heuristic) to another one.

Here, we use a simulated annealing move acceptance scheme, where the decision regarding the transition (move) to be accepted depends on quality of the solution obtained from applying heuristics (scale of improvement) and the elapsed CPU time. All improved moves are always accepted, and the acceptance of worsening ones follows Metropolis criterion Kirkpatrick (1984):where \(\Delta f\) is the difference between the post-transition and the current objective function values, T is a synthetic temperature and R(0, 1) is a uniform random number between 0 and 1. T represents the global temperature. When T is larger, many non-improving or even deteriorating transitions (moves) can be accepted, while, when it tends to zero, \(\exp (-\Delta f /T)\) become closer to zero, too. Therefore, for sufficiently small values of T, only improving moves are accepted.

The algorithm starts with solving Lagrangian relaxation LRX-CSApHLRP using bundle algorithm (Frangioni 1995). The output (when stopping criteria of bundle are met) is in the form of a feasible solution with respect to the kept constraints (at least the p hubs are identified) as well as a set of coefficients of variables in the objective function. Such coefficients contain dual information.

Solving Lagrangian dual The corresponding Lagrangian dual problem is solved using the bundle method of Frangioni (1995).

Cut management We add cuts mainly during the solution process to find the optimal solution to the MIP problem. Some cuts are added to almost all the nodes of the branch-and-bound tree, while others are added only at certain nodes. All such cuts are added if they meet a threshold of violation, \(\epsilon\). All the globally valid cuts are added as global cuts. This means that, once added, they remain in the LP until the end of the branch-and-bound process. No cut pool is maintained.

Separation of valid inequalities (20) If a node i is allocated to a hub node j, we can send one unit of flow from a dummy node p to the hub node where i is allocated to. If less than one flow arrives at that hub, a cut is identified.

Separation of valid inequalities (21) At any integer node where an inequality of form (21) is violated, every sub-path of length \(|S| + 1\) represents such a valid inequality and is violated by 1. This separation can be done in \(O(n^2)\).

Separation of valid inequalities (22) Initial computational experiments show that Padberg and Rao (1982) outperforms Fischetti et al. (1998) which is a heuristic mechanism.

Separation of valid inequalities (26) Separation based on block decomposition (as implemented for TSP in Concorde) is shown to be more efficient than that of Letchford and Lodi (2002)—even though a polynomial time.