Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.17 No.3 pp.588-599
DOI : https://doi.org/10.7232/iems.2018.17.3.588

The Single-Allocation Heuristic Hub Location Problem Solving

Davood Jafari*, Mahdi Hadian Pour
Department of Industrial Engineering, Islamic Azad University of Tehran, Parand Branch, Iran
Corresponding Author, E-mail: djafari5071@piau.ac.ir
May 19, 2018 August 20, 2018 August 30, 2018

ABSTRACT


Hubs are special facilities that consolidate and disseminate flows in many-to-many distribution systems. The hub location problem aims to find locations of hubs and allocate non-hub nodes directly to the hubs. However, this problem is necessary to extend when nodes do not have sufficient demand to justify direct connections between the non-hub nodes to the hubs since such direct connections increase the number of vehicles required and decrease the utilization of vehicles. In this research, after analyzing the definitions of the location of the hub and a variety of location models and their solving algorithms, we solved a case study of the classic Hub Location model algorithm by adding an annual fixed cost to determine the best way to carry goods from one country to another from the top 5 most requested destinations, aimed at minimizing shipping and distribution costs.



초록


    1. INTRODUCTION

    One of the new issues in the field of location is the question of finding a hub. A hub (axis) is a generic term referring to a location or point; the place where the goods or information is provided from several sources and then transferred to the other hubs of the network or the final destination. Hub site locator issues will determine the location of hubs and allocate network nodes to these hubs so that the total cost of hubs and shipping costs are minimized (Eid and Mirakhorli, 2011).

    In the context of hub placement, the service that is performed involves the movement of individuals, goods or information between a source location and a destination location. The use of these facilities will ultimately lead to the optimal organization of movements and the avoidance of additional traffic which will have the benefits of reducing fuel consumption, reducing air pollution, reducing depreciation and increasing the life of the road network, etc. (Sadeghpour et al., 2010).

    The design of the network in many transportation and communication tools is an important issue because it has a great impact on the ultimate service cost and efficiency. In some cases, the direct connection between nonaxial nodes is very expensive, and it is better to move goods from other nodes called the axis. Instead of using direct connections to the destination, indirect connections (connectivity to the axis) are used. This can be used to save on scale (Sasaki et al., 1999). In practice, saving to scale means, for example, that on air networks, larger and more efficient aircraft can be used on connecting lines, and in the case of communication networks, the use of higher-power optical fibers to interact Between pairs of axes is taken into consideration (Farahani and Hekmatfar, 2009).

    In hubs, instead of directly connecting each pair of source-destination nodes (Figure 1), flows are concentrated on the hub facility (Figure 2). Integration on a route from the source to the hub, from the hub to the destination, and even between the hubs (Sadeghpour et al., 2010).

    Application of hub location issues

    The application of these issues, in reality, is in the following three general areas (Alumar and Kara, 2008):

    • 1. Changing the direction and path

      Such as computer systems, power distribution, telephone networks and video conferencing traps

    • 2. Shipping

      Such as Airline passengers, Freight ships and special and fast transportation

    • 3. Sort centers

      Like: Postal Centers

      Applications in the real world

    Adler and Hashai (2005) reviewed airline and open air transport policies in the Middle East. Interestingly, as a result of this study, Cairo, Tehran, Istanbul, and Riyadh were ranked as the best-performing airport-hub locations, without mentioning Dubai. Dubai is now considered one of the major axes of the region. This suggests that in practice, political and economic issues have overcome the better location (Farahani and Hekmatfar, 2009).

    In order to make such comparisons, large cities and villages were selected based on available statistical data from the latest census. The result of these calculations was that the optimized solution was 10 to 40 percent less expensive than the observed solutions. However, optimized sites from landfills are quite close to those that are deployed. The only exception was the designers were diverted from their designs because of general opposition (Farahani and Hekmatfar, 2009).

    Understanding the Hub’s Location Problem

    Data on this issue are (Akhondzadeh et al., 2008):

    • 1) Complete graph with V nodes and E arcs G = (V, E)

    • 2) The weight or transit time between nodes i and j displayed with hij or wij (Requests)

    • 3) The distances between nodes i and j were displayed with dij.

    • 4) The cost of transporting goods or passengers or information on arcs

    • 5) Discount Factors

    Each destination path consists of three parts:

    • A path from the origin to the first axis

    • A path from the first axis to the last axis

    • A route from the last axis to the destination

    Of course, the second path will have zero flow if both source and destination nodes are connected to one axis.

    Therefore, the network consists of two levels:

    • Access level: Includes source bows and non-axis destinations to axes.

    • Axis surface: Incorporates bolts of axes to each other.

    The arcs will have different discounts depending on which pair of nodes is connected. If the three-factor discount factors are used, they are considered as follows (Akhondzadeh et al., 2008):

    • χ : discount factor for axis-based arcs

    • α : discount factor for axis-to-axle arcs

    • δ : discount factor for axis to destination

    ( α < χ   , α < δ )

    Usually the number of axes, P is considered. In the main, only the factor α is considered.

    What we are looking for is location-based issues, selecting nodes from the existing nodes (in some cases, the number of axes) and assigning the nodes to the nodes. The optimal points are the points that have the lowest cost. Scheme 1 illustrates a schematic of location-based issues.

    2. RESEARCH BACKGROUND

    The problem of finding a hub has a short history. Initially, Hakimi (1964) published the first paper on the node optimization area which later gave rise to a similar concept in the problem of locating the hub. The first paper in this area, in which the mathematical model and the method of solving are presented, was an attempt done by O’Kelly (1987).

    O’Kelly (1987) presented the first model of the problem-centered facility, with the condition of linking the allocation of demand centers to a focal point, the objective function of this model was to reduce the total cost of transportation of communication flows. Because of the low cost of communication between centers, he proposed a discount factor of between 0 and 1 that was used for communication between the axes (Farahani and Hekmatfar, 2009; Farahani et al., 2013). The focus of the articles was on modeling in the 1980s as well as 1990s, this focus was on modeling and optimization, and in the recent past efforts have been made on advanced models and new methods of solving it.

    Campbell (1994a) presented a multiple mathematical formulation and conducted a study on hub networks. Bryan and O’Kelly and Bryan (1999) examined the applications of hub mapping in communications, industry, and aviation. Alumar and Kara (2008) reviewed and classified papers published until 2007 (Farahani and Hekmatfar, 2009).

    The work done on the location of the hub can be grouped into three general categories (Eid and Mirakhorli, 2011):

    • Simplifying the mathematical model and presenting the new model with fewer variables and constraints

    • Providing new solving methods

    • Modifying the model and applying it

    In the studies in the field of hub location, three assumptions are considered (Alumar and Kara, 2008):

    • 1. Networking the axes together is a complete network.

    • 2. Savings of scale are considered by assigning the discount factor α to the interconnection connection.

    • 3. There is no direct relationship between non-axial nodes.

    In summary, it can be said that Hub location issues are not a part of the classic issues of location. In fact, these issues are a subset of network optimization issues. For this reason, and based on its application in practice, location-based location models are presented for each of the models that are located in a discrete classic location. The basic difference of location-based issues with the standard layout of facilities is the existence of flow with discounts among axes. Axes are introduced as communication points, and in these points, the flow is re-directional (Farahani and Hekmatfar, 2009).

    Hub Locator Locations

    In general, the hub’s location models are divided as follows:

    • Various Hub Locator Models

    • Cover hub

    • Mid-range hub with fixed cost

    • P-hub center

    • Middle p-hub

    • Hub Maximum Coverage Locator Model

    • Full-hub positioning model

    • Classic model of the problem of hub location

    • The problem of locating a single hub

    O’Kelly (1987) was the first person to address the problem of locating a single hub. There’s only one hub in this model.

    Model Inputs:

    • Hij: demand or flow between source node i and destination node j.

    • Cij: Cost unit (non-hub to hub) Transfer between nodes i and j.

    Model Outputs:

    • Xj: takes one if it is j hub, otherwise it will be zero.

    • Yij: If the node i allocates to the j-th hub, it takes one, otherwise it will have zero value

    Goal continued:

    min i j k h i k ( C i j + C j k ) y i j y k j
    (1)

    S.T

    j X j = 1
    (2)

    Y i j X j
    (3)

    X j =   0 ,   1 i , j
    (4)

    Y i j = 0 ,   1 i , j
    (5)

    In this model, equation (1) minimizes the total cost of transfers through the hub. Equation (2) shows that we must exactly locate a hub. Equation (3) shows that node i can only connect to the hub node. Equations (4) and (5) are of the type zero and one that are explained in the decision variables.

    2.1. P-Hub Mapping Model

    O’Kelly (1987) was the first to present a well-known mathematical formula for hub issues related to the airlift network. In this case, each non-stick node should only be assigned to a hub node. O’Kelly (1987) suggested this model. Hub nodes are connected and each non-hub node is connected to a hub. The number of hubs to be located is already known to be the number P. There is no cost to create hubs and the capacity of the hubs is unlimited. The output of this model is also binary. The model was also solved by the integer power program. Contreras et al. (2012) proposed a Benders Decomposition algorithm where they generate cuts for each hub candidate to solve the incapacitated multiple allocation p-hub median problem. They also constructed pareto-optimal cuts to enhance the convergence of the algorithm. Peiró et al. (2014) proposed a heuristic based on the GRASP methodology for rallocation p hub median problem. Moreover, Martí et al. (2015) proposed scatter search algorithm for the incapacitated r-allocation p hub median problem.

    2.2. Model Input

    • Hij: demand or flow between node i and node j.

    • Cij: the cost of the transfer between the nontraffic node i and the node j.

    Α: Discount Factor (1≥ α ≥0)

    Decision variables:

    • 1. Xj: When the node is j hub, the value of this variable is one, and otherwise it is zero.

    • 2. Yij: If the node i receives the j (hub) service, the value of this variable is one, otherwise it is zero.

    Goal continued:

    M i n i j h i j ( k Y i k C i k + m Y j m C j m + α k m Y i k Y j m C k m )
    (6)

    S.T

    j y i j = 1
    (7)

    j X j = P
    (8)

    ( n P + 1 ) X j 0 or Y ij X j   i , j
    (9)

    X j =   0 ,  1 i , j
    (10)

    Y i j =   0 ,  1 i , j
    (11)

    Equation (6) minimizes the cost of transfers between nodes. The first part of this equation expresses the cost of the transport from the non-node node to the node k when the node i is assigned to the k hub. The second part expresses the cost of connecting the destination path for node j to m hub. The third part expresses the cost of the hubs. Equation (7) shows that the non-hybrid node i is assigned to only one hub. Equation (8) states that exactly the P node of the hub is selected. Equation (9) shows that each non-traffic node can only be connected to the hub node. Equations (10) and (11) express the definition of output variables as binary, which, like the previous model, have a value equal to one or zero.

    Middle P-hub location model

    The purpose of this model is to reduce the cost of transportation (time, distance, etc.). In this model, n is the demanded node, and we already know the number of hubs we need to locate. This issue is divided into two single allocation and multiple allocation models.

    Allocation:

    Campbell (1994b) presented a linear programming model with n4 + n2 + n variable and n4 + 2n2 + n + 1 linear limitation. He used the liberation of LP to solve.

    Model Inputs:

    • Hij: demand or flow between node i and node j

    • Cij: Cost of switching between node i and node j

    • Α: discount factor; discount for transportation between hubs (0 ≤ α ≤ 1)

    • C i j k m : The cost of moving between source i and destination j through h and k m.

      ( C i j k m = C i k +   α C k m + C m j )

    Decision variables:

    • Xj : When node j is a hub, the value of this variable is 1, otherwise it is zero.

    • Z i j k m : Stream from node i to node j through h and k m.

    Goal continued:(12)

    Min i j k m C i j k m h i j Z i j k m
    (12)

    S.T(13)(14)(15)(16)(17)(18)(19)

    j y i j = 1
    (13)

    k X k = P
    (14)

    Y i j   X j i , j
    (15)

    Z i j k m = x m             i , j , k , m
    (16)

    Z i j k m = x k             i , j , k , m
    (17)

    Z i j k m = 0 , 1 i , j , k , m
    (18)

    x k = 0 , 1     k
    (19)

    Multiple Allocation

    This model was presented by Campbell (1991) with a linear objective function. In this model, any non-stick node can be connected to more than one hub. The assumptions of this model are similar to the P-hub model, with the exception that the allocations are subjected to change. Campbell (1991) solved this model using integer programming.

    Model Inputs:

    • Hij: demand or flow between node i and node j

    • Cij: Cost of switching between node i and node j

    • Α: discount factor; discount for transportation between hubs (0 ≤ α ≤ 1)

    • C i j k m : The cost of moving between source i and destination j through h and km.

      ( C i j k m = C i k + α C k m + C m j )

    Decision variables:

    • Xk : When node j is a hub, the value of this variable is 1, otherwise it is zero.

    • Z i j k m : Stream from node i to node j through h and km.

    Goal continued:

    Min i j k m C i j k m h i j Z i j k m
    (20)

    S.T

    k X k = P
    (21)

    k m Z i j k m = 1 i , j  
    (22)

    Z i j k m x m i , j , k , m
    (23)

    Z i j k m x k      i , j , k , m
    (24)

    Z i j k m = 0 , 1 i , j , k , m
    (25)

    x k = 0 , 1 k
    (26)

    Equation (20) minimizes the total shipping cost. Equation (21) shows that we must exactly locate P hubs. Equation (22) ensures that each destination (i, j) of the destination must be exactly the same as a hub pair. Equations (23) and (24) show that nodes cannot connect to other nodes other than hub nodes. Equation (25) is the standard of truth-limiting. Equation (26) shows that if k, the hub is the value of one, then otherwise it will be zero.

    P-hub average location model with fixed cost

    This model was created by adding fixed costs to the P-Hub model’s objective function. O’Kelly (1992) presented this model. In this model, we do not already know the number of hubs we need to locate. O’Kelly (1992) solved this model using the heuristic algorithm method.

    3. MODEL INPUT

    • Hij : demand or flow between node i and node j

    • Cij Cij: Cost of switching between node i and node j

    • Α: discount factor; discount for transportation between hubs (0 ≤ α ≤ 1)

    • C i k k m : The cost of moving between source i and destination j through h and k m.

    • Fk : The fixed cost of hub placement in node k.

    Decision variables:

    • 1. Xj : When the node is j hub, the value of this variable is 1, otherwise it is zero.

    • 2. Yij : If node i receives service from j (hub), then value 1, otherwise it will be zero.

    Goal continued:

    Min

    M i m i k i k C i k Y i k ( j h i j ) + k i C k i Y i k ( j h j i ) + α i j k m h i j C k m y j k y j m + k f k x k
    (27)

    S.objective function:

    j y i j = 1           i
    (28)

    y i j x j           i , j
    (29)

    x j = 0 ,   1           j
    (30)

    y i j = 0 , 1 i , j
    (31)

    Equation (27) Minimizes the cost of switching between nodes and the cost of creating a hub. Equation (28) ensures that the hubs must pass through the nodes to move. Equation (29) shows that a node cannot be connected to a node that is not a hub. Equation (30) If the node h is a value of 1, otherwise it will be set to zero. Equation (31) If the node i receives the service node j (hub), the value of one, and otherwise takes zero.

    P-Hub Center location model

    The P-Hub’s location model is one of the most important models for applications such as finding emergency facilities. This model is used in hub systems for degradable or degradable goods or sensitive goods. Campbell (1994a) presented this model. The assumptions of this model, like the P-hub model, are modest except for the Mini-Max model. He provided the first linear integer for solving this model. Ernst et al. (2009) proposed a new formulation which has more continuous variables compared to the form. Later, Meyer et al. (2009) proposed a two-phase algorithm for the single allocation p-hub center problem. Afterwards, Liang (2013) proposed an approximation for the star p-hub center problem.

    4. MODEL INPUTS

    • Hij : demand or flow between node i and node j

    • Cij : Cost of switching between node i and node j

    • Α: discount factor; discount for transportation between hubs (0 ≤ α ≤ 1)

    • C i j k m : The cost of moving between source i and destination j through h and k.

      ( C i j k m = C i k + α C k m + C m j )

    Decision variables:

    When the node is j hub, the value of this variable is 1, otherwise, it is zero.

    • Z i j k m : Stream from node i to node j through h and km.

    Goal continued:

    Min Max{ C i j k m h i j Z i j k m }
    (32)

    S.T

    k X k = P
    (33)

    k m Z i j k m = 1 i , j  
    (34)

    Z i j k m x m i , j , k , m
    (35)

    Z i j k m x k      i , j , k , m
    (36)

    Z i j k m = 0 , 1 i , j , k , m
    (37)

    x k = 0 , 1 k
    (38)

    Equation (32) minimizes the cost of the highest (highest) demand. Equation (33) shows that we must exactly locate P hubs. Equation (34) ensures that each source (i, j) of the destination (i, j) must be assigned exactly to a hub pair. Equations (35) and (36) show that nodes cannot connect to other nodes other than hub nodes. Equation (37) is the standard of truth-limiting. Equation (38) shows that if k, the hub is the value of one, and otherwise it will change the value of zero.

    4.1. Hub Covering Problems

    The hub covering problem could be investigated in two main types: hub set covering problem and maximal hub-covering problem. The hub set-covering problem aims to locate hubs to cover all demands while minimizing the cost of opening hubs. These two kinds of problems are firstly presented by Campbell (1994a) and he gives three criteria for hub covering: (I) hubs k and l cover the origin-destination pair (i; j) if the cost of routing from i to j via k and l does not exceed a threshold; (II) the cost of links in the route from i to j via k and l does not exceed a threshold; (III) origin to-hub and hub-to-destination links meet the specified values separately.

    Hub covering location perspective is used in different problems. Yildiz and Karaşan (2015) revisited the regenerator location problem with hub location perspective and they introduce ow-based compact formulations and cut formulation. They develop branch and cut algorithms based on the cut formulations.

    Hub Location and Routing Problems

    Nagy and Salhi (1998) introduced the hub location and routing problem to the location literature. The authors proposed a mathematical model where the objective function has two components: the first one is dependent on the distance traversed in the tours and between hubs and the other component is the fixed cost of opening hubs. They allow customers to be visited by two tours one for pickup and the other for delivery while obeying capacity and distance constraints. They do not have a restriction on the number of hubs opened. However, they do not solve the problem exactly. Instead, they propose a hierarchical solution methodology to tackle the problem. Çetiner et al. (2010) studied multiple allocation version of hub location and routing problem for the Turkish postal delivery services.

    4.2. Modeling the Full Coverage Hub

    The goal of the problem is to locate the full coverage hub, placing the axes in such a way as to cover the entire demand with the minimum cost possible for the establishment of the axes. The first formulation of this problem was presented by Campbell (1994a). According to this paper, the source-destination pairs (i, j) are covered by the k and m hubs, as Eid and Mirakhorli (2011) stated that this model should:

    • 1. The length or time of the entire path from node i to node j, which passes from the hub k and then m from the hub, does not exceed a predetermined value.

    • 2. The length or time of passing any arc located on this path does not exceed a predetermined value.

    • 3. The length or time of passing any bow between the hubs and the non-hub nodes located on the specified path does not exceed the predetermined value.

    The most important use of the problem is the cover hub in the traffic that is expected to reach the customer at a predetermined time, such as its use in post offices or airlines. Another point is that the following two issues are important in transportation networks (Eid and Mirakhorli, 2011):

    Model Input

    • Fk : The fixed cost of deploying the hub facility at node k.

    • C i j k m : The cost of moving from the source node i to the destination node j through the location hubs k and m.

    • Yij : the highest cost for the coverage of the demand connections of node i to node j.

    • V i j k m : is equal to one if the hubs located in nodes k and m can cover the pairs (i, j).

    Decision variables:

    The output of this model is similar to the P-Hub problem-solving variables.

    Goal continued

    M i n k F k X k
    (39)

    S.T

    k m V i j k m Z i j k m = 1 i , j  
    (40)

    Z i j k m x m i , j , k , m
    (41)

    Z i j k m x m i , j , k , m
    (42)

    Z i j k m = 0 , 1 i , j , k , m
    (43)

    x k = 0 , 1 k
    (44)

    Equation (39) minimizes the cost of creating a new hub. Equation (40) ensures that each pair request is covered by at least one pair of hubs. Equation (41) and (42) show that when pivoting from one node to another, the hubs must pass through. Equation (43) is the standard of truth-limiting. Equation (44) shows that if k, the hub is the value of one, and otherwise, the value of zero is chosen.

    4.3. The Problem of Locating the Maximum Coverage Hub

    The goal is to maximize covered demand with a certain number of axes. This is similar to the P-Hub problem. In this case, we know the number of hubs we need to locate, so the problem is an out-of-the-box problem and, as a result, we do not have the fixed cost of hubs. In this regard, the goal is to maximize the demand for transport covered.

    Hub Locator Problem Modeling Maximum Coverage:

    M a x i j k m h i j V i j k m Z i j k m
    (45)

    k X k = P
    (46)

    k m Z i j k m = 1 i , j
    (47)

    Z i j k m x m i , j , k , m
    (48)

    Z i j k m x k i , j , k , m
    (49)

    Z i j k m = 0 , 1 i , j , k , m
    (50)

    x k = 0 , 1 k
    (51)

    Equation (45) maximizes the demand for covered transport. Equation (46) shows that we must exactly locate P hubs. Equation (47) ensures that each destination (i, j) of the source-destination must be assigned to exactly the same hub pair. Equations (48) and (49) show that nodes cannot connect to other nodes other than hub nodes. The equation (50) is the standard of truth constraints and holds some binary. Equation (51) shows that if k, the hub is the value of one, and otherwise, the value of zero is chosen.

    4.4. The Star-P-Hub Center Question

    Yaman and Elloumi (2012) have presented this model in. In this model, β is the maximum path length between the source-destination pairs, which minimizes β_min this path. This model was solved by complex integer programming. In this model all pairs of nodes require communication. If node i is assigned to j, and node m is assigned to l, then the length between nodes i and m is equal to dij + d0j + d0l + dlm.

    Problem Model(52)(53)(54)(55)(58)

    M i n β m i n
    (52)

    S.T

    j X i j = 1
    (53)

    j X j = P
    (54)

    X i j X j
    (55)

    j ( d i j + d 0 j ) X i j + j ( d 0 l + d l m ) X m l β m i n     i < m , j 1
    (56)

    j ( d i j X i j + d m j X m j ) β m i n
    (57)

    X i j { 0 , 1 }
    (58)

    In this model, equation (56) is a state that β_min is at least as large as the length of this path. If the nodes i and m are assigned to the hub, then the length of this path is dij + dmj, so, according to equation (57), β_min cannot be less than this value. The rest of the equations are like previous models.

    4.5. Problem Solving Algorithms

    O’Kelly (1987) proposed two heuristic methods to solve the problem of the allocation of a single hub location. In the first heuristic method, each node was assigned to the nearest hub. Okly also knew that when the value of α was considered zero, the third part of equation (6) would be zero and the problem would be reduced to the P-median model. This method only applies if α is 0.5. In the second heuristic method, all paths are analyzed to the allocation of non-invariant nodes to the first or second node of a tight hub. If we have N nodes and P, then the number of paths ahead of us is N! / P! N! is. For each path N! / P! N! all 2^(N-P) paths are assigned to the assignment of non-hub nodes to the first or second node of the hub close to the predetermined. Increasing the number of time-resolving nodes increases as well. Also, the result of the second heuristic method is better than the first heuristic method, since the second heuristic is a more precise boundary than the first heuristic on the target function.

    4.6. Genetic Algorithm

    Genetic Algorithm is an algorithm for finding optimal solutions in vast spaces. That’s why the name of this algorithm is inspired by the population genetics.

    Greedy heuristic algorithm

    The greedy algorithm was first used by Sasaki et al. (1999) to solve the problem of multiple allocation of unplanned hubs. A stop means to move between each source-destination pair, only one hub can be passed. The application is for small networks such as Japan’s domestic airline network.

    Model Solving Formulas

    Formulas presented for the single allocation problem Campbell (1994a) proposed a linear integer programming model with n ^ 4 + n ^ 2 + n variables and n ^ 4 + 2n ^ 2 + n + 1. He helped liberate linear planning to solve it.

    Skorin-Kapov et al. (1996) presented a complex integer model in which the number of variables n ^ 4 + n ^ 2 and the linear constraints to 2n ^ 3 + n ^ 2 + N + 1 were changed. Furthermore, it was proved that the new model almost always gives integer solutions by using linear regression liberation.

    O’Kelly et al. (1996) proposed a formula that reduced the number of variables and constraints when the unit cost of the flow was symmetric and proportional to the distance traveled.

    Formulas presented for multiple allocation problems Ernst and Krishnamoorthy (1996) presented a new formula for the multiple assignment problem based on the idea that the answer to this question could be a good initial answer to the one-time allocation problem posed in 1996. This new formula has 2n ^ 3 + n ^ 2 + n variables, where n is an integer. The number of constraints is also 4n ^ 2 + n + 1.

    In Table 1 and Table 2, the tasks performed with the unknown number of the axis and the tasks performed with the specified number of axes are specified (Farahani and Hekmatfar, 2009; Farahani et al., 2013).

    When a hub is installed, it may have effects on traffic generated, which is known as the hobby effect. Regardless of the impact of the hub on traffic generated, there is no reason to take advantage of the economies of scale. For example, in airline networks, the impact of a hobby on passenger comfort is a critical issue for decision- makers. There is no research in this article in previous articles, this can be an important issue for future work (Farahani et al., 2013). Table 3-4

    In some applications of hubs, such as international airlines, fast delivery of other packaging systems and other distribution systems and communication systems (such as satellite communications signals to a number of widely distributed ground receivers) are thought to be thought. Existing facilities cover a fairly wide range of regional services. Hence, the grid and discrete domain assumptions of the answer domain are no longer applicable. Therefore, formulating this problem on airlines is an important assumption and it is more realistic to adopt these. And so far no research has ever been done in recent years (Farahani et al., 2013).

    5. CASE STUDY

    One of the most important food imports to Iran is rice. In general, imported rice comes from Pakistan. Six cities in the country are the main consumers of rice in Pakistan (Mashhad, Birjand, Zahedan, Kerman, Yazd, and Shiraz). Our goal is to minimize all costs by building a hub. In this case, the costs include the fixed annual cost of the hub and the cost of switching between the nodes. All information is provided in the following tables.

    If each city is selected as a hub, they will have a fixed cost per year, as described in the table below (Costs are in rbls).

    Modeling and problem solving:

    To model the problem, the classic Hub Locator model has been used to add an annual fixed cost.

    Model Inputs:

    • H : Stream (distance) between nodes i to j.

    • ij C : Cost of switching from node i to j. Here is the cost of the unit.

    • F : Annual fixed cost.

    Model Inputs:

    • H : Stream (distance) between nodes i to j.

    • ij C : Cost of switching from node i to j. Here’s oneunit cost.

    • F : Annual fixed fee. Decision variables:

    • Xij : If node i uses the hub j, the value of one, otherwise, is zero.

    • j Y : If node j hub takes a value of one.

    Problem Model:(59)(60)(61)(62)(63)

    M i n i = 1 n j = 1 n h i j c i j x i j +   i = 1 n f i y i
    (59)

    S.T

    i = 1 n y i = 1
    (60)

    X i j = y j
    (61)

    y i   { 0 , 1 }
    (62)

    x i j { 0 , 1 }
    (63)

    Solving model:

    The above model was solved by the exact method in the Lingo software and its output is as follows:

    Based on the results, Kerman was considered as a hub. Table and Figure 5-3

    6. CONCLUSION

    In the context of hub placement, the service that is performed involves the movement of individuals, goods or information between a source location and a destination location. The use of these facilities will ultimately lead to the optimal organization of movements and the avoidance of additional traffic, which will have the benefits of reducing fuel consumption, reducing air pollution, reducing depreciation and increasing the life of the road network, etc.

    Usually, in cases where the number of axes is unknown, the genetic algorithm method (depending on the nature of this algorithm) is used to determine the number of axes, and subsequent phases are performed with other algorithms. This suggests the applicability of the genetic algorithm in solving such problems. In the allocation phase and the determination of axes, the banning search algorithm is usually more appropriate.

    In cases where the number of axes is known, heuristic approaches are usually used. For large-scale issues, they have gone. The use of meta-curriculum is also appropriate if it fits perfectly with the conditions of the problem. However, methodological methods may be used only to generate the initial answer for the exact algorithms required. In this case, the need for adaptation to the conditions of the problem does not matter much, but if the methodologist expects the appropriate answer to the problem, this adaptation is needed.

    In summary, it can be said that location-based problems are not a part of the classic problem of locating. In fact, these issues are below a set of network optimization issues for this reason. According to its application, in practice, for each model that is located in a discrete classical location, location-based axis models are presented.

    7. FUTURE RESEARCH

    In the subject literature, all models used a target function while several target functions could be considered. As noted above, the exact solution methods are not capable of solving problems with 100 nodes and no more than 3 axes; hence, it is necessary to propose ways to solve these problems in order to find the optimal solution. On the other hand, when things get closer to reality and become more practical, they become more complicated. In this case, it is necessary for them to provide modeling and appropriate resolution methods.

    The following areas can be used for the future studies:

    • Investigating multiple goals

    • Introducing new mathematical models for simpler and faster solutions

    • Providing precise problem-solving methods for larger issues

    Making the existing issues closer to functional issues

    Figure

    IEMS-17-588_F1.gif

    The main consumers of Pakistani rice.

    IEMS-17-588_F2.gif

    Lingo software output.

    IEMS-17-588_F3.gif

    Hub determination.

    Table

    Work done for hub location problems with an uncertain number of axes

    Work done for hub location problems with a specified number of axes

    Distances between cities: (distances in km based on ground distance)

    Fixed cost per year

    Lingo software’s provided info

    REFERENCES

    1. Abdinnour‐Helm, S. (2001), Using simulated annealing to solve the p-Hub median problem , International Journal of Physical Distribution & Logistics Management, 31(3), 203-220.
    2. Abdinnour-Helm, S. and Venkataramanan, M. A. (1998), Solution approaches to hub location problems , Annals of Operations Research, 78, 31-50.
    3. Adler, N. and Hashai, N. (2005), Effect of open skies in the middle east region , Transportation Research- Part A: Policy and Practice, 39(10), 878-894.
    4. Alumar, S. and Kara, B. Y. (2008), Network hub location problems: The state of the art , European Journal of Operational Research, 190(1), 1-21.
    5. Aykin, T. (1996), Optimal shift scheduling with multiple break windows , Management Science, 42(4), 591-602.
    6. Boland, N. , Krishnamoorthy, M. , Ernst, A. T. , and Ebery, J. (2004), Preprocessing and cutting for multiple allocation hub location problems , European Journal of Operational Research, 155(3), 638-653.
    7. Bryan, D. L. and O Kelly, M. E. (1999), Hub and spoke networks in air transportation: An analytical review , Regional Sciences, 39(2), 275-295.
    8. Campbell, J. F. (1991), Hub location problems and the p-hub median problem , Center for Business and Industrial Studies, 44(6), 843-1019.
    9. Campbell, J. F. (1994a), A survey of network hub location , Studies in Locational Analysis, 6, 31-49.
    10. Campbell, J. F. (1994b), Integer programming formulations of discrete hub location problems , European Journal of Operational Research, 72(2), 387-405.
    11. Çetiner, S. , Sepil, C. , and S ral, H. (2010), Hubbing and routing in postal delivery systems , Annals of Operations Research, 181(1), 109-124.
    12. Contreras, I. , Cordeau, J. F. , and Laporte, G. (2012), Exact solution of large-scale hub location problems with multiple capacity levels , Transportation Science, 46(4), 439-459.
    13. Elhedhli, S. and Hu, F. X. (2005), Hub-and-spoke network design with congestion , Computers & Operations Research, 32(6), 1615-1632.
    14. Ernst, A. T. and Krishnamoorthy, M. (1996), Efficient algorithms for the incapacitated single allocation p-hub median problem , Location Science, 4(3), 139-154.
    15. Farahani, R. Z. and Hekmatfar, M. (2009), Facilities location: Concepts, models, algorithms and case studies, Heidelberg, Springer.
    16. Farahani, R. Z. , Hekmatfar, M. , Arabani, A. B. , and Nikbakhsh, E. (2013), Hub location problems: A review of models, classification, solution techniques, and applications , Computers & Industrial Engineering, 64(4), 1096-1109.
    17. Hakimi, S. L. (1964), Optimum locations of switching centers and the absolute centers and medians of a graph , Operations Research, 12(3), 450-459.
    18. Klincewicz, J. G. (1996), A dual algorithm for the uncapacitated hub location problem , Location Science, 4(3), 173-184.
    19. Liang, H. (2013), The hardness and approximation of the star p-hub center problem , Operations Research Letters, 41(2), 138-141.
    20. Martí, R. , Corber n, A. , and Peir , J. (2015), Scatter search for an uncapacitated p-hub median problem , Computers & Operations Research, 58, 53-66.
    21. Meyer, T. , Ernst, A. T. , and Krishnamoorthy, M. (2009), A 2-phase algorithm for solving the single allocation p-hub center problem , Computers & Operations Research, 36(12), 3143-3151.
    22. Nagy, S. and Salhi, S. (1998), The many-to-many location-routing problem , Top, 6(2), 261-275.
    23. O’Kelly, M. E. (1992), Hub facility location with fixed costs , Regional Science, 71(3), 293-306.
    24. O’Kelly, M. E. (1987), A quadratic integer program for the location of interacting hub facilities , European Journal of Operational Research, 32(3), 393-404.
    25. Peiró, J. , Corber n, A. , and Mart , R. (2014), GRASP for the uncapacitated r-allocation p-hub median problem , Computers & Operations Research, 43, 50-60.
    26. Pirkul, H. and Schilling, D. A. (1998), An efficient procedure for designing single allocation hub and spoke systems , Management Science, 44(12), S235-S235.
    27. Sasaki, M. , Suzuki, A. , and Drezner, Z. (1999), On the selection of hub airports for the airline hub and spoke system , Computers & Operations Research, 26(14), 1411-1422.
    28. Skorin-Kapov, D. , Skorin-Kapov, J. , and O Kelly, M. (1996), Tight linear programming relaxations of uncapacitated p-hub median problems , European Journal of Operational Research, 94(3), 582-593.
    29. Smith, K. , Palaniswami, M. , and Krishnamoorthy, M. (1996), A hybrid neural approach to combinatorial optimization , Computers & Operations Research, 23(6), 597-610.
    30. Sohn, J. H. and Park, S. S. (2000), The single allocation problem in the interacting three‐hub network , Networks, 35(1), 17-25.
    31. Topcuoglu, H. , Corut, F. , Ermis, M. , and Yilmaz, G. (2005), Solving the uncapacitated hub location problem using genetic algorithms , Operational Research, 32(4), 967-984.
    32. Yaman, H. and Elloumi, S. (2012), Star p-hub center problem and star p-hub median problem with bounded path lengths , Computers & operation Research, 39(11), 2725-2732.
    33. Yildiz, B. and Karaşan, O. E. (2015), Regenerator location problem and survivable extensions: A hub covering location perspective , Transportation Research Part B: Methodological, 71, 32-55.
    오늘하루 팝업창 안보기 닫기