LOCATION ALLOCATION MODELLING

Introduction

Dr. Sanjay Kumar Ghosh

Professor Department of Civil Engineering
Introduction
• Facility location problem (FLP) deals with the question of how to select from a given
set of potential locations, a cost-effective subset of sites to place new facilities or retain
existing ones.

• A facility could represent any service facility such as an electric power plant, hospital,
food production plant, a warehouse (depot), petrol station, government office, etc.

• FLPs are an essential class of problems in logistic management. Facility location and
the assignment of entities to such facilities usually determine the distribution pattern
and the associated characteristics (e.g., time, cost, and efficiency) of the facility.

• The placement of one or more facilities and the assignment of customers in an optimal
version not only improve the flow of materials and services offered by the facilities to
customers but also utilize the facilities in an optimum manner.
• Thus, it prevents the use of duplicated or redundant facilities.
For larger areas, the Web-GIS oriented technologies
and their applications have been reported in different
fields.

The most common approach for formulating FLP

models is by using integer programming (IP). IP is a
form of linear programming in which some or all the
decision variables are restricted to be non-negative
integer values.

https://schoolgis.nic.in/
GIS And Location-allocation Models In Public Facilities
Planning
1. Buffer Zones: It finds gaps in the urban areas which
cannot be served by the existing facilities. This method
does not take into consideration the distribution of
population, nor does it consider whether the land identified
is suitable for the facility or not.
2. Allocation: This method is like the buffer zone method,
but it takes population distribution into consideration.
However, it requires data to be available in a network
which is often not available in a GIS database.
3. Land Suitability Analysis: is one of the most commonly
used spatial analysis functions in GIS. It identifies sites
according to their suitability for the location of facility under a
set of criteria. Suitable sites are first identified, and they are
then evaluated by using either buffer zones or allocation
method.

However, these GIS methods do not guarantee the optimal

location of facilities.
Location-allocation (LA) models may be used to find the optimal location of facilities
by optimizing one or more of the following objectives:

✓minimum average/total distance,

✓• minimax distance,
✓• equal assignment,
✓• threshold constraint, or
✓• capacity constraint.
Problem types in Location-allocation
➢Minimize impedance

➢Maximize coverage

➢Maximize capacitated coverage

➢Minimize facilities

➢Maximize attendance

➢Maximize market share

➢Target market share

 Classification of problem types
Goal Type Description Applications
Minimize overall Minimize Impedance Facilities are located such that the Locate warehouses
transportation cost (P-Median) sum of all weighted costs between
demand points and solution
facilities is minimized.
Maximize Coverage Facilities are located such that as Locate fire stations
many demand points as possible
are allocated to solution facilities
Maximum Demand within the impedance cut-off.
allocated
Minimize Facilities Facilities are located such that as Locate PHC
many demand points as possible
are allocated to solution facilities
within the impedance cut-off;
additionally, the number of
facilities required to cover demand
points is minimized
 Location-allocation problem types
Goal Type Description Application
Maximize demand Maximize Attendance Facilities are chosen such that as Locate stores without
that diminishes with much demand weight as possible is competitors
distance allocated to facilities.
Maximize Market A specific number of facilities are Locate store with
Share chosen such that the allocated competitors
demand is maximized in the
presence of competitors.
Target Market Share Target Market Share chooses the Locate store with
Maximize Market minimum number of facilities competitors but without
Share necessary to capture a specific budget limit
percentage of the total market share
in the presence of competitors.
Location-Allocation
Example (Emergency Medical Services)

➢Demands
– Single / multi-supply
– Dynamic

➢Supplies
– Capacitated / non-capacitated

➢Cost-function
– Network distance
– Congestion/delay
LOCATION ALLOCATION MODELLING

Models in FLP

Dr. Sanjay Kumar Ghosh

Professor Department of Civil Engineering
Distance Function in Facility Location
• In the process of finding optimal locations for a set of facilities, a remarkable
phenomenon is the pattern of travel distances among service customers.
Customers always appreciate the placement of facilities not being too far from a
service point.

• Usually, these distances are measured over the set Zx with their values in Z.

• Thus, the distance functioned between points x and y denoted as d(x,y) satisfies
the basic properties of a metric distance.
• For a more general notation, the distance function between the points
x= (x1,x2,...,xx) and y=(y1,y2,...,y x) is denoted by dk,p(x,y) and is
called the Minkowski distance of order p and is defined as:

/𝒑
𝒅𝒌, 𝒑 𝒙, 𝒚 − (σ𝒏𝒊=𝟏 |𝒙𝒊 − 𝒚𝒊|𝒑)𝟏
1. Rectilinear distance: (p=1) This distance describes, for instance, the distance that a vehicle will
cover over a square block in a city layout where no one-way routes exist. It is given by

𝑑𝑘, 𝑝 𝑥, 𝑦 − (෍ |𝑥𝑖 − 𝑦𝑖|)

𝑖=1
Since it is simple to analyze distance compared to some other forms of distance, it has become popular
among researchers.

2. Euclidean distance: This is defined for p=2 as follows:

𝑑𝑘 , 𝑝 𝑥, 𝑦 − (෍ |𝑥𝑖 − 𝑦𝑖|2)1/2
𝑖=1
• This is the meter rule distance because it gives exactly what would be obtained if the distance
between two points was measured with a ruler.
3. The Chebyshev distance: is a metric defined on a vector space where the distance between two vectors is
the greatest of their differences along any coordinate dimension.
Thus, from a practical viewpoint, the parameter d k,2 being continuous is widely used because of its rotation
invariance.
This distance is defined for p=∞ as follows:

𝑙𝑖𝑚𝑖𝑡 𝑛 /
𝑑𝑘, 𝑝 𝑥, 𝑦 − 𝑝→0 (σ𝑖=1 |𝑥𝑖 − 𝑦𝑖|𝑝)1 𝑝 - max(∣∣∣x1−y1∣∣∣,...,∣∣∣xn−yn∣∣∣)
• By simple inspection, it is evident that d k,1 and dk,∞ assume discrete values.

• For each category of FLP, there is a corresponding suitable distance function. For instance, in the analytic
models of FLP, the travel distances follow the rectilinear metric.
• In contrast, in network problems consisting of nodes and arcs, distances are measured concerning the shortest
path. The discrete models can usually make use of all kinds of distance functions.
 Classification of location-allocation models
(depending upon objective of the study)
• Location allocation models may be divided into four classes:
❑analytic models
❑network models
❑continuous models
❑discrete models.

• The analytic models are based on assumptions of the fixed costs of locating a facility but
are hardly used to express real-world problems. These models are based on a large
number of simplifying assumptions such as the fixed cost of locating facility. The travel
distances follow the Manhattan metric.

• The network models are frequently encountered in transportation planning and other
applications that allow tours on routes represented on a network.
• FLP are further classified into continuous and discrete problems.
• In the continuous models, facilities to be located are placed anywhere in the
chosen plane and therefore computations are required to determine the best
locations with respect to the distances of the demand points (customers’ locations).
• Furthermore, in continuous location models, customers are grouped (using
appropriate techniques) and the centroid of each group is determined. Each
centroid then becomes the best location for each group (cluster). This approach of
locating facilities is very applicable in highly sensitive strategic planning.
• The classic model in this area is the Weber problem. Distances in the Weber
problem are often taken to be straight-line or Euclidean distances but almost all
kind of the distance functions can be used here.
• In most practical cases, estimates in continuous models make discrete models
become practicable. Discrete models handle the allocation of customers to a set of
potential location points.
• The objective in a discrete model is to select the required number of locations
for facilities from a set of known locations, and then allocate customers to
receive service from exactly one of these facilities at minimum cost.
• Discrete models usually consist of three main components of facilities to be
located, a set of locations, and demand points. The facilities have certain
features such as total number, type, and costs.
• In these models, there are a discrete set of candidate locations. Discrete N-
median, un-capacitated facility location, and coverage models are some well-
known models in this area. Like the distances in continuous models, all kind
of the distance functions can be used here but sometimes it could be specified
exogenously.
• There are two cases identified for the number of facilities. The first is the
single facility problem in which only one new facility is to be opened. The
more general case is the multi-facility problem where more than one facility
is established simultaneously. This in turn gives rise to the variants of un-
capacitated and capacitated FLP.
Various discrete and continuous models
i. Single Facility Location Problem (SFLP)

ii. Multi-Facility Location Problem (MFLP)

iii. Fixed Costs Capacitated Facility Location Problem (FC-CFLP)

iv. Capacitated p-Median Facility Location Problem (CpMFLP)

v. Covering Location Problems (SCLP)

vi. Undesirable Facility Location Problem (UFLP)

1. Single Facility Location Problem (SFLP)
• The SFLP belongs to the most straightforward class of location problems.

• It involves the location of a unique new facility in a plane intending to minimize the sum of
distances (Euclidean or rectilinear) between the proposed new facility and existing (planar)
locations.

X = (x,y) oordinates of the location of new facility

D(xi, yi) = the distance between of new facility and existing facility i
Pi (ai, bi) = coordinates of the location of existing facility i
wi : weights of existing facility i
• In some facility location problems, cost is not a simple linear function of distance.
• For example, the cost associated with the response of a fire truck to a fire is
expected to be nonlinear with distance.
• Depending on the location problem, f (X) can take on a number of different
formulations. One nonlinear form of f (X) is the gravity problem. Here the cost is
proportional to the square of the Euclidean distance between X and Pi .

• Another form of problem maybe of network location problems as well as some

instances involving conveyors and air travel involving Euclidean distance.
• Some electrical wiring problems and pipeline design problems are also examples of
Euclidean distance problems.
• In certain cases, norms are usually employed as the basis for distance predicting
functions in continuous location models. Since norms are convex functions,
incorporating a norm in the objective function of a continuous location problem
provides the useful property of convexity in the optimization model. Such problem
can be solved using lp-norm distance.
2. Multi-Facility Location Problem (MFLP)
• In a MFLP, more than one new facility are to be optimally located, such that each newly located facility
is connected to at least one other new facility.

• Thus, the model is a minimum model that finds the locations of new facilities such that the total cost
function (sum of costs directly proportional to the distances between the new facilities and costs
directly proportional to the distances between new and existing facilities is minimized.

• n: Number of new facilities

• m: Number of existing facilities
• wij : Nonnegative weight between new facility i and existing facility j by a unit distance
• vik: Nonnegative weight between new facilities i and k by a unit distance
• D(Xj; Pi): Distance between the location of new facility j and existing facility i
• D (Xj;Xk): Distance between the location of new facilities j and k
• Pj :(aj, bj) The location coordinates of existing facility j
• Xi : (xi, yi) The location coordinates of new facility i
3. Fixed Costs Capacitated Facility Location Problem (FC-CFLP)
• In an FC-CFLP, the objective is to minimize the fixed costs associated with the potential facilities. The FC-
CFLP is a minimum problem because it seeks to minimize the sum of the cost of flow between facilities
and customers.
• The fixed cost is a one-time expenditure that varies from location to location, which is expected to be
recovered during the entire life of the facility.

4. Capacitated p-Median Facility Location Problem (CpMFLP)

• This is a discrete problem where the list of potential depots is the same as the list of customers. The
selected depots are called the medians or concentrators.
• Consider a connected graph consisting of customers with associated network distances from each other,
Pnew facilities are to be opened to satisfy the demands of these customers. A p-median problem optimally
locates the P facilities so that the sum of the weighted distances in the network between the customers and
their respective closest facility is the smallest.
• p-Median problems are widely studied because of their relevance to most real-life issues. The CpMFLP is
a variant of the capacitated FLP (CFLP) when fixed costs associated with potential facilities are not
considered.
5. Covering Location Problems (SCLP)
• In SCLP, customers are allowed to receive services from potential facilities
depending on the distances between the customers and the facilities. A customer ’s
demand/request can only be satisfied at a facility provided the distance between
the customer and the facility is equal or less than a predefined value known as the
threshold distance or coverage radius.

• There are two cases of SCLP depending on the extent of coverage on the demands
of customers. When all the demand points are covered, the problem is called a
total SCLP, and when only some locations are included, the problem is a partial
SCLP.

• The symmetric total covering problem (STCP) is a typical example of a total

covering problem, while the maximum covering location problem (MCLP)
belongs to the family of partial covering problems.
5.1 Symmetrical Total Covering Problem (STCP)
The objective minimizes the total cost of covering all the demand points.
It ensures that each customer is covered by at least one facility.

5.2 Maximum Covering Location Problem (MCLP)

It has the objective of maximizing the total satisfying demands in the network with a limited
maximum number of facilities.

It ensures that the number of activated facilities can not exceed the maximum number of available
facilities.
6. Undesirable Facility Location Problem (UFLP)

• The UFLP belongs to a class of FLPs known as the maximum models.

• Unlike the p-median problems where the desirability of facilities allows for the
minimization of the objective function relating to distance or cost, in maximum
models, the concern is how to locate facilities far from the intended users.

• For instance, because of the health and environmental implications, locating

landfill facilities close to waste collection points may be undesirable.
Classification of location-allocation models
(depending upon solution of problem)
• Most location models are variants of four general classes:

❑Median

❑Covering

❑Capacitated

❑Competitive
❑A median model involves locating a fixed number of facilities in such a manner that
the average distance from any user to their closest facility is minimised. Classic
median models are based upon the assumption that there are enough resources at
each facility to handle whatever demand needs to be served. Thus, everyone is
assumed to be served by their closest facility.

❑Covering models involve locating facilities to cover all or most demand within
some desired service distance (often called the maximum service distance). The idea
is that the more users who are served relatively close to a facility, the better the
service.
❑Capacitated facility models place some limit on what can be accomplished at
each facility (e.g., the number of units that can be manufactured, the amount of
demand that can be served or assigned, the volume of garbage that can be handled
per day etc.).

❑Competition models involve the case where a competitor has the capability to
readjust to any location decisions other competitors make over predefined time
frames. If you locate a new branch which exploits a poorly served area of your
competitor, your competitor may over a period of time relocate a branch or locate
a new one to recoup some of that lost market.
 1 2 3 4 5 6
1 20 18 14 16 12
2 22 18 30 26
3 32 20 22
4 20 22
5 30
6

𝑀𝑖𝑛 ෍ 𝑑𝑖𝑗 𝑋𝑖𝑗 n=6 ; p=2

Median Non-median Distance Median Non-median Distance

1 3,4,5,6 60 3 5,6 74
2 - 4 1,2

Number of combinations required = nCp = n!/[p! (n-p)!]

 Distance matrix
A B C D E

A 0 14 10 22 27

B 0 23 17 16

C 0 12 28

D 0 16

E 0

Analyse dependency (Already existing facilities)

Node (wt) dependents ∑wij.dij.xij
A (450) C, B 200*10+250*14 = 5,500
B (575) A, C, D, E 14*100+23*200+17*125+13*150 = 10,075
C (475) A, B, D 100*10+250*23+125*12 = 8,250
D (600) C,B, E 200*12+250*17+150*16=9,050
E (375) B, D 250*13+125*16= 5,250
Solution Techniques for FLP
• There are two categories of techniques available for FLPs: precise and heuristics(approximate)
methods.

• In many cases, however, solutions that start with exact methods are usually concluded with
heuristic approaches to obtain desirable optimal solutions. Heuristics can be viewed as methods of
arriving at an approximate solution to a problem, that is, guessing a solution to a problem which is
considered good enough.

• Thus, making use of heuristic methods in finding the resolution of a problem is to apply a rule of
thumb, which is generally under the control of the computer to explore available paths and
reasonable guesses to arrive at an optimal solution. It is a search mechanism that checks all
possible alternatives to obtain the best.

• Heuristics are problem-dependent. In other words, a heuristic is usually defined for the problem
it seeks to solve. Meta-heuristics, a form of heuristics, differ from basic heuristics in that they are
problem-independent techniques and can generally be adapted to different types of problems.
Techniques for solving facility location-related
problems
i. Branch-and-Bound
ii. Lagrangian Relaxation Heuristic
iii. Constructive and Local Search
iv. Tabu Search
v. Large Neighborhood Search
vi. Particle Swarm Optimization
vii. Ant Colony Optimization and Variants
viii. Simulated Annealing
ix. Genetic Algorithm
i. Branch-and-Bound:
The branch-and-bound (BB) is by far the most widely used exact method for solving large-scale NP
(Non deterministic polynomial time)-hard optimization problems.

The BB algorithm searches the space of the feasible solution of a given problem for the best
solution. Since the number of possible solutions grows exponentially, only an implicit search of the
solution space is possible.

At the start of the process, only one subset of the solution space exists and is the complete solution
space having an optimal solution set at 1.

Successively, a pool of unexplored subsets is generated and represented as nodes in a search tree.

These nodes are then processed by an iterative algorithm with the following components: node
insertion, estimation of bounds, and branching.
ii. Lagrangian Relaxation Heuristic
Another method commonly used for solving FLP models is the Lagrangian relaxation (LR)heuristic,
which is both powerful and rich in analysis for solving NP-hard combinatorial optimization
problems.

The main idea behind the method is to identify one or more “complicating” constraints and then
attach a multiplier vector, also known as the penalty cost to this set of constraints before adding it to
the objective function.

The resulting problem is called the Lagrangian problem, and the objective function is known as the
Lagrangian dual function.
iii. Constructive and Local Search:
Constructive search algorithms build an optimal solution to a problem from scratch by repeatedly
extending the current known solution until a complete solution is found. The method generally
improves solutions than random methods.

It is often used to initialize many metaheuristic algorithms for obtaining near-optimal solutions. The
algorithm is usually thought of as being fast, as they are often a single-pass approach.

Local search methods, on their part, consider the neighborhood of the existing current solution for
possible replacement.

That is, a local search algorithm takes a complete solution and tries to improve it through local moves
within the neighborhood. Often, constructive algorithms are used to initiate solutions that local search
heuristics build on to provide optimal solutions. Generally, a local search follows the hill-climbing
search process until the best solution is reached.
iv. Tabu Search:
The Tabu search (TS) is a meta-heuristic approach that allows a form of hill-climbing to overcome
the local search optimal.

The technique is based on the neighborhood, also known as the short term memory of the search, in a
way that prevents movement in cycles.

In this way, moves in subsequent iterations that take the current solution to points in the feasible
space, which have previously been explored, are avoided.

Fundamental Elements
The search space and its neighborhood structure.
v. Large Neighborhood Search:
The broad large neighborhood search (LNS) is a meta-heuristic.

Unlike most neighborhood search methods where the neighborhood containing the solution is usually
explicitly defined, the LNS makes use of a destroy-repair approach to define an implicit region of the
solution.

The destroy technique removes part of a current solution while the repair method re-inserts the
eliminated candidate solution(s), thus rebuilding the solution structure. In the LNS, a solution
neighborhood J(x) is defined as a solution. This neighborhood can then be explored by the destroy
method, followed by the repair method.

The adaptive broad neighborhood search (ALNS) is an extension of the LNS heuristic. This method
allows multiple applications of the destroy-repair method within the same search. A weight value that
controls the frequency of attempt by each way is assigned. This assignment, however, undergoes
dynamical re-adjustment as the search progresses to allow problem adaptation. The use of multiple
destroy-repair methods indicates that the ALNS enables the creation of various neighborhoods.
Thank You
References
• Adeleke, Olawale & Olukanni, David. (2020). Facility Location Problems: Models, Techniques,
and Applications in Waste Management. Recycling. 5. 10. 10.3390/recycling5020010.

• Alghanmi, Nusaybah & Al-Otaibi, Reem & Alshammari, Sultanah & Alhothali, Areej & Bamasag,
Omaimah & Faisal, Kamil. (2022). A Survey of Location-Allocation of Points of Dispensing
During Public Health Emergencies. Frontiers in Public Health. 10. 811858.
10.3389/fpubh.2022.811858.

• Anthony Gar-On Yeh, Man Hong Chow. (1996). An integrated GIS and location-allocation
approach to public facilities planning—An example of open space planning, Computers,
Environment and Urban Systems, https://doi.org/10.1016/S0198-9715(97)00010-0.

• Longley, Paul A.. “Geographical information systems : principles, techniques, management, and
applications.” (2005).