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's gravatar image

MichiHH
1113
accept rate: 0%

edited 11 Sep '14, 03:28

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

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 10 Sep '14, 05:22

Seen: 3,087 times

Last updated: 09 Oct '14, 09:19

OR-Exchange! Your site for questions, answers, and announcements about operations research.