title: Traveling Salesman (TSP) with soft Time Windows and IBM ILOG CPLEX
body: <p>I'm trying to set up a traveling salesman problem with soft time windows in OPL and IBM ILOG CPLEX to solve. I have the Probelm after all, as a smaller version installed, but can not find my mistake, so i am very helpless.</p>
  
  <p>Forgive me my perhaps somewhat complicated way in programming OPL, I've never done something like this.</p>
  
  <p>The TSP - problem involves 1 depot (x [1] [1]) and three customers. From the Start at the depot, all three customers have to be visited and then returned to the depot.</p>
  
  <p>The time window (a [i], b [i]) thereby can be exceeded and to go below.</p>
  
  <p>w is the output-time of to early and m is the output-time of the late arriving.</p>
  
  <p>The underlying data are in the .dat file.</p>
  
  <p>I think the problem lies in the equation 4c and 4d, which should eliminate the subtours.</p>
  
  <p>Since I'm unfortunately totally clueless.</p>
  
  <p>I would appreciate any help very much.</p>
  
  <p>Thanks in advance</p>
  
  <p>Michael</p>
  
  <p><strong>OPL-Programm (.mod):</strong></p>
  
  <pre><code>//number of Nodes
  
  int V=...;
  
  // initialization driving Time between two nodes
  
  int u[1..V][1..V]=...;
  
  //initialization Time-Windows
  
  int a[2..V]=...;
  
  int b[2..V]=...;
  
  //initialization panalty-costs (not used in objective function)
  
  int c1[2..V]=...;
  
  int c2[2..V]=...;
  
  // Helping Variable for Linearization
  
  int M=51000;
  
  //initialization decision variable
  
  dvar boolean x [1..V][1..V];
  
  //initialization of d,w, m 
  
  //arrival Time
  
  dvar int d[1..V];
  
  // come too late
  
  dvar int m[2..V];
  
  //come too early // waitingtime
  
  dvar int w[2..V];
  
  //objective function
  
  minimize
  
      sum( i in 1..V, j in 1..V)
                                  u[i][j]*x[i][j]         
  //  + sum(i in 2..V )
  //                              c1[i]*w[i]  
  //  + sum(i in 2..V)
  //                              c2[i]*m[i]; 
      ;                                                     
  //constraints
  
  subject to{
  
  //1)
  // in each account only one edge must arrive TSP
  
  forall(i in 2..V) sum(j in 1..V)x[i][j]==1;
  //2) 3)
  //Ensures that the depot (1) is left and is approached.
  
  sum(j in 1..V)x[1][j]==1;
  
  sum(i in 1..V)x[i][1]==1;
  
  //4)
  //Ensures that every customer is visited and leave afterwards.
  
  forall(l in 2..V)
  
  sum(i in 1..V)x[i][l]-sum(j in 1..V)x[l][j] ==0;
  
  //4c) und 4d)
  //prevents subtours
  
  forall(i in 2..V, j in 1..V)
  
  (w[i]+d[i]+u[i][j])-(M*(1-x[i][j]))&lt;=d[j];
  
  forall(j in 2..V)
  
  x[1][j]*u[1][j]+w[j]&lt;=d[j];
  
  //4a)
  //earliest arrival time z [i] equal is greater than the lower limit of the customer time window.
  
  forall(i in 2..V)
  
  a[i]-w[i]&lt;=d[i];
  
  //4b)
  //earliest arrival z [i] is equal to less than the upper limit of the customer's time slot.
  
  forall(i in 2..V )
  
  b[i]+m[i]&gt;=d[i];
  
  forall(i in 1..V)
  
  d[i]&gt;=0;
  
  forall(i in 2..V)
  
  w[i]&gt;=0;
  
  forall(i in 2..V)
  
  m[i]&gt;=0;
  
  }
  </code></pre>
  
  <p><strong>The Data File (.dat):</strong></p>
  
  <pre><code>//number of Nodes 
  
   V = 4;
  
  // Traveltimes 
  
  u=[ [1000, 3, 5, 30] [3, 1000, 30, 9] [5, 30, 1000, 4] [30, 9, 4, 1000] ];
  
  //Time window lower limit // [Customer 1 Customer 2 Customer 3]
  
  a=[ 23 , 3, 10];
  
  //Time window limit // [Customer 1 Customer 2 Customer 3]
  
  b=[50, 4, 30];
  
   //penalty costs // [Customer 1 Customer 2 Customer 3]
  
  c1=[1, 1, 1];
  
  //penalty costs // [Customer 1 Customer 2 Customer 3]
  
  c2=[1, 1, 1];
  </code></pre>