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])
60 J,M = multidict({1:3000, 2:3000, 3:3000})
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])
87 J,M = multidict({1:35, 2:50, 3:40})
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])
114 J,M = multidict({1:500, 2:500, 3:500})
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__":
134 I,J,K,c,d,M = make_inst3();
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))