Warehouse location problem

The Warehouse Location Problem (WLP), also known as Uncapacitated Facility Location Problem (UFLP) or Simple Plant Location Problem (SPLP), is a discrete location problem that occurs primarily in logistics . There are several possible locations for one or more warehouses from which different customers are to be supplied. The locations of the customers and the quantities of goods they require are already known. It is asked at which of the locations one should set up storage facilities. With many regionally distributed warehouses, the transport costs are generally lower because the distances to the customers are shorter. But the cost of building these camps is high. With a few camps (in the extreme case only one) it is exactly the other way around. Mathematical modeling enables a solution through exact procedures or a heuristic solution search.

Basic assumptions

In the simplest case, it is important to supply a large number of customers with a good at the beginning of a period . For this purpose, warehouses can be opened from a number of possible locations . Be that crowd. Opening a location results in certain fixed costs . The costs of supplying the customer by location can be represented by a cost matrix. are the costs of the transport from to . ${\ displaystyle I = \ {1, \ ldots, n \}}$ ${\ displaystyle J = \ {1, \ ldots, m \}}$ ${\ displaystyle j}$ ${\ displaystyle f_ {j}}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle c_ {ij}}$ ${\ displaystyle j}$ ${\ displaystyle i}$

This can be modeled with an objective function to be minimized and its constraints. It should be noted that the weighting factor is between 0 and 1 and indicates the proportion to which the customer is supplied by the location , while a binary variable represents whether the warehouse is needed at all. ${\ displaystyle x_ {ij}}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle y_ {j}}$ ${\ displaystyle j}$

Then the expression

{\ displaystyle \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {m} c_ {ij} x_ {ij} + \ sum _ {j = 1} ^ {m} f_ { j} y_ {j}}

to be minimized under the constraints:

{\ displaystyle \ forall i \ in I \ colon \ quad \ quad \ sum _ {j = 1} ^ {m} x_ {ij} = 1}

{\ displaystyle \ forall i \ in I \ quad \ forall j \ in J \ colon \ quad \ quad 0 \ leq x_ {ij} \ leq y_ {j} \ in \ {0,1 \}}

Possible solutions

The problem can be solved with the help of operations research methods . This includes enumeration (for example through branch-and-bound ) or the use of heuristics to determine a not necessarily optimal (approximate) solution.

The WLP is NP-difficult . There are already possible partial quantities for the decision as to which warehouse should be opened (because you need at least one warehouse). If more than one warehouse is set up, it must also be specified for each customer what proportions he will be supplied from which warehouse. In principle, this opens up infinite possibilities, so that a complete listing is not possible, but you can also choose by supplying each customer from the warehouse with the lowest transport costs. ${\ displaystyle 2 ^ {m} -1}$ ${\ displaystyle x_ {ij} \ in \ {0,1 \}}$

The use of branch-and-bound algorithms ( e.g. DuaLoc from Erlenkotter) is a frequently used solution method. These work with the help of a decision tree and, at least under favorable circumstances, can very quickly determine the best solution.

A heuristic approach will not necessarily find the optimal solution. However, it is often preferred because it works much faster. The ADD and DROP algorithms (both greedy algorithms ) are simple examples , with the help of which an initial solution for the WLP can be found. These two methods are often used in combination.

example

A company has identified three possible locations for a warehouse.

The cost matrix is: ${\ displaystyle c_ {ij}}$ ${\ displaystyle {\ begin {pmatrix} 0 & 2 & 3 \\ 4 & 0 & 3 \\ 2 & 3 & 0 \ end {pmatrix}}}$

The fixed costs are , and . ${\ displaystyle f_ {1} = 10}$ ${\ displaystyle f_ {2} = 12}$ ${\ displaystyle f_ {3} = 8}$

This data can be interpreted as follows: The supply of customers by location with produces no transportation costs. In this case, the warehouse and the customer may be in the same place. The opening of three warehouses is still not optimal as the fixed costs would be. In this simple example, it would be optimal to select location 3, since the sum of the transport costs (5) and the fixed costs (8) for this problem is minimal. ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle i = j}$ ${\ displaystyle F = 10 + 12 + 8 = 30}$

literature

Barahona, Chudak: Solving Large Scale Uncapacitated Location Problems. 2005.
Domschke, Drexl: Logistics: Locations. 1996.
Love, Morris, Wesolowsky: Facilities Location: Models and Methods. 1988.

Individual evidence

^ Jens Lindemann: Location planning of internationally operating companies. (PDF; 2.6 MB) Dissertation at the University of Hamburg. September 9, 2006, accessed February 20, 2015 .

[1] Jens Lindemann: Location planning of internationally operating companies. (PDF; 2.6 MB) Dissertation at the University of Hamburg. September 9, 2006, accessed February 20, 2015 .