2.8.1 Multi-commodity Transportation (transp3)

Run LPL Code  ,  PDF Document

Problem

This is a simple multi-commodity transprortation problem: various products have to be transported from a supply location to different demand center. Unit transportation cost, supply quantity, transport capacity, and demand are given. How much of a product must be transported from a supply location to a demand location at minimial costs?

Modeling Steps

Given a set of locations i,j I and a set of products p P. All given routings and the cost are given as Rp,i,j and cp,i,j, that is, if a product p is transported from i ti j then routep,i,j is true otherwise false. Supply quantity from location i and demand quantity to j of a product p are given in sp,i and dp,j. From the route the supply locations and the destination location can be derived: Origi and Destj, that is: if i is a supply location then Origi is true (otherwise false). In the same way all the feasible connections COi,j can be derived from route. The variable is the quantity to be transported of a product p from i to j: Transp,i,j. The whole model is as follows:

             ∑
min               cp,i,j ⋅ T ransp,i,j
           (p,i,j)∈R
           ∑
subjectto      T ransp,i,j = sp,i       forall p ∈ P,i ∈ Orig
           ∑j∈R
               T ransp,i,j = dp,j       forall p ∈ P,j ∈ Dest
            i∈R
           ∑
               T ransp,i,j ≤ Capacity   forall (i,j) ∈ CO
            p∈R
           T ransp,i,j ≥ 0              forall (p,i,j) ∈ R

Further Comments

OPL uses the ellipsis ... to specify the missing data in an otherwise structural model code. They are given in an separate data file. The concept of tuple is used to related data, like the concept of “record” or “struct” in programming languages. This is definitely a concept that is missing in the LPL language. Due to this feature it is also possible to create compound (sparse) sets. However, I find LPL’s compound sets syntax more straightforward and shorter.

LPL model code (run transp3)

model transp3 "Multi-commodity Tansportation"; 
  set i,j,Cities; 
  set p,Products; 
  parameter Capacity; 
  set connection{i,j}; 
  set route{p,i,j}; 
  parameter Supply{p,i}; 
  parameter Demand{p,j}; 
  parameter Cost{p,i,j}; 
  set Orig{i};  Dest{j}; 
  variable Trans{p,i,j|route}; 
  minimize obj: sum{route[p,i,j]} Cost*Trans; 
  constraint ctSupply{p,Orig[i]}: 
    sum{j in route} Trans = Supply; 
  constraint ctDemand{p,Dest[j]}: 
     sum{i in route} Trans = Demand; 
  constraint ctCapacity{connection[i,j]}: 
    sum{p in route} Trans <= Capacity; 
end

LPL data model : (The data itself is in file transp3.txt)

model data; 
  Read('transp3.txt,%1:Cities',{i} i); 
  Read('%1:Products',{p} p); 
  Read('%1:Capacity', Capacity); 
  Read{p,i,j}('%1:Routes:Supply',p,i,j,route,Cost); 
  Read{p,i}('%1:Supply:Demand',p,i,Supply); 
  Read{p,j}('%1:Demand:Cost',p,j,Demand); 
  connection{i,j}:=exist{p} route; 
  Orig{i}:=exist{j} connection; 
  Dest{j}:=exist{i} connection; 
  {p} if(sum{Orig[i]} Supply <> sum{Dest[j]} 
     Demand , Write('Inconsistent' n')); 
end;

OPL code (download transp3.mod)

{string} Cities =...; 
{string} Products = ...; 
float Capacity = ...; 
tuple connection { string o; string d; } 
tuple route { 
  string p; 
  connection e; 
} 
{route} Routes = ...; 
{connection} Connections = { c | <p,c> in Routes }; 
tuple supply { 
  string p; 
  string o; 
} 
{supply} Supplies = { <p,c.o> | <p,c> in Routes }; 
float Supply[Supplies] = ...; 
tuple customer { 
  string p; 
  string d; 
} 
{customer} Customers = {<p,c.d> | <p,c> in Routes}; 
float Demand[Customers] = ...; 
float Cost[Routes] = ...; 
{string} Orig[p in Products] = { c.o | <p,c> in Routes }; 
{string} Dest[p in Products] = { c.d | <p,c> in Routes }; 
 
{connection} CPs[p in Products] = { c | <p,c> in Routes }; 
assert forall(p in Products) 
   sum(o in Orig[p]) Supply[<p,o>] == sum(d in Dest[p]) Demand[<p,d>]; 
 
dvar float+ Trans[Routes];

 

constraint ctSupply[Products][Cities]; 
constraint ctDemand[Products][Cities]; 
 
minimize 
  sum(l in Routes) Cost[l] * Trans[l]; 
subject to { 
  forall( p in Products , o in Orig[p] ) 
    ctSupply[p][o]: 
      sum( <o,d> in CPs[p] ) 
        Trans[< p,<o,d> >] == Supply[<p,o>]; 
  forall( p in Products , d in Dest[p] ) 
    ctDemand[p][d]: 
      sum( <o,d> in CPs[p] ) 
        Trans[< p,<o,d> >] == Demand[<p,d>]; 
  forall(c in Connections) 
    ctCapacity: 
      sum( <p,c> in Routes ) 
        Trans[<p,c>] <= Capacity; 
}