Faculty of Management and Technology, Mazandaran University of Science and Technology, Babol, Iran
Received: March 16, 2015; Accepted: August 18, 2015; Published: August 22, 2015
Citation: Fazlollahtabar H (2015) Capacitated Location-Allocation Hub Covering Problem in Manufacturing-Customer Interaction. J Appl Computat Math 4:243. doi:10.4172/2168-9679.1000243
Copyright: © 2015 Fazlollahtabar H. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at Journal of Applied & Computational Mathematics
This paper presents a location-allocation hub covering considering capacity constraints for multiple hubs and allocates non-hub nodes including the manufacturer and the customer. The model is an integer linear programming minimizing the transfer costs and optimizes the allocation requests from the manufacturer to the customer passing through one or two hubs. It also simultaneously minimize the cost allocation requests and optimize the use of any existing network hub and the use of any existing network hub due to restrictions on the transfer or collect applications to hub. The model optimization is fulfilled using Lingo 9.0 software, and a discussion is comprehensibly illustrating the aspects of the proposed model.
Location; Hub location; Relocation
The location - allocation hubs (through distributors) with the goal of designing distribution networks (transport, passenger transport, collection and distribution of postal letters, transmission...) as one of the most important issues in the field the transport network is discussed. Properly designed network of hubs and optimized allocation of non-hub nodes to hub nods cause the performance of the widely used transportation systems and communication networks are products of particular importance and that correct design in energy efficiency of transport networks will be effective.
The problem of locating hub facilities arises when some traffic must be transported from a set of origins to a set of destinations, but when it is impossible to establish a direct link between each pair of nodes or when it is too expensive to create such links. In this situation, generally a group of nodes is chosen to locate hubs, which will serve as consolidation, switching and distribution centers for traffic. The origins and destinations will be allocated to this set of hubs. So, if i is connected to hub k and j is connected to hub l, flows from i to j (Wij ) will be routed from i to k, from k to l and from l to j (Figure 1).
Facility location problems have been widely studied by many researchers on a variety of sectors. Examples can include public facilities such as schools and public libraries that are located to best serve the communities. Most of the time, community can be viewed as a group of people, where the initial demand for such facilities are known. Locations of these facilities are not intended for a short term. These facilities should be able to serve the communities for a longer time, where we can expect changes in the demand of the communities. Locating facilities initially and relocating them in the future is a long term decision. In such long term decisions the number of future facilities usually may not be known for sure at the time of locating initial facilities. This uncertainty may happen due to various reasons. For example, suppose that the available budget or company policies limit the number of initial facilities to open at the beginning. However, additional budget or policy changes may allow the company to plan for a different number of facilities in the future. Also, the number of facilities in the future may depend on the success of the initial ones.
There are many variants about this issue: non-hub nodes may be allocated only to one hub—single allocation, Ernst [1,2], O’Kelly  or to several hubs—multiple allocation, Ernst ; the use of direct links between non-hub nodes may be allowed; the location of some (or all) hubs may be fixed; hub nodes may be allowed to be located anywhere in a continuous region—continuous hub location problems, O’Kelly  or may be chosen from a discrete set of places—discrete hub location problems; there may exist a constraint fixing the number of nodes that will be selected as hubs—p-hub problem, Klincewicz , Skorin-Kapov , or a fixed cost for establishing a hub may be considered; instead of choosing nodes to locate hubs, we can select the arcs connecting the non-hub nodes to hubs—hub arc location problem, Campbell [8,9]. Capacities in hub location problems may assume different aspects: there can be capacities on the hub nodes (limiting the volume of flow into the hub, Ebery , Ernst , Aykin  or for the total flow through the hub) as well as on the flows between hubs or between hubs and non-hubs; on other hand, a minimum flow value needed to allow service on the link between a non-hub node and a hub may exist, Lee , Skorin-Kapov . Many different cost functions have been studied, for example, flow-dependent cost functions, O’Kelly ; time functions—latest arrival hub location problem, Kara . The scheme chosen for the hub location problem should depend and reflect the reality of the distribution system considered. For more details on the classification of hub location problems, see Campbell , Campbell  and Bryan . Hub location problems have important applications in transportation and telecommunication systems. The phenomenal growth of the air express package delivery business has been linked to the use of hub-and-spoke networks. Hub location in telecommunication systems has also received a lot of interest, for example, in designing backbone networks and locating concentrators, Klincewicz . This problem also arises in many different applications, such as, postal delivery services, airline services (air passenger travel, air freight travel), communication networks (telephone networks, video teleconferences and computer communications), emergency services and logistic systems [17,18,21].
Some authors considered relocation of facilities in dynamic environments such as the dynamic location allocation problem with facility relocation by Wesolowsky and Trusctott . Their goal was to minimize the overall relocation and allocation costs considering the opening and closing costs of facilities. A relocation problem for public facilities was introduced with the solution of a real life problem in Min . A fuzzy multi-objective model with constraints on budget and the maximum number of relocations per period was constructed to solve the problem. Supply chain point of view of the problem of location and its application in healthcare was also studied in the literature [24-27].
The remainder of the work is organized as follows. Next, we present the proposed problem, assumptions and the mathematical formulations. In Section 3, a numerical illustration is presented. We conclude in Section 4.
The model described in this paper is divided into two parts. The first part consists of locating hubs and allocating non-hub nodes to their (Hub location allocation problem) and the second part subsequently, is to consider different aspects of each hub, in other words, if the demand of each customer requested change so that assigned to that node would exceed the capacity of the hubs or if a customer or supplier location must be changed and hub assigned to the non-hub nodes are not optimal in terms of cost and distance, what would be the hub network.
We use this model, so that we can spend less time and money to meet each customer's demand. In this model manufacturers make up the points of origin and destination points are composed of demand nodes or customers and so network hubs including of distribution points. Model presented in this paper is expressed in terms of location - allocation hub covering problem with considering capacity constraints for each hub also multiple allocations for each non-hub node that includes supplier and customer points.
In the first part of the model, the demand of each customer needs to go through one or two hubs of the supplier to be satisfied, So that in terms of transport costs and distance and capacity constraints for each hub in the transfer demand is optimized. If for transfer between a supplier and a customer in terms of cost and capacity constraints using one hub not be economic, we can connect the first hub to the second hub, and then to reach the customer.
In the second part of the model, three modes for each hub are considered:
First state is the establishment in primary hubs location, in other words, if conditions change, the initial location of hubs and allocate non-hub, it is still optimal therefor hub remains in its original location.
Second state is transportation hubs of initial points to the secondary point, it means that if with considering a new location of customer or supplier, hubs assigned to them in the initial conditions is not optimal, the hub must be moved within the coverage radius of the model is considered so that it is optimal in terms of cost and distance.
The third case is closing hub. If the total demands claim of the hub is less than the hub minimum capacity, because of the cost savings will not be using from that hub. As a result, will be forced to close targeted distributor and requests that have been provided by this distributor will allocate to the other distributor.
Below we present the indices, parameters and decision variables to be used in the mathematical modeling.
i: Non-hub node of origin (manufacturer)
j: Non-hub node of destination (customer or demand points)
k: Hub node (first distribution)
L: Hub node (second distribution)
ai k: Distance from non-hub node i to hub node k
bkL: Distance from hub k to hub L
dLj: Distance from hub L to non-hub j
βkj: Distance from hub k to non-hub j
cik: Current cost between hub k and non-hub i
ekl: Current cost between hub k and hub L
nLj: Current cost between hub L and non- hub j
αkj: Current cost between hub k and non- hub j
Fk: Fixed cost of hub constructing
gk: Fixed cost of hub transportation
uk: Fixed cost of hub closing
wij: Current demand between non-hub i and non-hub j
Lck: The minimum capacity transmission demand from hub k to other nodes
Mck: The maximum capacity transmission demand from hub k to other nodes
Ndk: Critical Distance (cost) of non-hub nodes to hub nodes
Mdk: The maximum distance allowed for hub nodes to non- hub nodes
qik: The maximum cost for the current demand between hub k and non-hub node i
q'kL: The maximum cost for the current demand between hub k and hub node L
q"Lj: The maximum cost for the current demand between hub L and non- hub node j
q1kj: The maximum cost for the current demand between hub k and non- hub node j
r: Covering Radius for replace hub
xik: The current demand between hub k and non-hub node i
yikL: Current demand between hub k and hub L that comes from non-hub node i
ziLj: Current demand between hub L and non- hub j that comes from non-hub node i
Tikj: Current demand between hub k and non- hub j that comes from non-hub node i
hk: If hub k be selected for allocation 1, otherwise 0.
pL: If hub L be selected for allocation 1, otherwise 0.
mk: If hub k be selected for move to another location 1, otherwise 0.
m1k: If according to distance limitations of nodes i, hub k is chosen for the displacement 1, otherwise 0.
m2k: If according to distance limitations of nodes j, hub k is chosen for the displacement 1, otherwise 0.
Sk: If hub k be selected for shut down 1, otherwise 0.
S1k: If according to capacity constraints, hub k is chosen for the shut 1, otherwise 0.
S2k: If according to distance limitations of nodes i, hub k is chosen for the shut 1, otherwise 0.
S3k: If according to distance limitations of nodes j, hub k is chosen for the shut 1, otherwise 0.
Ok: If hub k be selected for stay in the first place 1, otherwise 0.
O1k: If according to capacity constraints, hub k is chosen for stay in first place 1, otherwise 0.
O2k: If according to distance limitations of nodes i, hub k is chosen for stay in first place 1, otherwise 0.
O3k: If according to distance limitations of nodes j, hub k is chosen for stay in first place 1, otherwise 0.
The formulation of the mathematical model is given below:
(1) In objective function of the proposed model we seek to minimize the cost of transport demand from origin to destination and minimize distances between hub and non-hub nodes, in other word, location and allocation must be done in a way that total cost of delivery is at its lowest, in addition, the distance between hub and non-hub nodes is optimized.
(2) The sum of the currents from the determine manufacturer to different hubs should be equal to total demand requested by different customers from that manufacturer.
(3) Total currents that distributed from second hub to the customer plus the sum of the currents of the first hub to be distributed directly to the customer should be equal to all requests that specific customer claim of particular manufacturer.
(4)According to specified manufacturer and the particular second hub, all currents is transmitted of different first hub to the particular second hub must be equal to all currents that go to from second hub to different customers.
(5) Total demands that distribution directly from selected hub k to different customers must be less than or equal to the maximum capacity of the hub in the transfer requests.
(6) Demands that hub k collecting from manufacturer i must be equal to sum of total flows that according to manufacturer i distribution from hub k to different hub L plus the sum of flows according that manufacturer distribution directly from hub k to customers.
(7) Current demands between hub k and manufacturer i is less than or equal to the total demands that are requested by different customers from the manufacturer i.
(8) Sum of flows according to different manufacturer that be transferred from second hub L to customer j is less than or equal to sum of demands that being ask by customer j from different manufacturer.
(9) If at least one of the constraints 10, 11, and 12 is satisfied, hub k will be closed.
(10) Use of the hub k is not optimal and needs to close if the total demand of different customers that asking from hub k be smaller than the minimum capacity of hub k for transport.
(11) If the total distance of different manufacturer be greater than of the maximum distance that hub k can be have with non-hub nodes, the hub will not be used for distribution.
(12) If the total distance of the customer that are directly related to the first hub be greater than of maximum distance that the first hub k can be have with non-hub nodes, the hub k will not be used for distribution.
(13) If at least one of constrains14, 15, and 16 is true, selected hub k is optimal and can also be used as a distributor.
(14) It would be advantageous to use a hub if sum of flows according to different customers be distribution from hub k, in other word, sum of flows that according to different manufacturer be collected in hub k placed within the maximum and minimum hubs capacity for collection and distribution.
(15) If the total distance of the different manufacturer be less than of critical distance (costly) that hub k can be have from non-hub nodes , use the hub as would be optimal.
(16) If the total distance of the different customer be less than of critical distance (costly) that hub k can be have from non-hub nodes , use the hub as would be optimal.
(17) If at least one of the limits of 18, 19 is placed on the need to seek a new location for the hub, in other word using this hub in current location is not optimal and must be found new hub for demands allocation in coverage area.
(18) If sum of distances of difference manufacturer from hub k to non-hub nodes is in range of maximum distance and critical distance, selected hub needs to relocation in coverage area.
(19) If sum of distances of difference customer from hub k to non-hub nodes is in range of maximum distance and critical distance, selected hub needs to relocation in coverage area.
(20) Each hub should be in the closed position or be moved or deployed in the first place, one hub cannot simultaneously true all three modes.
(21-24) this constrains show budget limitation.
(25-26) If hub k needs to relocation must be replaced at a distance less than the radius of coverage.
(27-28) enforce the binary and non- negativity restrictions on the corresponding decision variables.
We solved the presented mathematic model by using Lingo 9, which is operation research software. In this model, we are attempting to minimize the costs of fixed opening, relocation and closing facilities with minimize the costs of collection, transmission and distribution demands in hub network, and three modes for each hub includes closing, relocating , and staying in the first place according to capacity constraints and distance limitation has been investigated. Analyzing the suggested model we create the numerical example and solve that by lingo software.
In this example we consider the index quantities as variables between10 to 20 to solve the problem. So, we replace the inputs of problem in the model and by using the lingo we will solve the problem, and finally the outputs and the objective function amount and the implementation time of the model are obtained.
By attention to the inputs of the model and solving it, the outputs of model and objective function amount and the implementation time has been obtained which are as follow.
We consider 12 manufacturers (i), 10 hubs (k=L) and 15 customers (j), the obtained objective function is 1.03531e+008 which obtained in zero time. Some of important parameters are shown in Tables 1-3.
Table 1: Customer’s demand of each manufacturer (wij).
Table 2: Fixed costs of hub constructing, hub transportation and hub closing.
Table 3: Capacity constraints and distance limitation.
Covering Radius for replace hub (r) is equal to 200.
All the variables which were not zero 0 quantities for allocation non-hub nodes to hub nudes are shown in Table 4.
Table 4: Numerical results for allocation using LINGO 9 Software.
Now, we analyze the three modes for hubs including closing, relocating, and staying in the first location formulated in the proposed mathematical model via constraints 9-20. According to capacity constrain and distance limitation that is intended in the example considered, we will find out when the number of hubs simultaneously being at different positions, to select the optimal conditions according to the model’s objective function, a hub mode having less costs is chosen. For example, hub 7 according to capacity constrains should remain in its original location and according to distance limitation should be moved within the coverage radius, but while cost dedicated for moving this hub to new place is more than the cost of remaining in the first place, thus as a result and based on the objective function the model selected to remain in the original place for hub 7. In the same way the decision variable S(4) and S(10) gained 1. This means that hub 4 and hub 10 must be closed because in accordance with model constrains and parameters that we have considered for this example, using these hubs are not economic. The decision variable M(1), M(3), M(5), M(6), M(8) and M(9) obtained 1, means that these hubs must be relocated in radius of coverage and decision variable O(2) and O(7) obtained 1, it means that using hub 2 and hub 7 in their first location is optimal and does not need to change the situation.
With this example we have shown that our model is able to simultaneously allocate non-hub nodes to hub nodes and is capable to show how to optimize the use of hubs due to the constraints that exist in the real world. We presented a new model for hub locationallocation problem via changing constrains of previous models that was presented in the literatures and added new important constrains that considers budget restrictions and capacity constrain for each hub and limits of transport. Actually we have converted previous NP-hard hub location-allocation models to integer linear programming model that can be solved with the least computational efforts and without any complexity.
In this paper, we presented a model of location - allocation hub covering problem considering capacity constraints for each hub and multiple allocations for each non-hub node including manufacturer and customer nodes. We proposed to minimize the cost of transport demand from origin to destination and minimize distances between hub and non-hub nodes. In the other word, location and allocation must be done in a way that total cost of delivery is the lowest, in addition, the distance between hub and non-hub nodes was optimized. Moreover, we explored the causes of the existing hubs if distance or transmit capacity is changed. In other words, we studied three modes for each hub includes closing, relocating, and staying in the first place. The presented model was an integer linear programming model and we solved that using Lingo 9.0 software.