在纸浆中实施特定约束

Question

我已经成功地实现了一个程序，我为每个人分配 N truck drivers 到 M gathering hubs星期几。我实施的约束是：

- A driver 不能工作超过 6 天，即休息 1 天
- Adriver每天不能分配到超过1个hub
- 每个集线器必须满足一周中每一天的 driver 要求

程序运行顺利，满足整体 objective 并为每个 hub-driver 对输出以下形式的时间表：

                 Monday  Tuesday  Wednesday  Thursday  Friday  Saturday  Sunday
Hub   Driver                                                                   
Hub 1 Driver_20       1        0          0         0       0         0       0
Hub 2 Driver_20       0        0          0         0       0         0       0
Hub 3 Driver_20       0        0          0         0       0         0       0
Hub 4 Driver_20       0        0          0         0       0         0       0
Hub 5 Driver_20       0        1          0         0       0         0       0
Hub 6 Driver_20       0        0          0         0       1         0       0
Hub 7 Driver_20       0        0          0         1       0         1       1

但是， 我想添加一个 额外约束 强制 driver 在一个集线器上工作，如果可能的话，与其将他们的工作日分配到多个中心，不如在将 driver 分配到另一个中心之前最大限度地在一个中心工作。

例如，在上面的输出中，我们看到 driver 在不同的集线器上工作了 3 天，在集线器 7 上工作了 3 天。我们如何编写一个约束来使 drivers分配 - 如果可能的话 - 在一个枢纽工作？

请在下面找到我的代码。

谢谢

import pulp
import pandas as pd
import numpy as np

pd.set_option('display.max_rows', None)
pd.set_option('display.max_columns', None)
pd.set_option('display.width', 2000)
pd.set_option('display.float_format', '{:20,.2f}'.format)
pd.set_option('display.max_colwidth', None)

day_requirement = [[2, 2, 3, 2, 5, 2, 2],
                    [2, 2, 2, 2, 2, 2, 2],
                    [2, 2, 2, 2, 2, 2, 2],
                    [3, 3, 3, 3, 3, 3, 3],
                    [2, 2, 2, 2, 2, 2, 2],
                    [2, 2, 2, 2, 2, 2, 2],
                    [4, 4, 4, 4, 4, 4, 4],
                   ]

total_day_requirements = ([sum(x) for x in zip(*day_requirement)])

hub_names = {0: 'Hub 1',
             1: 'Hub 2',
             2: 'Hub 3',
             3: 'Hub 4',
             4: 'Hub 5',
             5: 'Hub 6',
             6: 'Hub 7'}

total_drivers = max(total_day_requirements)  # number of drivers
total_days = 7  # The number of days in week
total_hubs = len(day_requirement)  # number of hubs

def schedule(drivers, days, hubs):
    driver_names = ['Driver_{}'.format(i) for i in range(drivers)]
    var = pulp.LpVariable.dicts('VAR', (range(hubs), range(drivers), range(days)), 0, 1, 'Binary')

    problem = pulp.LpProblem('shift', pulp.LpMinimize)

    obj = None
    for h in range(hubs):
        for driver in range(drivers):
            for day in range(days):
                obj += var[h][driver][day]
    problem += obj

    # schedule must satisfy daily requirements of each hub
    for day in range(days):
        for h in range(hubs):
            problem += pulp.lpSum(var[h][driver][day] for driver in range(drivers)) == \
                       day_requirement[h][day]

    # a driver cannot work more than 6 days
    for driver in range(drivers):
        problem += pulp.lpSum([var[h][driver][day] for day in range(days) for h in range(hubs)]) <= 6

    # if a driver works one day at a hub, he cannot work that day in a different hub obviously
    for driver in range(drivers):
        for day in range(days):
            problem += pulp.lpSum([var[h][driver][day] for h in range(hubs)]) <= 1

    # Solve problem.
    status = problem.solve(pulp.PULP_CBC_CMD(msg=0))

    idx = pd.MultiIndex.from_product([hub_names.values(), driver_names], names=['Hub', 'Driver'])

    col = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']

    dashboard = pd.DataFrame(0, idx, col)

    for h in range(hubs):
        for driver in range(drivers):
            for day in range(days):
                if var[h][driver][day].value() > 0.0:
                    dashboard.loc[hub_names[h], driver_names[driver]][col[day]] = 1

    driver_table = dashboard.groupby('Driver').sum()
    driver_sums = driver_table.sum(axis=1)
    # print(driver_sums)

    day_sums = driver_table.sum(axis=0)
    # print(day_sums)

    print("Status", pulp.LpStatus[status])

    if (driver_sums > 6).any():
        print('One or more drivers have been allocated more than 6 days of work so we must add one '
              'driver: {}->{}'.format(len(driver_names), len(driver_names) + 1))
        schedule(len(driver_names) + 1, days, hubs)
    else:
        print(dashboard)
        print(driver_sums)
        print(day_sums)
        for driver in range(drivers):
            driver_name = 'Driver_{}'.format(driver)
            print(dashboard[np.in1d(dashboard.index.get_level_values(1), [driver_name])])


schedule(total_drivers, total_days, total_hubs)

Answer 1

您可以添加二进制变量 z 指示驱动程序是否在集线器上处于活动状态：

z = pulp.LpVariable.dicts('Z', (range(hubs), range(drivers)), 0, 1, 'Binary')

然后将您的 objective 更改为（最小化集线器上活动的驱动程序总数）：

for h in range(hubs):
    for driver in range(drivers):
        obj += z[h][driver]
problem += obj

添加约束以连接 z 和 var:

for driver in range(drivers):
    for h in range(hubs):
        problem += z[h][driver] <= pulp.lpSum(var[h][driver][day] for day in range(days))
        problem += total_days*z[h][driver] >= pulp.lpSum(var[h][driver][day] for day in range(days))

不过，这个模型比较复杂，找到最优解似乎需要一段时间。您可以设置一个超时时间（这里是10秒）来获得解决方案：

status = problem.solve(pulp.PULP_CBC_CMD(msg=0, timeLimit=10))

在纸浆中实施特定约束

Implementing specific constraint in Pulp

python

optimization

pulp