位置分配优化
此示例展示了我们如何使用开源 Python 处理大型分配和位置分配问题。该工作流程使用匿名数据，并演示了我们如何准备模型输入、构建起点-目的地矩阵、解决优化问题以及将输出导出回 GeoJSON，以便可以在 GIS 软件中进行查看。
规划问题很简单但很有用：考虑到每个社区或郊区的人口、每个设施的容量以及每个设施可以服务的最大距离，是否有足够的设施来服务全部人口，如果没有，哪些区域在当前的限制下仍未分配？
模型的作用
这是一个分配和位置分配模型。每个需求位置都由六边形表示，每个设施代表可用供应，模型将每个六边形分配给单个最佳设施，同时尊重服务距离和容量规则。相同的建模模式可用于医疗机构、学校、银行、零售店或其他我们需要了解覆盖范围、服务区域和访问差距的服务网络。
输出不仅仅是一个分配表。它还可以转化为服务区和贸易区图层，显示每个设施可以覆盖哪些位置，哪些需求区域被推向未分配的回退，以及当容量、距离或目标调整时结果如何变化。
目标函数
对于此示例，目标是最小化从每个需求六边形到其指定设施点的总距离。这给出了当前假设下最有效的分配。如果业务问题发生变化，可以使用不同的目标函数重新运行相同的框架。例如，我们可以最小化运营成本而不是距离，最小化旅行时间而不是直线距离，或者重新平衡需求，以便成本较高的设施获得足够的数量来证明其运营状况合理。
关键限制
- 每个设施都有最大服务距离，因此无法将超出该范围的需求分配给该设施。
- 每个设施都有最小和最大人口限制，因此分配给它的总需求必须保持在其容量限制内。
- 每个需求六边形必须分配给一个设施。
- 如果六边形无法分配给任何真实设施，则可以将其分配给虚拟
unassigned设施，以便模型保持可行并且覆盖间隙可见。 - 该示例使用六边形质心和设施之间的欧几里得距离进行快速原型设计，但在需要时可以将相同的工作流程切换到真实的可行驶路线。
工作流程
工作流程分为三个主要阶段：
- 将感兴趣的区域转换为六边形镶嵌，并导出每个六边形的人口。
- 生成每个需求六边形和每个设施点之间的起点-终点矩阵。
- 求解优化模型并将结果导出为 GeoJSON，以便可以在 QGIS、ArcGIS Pro 或其他地图软件中查看。
实现堆栈包括带有 shapely、pyproj、sqlite3、pyomo、CBC 求解器和 GeoJSON 输出的开源 Python。数据准备模式是故意模块化的，这使得替换需求层、更改设施约束、交换目标或使用附加业务规则扩展模型变得容易。
实施说明- 最初测试了 PuLP，但选择了 pyomo，因为它可以更可靠地处理更大的模型。
- 该模型是使用开源 CBC 求解器求解的，并且这种方法在不到一小时的时间内可扩展到超过 5000 万个决策变量。
- 对于更大的实例，在许可允许的情况下可以考虑使用 gurobi。
- 将大型输出写入 GeoJSON 可能比求解模型本身花费更长的时间，因此对于更大的生产运行，直接写入数据库可能会更有效。
- 构建此类模型的一种实用方法是在测试约束时从大六边形和快速欧几里德距离开始，然后在模型行为得到验证后切换到更精细的细分和更现实的路线成本。
- 可以逐步添加其他约束，但应谨慎引入它们，因为每个额外的业务规则都会增加使模型不可行的风险。
示例源代码
下面的代码直接在此页面上显示了端到端工作流程。
1.generate_hexagons.py
import json
import math
import os
import pyproj
from shapely.geometry import shape
# for converting the coordinates to and from geographic and projected coordinates
TRAN_4326_TO_3857 = pyproj.Transformer.from_crs("EPSG:4326", "EPSG:3857")
TRAN_3857_TO_4326 = pyproj.Transformer.from_crs("EPSG:3857", "EPSG:4326")
# the area of interest used for generating the hexagons
input_geojson_file = "input/area_of_interest.geojson"
# load the area of interest into a JSON object
with open(input_geojson_file) as json_file:
geojson = json.load(json_file)
# the area of interest coordinates (note this is for a single-part / contiguous polygon)
geographic_coordinates = geojson["features"][0]["geometry"]["coordinates"]
# create an area of interest polygon using shapely
aoi = shape({"type": "Polygon", "coordinates": geographic_coordinates})
# get the geographic bounding box coordinates for the area of interest
(lng1, lat1, lng2, lat2) = aoi.bounds
# get the projected bounding box coordinates for the area of interest
[W, S] = TRAN_4326_TO_3857.transform(lat1, lng1)
[E, N] = TRAN_4326_TO_3857.transform(lat2, lng2)
# the area of interest height
aoi_height = N - S
# the area of interest width
aoi_width = E - W
# the length of the side of the hexagon
l = 200
# the length of the apothem of the hexagon
apo = l * math.sqrt(3) / 2
# distance from the mid-point of the hexagon side to the opposite side
d = 2 * apo
# the number of rows of hexagons
row_count = math.ceil(aoi_height / l / 1.5)
# add a row of hexagons if the hexagon tessallation does not fully cover the area of interest
if(row_count % 2 != 0 and row_count * l * 1.5 - l / 2 < aoi_height):
row_count += 1
# the number of columns of hexagons
column_count = math.ceil(aoi_width / d) + 1
# the total height and width of the hexagons
total_height_of_hexagons = row_count * l * 1.5 if row_count % 2 == 0 else 1.5 * (row_count - 1) * l + l
total_width_of_hexagons = (column_count - 1) * d
# offsets to center the hexagon tessellation over the bounding box for the area of interest
x_offset = (total_width_of_hexagons - aoi_width) / 2
y_offset = (row_count * l * 3 / 2 - l / 2 - aoi_height - l) / 2
# create an empty feature collection for the hexagons
feature_collection = { "type": "FeatureCollection", "features": [] }
oid = 1
hexagon_count = 0
for i in range(0, column_count):
for j in range(0, row_count):
if(j % 2 == 0 or i < column_count - 1):
x = W - x_offset + d * i if j % 2 == 0 else W - x_offset + apo + d * i
y = S - y_offset + l * 1.5 * j
coords = []
for [lat, lng] in [
TRAN_3857_TO_4326.transform(x, y + l),
TRAN_3857_TO_4326.transform(x + apo, y + l / 2),
TRAN_3857_TO_4326.transform(x + apo, y - l / 2),
TRAN_3857_TO_4326.transform(x, y - l),
TRAN_3857_TO_4326.transform(x - apo, y - l / 2),
TRAN_3857_TO_4326.transform(x - apo, y + l / 2),
TRAN_3857_TO_4326.transform(x, y + l)
]:
coords.append([lng, lat])
hexagon = shape({"type": "Polygon", "coordinates": [coords]})
# check if the hexagon is within the area of interest
if aoi.intersects(hexagon):
hexagon_count += 1
if(hexagon_count % 1000 == 0):
print('Generated {} hexagons'.format(hexagon_count))
population = 0
hexagon_names = []
# open the geojson file with the population data
with open("input/population_areas.geojson") as json_file:
geojson = json.load(json_file)
for feature in geojson["features"]:
polygon = shape(
{
"type": "Polygon",
"coordinates": feature["geometry"]["coordinates"]
}
)
# check if hexagon is within the polygon and derive the population for that intersected part of the hexagon
if hexagon.intersects(polygon):
if not feature["properties"]["Name"] in hexagon_names:
hexagon_names.append(feature["properties"]["Name"])
population += (
hexagon.intersection(polygon).area
/ polygon.area
* feature["properties"]["Population"]
)
hexagon_names.sort()
f = {
"type": "Feature",
"properties": {
"id": oid,
"name": ', '.join(hexagon_names),
"population": population
},
"geometry": {
"type": "Polygon",
"coordinates": [coords]
}
}
# add the hexagon to the feature collection
feature_collection['features'].append(f)
oid += 1
print('Generated {} hexagons'.format(hexagon_count))
# output the feature collection to a geojson file
with open("output/hexagons.geojson", "w") as output_file:
output_file.write(json.dumps(feature_collection))
# Play a sound when the script finishes (macOS)
for i in range(1, 2):
os.system('afplay /System/Library/Sounds/Glass.aiff')
# Play a sound when the script finishes (Windows OS)
# import time
# import winsound
# frequency = 1000
# duration = 300
# for i in range(1, 10):
# winsound.Beep(frequency, duration)
# time.sleep(0.1)2.generate_origin_destination_matrix.py
import json
import math
import os
import pyproj
import sqlite3
def getDistance(x1,y1,x2,y2):
distance = math.sqrt((x2-x1)**2+(y2-y1)**2)
return int(distance)
def getHexagonCentroid(hexagon):
coordinates = hexagon['geometry']['coordinates'][0]
# remove the last pair of coordinates in the hexagon
coordinates.pop()
lat = sum(coords[1] for coords in coordinates) / 6
lng = sum(coords[0] for coords in coordinates) / 6
return lat, lng
# for converting the coordinates to and from geographic and projected coordinates
TRAN_4326_TO_3857 = pyproj.Transformer.from_crs("EPSG:4326", "EPSG:3857")
TRAN_3857_TO_4326 = pyproj.Transformer.from_crs("EPSG:3857", "EPSG:4326")
# create a sqlite database for the results
db = 'output/results.sqlite'
# delete the database if it already exists
if(os.path.exists(db)):
os.remove(db)
# create a connection to the sqlite database
conn = sqlite3.connect(db)
# create cursors for the database connection
c1 = conn.cursor()
c2 = conn.cursor()
# create the facilities table
c1.execute('''
CREATE TABLE facilities (
facility_id INT,
facility_x REAL,
facility_y REAL,
trade_area_distance_constraint REAL,
min_population_constraint INT,
max_population_constraint INT
);
''')
c1.execute('''
CREATE TABLE od_matrix (
facility_id INT,
hexagon_id INT,
facility_x REAL,
facility_y REAL,
hexagon_x REAL,
hexagon_y REAL,
distance INT,
optimal INT
);
''')
# the geojson for the facilities
input_geojson_file = "input/facilities.geojson"
# load the area of interest into a JSON object
with open(input_geojson_file) as json_file:
geojson = json.load(json_file)
facilities = geojson['features']
for facility in facilities:
facility_id = facility['properties']['OID']
trade_area_distance_constraint = facility['properties']['trade_area_dist_constraint']
min_population_constraint = facility['properties']['min_population_constraint']
max_population_constraint = facility['properties']['max_population_constraint']
[lng, lat] = facility['geometry']['coordinates']
[x, y] = TRAN_4326_TO_3857.transform(lat, lng)
sql = '''
INSERT INTO facilities (
facility_id,
facility_x,
facility_y,
trade_area_distance_constraint,
min_population_constraint,
max_population_constraint
)
VALUES ({},{},{},{},{},{});
'''.format(facility_id, x, y, trade_area_distance_constraint, min_population_constraint, max_population_constraint)
c1.execute(sql)
# create an empty feature collection for the hexagons
feature_collection = { "type": "FeatureCollection", "features": [] }
# the geojson for the hexagons
input_geojson_file = "output/hexagons.geojson"
# load the area of interest into a JSON object
with open(input_geojson_file) as json_file:
geojson = json.load(json_file)
hexagons = geojson['features']
for i, hexagon in enumerate(hexagons):
hexagon_id = hexagon['properties']['id']
lat, lng = getHexagonCentroid(hexagon)
[hexagon_x, hexagon_y] = TRAN_4326_TO_3857.transform(lat, lng)
rows = c1.execute('''
SELECT facility_id, facility_x, facility_y, trade_area_distance_constraint
FROM facilities;
''').fetchall()
for row in rows:
facility_id, facility_x, facility_y, trade_area_distance_constraint = row
distance = getDistance(hexagon_x, hexagon_y, facility_x, facility_y)
if(distance > int(trade_area_distance_constraint)):
distance = 100000
sql = '''
INSERT INTO od_matrix(facility_id, facility_x, facility_y, hexagon_id, hexagon_x, hexagon_y, distance)
VALUES ({},{},{},{},{},{},{});
'''.format(facility_id, facility_x, facility_y, hexagon_id, hexagon_x, hexagon_y, distance)
c2.execute(sql)
(hexagon_lat, hexagon_lng) = TRAN_3857_TO_4326.transform(hexagon_x, hexagon_y)
(facility_lat, facility_lng) = TRAN_3857_TO_4326.transform(facility_x, facility_y)
coords = [[facility_lng, facility_lat],[hexagon_lng, hexagon_lat]]
if(distance <= trade_area_distance_constraint):
f = {
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": coords
}
}
# add the hexagon to the feature collection
feature_collection['features'].append(f)
if((i+1) % 1000 == 0):
print('Processed {} hexagons'.format(i+1))
conn.commit()
conn.close()
# output the feasible facility-hexagon pairs to geojson
with open("output/routes.geojson", "w") as output_file:
output_file.write(json.dumps(feature_collection))
for i in range(1,2):
os.system('afplay /System/Library/Sounds/Glass.aiff')3.solve_the_model.py
from pyomo.environ import *
from pyomo.opt import SolverFactory
import datetime
import json
import os
import pyproj
import sqlite3
# for converting the coordinates to and from geographic and projected coordinates
TRAN_4326_TO_3857 = pyproj.Transformer.from_crs("EPSG:4326", "EPSG:3857")
TRAN_3857_TO_4326 = pyproj.Transformer.from_crs("EPSG:3857", "EPSG:4326")
# the input database created from the previous script
db = 'output/results.sqlite'
# create a database connection
conn = sqlite3.connect(db)
# create a cursor for the database connection
c = conn.cursor()
# the demand, supply, and cost matrices
Demand = {}
Supply = {}
Cost = {}
'''
Supply['S0'] is for infeasible results, i.e. hexagons that do not
have any facilities when the nearest facility is too far away,
or when the population constraint for the facilities means the
hexagon cannot be assigned to that facility
'''
# the population capacity constraint of the "unassigned" facility
Supply['S0'] = {}
Supply['S0']['min_pop'] = 0
Supply['S0']['max_pop'] = 1E10
sql = '''
SELECT DISTINCT hexagon_id
FROM od_matrix
ORDER BY 1;
'''
# the assignment constraint, i.e. each hexagon can only be assigned to one facility
for row in c.execute(sql):
hexagon_id = row[0]
d = 'D{}'.format(hexagon_id)
Demand[d] = 1
# the infeasible case for each hexagon
Cost[(d,'S0')] = 1E4
sql = '''
SELECT DISTINCT facility_id, min_population_constraint, max_population_constraint
FROM facilities
ORDER BY 1;
'''
# the facility capacity constraint - cannot supply more hexagons than the facility has capacity for
for row in c.execute(sql):
[facility_id, min_population_constraint, max_population_constraint] = row
s = 'S{}'.format(facility_id)
Supply[s] = {}
Supply[s]['min_pop'] = min_population_constraint
Supply[s]['max_pop'] = max_population_constraint
sql = '''
SELECT facility_id, hexagon_id, distance
FROM od_matrix;
'''
# creating the Cost matrix
for row in c.execute(sql):
(facility_id, hexagon_id, distance) = row
d = 'D{}'.format(hexagon_id)
s = 'S{}'.format(facility_id)
Cost[(d,s)] = distance
print('Building the model')
# creating the model
model = ConcreteModel()
model.dual = Suffix(direction=Suffix.IMPORT)
# Step 1: Define index sets
dem = list(Demand.keys())
sup = list(Supply.keys())
# Step 2: Define the decision variables
model.x = Var(dem, sup, domain=NonNegativeReals)
# Step 3: Define Objective
model.Cost = Objective(
expr = sum([Cost[d,s]*model.x[d,s] for d in dem for s in sup]),
sense = minimize
)
# Step 4: Constraints
model.sup = ConstraintList()
# each facility cannot supply more than its population capacity
for s in sup:
model.sup.add(sum([model.x[d,s] for d in dem]) >= Supply[s]['min_pop'])
model.sup.add(sum([model.x[d,s] for d in dem]) <= Supply[s]['max_pop'])
model.dmd = ConstraintList()
# each hexagon can only be assigned to one facility
for d in dem:
model.dmd.add(sum([model.x[d,s] for s in sup]) == Demand[d])
'''
There is no need to add a constraint for the service/trade area distances
for the facilities. We are already handling this when we generate
the origin destination matrix. If any hexagon falls outside of all
facility trade areas, then it gets assigned to the "unassigned" facility.
'''
print('Solving the model')
# use the CBC solver and solve the model
results = SolverFactory('cbc').solve(model)
# for c in dem:
# for s in sup:
# print(c, s, model.x[c,s]())
# if the model solved correctly
if 'ok' == str(results.Solver.status):
print("Objective Function = ", model.Cost())
print('Outputting the results to GeoJSON') # note it would be faster to write the results directly to a database, e.g. Postgres / SQL Server
# print("Results:")
for s in sup:
for d in dem:
if model.x[d,s]() > 0:
# print("From ", s," to ", d, ":", model.x[d,s]())
facility_id = s.replace('S','')
hexagon_id = d.replace('D','')
c.execute('''
UPDATE od_matrix
SET optimal = 1
WHERE facility_id = {}
AND hexagon_id = {};
'''.format(facility_id, hexagon_id))
# create an empty feature collection for the results
feature_collection = { "type": "FeatureCollection", "features": [] }
rows = c.execute('''
SELECT facility_id, hexagon_id, facility_x, facility_y, hexagon_x, hexagon_y, distance
FROM od_matrix
WHERE optimal = 1;
''')
for row in rows:
(facility_id, hexagon_id, facility_x, facility_y, hexagon_x, hexagon_y, distance) = row
(hexagon_lat, hexagon_lng) = TRAN_3857_TO_4326.transform(hexagon_x, hexagon_y)
(facility_lat, facility_lng) = TRAN_3857_TO_4326.transform(facility_x, facility_y)
coords = [[facility_lng, facility_lat],[hexagon_lng, hexagon_lat]]
f = {
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": coords
}
}
# add the route to the feature collection
feature_collection['features'].append(f)
# output the optimally assigned pairs to geojson
with open("output/optimal_results.geojson", "w") as output_file:
output_file.write(json.dumps(feature_collection))
# update the hexagons
with open('output/hexagons.geojson') as json_file:
geojson = json.load(json_file)
hexagons = geojson['features']
for hexagon in hexagons:
facility_id = -1
hexagon_id = hexagon['properties']['id']
sql = '''
SELECT facility_id
FROM od_matrix
WHERE hexagon_id = {}
AND optimal = 1;
'''.format(hexagon_id)
row = c.execute(sql).fetchone()
if row:
facility_id = row[0]
hexagon['properties']['facility_id'] = facility_id
# load the area of interest into a JSON object
with open("output/hexagon_results.geojson", "w") as output_file:
output_file.write(json.dumps(geojson))
else:
print("No Feasible Solution Found")
finish_time = datetime.datetime.now()
# print('demand nodes = {} and supply nodes = {} | time = {}'.format(no_of_demand_nodes, no_of_supply_nodes, finish_time-start_time))
conn.commit()
conn.close()
for i in range(1,2):
os.system('afplay /System/Library/Sounds/Glass.aiff')