pythonalgorithmmathematical-optimization

Transportation problem with transit limitations


I need to find the solution to transportation problem with transit limitations and below there is the code which works correctly.

However I don't know how to input these limitations in the code.

Lower bound:

1 2 1 2 1
2 1 1 1 3
0 1 2 1 1
2 1 3 1 2

Upper bound:

9 8 6 10 5
7 15 4 6 9
5 6 6 5 10
8 5 7 4 8

All your ideas will be appreciated. Thanks in advance.


import pandas as pd
import pulp

truck_capacity = 6
suppliers = pd.RangeIndex(name='supplier', stop=4)
consumers = pd.RangeIndex(name='consumer', stop=5)

supply = pd.Series(
    name='supply', 
    index=suppliers, 
    data=(17, 8, 10, 9),
)
demand = pd.Series(
    name='demand', 
    index=consumers, 
    data=(6, 15, 7, 8, 8),
)
price_per_tonne = pd.DataFrame(
    index=suppliers, columns=consumers,
    data=(
        (10,  8,  5,  9, 16),
        ( 4,  3,  4, 11, 12),
        ( 5, 10, 29,  7,  6),
        ( 9,  2,  4,  1,  3),
    ),
).stack()
price_per_tonne.name = 'price'

flow = pd.DataFrame(
    index=suppliers, columns=consumers,
    data=pulp.LpVariable.matrix(
        name='flow_s%d_c%d', cat=pulp.LpContinuous, lowBound=0,
        indices=(suppliers, consumers),
    ),
).stack()
flow.name = 'flow'

trucks = pd.DataFrame(
    index=suppliers, columns=consumers,
    data=pulp.LpVariable.matrix(
        name='trucks_s%d_c%d', cat=pulp.LpInteger, lowBound=0,
        indices=(suppliers, consumers),
    )
).stack()
trucks.name = 'trucks'

price = truck_capacity * pulp.lpDot(price_per_tonne, trucks)
prob = pulp.LpProblem(name='transportation', sense=pulp.LpMinimize)
prob.setObjective(price)

# The flow must not exceed the supply
for supplier, group in flow.groupby('supplier'):
    prob.addConstraint(
        name=f'flow_supply_s{supplier}',
        constraint=pulp.lpSum(group) <= supply[supplier],
    )

# The flow must exactly meet the demand
for consumer, group in flow.groupby('consumer'):
    prob.addConstraint(
        name=f'flow_demand_c{consumer}',
        constraint=pulp.lpSum(group) == demand[consumer],
    )

# The capacity must be able to carry the flow
for (supplier, consumer), truck_flow in flow.items():
    prob.addConstraint(
        name=f'capacity_s{supplier}_c{consumer}',
        constraint=truck_flow <= trucks[(supplier, consumer)] * truck_capacity
    )


 

print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal

print(f'Total price: ${price.value():.2f}')
print()

print('Flow:')
flow = flow.apply(pulp.value).unstack(level='consumer')
print(flow)
print()

print('Trucks:')
trucks = trucks.apply(pulp.value).unstack(level='consumer')
print(trucks)
print()

print('Prices:')
print(trucks * truck_capacity * price_per_tonne.unstack(level='consumer'))


Solution

  • Call bounds once for every lower/upper flow bound:

    import pandas as pd
    import pulp
    
    truck_capacity = 6
    suppliers = pd.RangeIndex(name='supplier', stop=4)
    consumers = pd.RangeIndex(name='consumer', stop=5)
    
    supply = pd.Series(
        name='supply',
        index=suppliers,
        data=(17, 8, 10, 9),
    )
    demand = pd.Series(
        name='demand',
        index=consumers,
        data=(6, 15, 7, 8, 8),
    )
    price_per_tonne = pd.DataFrame(
        index=suppliers, columns=consumers,
        data=(
            (10,  8,  5,  9, 16),
            ( 4,  3,  4, 11, 12),
            ( 5, 10, 29,  7,  6),
            ( 9,  2,  4,  1,  3),
        ),
    ).stack()
    price_per_tonne.name = 'price'
    
    flow = pd.DataFrame(
        index=suppliers, columns=consumers,
        data=pulp.LpVariable.matrix(
            name='flow_s%d_c%d', cat=pulp.LpContinuous,
            indices=(suppliers, consumers),
        ),
    ).stack()
    flow.name = 'flow'
    
    flow_lower = pd.DataFrame(
        index=suppliers, columns=consumers,
        data=(
            (1, 2, 1, 2, 1),
            (2, 1, 1, 1, 3),
            (0, 1, 2, 1, 1),
            (2, 1, 3, 1, 2),
        ),
    )
    flow_upper = pd.DataFrame(
        index=suppliers, columns=consumers,
        data=(
            (9,  8,  6, 10,  5),
            (7, 15,  4,  6,  9),
            (5,  6,  6,  5, 10),
            (8,  5,  7,  4,  8),
        ),
    )
    for (supplier, consumer), flow_value in flow.items():
        flow_value.bounds(
            low=flow_lower.loc[supplier, consumer],
            up=flow_upper.loc[supplier, consumer],
        )
    
    trucks = pd.DataFrame(
        index=suppliers, columns=consumers,
        data=pulp.LpVariable.matrix(
            name='trucks_s%d_c%d', cat=pulp.LpInteger, lowBound=0,
            indices=(suppliers, consumers),
        )
    ).stack()
    trucks.name = 'trucks'
    
    price = truck_capacity * pulp.lpDot(price_per_tonne, trucks)
    prob = pulp.LpProblem(name='transportation', sense=pulp.LpMinimize)
    prob.setObjective(price)
    
    # The flow must not exceed the supply
    for supplier, group in flow.groupby('supplier'):
        prob.addConstraint(
            name=f'flow_supply_s{supplier}',
            constraint=pulp.lpSum(group) <= supply[supplier],
        )
    
    # The flow must exactly meet the demand
    for consumer, group in flow.groupby('consumer'):
        prob.addConstraint(
            name=f'flow_demand_c{consumer}',
            constraint=pulp.lpSum(group) == demand[consumer],
        )
    
    # The capacity must be able to carry the flow
    for (supplier, consumer), truck_flow in flow.items():
        prob.addConstraint(
            name=f'capacity_s{supplier}_c{consumer}',
            constraint=truck_flow <= trucks[(supplier, consumer)] * truck_capacity
        )
    
    print(prob)
    prob.solve()
    assert prob.status == pulp.LpStatusOptimal
    
    print(f'Total price: ${price.value():.2f}')
    print()
    
    print('Flow:')
    flow = flow.apply(pulp.value).unstack(level='consumer')
    print(flow)
    print()
    
    print('Trucks:')
    trucks = trucks.apply(pulp.value).unstack(level='consumer')
    print(trucks)
    print()
    
    print('Prices:')
    print(trucks * truck_capacity * price_per_tonne.unstack(level='consumer'))
    
    Result - Optimal solution found
    
    Objective value:                966.00000000
    Enumerated nodes:               0
    Total iterations:               0
    Time (CPU seconds):             0.00
    Time (Wallclock seconds):       0.00
    
    Option for printingOptions changed from normal to all
    Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00
    
    Total price: $966.00
    
    Flow:
    consumer    0    1    2    3    4
    supplier                         
    0         2.0  8.0  1.0  5.0  1.0
    1         2.0  1.0  1.0  1.0  3.0
    2         0.0  5.0  2.0  1.0  2.0
    3         2.0  1.0  3.0  1.0  2.0
    
    Trucks:
    consumer    0    1    2    3    4
    supplier                         
    0         1.0  2.0  1.0  1.0  1.0
    1         1.0  1.0  1.0  1.0  1.0
    2         0.0  1.0  1.0  1.0  1.0
    3         1.0  1.0  1.0  1.0  1.0
    
    Prices:
    consumer     0     1      2     3     4
    supplier                               
    0         60.0  96.0   30.0  54.0  96.0
    1         24.0  18.0   24.0  66.0  72.0
    2          0.0  60.0  174.0  42.0  36.0
    3         54.0  12.0   24.0   6.0  18.0