Studies on Single-Source Capacitated Facility Location Problem of Two-Echelon

Studies on Single-Source Capacitated Facility Location Problem of Two-Echelon

Sari Artauly Silitonga, Wenny Ernawati Sihombing and Lamtiur Sinambela

Graduate School of Mathematics, University of Sumatera Utara

Abstract Facility location problem is an important part of integer programming problems, with application in the field of telecommunications, and transportation industry. This thesis discussed the facility location problem with two echelon. Each second echelon facilities have limited capacity and can only be supplied by a facility on second echelon. Each customer is served only by a single facility in second echelon. The number and location of the second echelon of customers to facilities determined echelon two simultaneous. This study addresses the question of decision-making in designing cargo distribution system where there is a two-echelon distribution system the two-level structure, components and issues related decisions. The purpose of the model in this study is to determine the location of the facilities at each echelon which is a distribution facility and cargo capacity at the facility so that can minimize the total cost of the minimum as the optimal solution of the modeling.

KeywordsCFLP, integer programming, optimization, two echelon

1. INTRODUCTION

   Coordination between existing facilities in a supply chain distribution of production activities is an important issue in determining the obtained optimal profit. We need a policy or an effective model to ensure that the used system is the optimal system to cover the level consumer demand in the competitive market conditions at this time. The basic idea of optimizing both operating costs and the cost of consumer facility was first introduced by [1]. Later, [2] provide a model based on the production rate with some rules of the company. The model then extended by [3] and successfully developed a framework for improving the availability of the model on production-distribution activities where existing facilities consist of single facility and single consumer. Furthermore, [4] describes a rule Consignment Stock (CS) on the issue of setting a model of an enterprise inventory (VMI) and indicates that the rule has a performance better than the uncoordinated optimization models. The model developed has been implemented for a single industry case in situations where the buyer is a buyer's double.

   Facility location problem, supply chain and chosen the feasible facilities problem is a common issue that has been discussed in operational research area. In this study, it is assumed there is a supply chain consist of a main facility and the point of consumer demand is assumed to be a deterministic demand function. The purpose of the model is

   to obtain and determine the location of the influenced by the number of facilities with a capacity of two types of facilities, in other word, echelon of two different types that used in facility location and routes that exist in each echelon. This study is based on the decomposition of Tabu Search seen as a problem of allocating two routes where each route decomposed into a limited facility location problems. In a facility location problem is not capacity, it is assumed that each facility has no limit on the capacity of the facility. for this case, each consumer demand can be met right from the facility. The development of this issue, where the issue involves two echelons on facility, the facility location problem is not capacity of two echelons. This issue discusses the supply chain inventory with the delivery process of the facility in the first echelon to the point of consumer demand through the facility in second echelon. Objective function as the purpose of modeling this problem is determine the number of facilities in each echelon location, the flow of product distribution between facilities at different echelons and determining the distribution of consumers to facility in the second echelon. For the capacity of the facility location problem, each facility has a certain capacity constraints. A case of this issue is a point where there is unmet consumer demand right only of the facility, which is known as the problem of the location of the source facility. This study has been discussed previously by [5].

   This study addresses the decision-making in designing cargo distribution system where there is a two-echelon distribution system the two-level structure, components and issues of related decisions. The obtained results are formulated in a mixed integer programming form as a two- echelon location problem. The purpose of this study is to determine the location of the facilities at each echelon of a distribution facility and cargo capacity at the facility with the aim is to minimize the total cost as the optimal solution of the modeling. Some constraints are used in the model where each facility is in echelon. This study unfold as follows. In Section 2 discussed some of the literature and study of theory relating to the issue of two-echelon facility location models. Chapter 3 describes the modified model of the location two echelons of facilities at the cargo distribution systems with conclusions and suggestions is given in Chapter 4.

2. REVIEWS OF TSCFLP MODEL

   Many heuristic algorithms and the approach taken to TSCFLP which has been proposed in the literature. Completion method and algorithm heuristic approaches have been proposed by [6], then with a heuristic relaxation Lagrangian by [7]. Various heuristic approaches and appropriate solution to TSCFLP one of which is the Lagrangian relaxation. The issue Capacitated Facility Location Problem (CFLP) is part of the facility location problem which includes the capacity for the facility. The issue of the location of the facility capacity is also known in combinatorial optimization problem which is applied in facility opening of a set so that customers can minimize operating costs and transportation. Given the capacity of a facility cannot be serve any demand at the facility. In this case needs to be done restrictions that meet the demand of each customer. and each supply facilities cannot exceed the capacity of the facility is opened. CFLP Applications include planning, distribution, location and area planning

   implemented and the results show that the Lagrangian heuristic gives the limit under which much better than those obtained from the linear programming relaxation. Get a feasible solution limits the upper limit can also be done efficiently. The Branch and Bound indicates that the algorithm is based on Lagrangian relaxation is an efficient approach. The issue of the two-echelon of capacitated facility location is an extension of the issue of the capacity facility location source. In this issue first of all put the facility and the second echelon simultaneous manner, where each facility has a capacity in the second echelon limited and can be supplied by only one facility in the first echelon. Each customer is served by only one facility in the second echelon. The first facility as the depot and later referred to as the second echelon facilities just as facilities so that we have the facilities, depots and formulate the consumer. For the issue of the two echelon of the capacity facility location source there is some symbol or notation to note:

   production, and in the design of telecommunications networks [8].

   CFLP contains of a set of m, any potential location with capacitated facility, and n, is the total covered consumer demand at any available facility. For example, given a set

   I {1,, m}

   K {1,, o}

   a j

   bi fik

   : set of total consuer at any location

   : set of any potential facilities

   : consumer demand j, j J

   : capacity of facility i, i I

   : cost of facility i to potential facility k,

   J (1, 2,3,,m) is the total number of facilities with

   i I, k K

   i J with capacity ai and K (1, 2,3,, n) is the total

   c : cost of consumer j from potential

   number of consumer with the demand rate, b j , and J K .

   The facility cost of facility i, fi, and cij is the transportation cost from i to j. xj represents total flow of facility i to

   ijk

   gk

   facility k

   : cost of potential facility at k

   consumer j. Flow of facility i to consumer j denoted as

   arc(i,j) and variable yi that defined as follows:

   and for the decision variable, they used

   i 0; otherwise

   y 1; if the facility is open

   Thus, the CFLP is formulated as

   Z min ckj xkj f j y j kK jJ jJ

   (2.1)

   yik

   xijk

   zk

   1; if the facility i is open at k

   0; otherwise

   1; if the facility i at k is covered consumer j

   0; otherwise

   1; whether potential facility at k

   Z is a function with purpose is to cover the demand of each customer and facility constraints in supply of all customers

   Lagrangian relaxation combined with subgradien optimization is one of the most widely used approach in determining the solution for combinatorial problems. Details and the application of Lagrangian relaxation proposed by [9] and [10]. It has been widely used

   0; otherwise

   Thus, this problem is formulated as follows

   P min cijk xijk fik yik gk zk

   iI kK jJ iI kK kK

3. OUR MODELS

   (2.2)

   techniques in solving several variants of the problems location facilities. Including the location of facilities with a capacity not raised by [11]. The issue of the location of the capacitated facility discussed by [12] and issue of the source of the facility location and capacity by [13], [8], [14], [15] and [4]. [5] Considering six different Lagrangian heuristic to resolve TSCFLP. All heuristics are

   This study provides a model formulation to the problem

   as a facility location decision-making process so as to obtain an optimal solution approaching from the existing objective function. This study is divided into two issue. First, determine the description of the distribution system cargo at a facility with a capacity of two echelons. And second, to develop a program mixed-integer programming

   as the basic idea in determining the model formulation two- echelon facility location problems. Constraint as a boundary problem in this modeling is that each facility is on the second echelon has supply is limited and can only be supplied by the facility back to the first echelon. The model

   T {t} : set of number of vehicle at first echelon

   V {v} : set of number of vehicle at second echelon

   fi : given value of capacitated facility at i P S

   F : cost of facility at i P S

   can be used in determining the location of the facility in each echelon which is the capacity of facilities and distribution of cargo on facilities. The purpose or objective function of the model is to minimize the total cost of the minimum as the optimal solution of the modeling.

   In the cargo distribution systems in facilities with a capacity of two echelons, there some of the definitions, limitations and mathematical notation used in this research.

   vi Vi Cij

   Dz Li

   : given value of capacitated vehicle at i T V

   : cost of vehicle at i T V

   : transportation cost from i to j

   : demand point at any location, z Z

   : a nonnegative continuous variable that ensure at least one of facility i at S is subset of facility at P

   Some of the definitions we used are as follows.

   1. The first facility is a major facility that has greater capacity than the second facility. The facility is assumed to have been allocated away from the point

      Then, we also used some decision making process of

      chosen the location and assignment of the vehicles from each echelon with the available capacitated facility by using 0-1 integer programming as follows.

      of consumer demand. In this study, it is assumed that there are constraints in the distribution of cargo in the first facility with the vehicle in the first echelon;

      1; if i precedes j at first echelon by t

      rt

      ij

      0; otherwise

      (3.1)

   2. The second facility has a lesser capacity of supply and

      xv 1; if i precedes j at first echelon by v

      (3.2)

      the cargo distribution is only for the second echelon of the first facility;

   3. For the final object of the chain cargo distribution system, consumers are the end point of the system with the assumption that the process of delivery to the

   ij

   wsz

   0; otherwise

   1; if consumer z distributed to s

   0; otherwise

   (3.3)

   consumer must be covered at least by one of the first or second echelon.

   Based on the purpose of this study, given some assumptions as follows.

   y 1; if facility is available at location i

   i 0; otherwise

   1; if vehicle at location i is available

   (3.4)

   ui

   of any echelon

   (3.5)

   1. It is assumed that the discrete demand of each consumer is given;

   2. All cargo distribution system begins with the first facility, the main facility of the distribution system.

      0; otherwise

      Thus, we can formulated our model as follows.

      Vehicles in the first echelon do the distribution activities of the first facilities to the vehicle in the

      min v p y p vs ys Vtut

      ij

      pP sS tT vV iS Z jS Z

      Cij xv

      (3.6)

      ij

      second echelon. On the second echelon, cargo distribution system will be distributed it to the consumer as an end point end of the system;

      s.t

      vV iPS jPS

      Cij rt Fi yi

      x

      zj

   3. Each both first and second facility facilities has its capacity, with assumption that the first facility has a greater capacity than the second.

   vV jS Z

   v 1,z Z

   (3.7)

   x

   x

   v v

   lj jl

   0,j Z S,v V

   (3.8)

   1. Some Notations

      lS Z lS Z

      ij

      Assume we have an undirected graph, G (N, A) with

      N {P S Z} and

      Li L j (| S | | Z |)

      Li L j (| P | | S |)

      xv (| S | | Z | 1), i, j Z S,i j

      vV

      rt (| P | | S | 1),i, j S P, i j

      (3.9)

      (3.10)

      P {p} : set of any available first facility

      ij

      vV

      S {s}

      : set of any available second facility t

      (3.11)

      f

      0

      ps

      Z {z} : set of given consumers

      The objective function (3.6) is to minimize total cost of both first and second facility location due to cost of vehicle and transportation capacity of the two echelon. Constraint (3.7) shows that for each demand consumer z, is covered exactly one by vehicles at second echelon, v. Eq. (3.8) shows that for each vehicles, v, exists some arc at location i. Eq. (3.9) gives the constraint of capacity from first echelon to second echelon. Eq. (3.10) is constraint of first facility and Eq. (3.11) represents any extended and nonnegative constraint in the model.

4. CONCLUSIONS

In this paper we propose a new model of the facility location with a capacity of the two echelons with single source. This problem is include NP-hard problem and it is formulated by a mixed integer programming formulation and applied it with a heuristics method. Th obtained model can be used on the facility location problem of the system with the application to the cargo distribution facility capacity by considering the presence of two echelon in the facility.

REFERENCES

1. Goyal, S.K. An integrated inventory model for a single supplier- single customer problem. International Journal of Production Research, Vol.15 (1976), pp.107-111

2. Banerjee, Al. A joint economic-lot-size model for purchaser and vendor: A comment. Decision Science, Vol.17 . (1986) , pp. 293- 311.

3. Zavanella, L. dan Zanoni, S. A one vendor multi-buyer integrated production inventory model: The consignment stock case. International Journal of Information and Management Sciences, Vol.20 (2009), pp. 217-223.

4. Barcelo, J and J. Casanovas. A heuristic Lagrangian algorithm for the capacitated plant location problem. European Journal of Operational Research, Vol. 15 (1984), pp. 212-226.

5. Holmberg, K. An exact algorithm for the capacitated facility location problems with single sourcing. European Journal of Operational Research, Vol. 133 (1999), pp. 544-559.

6. Tragantalerngsak, S. An exact method for the two-echelon, single source, capacitated facility location problem. European Journal of Operational Research, Vol. 123 (2000), pp. 473-489.

7. Aikens, C.H. Facility location models for distribution planning. European Journal of Operational Research, Vol. 22 (1985), pp. 263-279.

8. Fisher, M.L. The Lagrangian relaxation method for solving integer programming problem. Management Science, Vol. 27 (1981), pp. 1-18.

9. Geoffrion, A.M. Lagrangian relaxation for integer programming. Management Science, Vol. 27 (1974), pp. 82-114.

10. Laporte, G. Location-routing problems. In: Methods and Studies. NorthHolland, Amsterdam, (1988), pp: 163-198.

11. Balas, E. and E. Zemel. An algorithm for large zero one knapsack problems. Operations Research, Vol. 28 .(1980), pp. 1130145.

12. Christofides, N and J.E. Beasley. Extensions to a Lagrangian relaxation approach for the capacitated warehouse location problem. European Journal of Operational Research, Vol. 12 (1983), pp. 19-28.

13. Beasley, J.A. An algorithm for solving capacitated warehouse location problems European Journal of Operational Research, Vol. 33 (1988), pp. 314325.

14. Wu, K.S. dan Yen, H.F. On a note on the economic lot size of the integrated vendor buyer inventory system derived without derivatives. International Journal of Information and Management Sciences, Vol.20 (2009), pp. 217-223.

15. Beasley, J.A. Lagrangian heuristic for location problem. European Journal of Operational Research Vol. 65 (1993), pp. 383399.