2
$\begingroup$

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:

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

The program runs smoothly, satisfies the overall objective and outputs a schedule for each hub-driver pair.

However, the extra constraint that forces the drivers to work at one hub (constraint 4), instead of their working days being split into many hubs, is violated and assigns some drivers to many hubs.

How can that be fixed?

Please find my code below.

Thank you

import pulp
import pandas as pd
import numpy as np

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

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_hubs = len(day_requirement)  # number of hubs

days = 7

def schedule(drivers, hubs, day_requirement):
    # driver_names = ilm_riders['riders']
    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

    #  we 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')
    # 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 += days * z[h][driver] >= pulp.lpSum(var[h][driver][day] for day in range(days))

    # 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

    # 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

    # for driver in range(drivers):
    #     problem += pulp.lpSum([var[h][driver][day] for day in range(days) for h in range(hubs)]) >= 5

    # Solve problem. We have a very complex solution so we set a timeout at 10secs.
    status = problem.solve(pulp.PULP_CBC_CMD(msg=False, timeLimit=10))

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

    col = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']
    # col = ['Day_{}'.format(i) for i in range(days)]
    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

    # print(dashboard)

    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])
    return driver_sums, dashboard, status


driver_sums, dashboard, status = schedule(total_drivers, total_hubs, day_reqs)
while (driver_sums > 6).any() or status == -1:
    print('Staus infeasible OR one or more drivers have been allocated more than 6 days of work so '
          'we must add one '
          'driver: {}->{}'.format(total_drivers, total_drivers + 1))
    total_drivers += 1
    driver_sums, dashboard, status = schedule(total_drivers, total_hubs, day_reqs)


# dashboard = schedule(total_drivers, total_hubs, day_reqs)
driver_table = dashboard.groupby('Driver').sum()
driver_sums = driver_table.sum(axis=1)
# print(driver_sums)
day_sums = driver_table.sum(axis=0)

```
$\endgroup$
4
$\begingroup$

Introduce linear constraints: $$\sum_{\text{h}} z[\text{h}][\text{driver}] \le 1 \quad\text{for each driver}$$

$\endgroup$
18
  • $\begingroup$ Thank you for the answer. The problem is that when i add this constraint, then constraint 1, i.e. A driver cannot work more than 6 days, i.e. 1 day to rest, seems to be violated and only a few drivers work 6 days; most of them end up working 1-5 days. Can this somehow be amended? $\endgroup$
    – azal
    Jul 25 at 17:27
  • $\begingroup$ How does working 1-5 days violate the "cannot work more than 6 days" rule? $\endgroup$
    – RobPratt
    Jul 25 at 18:54
  • $\begingroup$ You’re right. Please Let me rephrase: I would like the truck drivers to work exactly 6 days per week and 1 day off. However, if I set the constraint to == 6 the problem seems to be unsolvable (?) $\endgroup$
    – azal
    Jul 25 at 21:27
  • $\begingroup$ The requirements add up to 134, which is not a multiple of 6. $\endgroup$
    – RobPratt
    Jul 25 at 23:52
  • $\begingroup$ Could you please elaborate on that? I literally have no idea what that means $\endgroup$
    – azal
    Jul 26 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.