Originally posted by: max__x
Dear all,
I am trying to integrate the Dantzig, Fulkerson and Johnson (DFJ) tsp formulation with wagner-whitin inventory problem.
The aim is to build T tsp tours which only visits the shops they need replenishment at that period.AND the objective is minimizing the total costs, including transportation costs and inventory costs.
My problems is that it seems to that if there are only two shops need replenishment, and it is not able to build tsp tour, it must will visit another shop and then visits these two shops. WHAT I AM TRYING TO SAY, is it seems to be it must contains 3 vertices in each tour. But this will not achieve the objective to minimize the total costs, visiting one more shops must leads to higher cost. I think it is the problem with my sub-tour elimination constraint, since If I use another tsp formulation it works.
I hope someone can help me to figure it out why only two shops in a tour is not valid in my code. I will very appreciate it.
//generate subsets of all the Cities
{int} I = {1,2,3,4};
range r=1.. ftoi(pow(2,card(I)));
{int} s2 [k in r] = {i | i in I: ((k div (ftoi(pow(2,(ord(I,i))))) mod 2) == 1)};
execute
{
writeln(s2);
}
// more than two elements and less than |S|-1 elements
tuple t
{
{int} set;
};
{t} res={<s2[k]> | k in r : 2<=card(s2[k])<=card(I)-1};
execute
{
writeln(res);
}
//decision variable
dvar boolean Orderdecision[Periods][Cities];
dvar float+ Inv[0..n][1..m];
dvar boolean x[Periods][i][j];
//objective function
dexpr float Transportationcost = (sum(i in Cities, j in Cities, t in Periods) Distance[i][j]*x[t][i][j]);
dexpr float Inventorycost = ( sum( t in Periods , c in Cities) Orderdecision[t][c] * Orderingcost[t][c])+
( sum(t in Periods, c in Cities ) Inv[t][c]* InventoryCost[c] );
minimize (Inventorycost+Transportationcost);
//constraint
subject to {
//initial inventory level
InitialInventorylevel:
forall(c in Cities)
Inv[0][c] == InitialInventory[c];
// inventory capacity
forall( t in Periods, c in Cities )
InventoryCapacity:
Inv[t][c] >=0;
forall (t in Periods, c in Cities)
Inv[t-1][c] + Orderdecision[t][c]*Orderquantity[t][c] <= Capacity[c] ;
//flow conservation
forall( t in Periods, c in Cities)
BalanceEquation:
Orderdecision[t][c]* Orderquantity[t][c] + Inv[t-1][c] == Inv[t][c] + Demand[t][c];
//force that if there is a shop j need services, then there must be a shop from shop i to shop j at time t
forall (j in Cities, t in Periods)
sum(i in Cities) x[t][i][j] >= Orderdecision[t][j];
//flow conservation, tsp formulation
forall(t in Periods, j in Cities)
sum(i in Cities: i!=j)x[t][i][j]==sum(i in Cities: i!=j)x[t][j][i];
//subtour elimination
forall(t in Periods, k in r: 1 < card(s2[k]) < card(I) - 1 )
sum(i in s2[k], j in s2[k]) x[t][i][j] <= card(s2[k]) - 1;
}
//data
int n=...;
range Periods=1..n; //number of time period
int m=...;
range Cities=1..m; //number of cities
range i= 1..m;
range j= 1..m;
//generate data
float Demand[Periods][Cities] = ...;
float Orderingcost[Periods][Cities] = ...;
float Orderquantity[Periods][Cities]=...;
float Capacity [Cities]=...;
float InitialInventory [Cities]= ...;
float InventoryCost [Cities]= ...;
float Distance[i][j]=...;
#DecisionOptimization#MathematicalProgramming-General