! Multi-commodity flow model in LINGO;
! Each node in a network has a demand for each
of a number of distinct commodities. A supply of
a commodity is represented as a negative demand.
Each link or arc in the network has an upper limit on how much
can be shipped over the link. The objective is to find a
shipment pattern for the commodities so as to minimize the
total shipping cost, subject to not exceeding any of the
arc capacities;
! Keywords: Network, Multi-commodity;
SETS:
NODE ; ! There is a set of nodes;
COMMODITY; ! There is a set of commodities;
ARC(NODE, NODE): ! Some of the node pairs have directed links;
U, !Total capacity on this arc;
FLO; !Flow on this arc, to be determined;
CXN( COMMODITY, NODE): ! Combinations of commodities and nodes;
B; !Demand - supply at this node of each commodity;
CXA( COMMODITY, ARC):
C, ! Cost/unit flow commodity k on this arc;
UK, ! Upper bound on flow of commodity k on this arc;
X; ! Flow of commodity k on this arc;
ENDSETS DATA:
COMMODITY = 1..2;
NODE = 1..9;
! Demand - supply at each node;
b = -9 -8 0 0 0 4 3 5 2 ! Commodity 1;
-8 -7 0 0 0 3 2 5 2; ! Commodity 1;
! Arcs available, and capacities over all commodities;
ARC U =
1 3 7
1 4 9
2 4 9
2 5 9
3 6 9
3 7 9
4 7 8
4 8 9
5 8 9
5 9 9 ;
! Commodity, Arc capacities and costs;
UK C =
! Commodity 1;
!1 3; 5 7
!1 4; 5 5
!2 4; 5 1
!2 5; 5 6
!3 6; 5 9
!3 7; 5 2
!4 7; 5 3
!4 8; 5 4
!5 8; 5 4
!5 9; 5 2
! Commodity 2;
!1 3; 5 1
!1 4; 5 1
!2 4; 5 7
!2 5; 5 8
!3 6; 5 3
!3 7; 5 8
!4 7; 5 7
!4 8; 5 4
!5 8; 5 5
!5 9; 5 6
ENDDATA
! MINIMIZE Cost of flow;
MIN=@SUM(CXA( k,i,j): X(k,i,j)*C(k,i,j));
! Conservation of flow for each commodity k at node i:
Flow in - Flow out >= demand (- supply);
@FOR( CXN( k, i):
@SUM( ARC( j,i): X(k,j,i)) - @SUM(ARC(i,j): X(k,i,j)) >= B(k,i);
);
! Capacity on arc i,j over all commodities;
@FOR( ARC(i,j):
FLO(i,j) = @SUM( COMMODITY(k): X(k,i,j));
FLO(i,j) <= U(i,j);
);
! Capacity on flow of commodity k on arc i,j;
@FOR( CXA(k,i,j):
X(k,i,j) <= UK(k,i,j);
);
|