Python PuLP Optimization – Simple Logistics Example

Python PuLP Optimization – Simple Logistics Example
August 20, 2017 Reece

Python COIN-OR

PuLP for Python is an optimization tool like the Excel Solver (COIN-OR PuLP). I had a use case that didn’t quite fit the out of the box examples provided by the writers of this awesome python package. After some trial and error, I was able to come up with a solution that I will review below.

Background

The logistics example (Beer Distribution Problem) provided by the developers is a great example, however, I wanted to approach it differently. I had already determined routes and an estimated margin impact for each of the lanes. We had other constraints that required a minimum volume per week on certain lanes to meet certain demands even if they were not a net positive on the transportation margin (see the ‘ImpactPer’ column in the data). We also had a limit on how many miles we could cover in a week due to a finite amount of trucks. The goal was to optimally select which lanes to run and at what volumes to maximize equipment utilization and financial impact.


Sample Data

The below is a random sample data set that is similar to the data set I had to work with.

LaneId
Distance
ImpactPer
MinVol
MaxVol
0570349.5026
1117109.4203
21200.451525
31116-915.5900
41058-1,000.5600
5942-550.6800
61103-960.4500
7921-787.0002
81091-927.7500
944382.0838
101688-889.4900
11432-265.2824
12451-81.15810
13505-545.4600
14444-50.0000
151247-878.5400
16710-837.9502
17323-379.9101
181035-508.7312
191139-946.0800
201136-535.7401
211251512.7966
221107-952.4100
231180-1,045.2904
24268107.7244
25863-47.5001

Python Code

First, we import our modules, set our high-level constraints, and import the data itself.


import pandas as pd
from pulp import *

''' SET HIGH LEVEL CONSTRAINTS '''
OPTSET_MILE_LIMIT_UPPER = 22000
OPTSET_MILE_LIMIT_LOWER = 20000


'''
Import the data, set the laneId as the Index
'''
data = pd.read_excel('SampleData.xlsx')

Now with the basics in place, we setup the PuLP model itself by defining our lanes, constraints, problem type, etc.

''' INIT LP SOLVER '''
prob = pulp.LpProblem('LaneSelectionOptimization', LpMaximize)

''' SOLVER SETUP '''
Lanes = data.index
MaxVols = data['MaxVol']
MinVols = data['MinVol']
Impacts = data['ImpactPer']
Miles = data['Distance']

x = LpVariable.dicts('Lane', Lanes, None, None, LpInteger)

for l in Lanes:
 x[l].bounds(MinVols[l], MaxVols[l])
 
''' SET THE OBJECTIVE FUNCTION '''
prob += sum([x[l] * Impacts[l] for l in Lanes]), 'Sum_of_Impact'


''' SET THE CONSTRAINTS '''
prob += lpSum([Miles[l] * x[l] for l in Lanes]) <= OPTSET_MILE_LIMIT_UPPER
prob += lpSum([Miles[l] * x[l] for l in Lanes]) >= OPTSET_MILE_LIMIT_LOWER

Now, all we have to do is let PuLP work its magic and then merge the results with the original data set.

'''WRAP UP AND SOLVE '''
LpSolverDefault.msg = 1
prob.writeLP('LaneOpt.lp')
prob.solve()


''' HANDLE RESULTS '''
TotalImpact = prob.objective.value()
Status = pulp.LpStatus[prob.status]
print('Status:',Status)
print('Total Impact:', TotalImpact)

flow = {l:x[l].varValue for l in Lanes}

output = []
for lane in Lanes:
 var_output = {
 'Lane':lane,
 'Production':flow[lane]
 }
 output.append(var_output)
 
dfOptResults = pd.DataFrame.from_records(output)
dfOptResults.set_index('Lane', inplace=True)

''' MERGE RESULTS WITH ORIGINAL DATA '''
data = pd.merge(data, dfOptResults, how='left', left_index=True, right_index=True)

''' BONUS: CALC IMPACT FOR EACH LANE '''
data['LaneImpact'] = data['ImpactPer'] * data['Production']

What’s Going On?

All that code is nifty and accomplishes the optimization, but what is it doing? Well, the main thing is setting up the ‘prob‘ variable which is what PuLP uses to actually do the optimization. It is essentially a specially formatted text file. You will notice a new file in the working directory suffixed with ‘.lp’ after running your script.

LaneSelectionOptimization:
MAXIMIZE
349.5*Lane_0 + 109.42*Lane_1 + -889.49*Lane_10 + -265.28*Lane_11 
+ -81.15*Lane_12 + -545.46*Lane_13 + -50.0*Lane_14 + -878.54*Lane_15 
+ -837.95*Lane_16 + -379.91*Lane_17 + -508.73*Lane_18 
+ -946.08*Lane_19 + 0.45*Lane_2 + -535.74*Lane_20 + 512.79*Lane_21 
+ -952.41*Lane_22 + -1045.29*Lane_23 + 107.72*Lane_24 + -47.5*Lane_25 
+ -915.59*Lane_3 + -1000.56*Lane_4 + -550.68*Lane_5 + -960.45*Lane_6 
+ -787.0*Lane_7 + -927.75*Lane_8 + 82.08*Lane_9 + 0.0

SUBJECT TO
_C1: 570 Lane_0 + 117 Lane_1 + 1688 Lane_10 + 432 Lane_11 + 451 Lane_12
+ 505 Lane_13 + 444 Lane_14 + 1247 Lane_15 + 710 Lane_16 + 323 Lane_17
+ 1035 Lane_18 + 1139 Lane_19 + 120 Lane_2 + 1136 Lane_20 + 1251 Lane_21
+ 1107 Lane_22 + 1180 Lane_23 + 268 Lane_24 + 863 Lane_25 + 1116 Lane_3
+ 1058 Lane_4 + 942 Lane_5 + 1103 Lane_6 + 921 Lane_7 + 1091 Lane_8
+ 443 Lane_9 <= 22000

_C2: 570 Lane_0 + 117 Lane_1 + 1688 Lane_10 + 432 Lane_11 + 451 Lane_12
+ 505 Lane_13 + 444 Lane_14 + 1247 Lane_15 + 710 Lane_16 + 323 Lane_17
+ 1035 Lane_18 + 1139 Lane_19 + 120 Lane_2 + 1136 Lane_20 + 1251 Lane_21
+ 1107 Lane_22 + 1180 Lane_23 + 268 Lane_24 + 863 Lane_25 + 1116 Lane_3
+ 1058 Lane_4 + 942 Lane_5 + 1103 Lane_6 + 921 Lane_7 + 1091 Lane_8
+ 443 Lane_9 >= 20000

VARIABLES
2 <= Lane_0 <= 6 Integer
0 <= Lane_1 <= 3 Integer
Lane_10 = 0 Integer
2 <= Lane_11 <= 4 Integer
8 <= Lane_12 <= 10 Integer
Lane_13 = 0 Integer
Lane_14 = 0 Integer
Lane_15 = 0 Integer
0 <= Lane_16 <= 2 Integer
0 <= Lane_17 <= 1 Integer
1 <= Lane_18 <= 2 Integer
Lane_19 = 0 Integer
15 <= Lane_2 <= 25 Integer
0 <= Lane_20 <= 1 Integer
Lane_21 = 6 Integer
Lane_22 = 0 Integer
0 <= Lane_23 <= 4 Integer
Lane_24 = 4 Integer
0 <= Lane_25 <= 1 Integer
Lane_3 = 0 Integer
Lane_4 = 0 Integer
Lane_5 = 0 Integer
Lane_6 = 0 Integer
0 <= Lane_7 <= 2 Integer
Lane_8 = 0 Integer
3 <= Lane_9 <= 8 Integer

Conclusion

I am still amazed and enthused with the versatility and usability of Python. The PuLP library for Python gets me that much further away from doing analysis in excel and further into using Python for analysis projects. This was a head-scratcher for me in the beginning and there wasn’t much documentation that I could find on this, but hopefully, this helps people in a similar situation.

What do you think? Is this something you could use?

Resources:

You can find the sample dataset and full code over on my GitLab repository.

PuLP’s website is here: https://pythonhosted.org/PuLP/

7 Comments

  1. sidkhullar 3 years ago

    Thank you for sharing. I’m trying something using similar constructs, but it isn’t working for me. In my case, I’m trying to balance the components of a meal plan to adhere to the basic macronutrient ratios.

    • Reece Althoff 3 years ago

      Glad you found it! The way I did it here took me a couple hours of tinkering to actually get it to run without errors and correctly. I hope you are able to get your model running. Its a great feeling when it first runs correctly after hours of trying to beat the square peg into a round hole.

      • sidkhullar 3 years ago

        I’ve been trying to get it to work for a couple of days now and it just isn’t working. I’m still at it because if it works, it’ll save me a ton of time in writing separate custom solvers for the many similar situations that are bound to crop up. *sigh* Let’s see. 🙁

        If you’re aware of somewhat complex examples, please do share. 🙂

        • Reece Althoff 3 years ago

          Yea, there isn’t a lot out there for it. I only had the examples from the original authors of it with the ‘beer distribution’ and ‘cat food’ examples. I used the beer distribution one as my starting point. I wonder if you could use that ‘cat food’ example as a starting point and do some heavy tweaking.

        • Reece Althoff 3 years ago

          Its been a bit… Any luck with your project?

          • sidkhullar 2 years ago

            I gave up. :/

          • Reece Althoff 2 years ago

            Sorry to see you gave up on it. It definitely isn’t the easiest thing to implement.

            Do you have some fake data that is similar to your actual data (so we don’t have to worry about NDA’s) that you could send me? I’d be interested to see if I can get it working.

Leave a reply

Your email address will not be published. Required fields are marked *

*