有两家面包店（B1, B2)以及四个客户（C1, C2, C3, C4)。面包店B1每天最多生
产800个面包，而面包店B2每天最多生产600个面包。客户（C1, C2, C3, C4) 对于
面包的需求分别为150, 250, 350 and 450 个/天，面包店至客户的单位运输成本如
下图所示，请问最便宜的运输计划是怎样的？
简单配送问题举例
运输问题
数学模型
Transportation Problem
Mathematical model
3
面包店i的产量 。
我们定义为ai
面包的销售j的销量，
我们定义为bj
练习
试通过Xpress 软件编写程序，解决以下问题，目标为总运费最小？
Cij B1 B2 B3 B4 产量
A1 3 11 3 5 12
A2 6 9 8 7 20
A3 4 2 14 10 32
销量 26 18 8 7
运输问题—计算机解法
关于Xpress IVE
(basic features for student restricted version)
• 常常用于优化问题的解决。
• Maximum number of constraints 限制条件 (rows): 400
• Maximum number of variables 变量 (columns): 800
• Maximum number of matrix coefficients 矩阵的元素(elements): 5000
• Maximum number of binary and integer variables二元变量, etc (global elements): 400
FICO Xpress-IVE
Start > Programs > Xpress > Xpress IVE
FICO Xpress-IVE
FICO Xpress-IVE
FICO Xpress-IVE
FICO Xpress-IVE
Mosel Xpress-IVE
Writing a model in Mosel
model Transportation
uses “mmxprs” 定义模型名称
变量声明
declarations
a: array (1..2) of integer
b: array (1..4) of integer
c: array (1..2, 1..4) of integer
x: array (1..2, 1..4) of mpvar
end-declarations
forall(i in 1..2,j in 1..4)
x(i,j) is_integer
initializations from "example of "
a
b
c
end-initializations !引入数据
Writing a model in Mosel
目标函数与限制条件
! 设置总成本函数
Cost:=sum (i in 1..2, j in 1..4) c(i,j)*x(i,j)
! 设置限制条件
forall (i in 1..2) sum (j in 1..4) x(i,j) <= a(i)
forall (j in 1..4) sum (i in 1..2) x(i,j) >= b(j)
minimize(Cost) !设置目标函数，成本变量不需要声明
Writing a model in Mosel
Output & results
! 输出目标函数 getobjval 表示优化后的值
writeln(“Total cost: “, getobjval)
! 输出各个变量的值
forall (i in 1..2, j in 1..4)
writeln(“x (”,i,”,”,j,”) = “,getsol(x(i,j)))
How to write a model
in Mosel Xpress-IVE
Name of the model
Declarations (decision variables, arrays, etc.)
Data input
Objective function
Constraints
Output & results
15
How to write a model
(1) Name of the model
model ModelName
uses “mmxprs”
16
How to write a model
(2) Declarations (variables, arrays, etc.)
declarations
Variable(变量名） : mpvar
VariableArray (变量名） : array() of mpvar
end-declarations
17
How to write a model
(3) Data input – optional section
initializations from “Filename”
UnitCost;
end-initializations
18
How to write a model
(4) Objective function
Cost:=2*x1+3*x2
!...constraints
minimize(Cost) !you don’t need to declare Cost
or
Profit:=2*x1+3*x2
!...constraints
minimize(Profit) !you don’t need to declare Profit
19
How to write a model
(5) Constraints
! simple constraint
X1+3*X2-5*X3<=8
! multiple constraints using loop
forall(i in 1..10) Z(i)<=1
! sum constraint
sum(i in 1..10) X(i)<=B
! multiple sum constraints using loop
forall(i in 1..5) sum (j in 1..10) X(i,j)=1
20
How to write a model
(6) Output & results
! Value of objective function - getobjval
writeln(“Objective value: “, getobjval)
! Vlue of decision variable
writeln(“X1 = “,getsol(X1))
! Values of decision variables in array using loop
forall(i in 1..M)
writeln(" Y(“, i,") = “, getsol(Y(i)))
21
What should be answered in this lesson?
Which decisions are made when a distribution system is designed?
Which costs must be taken in consideration, if we want to reach the
most efficient performance of the system?
How to describe the distribution design problem, which is to be
solved by computer?
Distribution System
A distribution system is a composition of primary sources of goods,
customers, warehouses and stores and a transportation system.
A distribution system satisfies customer’s demands for goods from a set
of primary sources.
The activities, which cause the move of goods from a primary source to a
customer, form logistic chains.
Distribution System Structure
How many echelons (levels) should have the distribution system?
How many warehouses, if any, should be located and where should they
be placed?
How many buffer stores, if any, should be run and where?
Which facility should supply a customer?
Which warehouse or primary source should supply a buffer store?
What does the system structure design contribute?
Don’t you believe me? Money!!
Follow the next toy example!
Let us consider one producer P and four customers, which are
supplied each day with one item of product each. Customers can
be supplied only by trucks and each truck can carry exactly one
item of the product at transportation cost 2 RMB per unit distance.
What does the system structure design contribute?
Producer P
Customers
1
1
1
1
11
11
If the customers are supplied directly
from P, two items are delivered along
the distance of 4 units and another
two items are carried along the
distance of 5 units. The total
distance traversed is 18 units and the
associated cost is 36 RMB.
What does the system structure design contribute?
Producer P
Customers
1
1
1
1
11
11
But, there is a railway, which starts from
P and goes near to the customers
through two places, where
transshipment places may be
constituted (each for six RMB per day) .
This transportation means is able to
transports one item at one RMB per
distance unit.
What does the system structure design contribute?
Producer P
Customers
1
1
1
1
11
11
Now, three other possibilities have
arisen. The transshipment places can be
constituted at both crossings or at one of
the two possibilities.
What does the system structure design
contribute?
Producer P
Customers
1
1
1
1
11
11
Here, two transshipment places are
constituted at price of 12 rmb.
Items are carried by railway by two 3 and
4 distance units respectively, what does
14 units totally (and 14 RMB).
The total distance traversed by trucks is 4
and the cost is 8.
The total cost is 34.
What does the system structure design contribute?
Producer P
Customers
1
1
1
1
11
11
In this situation, one places is
constituted at price of 6 .
Items are carried by railway by 16
distance units totally, what does 16
RMB.
The total distance traversed by trucks is
6 and the cost is 12.
The total cost is also 34.
What does the system structure design contribute?
Producer P
Customers
1
1
1
1
11
11
In this situation, also one places is
constituted at price of 6 .
Items are carried by railway by 12
distance units totally, what does 12
RMB.
The total distance traversed by trucks is
6 and the cost is 12.
The total cost is also 30.
What does the system structure design contribute?
Producer P
Customers
1
1
1
1
11
11
This structure with the total cost 30
wins!
It is by 6 better than the original
direct distribution in this case.
33
Why we build the model if we were able to solve the
problem without it?
Our toy problem has exactly four feasible solutions given by sets of
places, at which a facility is located.
A problem with n possible places has 2n feasible solutions.
If there are 64 possible locations, then 2n is approximately *1019.
When we were able to evaluate one million solutions in one second,
determination of the optimal solution would required *1013 seconds,
what is 584*103 years.
Relevant Costs of Distribution
Holding cost (rent cost for a warehouse, fixed charge fi for locating or
keeping a warehouse at given place i).
Handling cost (manipulating cost connected with transshipment or storing
one unit of goods gi ).
Transportation costs (costs connected with way of transport at the
particular echelon, . bulk transport cost and distribution transport cost).
35
Relevant Cost of Distribution
Primary source
Customers
Warehouse 1 Warehouse i
Transportation cost of bulk transport
Fixed charge fi
Handling cost gi
Transportation cost of distribution
transport
Let us demonstrate the procedure on the toy
example
Producer P
Customers
1
1
1
1
11
11
Nodes of special importance are here
the producer P and the crossings P1
and P2.
We obtain distances:
P1
P2
C1 C2
C3 C4
P P1 P2 C1 C2 C3 C4
P 0 3 4 4 4 5 5
P1 3 0 1 1 1 2 2
P2 4 1 0 2 2 1 1
Cost of Customer’s Demand Satisfaction
Notice the prime costs e0 and
e1 please!
Each of them gives a cost of
transport of one demand unit
along one distance unit.
Primary source
Customer j
Warehouse i
dsi – distance between primary source
and warehouse i
dij – distance between warehouse i
and customer j.
gi – handling cost at i
Let us demonstrate the cost calculation on the toy
example
Producer P =s
Customers
1
1
1
1
11
11
The prime cost e0 is 2 RMB and e1 is
1 RMB。
Handling cost gi =0 and bj=1.
P1
P2
C1 C2
C3 C4
dij P P1 P2 C1 C2 C3 C4
P 0 3 4 4 4 5 5
P1 3 0 1 1 1 2 2
P2 4 1 0 2 2 1 1
39
Let us demonstrate the cost calculation on the toy
example
Customers
Producer P=s
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
dij P P1 P2 C1 C2 C3 C4
1 P 0 3 4 4 4 5 5
2 P1 3 0 1 1 1 2 2
3 P2 4 1 0 2 2 1 1
Cij P P1 P2 C1 C2 C3 C4
1 P 8 8 10 10
2 P1 5 5 7 7
3 P2 8 8 6 6
1
2
3
40
Decision Variables for Distribution System Structure
Design
Decision on a facility location at place i will be
modeled by a variable yi {0,1}.
y3 {0,1}
Producer P=s
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
y2{0,1}
y1{0,1}
1
2
3
41
Decision Variables for Distribution System Structure
Design
Decision on supplying of customer j
from place i will be modeled by a
variable
zij {0,1}.
Customer j=2
z32{0,1}.
Producer P=s
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
y1{0,1}
1
2
3
42
Decision Variables for Distribution System Structure
Design
Primary source
Customer j
Location i
yi {0,1}– Will ( yi =1) or will not ( yi =0) be
a warehouse located at place i ?
zij {0,1}– Will ( zij =1) or will not ( zij =0) be
customer j assigned to location i ?
43
A Model of the Total Cost
This is fixed cost (charge), which will appear at place i
depending on the decision yi.
If no warehouse is located at i, then yi=0 and also fiyi=0. On
the contrary, if a warehouse is located at i, then yi=1 and
fiyi=fi.
44
A Model of the Total Cost
This is fixed cost (charge), at all considered places of I.
45
A Model of the Total Cost
This is cost of customer’s j demand satisfaction via place i,
which will appear depending on the decision zij.
If customer j is not satisfied via i, then zij=0 and also cijzij
=0. On the contrary, if customer j is satisfied via i, then zij=1
and cijzij =cij .
46
A Model of the Total Cost
This is cost of customer’s j demand satisfaction.
It must be supplied via one place from the set I.
47
A Model of the Total Cost
This is cost of demand satisfaction of all customers.
48
A Model of the Total Cost
This is relevant total cost the distribution system over a
considered time period.
49
A Model of Two-echelon Distribution System Design
These are the constraints,
which assure that each
customer is supplied via
exactly one place from I.
Customer j=2
z32{0,1}
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
1
2
3
50
A Model of Two-echelon Distribution System Design
These constraints ensure that customer j is allowed to be supplied via
place i, only if a warehouse is located there, . yi=1.
51
A Model of Two-echelon Distribution System Design
Customer j=2
z32{0,1}
Producer P=s
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
y1{0,1}
1
2
3
52
Let us demonstrate the model building on the toy
example
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
J 1 2 3 4
fi I cij C1 C2 C3 C4
0 1 P 8 8 10 10
6 2 P1 5 5 7 7
6 3 P2 8 8 6 6
53
Let us demonstrate the model building on the toy
example
Customer j=2
z32{0,1}
Producer P=s
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
y1{0,1}
1
2
3
1
1
1
1
11
11
P1
P2
C1 C2
C3 C4
54
Writing a model in Mosel
Loops, sums & data from file
练习：
生产商P只生产一种产品，有四个客户，每个客户每天
的需求量为一件。每个客户只能由货车送货上门，每辆货
车运载量为1件。 每件货物用货车运输的单位运费为2
RMB。
有一条铁路，从P出发将经过两个离客户比较近的地方
P1和P2，P1和P2可以作为中转站配送货物。每个中转站
租金为6 RMB每天。生厂商P通过铁路把货物运输至中转
站的单位运输成本为1RMB。
问题：请用Xpress计算出最优的物流配送方案。
Producer P
Customers
1
1
1
1
11
11
P1
P2
declarations
m, n: integer
end-declarations
initializations from “”
m
n
end-initializations
56
Writing a model in Mosel
Declarations of variables using arrays & loops
declarations
I = 1..m
J = 1..n
y : array (I) of mpvar
z : array (I,J) of mpvar
f : array (I) of integer
c : array (I,J) of integer
end-declarations
57
Writing a model in Mosel
Declarations of variables using arrays & loops
initializations from “”
f
c
end-initializations
Structure of the input file “”:
m:[3]
n:[4]
f:[0,6,6]
c:[8, 8,10,10,
5, 5, 7, 7,
8, 8, 6, 6]
58
Writing a model in Mosel
Data input
THANKS! !
