换电站供应仓库匹配优化问题类型及适配OR算法选型咨询

该场景属于带容量约束、服务半径限制、最低需求满足约束的设施分配问题（Capacitated Facility Location Problem, CFLP 变种），归属于整数线性规划范畴的NP-hard问题，核心特征匹配如下：

• 决策变量：仓库与换电站的绑定关系、各仓库向绑定换电站分配的电池供给量
• 硬约束条件：仓库总分配量不超过自身存储容量、每个换电站获得的供给量不低于自身需求的50%、仅允许距离≤50英里的仓库和换电站绑定
• 可自定义优化目标：通常可选最小化总运输距离/成本、最大化整体需求满足率、最小化仓库启用成本等

可根据问题规模选择对应的求解方案：

• 小体量场景（仓库+换电站总数≤100）：直接用整数规划求解器即可得到全局最优解，可选工具包括商业求解器Gurobi/CPLEX，或开源求解器OR-Tools/PuLP/CBC
• 大体量场景（仓库+换电站总数≥1000）：可采用元启发式算法求近似最优解，适配算法包括拉格朗日松弛算法、遗传算法、模拟退火、禁忌搜索，求解速度远快于精确求解器，结果精度可满足工业场景需求
• 快速验证场景：可采用贪心算法，按距离由近到远优先给换电站匹配最近的可用容量仓库，实现逻辑简单、求解速度极快，仅结果通常非最优

你提供的示例数据如下：

import numpy as np
# 换电站与仓库距离表（单位：英里）
distance_df= [{'Fuel Station':'FS1', 'Warehouse1': 40, 'Warehouse2': 38, 'Warehouse3':68},
    {'Fuel Station':'FS2', 'Warehouse1':53, 'Warehouse2': 46, 'Warehouse3': 50},
    {'Fuel Station':'FS3', 'Warehouse1':62, 'Warehouse2': 80, 'Warehouse3': np.nan},
    {'Fuel Station':'FS4', 'Warehouse1':75, 'Warehouse2': np.nan, 'Warehouse3': 50}]
# 仓库容量表（单位：电池数量）
capacity_df = [{'Warehouse':'Warehouse1', 'Capacity': 2500},
    {'Warehouse':'Warehouse2', 'Capacity':2000},
    {'Warehouse':'Warehouse3', 'Capacity':3200}]
# 换电站需求表（单位：电池数量）
demand_df = [{'Fuel Station':'FS1', 'Demand': 2300},
    {'Fuel Station':'FS2', 'Demand':4680},
    {'Fuel Station':'FS3', 'Demand':8000}]

按50英里距离约束预过滤后，FS3不存在符合条件的绑定仓库，无法满足最低50%需求的约束，需要补充覆盖FS3的仓库或放宽距离要求后再求解。

内容的提问来源于stack exchange，提问作者themlchic