Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

The capacitated multiple allocation hub location problem: Formulations and algorithms

In this paper we consider and present formulations and solution approaches for the capacitated multiple allocation hub location problem. We present a new mixed integer linear programming formulation for the problem. We also construct an efficient heuristic algorithm, using shortest paths. We incorporate the upper bound obtained from this heuristic in a linear-programming-based branch-and-bound solution procedure. We present the results of extensive computational experience with both the heuristic and the exact methods.     

Strategic oscillation for the capacitated hub location problem with modular links

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

The capacitated single-allocation hub location problem revisited: A note on a classical formulation

In this paper a well-known formulation for the capacitated single-allocation hub location problem is revisited. An example is presented showing that for some instances this formulation is incomplete. The reasons for the incompleteness are identified leading to the inclusion of an additional set of constraints. Computational experiments are performed showing that the new constraints also help to decrease the computational time required to solve the problem optimally.     

A non-triangular hub location problem

Hub location problems generally assume that the triangle inequality applies on the edges of a complete graph. Hence the flow between any pair of nodes requ     

A capacitated competitive facility location problem

We consider a mathematical model similar in a sense to competitive location problems. There are two competing parties that sequentially open their facilities aiming to “capture” customers and maximize profit. In our model, we assume that facilities’ capacities are bounded. The model is formulated as a bilevel integer mathematical program, and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as that of maximization of a pseudo-Boolean function with the number of arguments equal to the number of places available for facility opening. We propose an algorithm for calculating an upper bound for values that the function takes on subsets which are specified by partial (0, 1)-vectors.     

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.     

A competitive hub location and pricing problem

We formulate and solve a new hub location and pricing problem, describing a situation in which an existing transportation company operates a hub and spoke network, and a new company wants to enter into the same market, using an incomplete hub and spoke network. The entrant maximizes its profit by choosing the best hub locations and network topology and applying optimal pricing, considering that the existing company applies mill pricing. Customers’ behavior is modeled using a logit discrete choice model. We solve instances derived from the CAB dataset using a genetic algorithm and a closed expression for the optimal pricing. Our model confirms that, in competitive settings, seeking the largest market share is dominated by profit maximization. We also describe some conditions under which it is not convenient for the entrant to enter the market.     

Heuristics for solving a capacitated multiple allocation hub location problem with application in German wagonload traffic

In this paper, we present a capacitated multiple allocation hub location problem, which arose from a network design problem in German wagonload traffic. We develop heuristic solution approaches based on local improvements. We solve the problem with the heuristics and CPLEX on test data sets provided by our partner Deutsche Bahn AG. The computational results are presented and compared.     

The ordered capacitated facility location problem

In this paper, we analyze flexible models for capacitated discrete location problems with setup costs. We introduce a major extension with regards to standard models which consists of distinguishing three different points of view of a location problem in a logistics system. We develop mathematical programming formulations for these models using discrete ordered objective functions with some new features. We report on the computational behavior of these formulations tested on a randomly generated battery of instances.     

Stochastic air freight hub location and flight routes planning

This paper introduced a stochastic programming model to address the air freight hub location and flight routes planning under seasonal demand variations. Most existing approaches to airline network design problems are restricted to a deterministic environment. However, the demand in the air freight market usually varies seasonally. The model is separated into two decision stages. The first stage, which is the decision not affected by randomness, determines the number and the location of hubs. The second stage, which is the decision affected by randomness, determines the flight routes to transport flows from origins to destinations based upon the hub location and realized uncertain scenario. Finally, the real data based on the air freight market in Taiwan and China is used to test the proposed model.     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

A clustering approach to the planar hub location problem

The problem tackled in this paper is as follows: consider a set ofn interacting points in a two-dimensional space. The levels of interactions between the observations are given exogenously. It is required to cluster then observations intop groups, so that the sum of squared deviations from the cluster means is as small as possible. Further, assume that the cluster means are adjusted to reflect the interaction between the entities. (It is this latter consideration which makes the problem interesting.) A useful property of the problem is that the use of a squared distance term yields a linear system of equations for the coordinates of the cluster centroids. These equations are derived and solved repeatedly for a given set of cluster allocations. A sequential reallocation of the observations between the clusters is then performed. One possible application of this problem is to the planar hub location problem, where the interacting observations are a system of cities and the interaction effects represent the levels of flow or movement between the entities. The planar hub location problem has been limited so far to problems with fewer than 100 nodes. The use of the squared distance formulation, and a powerful supercomputer (Cray Y-MP) has enabled quick solution of large systems with 250 points and four groups. The paper includes both small illustrative examples and computational results using systems with up to 500 observations and 9 clusters.     

A heuristic lagrangean algorithm for the capacitated plant location problem

Lagrangean techniques have been widely applied to the uncapacitated plant location problem, and in some cases they have proven to be successfull even when capacitated problems with additional constraints are taken into account. In our paper we study the application of these techniques to the capacitated plant location problem when the model considered is a pure integer one. Several lagrangean decompositions are considered and for some of them heuristic algorithms have been designed to solve the resulting lagrangean subproblems, the heuristics consisting of a two phase procedure. The first (location phase) defines a set of multipliers from the analysis of the dual LP relaxation, and makes a choice of the plants considering the resulting subproblems as a particular case of the general assignment problems. Several heuristics have been studied for this second phase, based either on a decomposition of knapsack type subproblems through a definition of a set of penalties, or of looking into the duality gap and trying to reduce it. Computational experience is reported.     

A partial dual algorithm for the capacitated warehouse location problem

The Capacitated Warehouse Location Problem (CWLP) consists of the ordinary transportation problem with the additional feature of a fixed cost associated with each supplier. A supplier can be used towards meeting the demands of the customers only if the corresponding fixed cost is incurred. The problem is to determine which suppliers to use and how the customer demands should be met, so that total cost is minimised.Most of the recently published algorithms for CWLP use branch and bound based on a Lagrangian relaxation of demand constraints. Here, a partial dual of a tight LP formulation is used in order to take advantage of the properties of transportation problems. Computational results are given which show good overall performance of the algorithm, with the size of the tree search being reduced compared with previous published results.     

Design of intermodal logistics networks with hub delays

In an intermodal hub network, cost benefits can be achieved through the use of intermodal shipments and the economies of scale due to consolidation of flows at the hubs. However, due to limited resources at the logistics hubs, shipment delays may affect the service performance. In this research hub operations are modeled as a GI/G/1 queuing network and the shipments as multiple job classes with deterministic routings. By integrating the hub operation queuing model and the hub location-allocation model, the effect of limited hub resources on the design of intermodal logistics networks under service time requirements is investigated. The managerial insights gained from a study of 25-city road-rail intermodal logistics network show that the level of available hub resources significantly affects the logistics network structure in terms of number and location of hubs, total network costs, choice of single-hub and inter-hub shipments and service performance.     

A cutting plane algorithm for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of clients. A multi-source version of the problem is considered in which each client can be served by more than one facility. In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable. We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope. We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable. To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities. We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach.     

A co-opetitive framework for the hub location problems in transportation networks

In this paper, we present the first model of co-opetition for a Hub Location Problem between two logistics service provider (LSPs) companies where the mother company is the owner of infrastructure. The LSPs would like to cooperate with each other by establishing joint edges with limited capacities connecting their service networks. Such services are in form of pendulum services (a direct service between two points) between nodes of different networks. Additional market can be generated as a result of joining the two networks. At the same time, a competition is taking place between the two operators to increase their share from the additional market generated. In order to solve this problem, we propose a matheuristic approach combining a local search algorithm and a Lagrangian relaxation-based approach. In our matheuristic algorithm, the neighbourhood solutions are evaluated using a Lagrangian relaxation-based approach. Numerical results of applying the proposed algorithm on a real case study of the problem are presented.     

LP-based approximation for uniform capacitated facility location problem

In this paper, we study uniform hard capacitated facility location problem. The standard LP for the problem is known to have an unbounded integrality gap. We present constant factor approximation by rounding a solution to the standard LP with a slight $(1+ϵ)$ violation in the capacities.Our result shows that the standard LP is not too bad.Our algorithm is simple and more efficient as compared to the strengthened LP-based true approximation that uses the inefficient ellipsoid method with a separation oracle. True approximations are also known for the problem using local search techniques that suffer from the problem of convergence. Moreover, solutions based on standard LP are easier to integrate with other LP-based algorithms.The result is also extended to give the first approximation for uniform hard capacitated $k$-facility location problem violating the capacities by a factor of $(1+ϵ)$ and breaking the barrier of 2 in capacity violation. The result violates the cardinality by a factor of $\frac{2}{1+ϵ}$.     

A fuzzy programming approach for dynamic virtual hub location problem

Hub location problem has been used in transportation network to exploit economies of scale. For example, a controversial issue in the planning of air transportation networks is inclement weather or emergency conditions. In this situation, hub facilities would not be able to provide a good service to their spoke nodes temporarily. Thus, some other kinds of predetermined underutilized facilities in the network are used as virtual hubs to host some or all connections of original hubs to recover the incurred incapacitation and increase network flexibility and demand flow. In such an unexpected situation, it is not unreasonable to expect that some information be imprecise or vague. To deal with this issue, fuzzy concept is used to pose a more realistic problem. Here, we present a fuzzy integer liner programming approach to propose a dynamic virtual hub location problem with the aim of minimizing transportation cost in the network. We examine the effectiveness of our model using the well-known CAB data set.