Multicommodity transportation problem#
Description: Multicommodity transportation model with binary variables
Tags: ampl-only, ampl-book, mixed-integer-linear
Notebook author: Marcos Dominguez Velad <marcos@ampl.com>
Model author: N/A
# Install dependencies
%pip install -q amplpy
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["coin"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
Model#
There are a set of origin nodes, a set of destination nodes, and products to be demanded/supplied from origins to destinations.
Sets:
ORIG
: origin cities that supply productsDEST
: final cities that demand and receive productsPROD
: set of products to deliver
Parameters:
supply {ORIG,PROD}
: amounts of product available at originsdemand {DEST,PROD}
: amounts required at destinationslimit {ORIG,DEST}
: maximum capacity on routes between two nodesvcost {ORIG,DEST,PROD}
: variable shipment cost on routes that depends on the units of product sentfcost {ORIG,DEST}
: fixed cost for using a route
Variables:
Trans {ORIG,DEST,PROD}
: units to be shippedUse {ORIG,DEST}
: binary variable equals to 1 if route is used, else 0
Objective: minimize total cost
Constraints:
Supply {ORIG,PROD}
: node ships units equal to supply capacity
\[\sum \limits_{j \in DEST} Trans[i,j,p] = supply[i,p]\]Demand {DEST,PROD}
: node gets units equal to demand
\[\sum \limits_{i \in ORIG} Trans[i,j,p] = demand[j,p]\]Multi {ORIG,DEST}
: links capacity is bounded
\[\sum \limits_{p \in PROD} Trans[i,j,p] \leq limit[i,j] \cdot Use[i,j]\]
%%writefile multmip1.mod
set ORIG; # origins
set DEST; # destinations
set PROD; # products
param supply {ORIG,PROD} >= 0; # amounts available at origins
param demand {DEST,PROD} >= 0; # amounts required at destinations
check {p in PROD}:
sum {i in ORIG} supply[i,p] = sum {j in DEST} demand[j,p];
param limit {ORIG,DEST} >= 0; # maximum shipments on routes
param vcost {ORIG,DEST,PROD} >= 0; # variable shipment cost on routes
var Trans {ORIG,DEST,PROD} >= 0; # units to be shipped
param fcost {ORIG,DEST} >= 0; # fixed cost for using a route
var Use {ORIG,DEST} binary; # = 1 only for routes used
minimize Total_Cost:
sum {i in ORIG, j in DEST, p in PROD} vcost[i,j,p] * Trans[i,j,p]
+ sum {i in ORIG, j in DEST} fcost[i,j] * Use[i,j];
subject to Supply {i in ORIG, p in PROD}:
sum {j in DEST} Trans[i,j,p] = supply[i,p];
subject to Demand {j in DEST, p in PROD}:
sum {i in ORIG} Trans[i,j,p] = demand[j,p];
subject to Multi {i in ORIG, j in DEST}:
sum {p in PROD} Trans[i,j,p] <= limit[i,j] * Use[i,j];
Writing multmip1.mod
%%writefile multmip1.dat
data;
set ORIG := GARY CLEV PITT ;
set DEST := FRA DET LAN WIN STL FRE LAF ;
set PROD := bands coils plate ;
param supply (tr): GARY CLEV PITT :=
bands 400 700 800
coils 800 1600 1800
plate 200 300 300 ;
param demand (tr):
FRA DET LAN WIN STL FRE LAF :=
bands 300 300 100 75 650 225 250
coils 500 750 400 250 950 850 500
plate 100 100 0 50 200 100 250 ;
param limit default 625 ;
param vcost :=
[*,*,bands]: FRA DET LAN WIN STL FRE LAF :=
GARY 30 10 8 10 11 71 6
CLEV 22 7 10 7 21 82 13
PITT 19 11 12 10 25 83 15
[*,*,coils]: FRA DET LAN WIN STL FRE LAF :=
GARY 39 14 11 14 16 82 8
CLEV 27 9 12 9 26 95 17
PITT 24 14 17 13 28 99 20
[*,*,plate]: FRA DET LAN WIN STL FRE LAF :=
GARY 41 15 12 16 17 86 8
CLEV 29 9 13 9 28 99 18
PITT 26 14 17 13 31 104 20 ;
param fcost: FRA DET LAN WIN STL FRE LAF :=
GARY 3000 1200 1200 1200 2500 3500 2500
CLEV 2000 1000 1500 1200 2500 3000 2200
PITT 2000 1200 1500 1500 2500 3500 2200 ;
Writing multmip1.dat
%%ampl_eval
model multmip1.mod;
data multmip1.dat;
option solver cbc;
solve;
option display_eps .000001;
option display_transpose -10;
display Use;
display Trans;
CBC 2.10.5: CBC 2.10.5 optimal, objective 229850
6 nodes, 1785 iterations, 0.457534 seconds
Use [*,*]
: DET FRA FRE LAF LAN STL WIN :=
CLEV 1 1 0 1 1 1 1
GARY 0 0 1 0 1 1 0
PITT 1 1 1 1 0 1 0
;
Trans [CLEV,*,*]
: bands coils plate :=
DET 0 525 100
FRA 275 0 0
FRE 0 0 0
LAF 0 375 50
LAN 0 350 0
STL 350 100 100
WIN 75 250 50
[GARY,*,*]
: bands coils plate :=
DET 0 0 0
FRA 0 0 0
FRE 0 525 100
LAF 0 0 0
LAN 100 50 0
STL 300 225 100
WIN 0 0 0
[PITT,*,*]
: bands coils plate :=
DET 300 225 0
FRA 25 500 100
FRE 225 325 0
LAF 250 125 200
LAN 0 0 0
STL 0 625 0
WIN 0 0 0
;