# Traveling Salesman Problem with soft Time Windows and IBM ILOG CPLEX

 0 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. Forgive me my perhaps somewhat complicated way in programming OPL, I've never done something like this. 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. The time window (a [i], b [i]) thereby can be exceeded and to go below. w is the output-time of to early and m is the output-time of the late arriving. The underlying data are in the .dat file. I think the problem lies in the equation 4c and 4d, which should eliminate the subtours. Since I'm unfortunately totally clueless. I would appreciate any help very much. Thanks in advance Michael OPL-Programm (.mod): //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]))<=d[j]; forall(j in 2..V) x[1][j]*u[1][j]+w[j]<=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]<=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]>=d[i]; forall(i in 1..V) d[i]>=0; forall(i in 2..V) w[i]>=0; forall(i in 2..V) m[i]>=0; }  The Data File (.dat): //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];  asked 10 Sep '14, 05:22 MichiHH 11●1●3 accept rate: 0% 3 Check out https://www.or-exchange.org/questions/9068/or-software-forums for the address of a software forum devoted to OPL questions. (07 Oct '14, 13:25) 4er You do not state the issue. If you go the the OPL forum suggested by @4er, please explain why you are unhappy with your model. (09 Oct '14, 09:19) jfpuget
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190

Seen: 3,087 times

Last updated: 09 Oct '14, 09:19