Modeling a transshipment problem in Pyomo
642 views
Skip to first unread message
Michaël Lambé
Nov 2, 2019, 11:22:00 AM11/2/19
to Pyomo Forum
I am working on a transshipment problem and I want to use Pyomo to solve the problem.
So far I understand that I must make the transshipment rule such that the Crossdock facilities will not HOLD any goods, just receive and ship them. This constraint addresses this by saying everything that flows IN to a crossdock must equal what flows OUT.
The constraint can be written as
Where m is the number of supply points (Factory), n is the number of demand points (DC's), and
xi,j is the amount of the product shipped from supply point i to demand point j.
I try to implement this problem in Pyomo but unfortunately, I am ending with a cost of "zero" - Thanks in advance for checking if my constraint formulation are correct.
from pyomo.environ import *
from pprint import pprint
model = ConcreteModel(name="Transshipment problem")
## define sets ##
# sets
# i = factory
# j = DCs
model.i = Set(
initialize=[
"Factory 1",
"Factory 2",
"Factory 3",
"Factory 4",
"Factory 5",
"Crossdock 1",
"Crossdock 2",
],
doc="Production Facility",
)
model.j = Set(
initialize=["DC 1", "DC 2", "DC 3", "DC 4", "DC 5", "Crossdock 1", "Crossdock 2"],
doc="Regional DC's",
)
model.k = Set(initialize=["Crossdock 1", "Crossdock 2"], doc="Crossdocs")
## define parameters ##
# Parameters
# a(i) = capacity of production facility (i) in cases
# b(j) = demand at each DC (j) in cases
model.a = Param(
model.i,
initialize={
"Factory 1": 200,
"Factory 2": 300,
"Factory 3": 100,
"Factory 4": 150,
"Factory 5": 220,
"Crossdock 1": 0,
"Crossdock 2": 0,
},
)
model.b = Param(
model.j,
initialize={
"DC 1": 150,
"DC 2": 100,
"DC 3": 110,
"DC 4": 200,
"DC 5": 180,
"Crossdock 1": 0,
"Crossdock 2": 0,
},
)
# Table fa_cx_tab(i, k) transportation cost from factories to crossdocs (per tone)
transship_tab = {
("Factory 1", "Crossdock 1"): 30,
("Factory 2", "Crossdock 1"): 23,
("Factory 3", "Crossdock 1"): 35,
("Factory 4", "Crossdock 1"): 70,
("Factory 5", "Crossdock 1"): 65,
("Factory 1", "Crossdock 2"): 50,
("Factory 2", "Crossdock 2"): 66,
("Factory 3", "Crossdock 2"): 14,
("Factory 4", "Crossdock 2"): 12,
("Factory 5", "Crossdock 2"): 70,
("Factory 1", "DC 1"): 0,
("Factory 2", "DC 1"): 0,
("Factory 3", "DC 1"): 0,
("Factory 4", "DC 1"): 0,
("Factory 5", "DC 1"): 0,
("Factory 1", "DC 2"): 0,
("Factory 2", "DC 2"): 0,
("Factory 3", "DC 2"): 0,
("Factory 4", "DC 2"): 0,
("Factory 5", "DC 2"): 0,
("Factory 1", "DC 3"): 0,
("Factory 2", "DC 3"): 0,
("Factory 3", "DC 3"): 0,
("Factory 4", "DC 3"): 0,
("Factory 5", "DC 3"): 0,
("Factory 1", "DC 4"): 0,
("Factory 2", "DC 4"): 0,
("Factory 3", "DC 4"): 0,
("Factory 4", "DC 4"): 0,
("Factory 5", "DC 4"): 0,
("Factory 1", "DC 5"): 0,
("Factory 2", "DC 5"): 0,
("Factory 3", "DC 5"): 0,
("Factory 4", "DC 5"): 0,
("Factory 5", "DC 5"): 0,
("Crossdock 1", "Crossdock 1"): 0,
("Crossdock 1", "Crossdock 2"): 0,
("Crossdock 2", "Crossdock 1"): 0,
("Crossdock 2", "Crossdock 2"): 0,
("Crossdock 1", "DC 1"): 12,
("Crossdock 1", "DC 2"): 25,
("Crossdock 1", "DC 3"): 22,
("Crossdock 1", "DC 4"): 40,
("Crossdock 1", "DC 5"): 41,
("Crossdock 2", "DC 1"): 65,
("Crossdock 2", "DC 2"): 22,
("Crossdock 2", "DC 3"): 23,
("Crossdock 2", "DC 4"): 12,
("Crossdock 2", "DC 5"): 15,
}
model.c = Param(
model.i,
model.j,
initialize=transship_tab,
doc="Transportation cost from factory to crossdocs (per tone)",
)
## Define variables ##
# Variables
# x
# z = total cost
model.x = Var(model.i, model.j, bounds=(0.0, None))
model.y = Var(model.k, bounds=(0.0, None))
## Define constraints ##
# supply(i) observe supply limit at facitity i
# supply(i) .. sum(j, x(i,j)) <= a(i)
def supply_rule(model, i):
return sum(model.x[i, j] for j in model.j) <= model.a[i]
model.supply = Constraint(
model.i, rule=supply_rule, doc="Observe supply limit at facility i"
)
# demand(i) satisfy demant at restaurant j
# demand(j) .. sum(i, x(i, j)) >= b(j)
def demand_rule(model, j):
return sum(model.x[i, j] for i in model.i) >= model.b[j]
model.demand = Constraint(model.j, rule=demand_rule, doc="Satisfy demand at facility j")
def transsphipment_rule(model, i, j):
return sum(model.x[i, j] for i in model.i if i in model.k) - sum(model.x[i, j] for j in model.k) == 0
model.transshipment = Constraint(
model.i,
model.j,
rule=transsphipment_rule,
doc="The inbound flow must equal the outbound flow - XC does not hold goods",
)
## Define objective and solve ##
# cost define objective function
# z = sum((i, j), t(i, j) * x(i, j))
# solve transport using lp minimizing z
def objective_rule(model):
return sum(model.c[i, j] * model.x[i, j] for i in model.i for j in model.j)
model.objective = Objective(
rule=objective_rule, sense=minimize, doc="Define objective function"
)
## Display of the output ##
# Display x
def pyomo_postprocess(options=None, instance=None, results=None):
#pprint(model.display())
print("Total cost:", model.objective())
model.x.display()
if __name__ == "__main__":
# This emulates what the pyomo command-line tools does
from pyomo.opt import SolverFactory
import pyomo.environ
opt = SolverFactory("glpk")
results = opt.solve(model)
# sends results to stdout
results.write()
print("\nDisplaying Solution\n" + "-" * 80)
pyomo_postprocess(None, model, results)
Soheil.mt
Nov 2, 2019, 12:00:23 PM11/2/19
to pyomo...@googlegroups.com
Hi Michaël
The problem is you set cost for forbidden arc like "Factory 1 to DC 1" or "Crossdock 1 to Crossdock 1" to zero, hence the model cost always become zero.
The simplest way to overcome this issue is set cost for such arc to a big number (for example 1000 in your case).
Moreover, I'am curious why you set Param "a" for crossdocks to zero.
--
You received this message because you are subscribed to the Google Groups "Pyomo Forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pyomo-forum...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pyomo-forum/4bdf3f4f-a9d7-4e58-a893-3b8808045bdd%40googlegroups.com.
Michaël Lambé
Nov 2, 2019, 2:12:59 PM11/2/19
to Pyomo Forum
Hi,
Thanks for your quick feedback. Concerning the Param "a" for crossdocks, I placed them to zero otherwise crossdock 1 and 2 are undefended.
If I place 1000 for all the forbidden arcs, I am getting a cost of 740000.0 however, this is not correct.
if I use a different value than 1000 I am getting different outputs.
Here is the output of the model
# ==========================================================
# = Solver Results =
# ==========================================================
# ----------------------------------------------------------
# Problem Information
# ----------------------------------------------------------
Problem:
- Name: unknown
Lower bound: 740000.0
Upper bound: 740000.0
Number of objectives: 1
Number of constraints: 64
Number of variables: 50
Number of nonzeros: 287
Sense: minimize
# ----------------------------------------------------------
# Solver Information
# ----------------------------------------------------------
Solver:
- Status: ok
Termination condition: optimal
Statistics:
Branch and bound:
Number of bounded subproblems: 0
Number of created subproblems: 0
Error rc: 0
Time: 0.005972862243652344
# ----------------------------------------------------------
# Solution Information
# ----------------------------------------------------------
Solution:
- number of solutions: 0
number of solutions displayed: 0
Displaying Solution
--------------------------------------------------------------------------------
Total cost: 740000.0
x : Size=49, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
('Crossdock 1', 'Crossdock 1') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 1', 'Crossdock 2') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 1', 'DC 1') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 1', 'DC 2') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 1', 'DC 3') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 1', 'DC 4') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 1', 'DC 5') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 2', 'Crossdock 1') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 2', 'Crossdock 2') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 2', 'DC 1') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 2', 'DC 2') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 2', 'DC 3') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 2', 'DC 4') : 0.0 : 0.0 : None : False : False : Reals
('Crossdock 2', 'DC 5') : 0.0 : 0.0 : None : False : False : Reals
('Factory 1', 'Crossdock 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 1', 'Crossdock 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 1', 'DC 1') : 0.0 : 150.0 : None : False : False : Reals
('Factory 1', 'DC 2') : 0.0 : 50.0 : None : False : False : Reals
('Factory 1', 'DC 3') : 0.0 : 0.0 : None : False : False : Reals
('Factory 1', 'DC 4') : 0.0 : 0.0 : None : False : False : Reals
('Factory 1', 'DC 5') : 0.0 : 0.0 : None : False : False : Reals
('Factory 2', 'Crossdock 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 2', 'Crossdock 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 2', 'DC 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 2', 'DC 2') : 0.0 : 50.0 : None : False : False : Reals
('Factory 2', 'DC 3') : 0.0 : 110.0 : None : False : False : Reals
('Factory 2', 'DC 4') : 0.0 : 140.0 : None : False : False : Reals
('Factory 2', 'DC 5') : 0.0 : 0.0 : None : False : False : Reals
('Factory 3', 'Crossdock 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 3', 'Crossdock 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 3', 'DC 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 3', 'DC 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 3', 'DC 3') : 0.0 : 0.0 : None : False : False : Reals
('Factory 3', 'DC 4') : 0.0 : 60.0 : None : False : False : Reals
('Factory 3', 'DC 5') : 0.0 : 40.0 : None : False : False : Reals
('Factory 4', 'Crossdock 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 4', 'Crossdock 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 4', 'DC 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 4', 'DC 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 4', 'DC 3') : 0.0 : 0.0 : None : False : False : Reals
('Factory 4', 'DC 4') : 0.0 : 0.0 : None : False : False : Reals
('Factory 4', 'DC 5') : 0.0 : 140.0 : None : False : False : Reals
('Factory 5', 'Crossdock 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 5', 'Crossdock 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 5', 'DC 1') : 0.0 : 0.0 : None : False : False : Reals
('Factory 5', 'DC 2') : 0.0 : 0.0 : None : False : False : Reals
('Factory 5', 'DC 3') : 0.0 : 0.0 : None : False : False : Reals
('Factory 5', 'DC 4') : 0.0 : 0.0 : None : False : False : Reals
('Factory 5', 'DC 5') : 0.0 : 0.0 : None : False : False : RealsTo unsubscribe from this group and stop receiving emails from it, send an email to pyomo...@googlegroups.com.
Soheil.mt
Nov 2, 2019, 3:16:06 PM11/2/19
to pyomo...@googlegroups.com
Hi,
I try to improve your model. You can find my suggestion in attachment file. I get "30220" as an objective value.
hope this helps.
To unsubscribe from this group and stop receiving emails from it, send an email to pyomo-forum...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pyomo-forum/e419b130-72d8-449e-9ca3-4ad3046bf535%40googlegroups.com.
Michaël Lambé
Nov 2, 2019, 3:35:32 PM11/2/19
to Pyomo Forum
Thanks for your support and sharing the code, I understand my problems - the objective function was not formulated correctly in my implementation.
Again thank you!
To view this discussion on the web visit https://groups.google.com/d/msgid/pyomo-forum/e419b130-72d8-449e-9ca3-4ad3046bf535%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages