4 Model for solving the multi-commodity transportation problem:
5 minimize the total transportation cost for satisfying demand at
6 customers, from capacitated facilities.
8 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
11 from pyscipopt
import Model, quicksum, multidict
14 """mctransp -- model for solving the Multi-commodity Transportation Problem
17 - J: set of facilities
18 - K: set of commodities
19 - c[i,j,k]: unit transportation cost on arc (i,j) for commodity k
20 - d[i][k]: demand for commodity k at node i
22 Returns a model, ready to be solved.
25 model = Model(
"multi-commodity transportation")
31 x[i,j,k] = model.addVar(vtype=
"C", name=
"x(%s,%s,%s)" % (i,j,k))
36 model.addCons(sum(x[i,j,k]
for j
in J
if (i,j,k)
in x) == d[i,k],
"Demand(%s,%s)" % (i,k))
40 model.addCons(sum(x[i,j,k]
for (i,j2,k)
in x
if j2 == j) <= M[j],
"Capacity(%s)" % j)
43 model.setObjective(
quicksum(c[i,j,k]*x[i,j,k]
for (i,j,k)
in x),
"minimize")
51 """creates example data set 1"""
52 d = {(1,1):80, (1,2):85, (1,3):300, (1,4):6,
53 (2,1):270, (2,2):160, (2,3):400, (2,4):7,
54 (3,1):250, (3,2):130, (3,3):350, (3,4):4,
55 (4,1):160, (4,2):60, (4,3):200, (4,4):3,
56 (5,1):180, (5,2):40, (5,3):150, (5,4):5
58 I =
set([i
for (i,k)
in d])
59 K =
set([k
for (i,k)
in d])
62 produce = {1:[2,4], 2:[1,2,3], 3:[2,3,4]}
63 weight = {1:5, 2:2, 3:3, 4:4}
64 cost = {(1,1):4, (1,2):6, (1,3):9,
65 (2,1):5, (2,2):4, (2,3):7,
66 (3,1):6, (3,2):3, (3,3):4,
67 (4,1):8, (4,2):5, (4,3):3,
68 (5,1):10, (5,2):8, (5,3):4
74 c[i,j,k] = cost[i,j] * weight[k]
79 """creates example data set 2"""
85 I =
set([i
for (i,k)
in d])
86 K =
set([k
for (i,k)
in d])
88 produce = {1:[1], 2:[1], 3:[1]}
90 cost = {(1,1):8, (1,2):9, (1,3):14,
91 (2,1):6, (2,2):12, (2,3):9 ,
92 (3,1):10, (3,2):13, (3,3):16,
93 (4,1):9, (4,2):7, (4,3):5 ,
99 c[i,j,k] = cost[i,j] * weight[k]
105 """creates example data set 3"""
106 d = {(1,1):40, (1,2):30, (1,3):10,
107 (2,1):70, (2,2):100, (2,3):100,
108 (3,1):0, (3,2):0, (3,3):250,
109 (4,1):60, (4,2):100, (4,3):0,
110 (5,1):180, (5,2):0, (5,3):0
112 I =
set([i
for (i,k)
in d])
113 K =
set([k
for (i,k)
in d])
116 produce = {1:[2,4], 2:[1,2,3], 3:[2,3,4]}
117 weight = {1:5, 2:2, 3:3, 4:4}
118 cost = {(1,1):4, (1,2):6, (1,3):9,
119 (2,1):5, (2,2):4, (2,3):7,
120 (3,1):6, (3,2):3, (3,3):4,
121 (4,1):8, (4,2):5, (4,3):3,
122 (5,1):10, (5,2):8, (5,3):4
128 c[i,j,k] = cost[i,j] * weight[k]
133 if __name__ ==
"__main__":
136 model.writeProblem(
"transp.lp")
139 print(
"Optimal value:",model.getObjVal())
145 if model.getVal(x[i,j,k]) > EPS:
146 print(
"sending %10s units of %3s from plant %3s to customer %3s" % (model.getVal(x[i,j,k]),k,j,i))