商品分配算法优化：使用KD树加速距离计算

首先，我们需要读取两个Excel文件中的数据，并将其存储在适当的数据结构中。

import pandas as pd

# 读取商品信息
product_df = pd.read_excel('D:\pythonProject3\商品信息\商品打包.xlsx')
product_data = product_df[['商品编号', '新商品GPS纬度', '新商品GPS经度', '打包数量']].values.tolist()

# 读取会员信息
member_df = pd.read_excel('D:\pythonProject3\打包问题\会员信息.xlsx')
member_data = member_df[['会员编号', '会员GPS纬度', '会员GPS经度', '预订商品限额']].values.tolist()

接下来，我们需要编写一个函数来计算两个坐标之间的距离。

from math import radians, sin, cos, sqrt, atan2

def calculate_distance(lat1, lon1, lat2, lon2):
    # 将角度转换为弧度
    lat1 = radians(lat1)
    lon1 = radians(lon1)
    lat2 = radians(lat2)
    lon2 = radians(lon2)

    # 使用Haversine公式计算距离
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
    c = 2 * atan2(sqrt(a), sqrt(1 - a))
    distance = 6371 * c

    return distance

然后，我们可以开始实现主要的逻辑。首先，我们需要按照会员的预订商品限额从大到小排序。

# 按照预订商品限额从大到小排序
member_data.sort(key=lambda x: x[3], reverse=True)

接下来，我们可以遍历每个会员，并为其选择最近的商品。

selected_products = []
allocated_members = []

for member in member_data:
    member_id = member[0]
    member_lat = member[1]
    member_lon = member[2]
    member_limit = member[3]
    allocated_quantity = 0

    for product in product_data:
        product_id = product[0]
        product_lat = product[1]
        product_lon = product[2]
        product_quantity = product[3]

        # 检查商品是否已经被分配给其他会员
        if product_id in selected_products:
            continue

        # 计算商品与会员之间的距离
        distance = calculate_distance(member_lat, member_lon, product_lat, product_lon)

        # 检查距离是否满足要求
        if distance > 0.1:
            continue

        # 检查商品数量是否超过会员的预订商品限额
        if allocated_quantity + product_quantity > member_limit:
            continue

        # 将商品分配给会员
        selected_products.append(product_id)
        allocated_members.append((product_id, member_id))
        allocated_quantity += product_quantity

        # 检查是否已经达到会员的预订商品限额
        if allocated_quantity >= member_limit:
            break

最后，我们可以输出结果。

# 输出每个会员挑选到的商品数量和会员的预订商品限额
for member in member_data:
    member_id = member[0]
    member_limit = member[3]
    allocated_quantity = sum([product[3] for product in allocated_members if product[1] == member_id])
    print(f'会员{member_id}挑选到的商品数量：{allocated_quantity}，预订商品限额：{member_limit}')

# 输出每个商品被分配到哪个会员
product_allocation = {}
for product, member in allocated_members:
    if product in product_allocation:
        product_allocation[product].append(member)
    else:
        product_allocation[product] = [member]

for product, members in product_allocation.items():
    print(f'商品{product}被分配到会员：{', '.join(members)}')

这是一个基本的实现，但是在处理大量数据时可能会非常耗时。为了优化算法，我们可以使用KD树数据结构来加速距离计算。

首先，我们需要安装scipy库。

pip install scipy

然后，我们可以使用scipy库中的KDTree类来构建KD树。

from scipy.spatial import KDTree

# 构建商品的KD树
product_coordinates = [(product[1], product[2]) for product in product_data]
product_kd_tree = KDTree(product_coordinates)

接下来，我们可以使用KD树来查找每个会员附近的商品。

selected_products = []
allocated_members = []

for member in member_data:
    member_id = member[0]
    member_lat = member[1]
    member_lon = member[2]
    member_limit = member[3]
    allocated_quantity = 0

    # 在KD树中查找附近的商品
    nearest_indices = product_kd_tree.query_ball_point((member_lat, member_lon), 0.1)

    for index in nearest_indices:
        product = product_data[index]
        product_id = product[0]
        product_quantity = product[3]

        # 检查商品是否已经被分配给其他会员
        if product_id in selected_products:
            continue

        # 将商品分配给会员
        selected_products.append(product_id)
        allocated_members.append((product_id, member_id))
        allocated_quantity += product_quantity

        # 检查是否已经达到会员的预订商品限额
        if allocated_quantity >= member_limit:
            break

这样，我们使用KD树来加速距离计算，从而提高了算法的效率。