1
$\begingroup$

Can someone tell me what is the meaning of this multi commodity flow formulation that I got in LINGO ? I have the brief explanation about the model but don't quite understand the logic behind, here is the information and the code:

Decision Variable:
Flo( i, j, c, k) = amount of commodity destined for node c, 
                      carried from node i to node j on vehicle type k; 

! Model multi-commodity flow;
! Cannot have flow within a single node;
  @FOR( Set( j) :
     @SUM( Vehicle( k): @SUM( Set( c): Flo( j, j, c, k))) = 0;
    );

! Flow into node j of commodity c = demand for c at j + flow out;
@FOR( Vehicle( k):
  @FOR( Set( j) | j #NE# Depot:
    @FOR( Set( c) | c #NE# j #AND# c #NE# Depot:
   [CFLO]  @SUM( Set( i) | i #NE# j: Flo( i, j, c, k)) =
           @SUM( Set( i) | i #NE# j: Flo( j, i, c, k)) 
        );
      );
    );

  @FOR( Set( j) | j #NE# Depot:
  ! Flow entering j of commodity for j;
   [DFLOE]  @SUM( SxSxSxV( i, j, c, k) | i #NE# j #AND# j #EQ# c: Flo( i, j, c, k)) = Demand( j);
  ! Flow departing j of commodity for j;
   [DFLOD]  @SUM( SxSxSxV( j, i, c, k) | i #NE# j #AND# j #EQ# c: Flo( j, i, c, k)) = 0;  
     );

! Only source of supply is the Depot;
 @FOR( Set( c):
   @SUM( SxSxSxV( i, j, c, k) | i #EQ# Depot: Flo( i, j, c, k)) = Demand( c)
     );

! Any flow on arc i, j of commodity c means arc i, j, k is used;
  @FOR( SxSxSxV( i, j, c, k) | j #NE# Depot #AND# c #NE# Depot:
 [FORCE]    Flo( i, j, c, k) <= Demand( c) * x( i, j, k)
      );

I have tested with small nodes of 3: Here is what I got:

Selected route: 1 - 3 - 2 - 1 (1 is depot)
x(1,3,1) = 1
x(3,2,1) = 1
x(2,1,1) = 1

And the flow variables:

Flo(1,3,2,1) = 9
Flo(1,3,3,1) = 7
Flo(3,2,2,1) = 9

Is the flow not balanced? I mean why is there not have another 7 in there?

$\endgroup$

1 Answer 1

1
$\begingroup$

Flo(i,j,c,k) is the amount of flow destined for node c that is carried by vehicle k from node i to node j. So Flo(1,3,3,1) is the amount destined for node 3 that is carried on vehicle 1 from node 1 to node 3. Since node 3 is its destination, there is no reason for it to be carried out of node 3.

$\endgroup$
4
  • $\begingroup$ Why they carry 9 on the node of 2 ? Flo(3,2,2,1) = 9 $\endgroup$
    – overboxed
    Commented Aug 18, 2022 at 23:19
  • $\begingroup$ Because node 2 has a demand for 9 (or more)? $\endgroup$
    – prubin
    Commented Aug 19, 2022 at 2:48
  • $\begingroup$ is it not fulfilled with f(1,3,2,1) = 9. The demand of node 2 is 9 units and the demand for node 3 is 7 units $\endgroup$
    – overboxed
    Commented Aug 19, 2022 at 4:29
  • $\begingroup$ 9 units of whatever node 2 ordered flow from node 1 to node 3 [Flo(1,3,2,1) = 9] and then from node 3 to node 2 [Flo(3,2,2,1) = 9]. 7 units of whatever node 3 ordered flow directly from node 1 to node 3 [Flo(1,3,3,1) = 7]. $\endgroup$
    – prubin
    Commented Aug 19, 2022 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.