Difficult in implementing specific constraint

[gelazari]

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 requirements in drivers for each day of the week

The program runs smoothly and 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 to force the drivers work at one hub, if possible, instead of their working days being split in many hubs.

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)

[gelazari]

Any ideas?

[stumitchell]

probably better to ask in stack overflow as there are more people there.

but in short

make a binary variable that represents a driver allocation to a hub

for hub in range(hubs):
      DH[hub][driver] <= lpsum(var[h][driver][day] for driver in range(drivers) for day in range(days)

then add the DH variables to the objective some way depending if you want to minimise the maximum hubs a driver works out of or minimise the total of DH

Stu