如何提升商店经理分配优化问题的可扩展性？

我正尝试在多种约束下优化商店经理的数量，目标是最小化每周需每日拜访门店的经理人数。使用PuLP库构建的优化模型在门店数量极少（最多10家）时可行，但无法扩展到更大规模（如300家门店）。

业务约束 #

• 每家门店每周必须被且仅被一位经理拜访一次
• 经理每日工作（含出行）时长不超过8小时
• 若经理拜访某门店，会从其拜访的门店中指定一个作为「家门店」，用于简化出行时长计算

当前模型现状 #

目前尚未实现完整的出行时间计算逻辑（暂假设出行耗时2小时），实际需考虑当日拜访门店与「家门店」之间的最大出行时长。已知这涉及TSP问题，但无法直接实现，因此计划先获取分配方案，再通过TSP验证是否可行。

对优化领域了解有限，请问该如何优化模型以提升可扩展性？或是该问题从一开始就过于复杂，计算耗时过长？

当前实现代码 #

import pulp as lp
import numpy as np

# Number of stores
num_stores = 11

# Generate a random time matrix (hours)
np.random.seed(42)  # Set seed for reproducibility
random_distances = np.random.uniform(1, 2, size=(num_stores, num_stores))

# Make the matrix symmetric by copying the upper triangle to the lower triangle
time_matrix = (random_distances + random_distances.T) / 2

# Set the diagonal to 0 (distance from a store to itself is zero)
np.fill_diagonal(time_matrix, 0)

# Convert the numpy matrix to a Python list (for use in PuLP)
time_matrix = time_matrix.tolist()

# Parameters
num_managers = 4 # Max number of area managers
num_days = 5  # Days in a week
working_hours_per_day = 8
service_time = 1  # Time spent at each store 

# Create a PuLP model
model = lp.LpProblem("StoreManagerAssignmentPerDay", lp.LpMinimize)

# Decision variables
# x[i, j, d] = 1 if store i is assigned to manager j on day d, otherwise 0
x = lp.LpVariable.dicts("x", ((i, j, d) for i in range(num_stores) for j in range(num_managers) for d in range(num_days)), cat=lp.LpBinary)

# z[i1, i2, j, d] = 1 if both stores i1 and i2 are assigned to manager j on day d
z = lp.LpVariable.dicts("z", ((i1, i2, j, d) for i1 in range(num_stores) for i2 in range(num_stores) 
                              for j in range(num_managers) for d in range(num_days)), cat=lp.LpBinary)

# New binary variables y[j] to indicate if manager j is used
y = lp.LpVariable.dicts("y", (j for j in range(num_managers)), cat=lp.LpBinary)

# Home store assignment variable
h = lp.LpVariable.dicts("h", ((i, j) for i in range(num_stores) for j in range(num_managers)), cat=lp.LpBinary)

# Objective: Minimize the number of managers used
model += lp.lpSum([y[j] for j in range(num_managers)])

# Constraints

#0. Link y[j] to manager usage
for j in range(num_managers):
    model += y[j] >= lp.lpSum([x[i, j, d] for i in range(num_stores) for d in range(num_days)])/(num_stores*num_days), f"Link_y_{j}"

# 1. Each store must be assigned to exactly one manager across all days
for i in range(num_stores):
    model += lp.lpSum([x[i, j, d] for j in range(num_managers) for d in range(num_days)]) == 1, f"AssignStore_{i}"

# 2. Linking constraints for z variables
for j in range(num_managers):
    for d in range(num_days):
        for i1 in range(num_stores):
            for i2 in range(i1 + 1, num_stores):
                # z[i1, i2, j, d] can only be 1 if both x[i1, j, d] and x[i2, j, d] are 1
                model += z[i1, i2, j, d] <= x[i1, j, d], f"Link_z_{i1}_{i2}_{j}_{d}_1"
                model += z[i1, i2, j, d] <= x[i2, j, d], f"Link_z_{i1}_{i2}_{j}_{d}_2"
                model += z[i1, i2, j, d] >= x[i1, j, d] + x[i2, j, d] - 1, f"Link_z_{i1}_{i2}_{j}_{d}_3"

# 3. Maximum working hours per day
for j in range(num_managers):
    for d in range(num_days):
        service_time_total = lp.lpSum([x[i, j, d] * service_time for i in range(num_stores)])
        travel_time_total = lp.lpSum([z[i1, i2, j, d] * time_matrix[i1][i2] 
                                      for i1 in range(num_stores) for i2 in range(i1 + 1, num_stores)])
        
        # Introduce a variable to represent the maximum travel time to the home store for each manager and day
        max_travel_to_home = lp.LpVariable(f"max_travel_to_home_{j}_{d}", lowBound=0)

        # Add constraints to ensure max_travel_to_home[j, d] captures the maximum travel time to home
        # for h_i in range(num_stores):
        #     # Add a constraint that captures the maximum travel time
        #     model += max_travel_to_home >= lp.lpSum([travel_time[i][h_i] * x[i, j, d] for i in range(num_stores)]) * h[h_i, j], f"MaxTravelToHome_{j}_{d}_{h_i}"

        # Total time for each manager per day includes service time, travel time, and the maximum travel time to the home store
        total_time = service_time_total + travel_time_total + 2
        model += total_time <= working_hours_per_day, f"MaxWorkingHours_{j}_{d}"

# 4. Home store assignment
for j in range(num_managers):
    # Linking visits to having a home store
    model += lp.lpSum([h[i, j] for i in range(num_stores)]) >= lp.lpSum([x[i, j, d] for i in range(num_stores) for d in range(num_days)])/num_stores, f"HomeStoreIfVisited_{j}"
    # Ensure no home store if no visits
    model += lp.lpSum([h[i, j] for i in range(num_stores)]) <= lp.lpSum([x[i, j, d] for i in range(num_stores) for d in range(num_days)]), f"NoVisitsNoHomeStore_{j}"
    # A manager cannot have more than one home store
    model += lp.lpSum([h[i, j] for i in range(num_stores)]) <= 1, f"OneHomeStorePerManager_{j}"


# 5. If a manager is assigned a home store, they must visit it during the week
for i in range(num_stores):
    for j in range(num_managers):
        model += h[i, j] <= lp.lpSum([x[i, j, d] for d in range(num_days)]), f"HomeStoreVisits_{i}_{j}"


solver = lp.PULP_CBC_CMD(msg=1)
model.solve(solver)

min_managers = int(lp.value(lp.lpSum([y[j] for j in range(num_managers)])))

print(f"Minimum number of managers required: {min_managers}")

解决方案建议 #

1. 大幅削减变量数量 #

当前模型的z变量是导致规模爆炸的核心问题：当有300家门店时，z变量的数量是300*300*num_managers*5，会生成百万级甚至千万级的变量和约束，完全超出常规求解器的处理能力。

替代方案：

• 取消z变量，改用更高效的方式计算出行时间。由于你计划后续用TSP验证，模型阶段可以先使用简化的出行时间估算：比如按单店平均出行时间，或者按当日拜访门店的数量乘以固定系数（比如每增加一家店增加0.5小时出行时间）。
• 或者，将出行时间约束延迟到TSP验证阶段，模型只处理门店-经理-日期的分配，以及每日拜访门店数量的上限（根据服务时间和剩余工作时长估算最大可拜访门店数）。

2. 分层优化（两阶段求解） #

将问题拆分为两个独立的优化步骤，避免在单个模型中处理所有复杂约束：

• 第一阶段：仅解决门店到经理的分配（不考虑日期），目标是最小化经理数量，同时保证每个经理负责的门店集合可以在5天内完成拜访（根据每日最大可拜访门店数）。
• 第二阶段：将每个经理的门店集合分配到具体日期，再用TSP验证每日行程的时间可行性，若不可行则调整日期分配或重新划分门店集合。

3. 放松模型精度，使用启发式算法 #

对于300家门店的规模，精确求解整数规划问题本身就非常困难，可以考虑使用启发式算法快速得到近似最优解：

• 先按地理位置对门店聚类，将相邻门店分配给同一经理，再调整聚类结果以满足每日工作时长约束。
• 使用遗传算法、模拟退火等启发式方法，在合理时间内找到可行的分配方案。

4. 优化现有模型的约束和变量 #

• 简化Link_y约束：将y[j] >= lp.lpSum(x[i,j,d] for i,d)/(num_stores*num_days)改为y[j] >= lp.lpSum(x[i,j,d] for i,d) * 1e-6，只要经理负责至少一家门店，y[j]就会被强制设为1，约束更紧凑且易于求解。
• 移除h变量：将「家门店」的选择延迟到TSP阶段，模型中不处理该变量，只在后续行程规划时选择最优的家门店以最小化出行时间。

5. 使用更高效的求解器 #

PuLP默认的CBC求解器在处理大规模整数规划时性能有限，可以尝试：

• 商业求解器：如Gurobi、CPLEX，它们在处理大规模问题时有更好的剪枝和并行计算能力。
• 开源高性能求解器：如SCIP，其性能优于CBC，适合处理复杂整数规划问题。

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