我有一个包含 shop_id、纬度和经度的列表。假设我们有相同数量的点，我想将每个商店与另一个商店匹配，这样我们的连接是独一无二的，并且我们最小化了整体距离。
我很好奇我的方法是否不太愚蠢，以及更好的方法会是什么。目前，这在合理的时间（一小时）内有效，可获得 1000 分。
假设我们有一个这样的列表：
shops = [[1, '53.382072', '-2.7262165'],
[2, '52.478499', '-0.9222608'],
[3, '52.071258', '-1.2722802'],
...]
我使用 PuLP 使用此工作流程创建一个 .lp 文件：
prob = LpProblem("Minimise distance",LpMinimize)
# Variables
x = []
xnames = []
for one in store_connect(shops):
xnames.append(one)
x.append(LpVariable(one,0,1,LpInteger))
print("Created %d variables" % len(x))
# Objective
prob += pulp.lpSum([i[1]*x[i[0]] for i in enumerate(distances(shops))])
print("Created objective")
# Constraints
counter = 0
for constraint_rw in all_constraints(shops):
prob += pulp.lpSum(x[xnames.index(one_cn)] for one_cn in constraint_rw) == 1
counter += 1
if counter % 10 == 0:
print("Added %d contraints out of %d" % (counter,len(shops)))
# Save "LP" file for other solvers
prob.writeLP("for_cplex.lp")
我在其中调用了一些生成器功能（以帮助 RAM ...）
def store_connect(shops):
"""
Cross stores and return connection e.g. "v1-2" by ID
"""
for i in range(len(shops)-1):
for j in range(i+1,len(shops)):
yield 'v'+str(shops[i][0])+'-'+str(shops[j][0])
def distances(shops):
"""
Return distance in miles for crosses
"""
for i in range(len(shops)-1):
for j in range(i+1,len(shops)):
yield haversine([shops[i][1],shops[i][2]],
[shops[j][1],shops[j][2]])
def all_constraints(shops):
"""
Return constraint row
"""
for a in shops:
cons = []
for b in shops:
if a[0]<b[0]:
cons.append("v"+str(a[0])+"-"+str(b[0]))
elif a[0]>b[0]:
cons.append("v"+str(b[0])+"-"+str(a[0]))
yield cons
如果我在 100 家商店上运行它，速度非常快，我可以使用默认的 PuLP 求解器。否则，我将 LP 文件提交给 NEOS 服务器上的 CPLEX。我创建了一个小辅助函数，它可以可视化结果匹配：
这是我的 LP 文件如何查找 10 个商店（截断）的简单示例：
Minimize
OBJ: 131.513 v1_10 + 97.686 v1_2 + 109.107 v1_3 + 36.603 v1_4 + 11.586 v1_5
+ 109.067 v1_6 + 113.862 v1_7 + 169.371 v1_8 + 220.098 v1_9 + 101.958 v2_10
+ 31.793 v2_3 + 61.792 v2_4 + 105.822 v2_5 + 73.055 v2_6 + 32.008 v2_7
+ 81.627 v2_8 + 122.493 v2_9 + 72.945 v3_10 + 72.983 v3_4 + 114.609 v3_5
+ 46.098 v3_6 + 5.555 v3_7 + 60.305 v3_8 ...
Subject To
_C1: v1_10 + v1_2 + v1_3 + v1_4 + v1_5 + v1_6 + v1_7 + v1_8 + v1_9 = 1
_C10: v1_10 + v2_10 + v3_10 + v4_10 + v5_10 + v6_10 + v7_10 + v8_10 + v9_10
= 1
_C2: v1_2 + v2_10 + v2_3 + v2_4 + v2_5 + v2_6 + v2_7 + v2_8 + v2_9 = 1
_C3: v1_3 + v2_3 + v3_10 + v3_4 + v3_5 + v3_6 + v3_7 + v3_8 + v3_9 = 1
_C4: v1_4 + v2_4 + v3_4 + v4_10 + v4_5 + v4_6 + v4_7 + v4_8 + v4_9 = 1
_C5: v1_5 + v2_5 + v3_5 + v4_5 + v5_10 + v5_6 + v5_7 + v5_8 + v5_9 = 1
...
Binaries
v1_10
v...
End
结果：
Status: Optimal
Total minimised distance (miles): 190.575
最后，这是一个关于 1000 点的更大示例：
