Author: Dr. Jean-Paul Rodrigue

Location-allocation models look at assigning optimal location choices for facilities considering the distribution of the demand.

1. Context

Location-allocation models are designed to assess the most suitable location for a single or group of facilities to serve a defined demand. This demand is often expressed as a distribution of discrete points that can be of equal or different value. The model can be considered from two different perspectives:

• Location: The most suitable location(s) considering the demand distribution. Suitability is commonly the outcome of minimizing transportation costs, often using distance as a proxy.
• Allocation: The most suitable allocation of flows from points of distribution to points of demand. As for location, suitability is commonly the outcome of minimizing transportation costs. Some demand points may turn out to be unserviceable.

Location-allocation models consider factors such as the number of facilities (single or multiple), the cost of building and maintaining these facilities, their capacity or size, the variability of the demand, and the impedance between facilities and demand points.

2. The P-Median Problem

A core approach to location theory involves the p-median problem. It aims to locate a p number of facilities (at least one) to minimize the demand-weighted average cost or distance between demand nodes and the selected facilities(s). Most p-median problems can be considered from three perspectives:

• Number of facilities. Simple problems consider locating a single facility such as a new store or distribution center. More complex problems consider a multitude of facilities and demand locations.
• Number, nature and distribution of locations to be served. A demand point can be a single discrete location or the centroid of an area. Simpler problems consider a relatively small number of uniformly distributed demand points. Complex problems consider a large number of demand points having different characteristics.
• Type of impedance. Simple problems consider Euclidean distance, while complex problems consider impedance through navigation within an existing transportation network that can include several modes.

Weber’s industrial location problem is the earliest form of a p-median approach as it seeks to find an optimal location based on three considerations; two sources of supply and a market. The goal is to minimize the total transport cost, which should point to a single optimal location.

3. Linear Programming Method

Linear programming aims to minimize an objective linear function subject to constraints, which has a wide array of applications. For transportation problems, it involves an allocation that considers several origins and destinations to optimize a solution by minimizing transport costs with fixed demand, origins, and destinations. It considers linear transport costs, known surpluses (origins), demands (destinations), and possible paths. Linear programming, consequently, is relevant to the field of logistics, as it enables assessing an optimal distribution system that can help set or improve a real-world distribution system. The linear programming formulation for a distribution problem is basically expressed as follows:

Where Q(a,b) is the traffic between origin a and destination b, and g is a cost function. So g(Q(a,b)) is the transport cost related to traffic Q(a,b). This equation aims to minimize the summation of transport costs of each origin-destination pair. The traffic of each pair must be superior or equal to 0 (rule of non-negativity).

4. Allocation Demonstration

A supply chain manager is considering a distribution system between warehouses (A, B, and C) and customers (W, X, Y, and Z) and wishes to minimize global transport costs. The first issue concerns the generation of demand and supply matrices, where the number of units produced and consumed is the same, implying a market equilibrium. Any additional unit being produced would not be transported because there is no additional demand, and any additional demand will not be transported because there is no additional supply. The transport cost matrix (C) in dollars per unit transported between warehouses and customers is also available.

For instance, it costs $20 to transport 1 unit from warehouse A to customer W. In the above figure, each warehouse and customer is a node, and each transport cost pair is a vector. With the data provided, linear programming can find an allocation with minimal transport cost. (Note: this problem can also be solved using the “Solver” add-in in Excel). Below is the heuristic method where relatively simple problems (matrix of about 5 by 5) can be solved.

The first step is to order the transport costs for each cell by beginning with the lowest, which has a rank of 1, to the highest. The same rank is assigned to cells having equal costs. The outcome is a cost ranking matrix (R). In this matrix, take the cell with the lowest transport cost. In this case, it is the C-W cell ($10 per unit). Allocate the highest possible number of units to this cell. Subtract this number from the number of surpluses and demands for the respective row and column. Continue the same procedure by rank order until all surpluses are used, and all demands are answered (origins and destinations having 0). The result is the allocation matrix (A), representing the flows between the warehouses and the customers. Calculate the transport costs of this assignment by multiplying the flow of each cell in the allocation matrix by its related unit cost in the transport cost matrix (C*A). The total transport cost of this allocation is $153,000.

The estimation costs matrix (E) must be built to find if this allocation is the least cost distribution. This process is stepwise. First, write down the transport cost per unit in each cell used in the allocation and leave the other cells blank. Second, put a value of 0 to the summation of the first row (row A) (E1). Third, use the value(s) of each cell in row A to find the summation of each column with a value. For this example, only cell A-W has a value (40), which means that the value 40 must be placed in the summation of column X (0 + 40 =40) (E2).

Fourth, to summate the remaining rows and columns, enter the difference between column 1, row 1 and column 1, row n where n is the number of the current row. For the example, the next step would be to fill the summation cell of row B with the value of 20 since cell B-X has a value of 60, and the value of 40 is already in the summation cell of column X (E3). Fifth, continue the procedure until all the empty cells are filled, and keep in mind that cells must be the summation of the values at the summation of their respective rows and columns. The outcome is the completed estimation costs matrix (E’).

The next step compares the estimation costs matrix (E’) and the transport cost matrix (C). There can be only two alternatives to this comparison:

• First, if the estimation costs are higher than the real costs. In this case, the solution is not optimal, and a readjustment is necessary.
• Second, if the estimation costs are equal to or smaller than the real costs. In this case, no readjustments are necessary since the assignment is optimal; therefore, a solution has been found.

In this example, cell A-W in matrix E’ has higher estimation costs (50) than real costs (20). Cell A-Z also has higher estimation costs (60) than real costs (50). This assignment is not an optimal solution, and a readjustment is thus necessary.

If a readjustment is necessary, choose the cell with the highest difference between its estimation and real costs. If two cells have equal differences, choose the cell with the smallest real costs. In this example, it is cell A-W having a difference of 30. Cell A-Z has a difference of only 10.

Readjustments are done by transferring values between cells (partial or full flows). They are performed according to three rules.

• First, transfers are done along a circuit from an unused cell by altering vertical and horizontal stages and using only occupied cells.
• Second, each transfer is the exact opposite value of the other.
• Third, the value of a transfer is determined by the maximum value that all cells could subtract while respecting the supply and demand constraints. For instance, 400 is the highest readjustment possible in cell A-W because cell A-X cannot subtract more since it would exceed the supply constraint of row A (warehouse A supplies 400 units).

The outcome is a new traffic allocation matrix (A’) and its associated transport cost matrix (C*A’).

The transport cost of this new allocation is $141,000, which is lower than the initial figure of $153,000. To confirm if this is the optimal cost, the estimation costs matrix is again generated (E”). No cell in this matrix has estimation costs higher than real costs. The solution is thus optimal ($141,000 is the minimal cost).

References

Daskin, M.S., Maass, K.L. (2015). The p-Median Problem. In: Laporte, G., Nickel, S., Saldanha da Gama, F. (eds) Location Science. Springer, Cham. https://doi.org/10.1007/978-3-319-13111-5_2