Implementing specific constraint in Pulp

Question

I have successfully implemented a program where I allocate N truck drivers to M gathering hubs for each one of the days of the week. The constraints I have implemented are:

1. • A driver cannot work more than 6 days, i.e. 1 day to rest
2. • A driver cannot be allocated in more than 1 hubs for each day
3. • Each hub must satisfy its driver requirements for each day of the week

The program runs smoothly, satisfies the overall objective and outputs for each hub-driver pair a schedule in the following form:

                 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 

However, I would like to add an extra constraint that forces the drivers to work at one hub, if possible, instead of their working days being split in many hubs, i.e. maximize work at one hub before allocating the driver at a different hub.

For instance, in the above output, we see that the driver works 3 days at a different hub and 3 days at Hub 7. How can we write a constraint to make drivers be allocated -if possible- to work at one hub if possible?

Please find my code below.

Thank you

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

You could add binary variables z indicating if a driver is active on a hub:

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

Then change your objective to (minimize the sum of drivers active on hubs):

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

Add constraints to connect z with 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))

However, this model is more complex and finding an optimal solution seems to take a while. You can set a timeout (here 10 seconds) to get a solution:

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