基于地理位置和限额的商品分配Python算法及优化

import pandas as pd
import numpy as np
from geopy.distance import geodesic

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

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

# 计算距离
def calculate_distance(lat1, lon1, lat2, lon2):
    coords_1 = (lat1, lon1)
    coords_2 = (lat2, lon2)
    return geodesic(coords_1, coords_2).km

# 初始化结果
result = pd.DataFrame(columns=['会员编号', '商品编号', '打包数量'])

# 优化算法：预先计算距离矩阵
distance_matrix = np.zeros((len(member_df), len(product_df)))
for i in range(len(member_df)):
    for j in range(len(product_df)):
        distance_matrix[i, j] = calculate_distance(member_df.iloc[i]['会员GPS纬度'], 
                                                    member_df.iloc[i]['会员GPS经度'], 
                                                    product_df.iloc[j]['新商品GPS纬度'], 
                                                    product_df.iloc[j]['新商品GPS经度'])

# 遍历会员
for i in range(len(member_df)):
    member = member_df.iloc[i]
    member_id = member['会员编号']
    member_limit = member['预订商品限额']
    
    # 找到距离 within 0.1 的商品索引
available_products = np.where(distance_matrix[i] <= 0.1)[0]
    
    # 如果没有符合距离的商品，跳过该会员
    if len(available_products) == 0:
        print(f'会员编号：{member_id}，挑选到商品数量：0，预订商品限额：{member_limit}')
        continue
    
    # 按距离排序
sorted_products = np.argsort(distance_matrix[i])[available_products]
    
    # 贪心算法：优先选择数量少于限额的商品
total_quantity = 0
    selected_products = []
    for j in sorted_products:
        product_quantity = product_df.iloc[j]['打包数量']
        if total_quantity + product_quantity <= member_limit:
            total_quantity += product_quantity
            selected_products.append(j)
            
    # 更新结果
    for j in selected_products:
        result = result.append({'会员编号': member_id, '商品编号': product_df.iloc[j]['商品编号'], '打包数量': product_df.iloc[j]['打包数量']}, ignore_index=True)
    
    # 输出每个会员挑选到商品的数量和会员的预订商品限额
    print(f'会员编号：{member_id}，挑选到商品数量：{total_quantity}，预订商品限额：{member_limit}')

# 输出每个商品被分配到哪个会员
product_group = result.groupby('商品编号')
for product, group in product_group:
    print(f'商品编号：{product}，被分配到会员：{', '.join(group['会员编号'].tolist())}')

优化思路：

预先计算距离矩阵: 避免重复计算会员和商品之间的距离，提高效率。
使用numpy数组操作: 使用numpy数组进行距离计算和排序，比循环遍历DataFrame更高效。
贪心算法: 优先选择数量少于限额且距离最近的商品，可以更快地找到可行解，但可能无法保证找到全局最优解。

其他优化方向：

动态规划: 可以使用动态规划算法寻找全局最优解，但时间复杂度较高。
多线程/多进程: 可以使用多线程或多进程并行处理不同会员的商品分配，进一步提高效率。