Advanced Optimisation with Python
• Location Problems
• Integer Programming Formulation • PuLP Modelling & Solution
Copyright By PowCoder代写 加微信 powcoder
Location examples
A location problem typically involves supplies and demands. Some examples:
• Locate warehouses to supply sales centres
• Location of hospitals or schools. In this case the ‘demand’ are patients or children. The choice of locations must consider the distribution of demand and try to minimise travel distances.
• Location of fire stations. The ‘demand’ is where fires are most likely to occur and the consequence of those fires.
Classes of Location Models
Set-covering
Find a subset of possible locations to ensure all demand points are covered.
Maximum coverage
Given an upper bound on the number of feasible facilities, maximise the demand covered
Centre models
Like set-covering models but choose locations to minimise the maximum distance of demand points to a facility.
Unlike the above models each demand centre can be satisfied by a combination of facilities. The objective is to minimise the sum of the distances between demand and facilities, with the constraint that the total demand of the facilities assigned to set of demands does not exceed its given capacity.
Fixed charge facility location models
The cost of installing a facility may depend on the location. In this class of problems the location-dependent fixed charge costs must be minimised while simultaneously meeting the cost of satisfying demand.
Depot Location
A company needs to site up to 12 depots to deliver to 12 service centres
Depot Location
Depot Location
buildd is a binary variable indicating whether a depot is built or not.
fflowdc is a variable indicating the proportion of the demand of service centre c which is satisfied by depot d.
Depot Location
⚫ Minimise total cost:
CFIX d buildd + COSTdc fflowdc
dDEPOTS dDEPOTS cCUST
⚫ Fixed costs for each depot to be built
⚫ Costs of supplying each service centre from each depot, multiplied by the fraction actually supplied
Depot Location
⚫ Since it’s a ratio: dDEPOTS,cCUST:fflow 0
dDEPOTS,cCUST:fflow 1 dc
⚫ Also, we need to satisfy demand for all customers: cCUST : fflow =1
dc dDEPOTS
Depot Location
⚫ For each depot, the demand it supplies is less than its capacity.
⚫ If it isn’t built, its capacity becomes zero.
⚫ Each customers demand is multiplied by the fraction satisfied by depot d, and this is summed across all customers.
dDEPOTS: DEM fflow CAP build
Location of GSM transmitters
Choose from seven potential transmitter sites, indicated by black dots, to cover 15 communities.
Location of GSM transmitters
Location of GSM transmitters
Decision variables
coveredc 1 if community c is covered, 0 otherwise buildp 1 if a transmitters is build in site p, 0 otherwise
Location of GSM transmitters
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com