Skip to main content
 首页 » 编程设计

python之将许多点分组为最接近的对之Python + LP

2025年05月04日13think

我有一个包含商店 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 点的更大的例子:

请您参考如下方法:

考虑一个 pandas解决方案(Python 的数据分析包)。我的初等几何提醒我,两点之间最近的距离是一条直线,它在坐标平面中是 Lat 和 Lng 点之间的斜边。

下面首先运行商店之间的笛卡尔乘积(集合之间所有可能的组合),然后使用地理坐标计算斜边。从那里聚合最小值:

import pandas as pd 
 
# ORIGINAL LIST 
shops = [[1, 53.382072, -2.7262165], 
         [2, 52.478499, -0.9222608], 
         [3, 52.071258, -1.2722802]] 
 
# CONVERTING INTO TWO DUPLICATE SHOPS DATA FRAMES     
shopsdfA = pd.DataFrame(shops, columns=['ID_A', 'Lat_A', 'Lng_A']) 
shopsdfA['key']=1 
shopsdfB = pd.DataFrame(shops, columns=['ID_B', 'Lat_B', 'Lng_B']) 
shopsdfB['key']=1 
 
# CROSS JOINING BOTH DATA FRAMES FOR CARTESIAN PRODUCT SET  
compareshops = pd.merge(shopsdfA, shopsdfB, on='key')[['ID_A', 'Lat_A', 'Lng_A',  
                                                       'ID_B','Lat_B', 'Lng_B']] 
#  (REMOVING SHOPS COMPARED TO ITSELF) 
compareshops = compareshops[compareshops['ID_A'] != compareshops['ID_B']].\ 
               reset_index(drop=True) 
#   ID_A      Lat_A     Lng_A  ID_B      Lat_B     Lng_B 
#0     1  53.382072 -2.726217     2  52.478499 -0.922261 
#1     1  53.382072 -2.726217     3  52.071258 -1.272280 
#2     2  52.478499 -0.922261     1  53.382072 -2.726217 
#3     2  52.478499 -0.922261     3  52.071258 -1.272280 
#4     3  52.071258 -1.272280     1  53.382072 -2.726217 
#5     3  52.071258 -1.272280     2  52.478499 -0.922261 
 
# CALCULATE HYPOTENUSE 
compareshops['hypotenuse'] = ((compareshops['Lat_A'] - compareshops['Lat_B']) ** 2 + 
                              (compareshops['Lng_A'] - compareshops['Lng_B']) ** 2) ** (1/2) 
#   ID_A      Lat_A     Lng_A  ID_B      Lat_B     Lng_B  hypotenuse 
#0     1  53.382072 -2.726217     2  52.478499 -0.922261    2.017598 
#1     1  53.382072 -2.726217     3  52.071258 -1.272280    1.957591 
#2     2  52.478499 -0.922261     1  53.382072 -2.726217    2.017598 
#3     2  52.478499 -0.922261     3  52.071258 -1.272280    0.536991 
#4     3  52.071258 -1.272280     1  53.382072 -2.726217    1.957591 
#5     3  52.071258 -1.272280     2  52.478499 -0.922261    0.536991 
 
# AGGREGATE FOR MINIMUM HYPOTENUSE AND MERGE CORRESPONDING PAIRED IDS 
compareshops = pd.merge(compareshops[['ID_A','hypotenuse']].groupby(['ID_A']).min().reset_index(), 
                        compareshops[['ID_B','hypotenuse']], on='hypotenuse') 
# (REMOVING SAME STORE PAIRINGS) 
compareshops = compareshops[compareshops['ID_A'] != compareshops['ID_B']].\ 
                     reset_index(drop=True)[['ID_A','ID_B','hypotenuse']] 
 
#   ID_A  ID_B  hypotenuse 
#0     1     3    1.957591 
#1     2     3    0.536991 
#2     3     2    0.536991 

一个可预见的挑战是您的 map 没有重叠连接,每个商店只有一对。可能需要运行迭代斜边计算以找到“下一个”最短距离。