在纸浆中实现特定约束

Question

我已成功实施了一项计划，在该计划中，我为一周中的每一天分配Ntruck drivers到Mgathering hubs。我实施的约束条件包括：

1. • 驾驶员工作时间不能超过6天，即休息1天
2. • 每天不能在超过1个集线器中分配驱动程序
3. • 每个枢纽必须满足其驾驶员一周中每天的要求

该计划运行平稳，满足总体目标，并为每个轮毂驱动器对输出以下形式的时间表：

                 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 

但是，我想添加一个额外约束，强制驾驶员在一个中心工作，如果可能的话，而不是将他们的工作日分成多个中心，即在将驾驶员分配到不同的中心之前，最大限度地提高在一个中心的工作效率

例如，在上面的输出中，我们看到驱动程序在不同的中心工作3天，在中心7工作3天。我们如何编写一个约束，使驱动程序被分配（如果可能的话）在一个中心工作（如果可能的话）

请在下面找到我的代码

多谢各位

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')

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

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))