如何提高优化问题的可扩展性？

问题描述 投票：0回答：1

我正在尝试在考虑到不同限制的情况下优化商店经理的数量。 基本上，我想尽量减少一周内每天必须访问商店的经理数量。 我用 Pulp 库设计了这个问题，发现它适用于很少数量的商店（直到 10 家），但它不会扩展到更多（例如 300 家商店）

有关用例的一些解释：

  • 每家商店必须每周拜访一次，最多 1 名经理
  • 经理每天最多可以工作（包括出差）8小时
  • 如果经理访问一家商店，那么他将被归因于他访问的随机“家”商店，就好像他住在那里一样（简化行程时间计算）

我还没有实现旅行功能（目前我假设需要 2 小时），但它实际上应该考虑到当天访问的商店和“家”商店之间的最大旅行时间。对于商店之间的时间旅行，我现在考虑每天最大工作时间的任意值（我知道这是一个 TSP 问题，但我无法直接实现它，所以我将检索解决方案，然后对它们执行 TSP 以查看如果合适的话）。

我对优化了解甚少，您认为可以如何优化？还是一开始就太复杂，需要太多时间来计算？

import pulp as lp
import numpy as np

# Number of stores
num_stores = 11

# Generate a randomd 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. Set objective function
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}")
python optimization pulp
1个回答
0
投票

有几件事可以帮助推动这一进程：

  1. 这是一个有数次曲折的 TSP，因此它不会很好地扩展，但它应该可以超过 10。

  2. 您的链接变量 z 未正确实现，因此您的结果不准确。 对 TSP 的链接变量进行一些侧面研究。 网上或任何 LP 教科书中都有很多。 不相信？ 在解决后添加此内容：

for idx in z:
    print(idx, z[idx].varValue)

  1. 尚不清楚

    days
    的含义是什么。 如果旅行者只是从前一天离开的地方继续（假设），为什么还要花时间而不只是做 8 x 5 = 40 小时呢？

  2. 开发此功能时，请从小数据和非随机值开始。 您可以在一张草稿纸上算出一些东西，并制定一个公式，根据解决后的 

    .varValue
    计算每个经理的出行时间，然后检查它！ 从 1 名经理、4 家商店开始。 说服自己它有效并且与您的手动计算一致。 添加第二位经理并尝试尽量减少旅行时间等，并说服自己有效，从那里开始......:)

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.