{
"metadata": {
"name": "",
"signature": "sha256:a5129906f23653083e0a5cbec5eef1aa52a02a6de88ef2203da88780f43ec8db"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 6,
"metadata": {},
"source": [
"The latest version of this IPython notebook is available at [http://github.com/jckantor/ESTM60203](http://github.com/jckantor/ESTM60203) for noncommercial use under terms of the [Creative Commons Attribution Noncommericial ShareAlike License (CC BY-NC-SA 4.0)](http://creativecommons.org/licenses/by-nc-sa/4.0/)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"J.C. Kantor (Kantor.1@nd.edu)"
]
},
{
"cell_type": "heading",
"level": 1,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Transportation Networks"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This [IPython notebook](http://ipython.org/notebook.html) demonstrates the solution of transportation network problems using GLPK/MathProg. Problem data is adapted from Chapter 5 of Johannes Bisschop, \"AIMMS Optimization Modeling\", Paragon Decision Sciences, 1999. "
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Initializations"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from IPython.core.display import HTML\n",
"HTML(open(\"styles/custom.css\", \"r\").read())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 3,
"text": [
""
]
}
],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 2,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Background"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The prototypical transportation problem deals with the distribution of a commodity from a set of sources to a set of destinations. The object is to minimize total transportation costs while satisfying constraints on the supplies available at each of the sources, and satisfying demand requirements at each of the destinations.\n",
"\n",
"Here we illustrate the transportation problem using an example from Chapter 5 of Johannes Bisschop, \"AIMMS Optimization Modeling\", Paragon Decision Sciences, 1999. In this example there are two factories and six customer sites located in 8 European cities as shown in the following map. The customer sites are labeled in red, the factories are labeled in blue."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Transportation costs between sources and destinations are given in units of €/ton of goods shipped, and list in the following table along with source capacity and demand requirements.\n",
"\n",
"#### Table of Transportation Costs, Customer Demand, and Available Supplies\n",
"\n",
"| Customer\\Source | Arnhem [€/ton] | Gouda [€/ton] | Demand [tons]|\n",
"| :--: | :----: | :---: | :----: |\n",
"| London | n/a | 2.5 | 125 |\n",
"| Berlin | 2.5 | n/a | 175 |\n",
"| Maastricht | 1.6 | 2.0 | 225 |\n",
"| Amsterdam | 1.4 | 1.0 | 250 |\n",
"| Utrecht | 0.8 | 1.0 | 225 |\n",
"| The Hague | 1.4 | 0.8 | 200 |\n",
"| **Supply [tons]** | 550 tons | 700 tons | |\n",
"\n",
"The situation can be modeled by links connecting a set nodes representing sources to a set of nodes representing customers.\n",
"\n",
"\n",
"\n",
"For each link we can have a parameter $T[c,s]$ denoting the cost of shipping a ton of goods over the link. What we need to determine is the amount of goods to be shipped over each link, which we will represent as a non-negative decision variable $x[c,s]$.\n",
"\n",
"The problem objective is to minimize the total shipping cost to all customers from all sources. \n",
"\n",
"$$\\mbox{minimize:}\\quad \\mbox{Cost} = \\sum_{c \\in Customers}\\sum_{s \\in Sources} T[c,s] x[c,s]$$\n",
"\n",
"Shipments from all sources can not exceed the manufacturing capacity of the source.\n",
"\n",
"$$\\sum_{c \\in Customers} x[c,s] \\leq \\mbox{Supply}[s] \\qquad \\forall s \\in Sources$$\n",
"\n",
"Shipments to each customer must satisfy their demand.\n",
"\n",
"$$\\sum_{s\\in Sources} x[c,s] = \\mbox{Demand}[c] \\qquad \\forall c \\in Customers$$"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"MathProg Model"
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Model File"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%writefile TransportNet.mod\n",
"\n",
"# Step 1: Define the sets\n",
"set SOURCES;\n",
"set CUSTOMERS;\n",
"\n",
"# Step 2: Define parameters. Note the use of checks and defaults values.\n",
"param Demand {CUSTOMERS} >= 0;\n",
"param Supply {SOURCES} >= 0;\n",
"param T {CUSTOMERS, SOURCES} default 1000;\n",
"\n",
"# Step 3: Define the decision variables\n",
"var x {CUSTOMERS, SOURCES} >= 0;\n",
"\n",
"# Step 4: Write the objective\n",
"minimize Cost: sum{c in CUSTOMERS, s in SOURCES} T[c,s]*x[c,s];\n",
"\n",
"# Step 5: Write the constraints\n",
"subject to SRC {s in SOURCES}: sum {c in CUSTOMERS} x[c,s] <= Supply[s];\n",
"subject to DST {c in CUSTOMERS}: sum {s in SOURCES} x[c,s] = Demand[c];\n",
"\n",
"# Step 6: Call for a solution\n",
"solve;\n",
"\n",
"# Step 7: Write results to .csv files\n",
"printf \"\\nTotal Cost = %7.2f\\n\\n\", Cost;\n",
"\n",
"table shiptable {c in CUSTOMERS, s in SOURCES} OUT \"CSV\" \"ship.csv\" :\n",
" c~Customer, s~Source, x[c,s]~Quantity, x[c,s].dual~Marginal, T[c,s]*x[c,s]~Cost;\n",
"\n",
"table sources {s in SOURCES} OUT \"CSV\" \"source.csv\" :\n",
" s~Source, Supply[s]~Supply, SRC[s]~Activity, SRC[s].dual~Marginal;\n",
" \n",
"table customers {c in CUSTOMERS} OUT \"CSV\" \"customer.csv\" :\n",
" c~Customer, Demand[c]~Demand, DST[c]~Activity, DST[c].dual~Marginal;\n",
"\n",
"end;\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Writing TransportNet.mod\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Data File"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%script glpsol -m TransportNet.mod -d /dev/stdin -o output.txt\n",
"\n",
"/* \n",
"Problem Data from Chapter 5 of Johannes Bisschop, \"AIMMS Optimization Modeling\",\n",
"Paragon Decision Sciences, 1999. \n",
"*/\n",
"\n",
"param: CUSTOMERS: Demand :=\n",
" Lon 125 # London\n",
" Ber 175 # Berlin\n",
" Maa 225 # Maastricht\n",
" Ams 250 # Amsterdam\n",
" Utr 225 # Utrecht\n",
" Hag 200 ; # The Hague\n",
"\n",
"param: SOURCES: Supply :=\n",
" Arn 550 # Arnhem\n",
" Gou 700 ; # Gouda\n",
"\n",
"param T : Arn Gou :=\n",
" Lon . 2.5\n",
" Ber 2.5 .\n",
" Maa 1.6 2.0\n",
" Ams 1.4 1.0\n",
" Utr 0.8 1.0\n",
" Hag 1.4 0.8 ;\n",
"\n",
"end;"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"GLPSOL: GLPK LP/MIP Solver, v4.52\n",
"Parameter(s) specified in the command line:\n",
" -m TransportNet.mod -d /dev/stdin -o output.txt\n",
"Reading model section from TransportNet.mod...\n",
"36 lines were read\n",
"Reading data section from /dev/stdin...\n",
"27 lines were read\n",
"Generating Cost...\n",
"Generating SRC...\n",
"Generating DST...\n",
"Model has been successfully generated\n",
"GLPK Simplex Optimizer, v4.52\n",
"9 rows, 12 columns, 36 non-zeros\n",
"Preprocessing...\n",
"8 rows, 12 columns, 24 non-zeros\n",
"Scaling...\n",
" A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00\n",
"Problem data seem to be well scaled\n",
"Constructing initial basis...\n",
"Size of triangular part is 8\n",
" 0: obj = 1.763975000e+05 infeas = 5.000e+02 (0)\n",
"* 3: obj = 1.264425000e+05 infeas = 0.000e+00 (0)\n",
"* 6: obj = 1.715000000e+03 infeas = 0.000e+00 (0)\n",
"OPTIMAL LP SOLUTION FOUND\n",
"Time used: 0.0 secs\n",
"Memory used: 0.1 Mb (136409 bytes)\n",
"\n",
"Total Cost = 1715.00\n",
"\n",
"Writing shiptable...\n",
"Writing sources...\n",
"Writing customers...\n",
"Model has been successfully processed\n",
"Writing basic solution to `output.txt'...\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "heading",
"level": 2,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Solution"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import pandas as pd\n",
"df = pd.read_csv('ship.csv')\n",
"df[df['Quantity'] > 0]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"
\n",
"
\n",
" \n",
"
\n",
"
\n",
"
Customer
\n",
"
Source
\n",
"
Quantity
\n",
"
Marginal
\n",
"
Cost
\n",
"
\n",
" \n",
" \n",
"
\n",
"
1
\n",
"
Lon
\n",
"
Gou
\n",
"
125
\n",
"
0
\n",
"
312.5
\n",
"
\n",
"
\n",
"
2
\n",
"
Ber
\n",
"
Arn
\n",
"
175
\n",
"
0
\n",
"
437.5
\n",
"
\n",
"
\n",
"
4
\n",
"
Maa
\n",
"
Arn
\n",
"
225
\n",
"
0
\n",
"
360.0
\n",
"
\n",
"
\n",
"
7
\n",
"
Ams
\n",
"
Gou
\n",
"
250
\n",
"
0
\n",
"
250.0
\n",
"
\n",
"
\n",
"
8
\n",
"
Utr
\n",
"
Arn
\n",
"
150
\n",
"
0
\n",
"
120.0
\n",
"
\n",
"
\n",
"
9
\n",
"
Utr
\n",
"
Gou
\n",
"
75
\n",
"
0
\n",
"
75.0
\n",
"
\n",
"
\n",
"
11
\n",
"
Hag
\n",
"
Gou
\n",
"
200
\n",
"
0
\n",
"
160.0
\n",
"
\n",
" \n",
"
\n",
"
"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 6,
"text": [
" Customer Source Quantity Marginal Cost\n",
"1 Lon Gou 125 0 312.5\n",
"2 Ber Arn 175 0 437.5\n",
"4 Maa Arn 225 0 360.0\n",
"7 Ams Gou 250 0 250.0\n",
"8 Utr Arn 150 0 120.0\n",
"9 Utr Gou 75 0 75.0\n",
"11 Hag Gou 200 0 160.0"
]
}
],
"prompt_number": 6
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The solution has the interesting property that, with the exception of Utrecht, customers are served by just one source.\n",
"\n",
"\n"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Sensitivity Analysis"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Analysis by Source"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import pandas as pd\n",
"pd.read_csv('source.csv')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"
\n",
"
\n",
" \n",
"
\n",
"
\n",
"
Source
\n",
"
Supply
\n",
"
Activity
\n",
"
Marginal
\n",
"
\n",
" \n",
" \n",
"
\n",
"
0
\n",
"
Arn
\n",
"
550
\n",
"
550
\n",
"
-0.2
\n",
"
\n",
"
\n",
"
1
\n",
"
Gou
\n",
"
700
\n",
"
650
\n",
"
0.0
\n",
"
\n",
" \n",
"
\n",
"
"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 13,
"text": [
" Source Supply Activity Marginal\n",
"0 Arn 550 550 -0.2\n",
"1 Gou 700 650 0.0"
]
}
],
"prompt_number": 13
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The 'marginal' values are telling us how much the total costs will be increased for each one ton increase in the available supply from each source. The optimization calculation says that only 650 tons of the 700 available from Gouda should used for a minimum cost solution, which rules out any further cost reductions by increasing the available supply. In fact, we could decrease the supply Gouda without any harm. The marginal value of Gouda is 0.\n",
"\n",
"The source at Arnhem is a different matter. First, all 550 available tons are being used. Second, from the marginal value we see that the total transportations costs would be reduced by 0.2 Euros for each additional ton of supply. \n",
"\n",
"The management conclusion we can draw is that there is excess supply available at Gouda which should, if feasible, me moved to Arnhem.\n",
"\n",
"Now that's a valuable piece of information!"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Analysis by Customer"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"pd.read_csv('customer.csv')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"
\n",
"
\n",
" \n",
"
\n",
"
\n",
"
Customer
\n",
"
Demand
\n",
"
Activity
\n",
"
Marginal
\n",
"
\n",
" \n",
" \n",
"
\n",
"
0
\n",
"
Lon
\n",
"
125
\n",
"
125
\n",
"
2.5
\n",
"
\n",
"
\n",
"
1
\n",
"
Ber
\n",
"
175
\n",
"
175
\n",
"
2.7
\n",
"
\n",
"
\n",
"
2
\n",
"
Maa
\n",
"
225
\n",
"
225
\n",
"
1.8
\n",
"
\n",
"
\n",
"
3
\n",
"
Ams
\n",
"
250
\n",
"
250
\n",
"
1.0
\n",
"
\n",
"
\n",
"
4
\n",
"
Utr
\n",
"
225
\n",
"
225
\n",
"
1.0
\n",
"
\n",
"
\n",
"
5
\n",
"
Hag
\n",
"
200
\n",
"
200
\n",
"
0.8
\n",
"
\n",
" \n",
"
\n",
"
"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 15,
"text": [
" Customer Demand Activity Marginal\n",
"0 Lon 125 125 2.5\n",
"1 Ber 175 175 2.7\n",
"2 Maa 225 225 1.8\n",
"3 Ams 250 250 1.0\n",
"4 Utr 225 225 1.0\n",
"5 Hag 200 200 0.8"
]
}
],
"prompt_number": 15
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Looking at the demand constraints, we see that all of the required demands have been met by the optimal solution.\n",
"\n",
"The marginal values of these constraints indicate how much the total transportation costs will increase if there is an additional ton of demand at any of the locations. In particular, note that increasing the demand at Berlin will increase costs by 2.7 Euros per ton. This is actually **greater** than the list price for shipping to Berlin which is 2.5 Euros per ton. Why is this?\n",
"\n",
"To see what's going on, let's resolve the problem with a one ton increase in the demand at Berlin."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%script glpsol -m TransportNet.mod -d /dev/stdin -o output.txt\n",
"\n",
"/* \n",
"Problem Data from Chapter 5 of Johannes Bisschop, \"AIMMS Optimization Modeling\",\n",
"Paragon Decision Sciences, 1999. \n",
"*/\n",
"\n",
"param: CUSTOMERS: Demand :=\n",
" Lon 125 # London\n",
" Ber 176 # Berlin <=== INCREASE BY ONE TON\n",
" Maa 225 # Maastricht\n",
" Ams 250 # Amsterdam\n",
" Utr 225 # Utrecht\n",
" Hag 200 ; # The Hague\n",
"\n",
"param: SOURCES: Supply :=\n",
" Arn 550 # Arnhem\n",
" Gou 700 ; # Gouda\n",
"\n",
"param T : Arn Gou :=\n",
" Lon . 2.5\n",
" Ber 2.5 .\n",
" Maa 1.6 2.0\n",
" Ams 1.4 1.0\n",
" Utr 0.8 1.0\n",
" Hag 1.4 0.8 ;\n",
"\n",
"end;"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"GLPSOL: GLPK LP/MIP Solver, v4.52\n",
"Parameter(s) specified in the command line:\n",
" -m TransportNet.mod -d /dev/stdin -o output.txt\n",
"Reading model section from TransportNet.mod...\n",
"36 lines were read\n",
"Reading data section from /dev/stdin...\n",
"27 lines were read\n",
"Generating Cost...\n",
"Generating SRC...\n",
"Generating DST...\n",
"Model has been successfully generated\n",
"GLPK Simplex Optimizer, v4.52\n",
"9 rows, 12 columns, 36 non-zeros\n",
"Preprocessing...\n",
"8 rows, 12 columns, 24 non-zeros\n",
"Scaling...\n",
" A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00\n",
"Problem data seem to be well scaled\n",
"Constructing initial basis...\n",
"Size of triangular part is 8\n",
" 0: obj = 1.773975000e+05 infeas = 5.010e+02 (0)\n",
"* 3: obj = 1.264450000e+05 infeas = 0.000e+00 (0)\n",
"* 6: obj = 1.717700000e+03 infeas = 0.000e+00 (0)\n",
"OPTIMAL LP SOLUTION FOUND\n",
"Time used: 0.0 secs\n",
"Memory used: 0.1 Mb (136409 bytes)\n",
"\n",
"Total Cost = 1717.70\n",
"\n",
"Writing shiptable...\n",
"Writing sources...\n",
"Writing customers...\n",
"Model has been successfully processed\n",
"Writing basic solution to `output.txt'...\n"
]
}
],
"prompt_number": 16
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see the total cost has increased from 1715.0 to 1717.7 Euros, an increase of 2.7 Euros just as predicted by the marginal value assocated with the demand constraint for Berlin.\n",
"\n",
"Now let's look at the solution."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"df = pd.read_csv('ship.csv')\n",
"df[df['Quantity'] > 0]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"
\n",
"
\n",
" \n",
"
\n",
"
\n",
"
Customer
\n",
"
Source
\n",
"
Quantity
\n",
"
Marginal
\n",
"
Cost
\n",
"
\n",
" \n",
" \n",
"
\n",
"
1
\n",
"
Lon
\n",
"
Gou
\n",
"
125
\n",
"
0
\n",
"
312.5
\n",
"
\n",
"
\n",
"
2
\n",
"
Ber
\n",
"
Arn
\n",
"
176
\n",
"
0
\n",
"
440.0
\n",
"
\n",
"
\n",
"
4
\n",
"
Maa
\n",
"
Arn
\n",
"
225
\n",
"
0
\n",
"
360.0
\n",
"
\n",
"
\n",
"
7
\n",
"
Ams
\n",
"
Gou
\n",
"
250
\n",
"
0
\n",
"
250.0
\n",
"
\n",
"
\n",
"
8
\n",
"
Utr
\n",
"
Arn
\n",
"
149
\n",
"
0
\n",
"
119.2
\n",
"
\n",
"
\n",
"
9
\n",
"
Utr
\n",
"
Gou
\n",
"
76
\n",
"
0
\n",
"
76.0
\n",
"
\n",
"
\n",
"
11
\n",
"
Hag
\n",
"
Gou
\n",
"
200
\n",
"
0
\n",
"
160.0
\n",
"
\n",
" \n",
"
\n",
"
"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 17,
"text": [
" Customer Source Quantity Marginal Cost\n",
"1 Lon Gou 125 0 312.5\n",
"2 Ber Arn 176 0 440.0\n",
"4 Maa Arn 225 0 360.0\n",
"7 Ams Gou 250 0 250.0\n",
"8 Utr Arn 149 0 119.2\n",
"9 Utr Gou 76 0 76.0\n",
"11 Hag Gou 200 0 160.0"
]
}
],
"prompt_number": 17
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here we see that increasing the demand in Berlin resulted in a number of other changes. This figure shows the changes shipments.\n",
"\n",
"\n",
"\n",
"* Shipments to Berlin increased from 175 to 175 tons, increasing costs for that link from 437.5 to 440.0, or a net increase of 2.5 Euros.\n",
"* Since Arnhem is operating at full capacity, increasing the shipments from Arnhem to Berlin resulted in decreasing the shipments from Arhhem to Utrecht from 150 to 149 reducing those shipping costs from 120.0 to 119.2, a net decrease of 0.8 Euros.\n",
"* To meet demand at Utrecht, shipments from Gouda to Utrecht had to increase from 75 to 76, increasing shipping costs by a net amount of 1.0 Euros.\n",
"* The net effect on shipping costs is 2.5 - 0.8 + 1.0 = 2.7 Euros.\n",
"\n",
"The important conclusion to draw is that when operating under optimal conditions, a change in demand or supply can have a ripple effect on the optimal solution that can only be measured through a proper sensitivity analysis."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### Exercises\n",
"\n",
"1. Move 50 tons of supply capacity from Gouda to Arnhem, and repeat the sensitivity analysis. How has the situation improved? In practice, would you recommend this change, or would you propose something different?\n",
"2. What other business improvements would you recommend?"
]
}
],
"metadata": {}
}
]
}