# 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
)  # 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 products

• DEST: final cities that demand and receive products

• PROD: set of products to deliver

• Parameters:

• supply {ORIG,PROD}: amounts of product available at origins

• demand {DEST,PROD}: amounts required at destinations

• limit {ORIG,DEST}: maximum capacity on routes between two nodes

• vcost {ORIG,DEST,PROD}: variable shipment cost on routes that depends on the units of product sent

• fcost {ORIG,DEST}: fixed cost for using a route

• Variables:

• Trans {ORIG,DEST,PROD}: units to be shipped

• Use {ORIG,DEST}: binary variable equals to 1 if route is used, else 0

• Objective: minimize total cost

$$\sum \limits_{\substack{i \in ORIG \ j \in DEST \ p \in PROD}} vcost[i,j,p] \cdot Trans[i,j,p] • \sum \limits_{\substack{i \in ORIG \ j \in DEST}} fcost[i,j] \cdot Use[i,j]$$

• 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
;