Need help with subtours.

[Rabi]

Hi!
We need help with our code. We have two AGVs that are going to drive to some
shelfs in a warehouse so we are going to optimize a route for each vehicle.

We have the following modelfile
#Modellfil: Ruttplanering.mod


set STARTNODE;
set ENDNODE;
set VEHICLE;


param c{STARTNODE,ENDNODE}; #costs


var x{STARTNODE, ENDNODE, VEHICLE} >= 0 binary;

minimize z: sum{k in VEHICLE, i in STARTNODE, j in
ENDNODE}(c[i,j]*x[i,j,k]);

subject to
villkor1{k in VEHICLE, j in ENDNODE}: sum{i in STARTNODE}x[i,j,k]=1; #one
way in
villkor2{k in VEHICLE, i in STARTNODE}: sum{j in ENDNODE}x[i,j,k]=1; #one
way out
villkor3{k in VEHICLE}:sum{j in ENDNODE}x[1,j,k]=1; #starting place(depot)
villkor4:sum{i in STARTNODE}x[i,35,1]>=1; #shelf
villkor5:sum{i in STARTNODE}x[i,34,1]>=1; #shelf
villkor6:sum{i in STARTNODE}x[i,30,1]>=1; #shelf
villkor7:sum{i in STARTNODE}x[i,31,1]>=1; #shelf
villkor8:sum{i in STARTNODE}x[i,29,2]>=1; #shelf
villkor9:sum{i in STARTNODE}x[i,27,2]>=1; #shelf
villkor10:sum{i in STARTNODE}x[i,32,2]>=1; #shelf
villkor11:sum{i in STARTNODE}x[i,33,2]>=1; #shelf
villkor12:sum{j in ENDNODE, k in VEHICLE}x[1,j,k]>=1; #We visit node 1 more
than 1 time
villkor13:sum{j in ENDNODE, k in VEHICLE}x[1,j,k]=sum{i in ENDNODE, k in
VEHICLE}x[i,1,k]; #- if we drive out from node 1 more than once, we have to
go back to node 1 (we want to start and end in the depot)



This is our data file:
set STARTNODE := 1 27 29 30 31 32 33 34 35;
set ENDNODE:= 1 27 29 30 31 32 33 34 35;
set VEHICLE := 1 2;

param c: 1 27 29 30 31 32 33 34 35:=
1 1000 10.9 60.3 24.3 26.1 69.9 27.9 71.6 41.3
27 10.9 1000 49.4 23.6 37 59 38.8 60.8 52.2
29 60.3 49.4 1000 51.2 64.7 31.2 78.1 44.7 90
30 24.3 23.6 51.2 1000 35.2 45.6 37 47.4 50.4
31 26.1 37 64.7 35.2 1000 43.8 23.6 45.5 37
32 69.9 59 31.2 45.6 43.8 1000 57.1 23.4 58.9
33 27.9 38.8 78.1 37 23.6 57.1 1000 43.7 23.6
34 71.6 60.8 44.7 47.4 45.5 23.4 43.7 1000 45.5
35 41.3 52.2 90 50.4 37 58.9 23.6 45.5 1000;


These are the shelfs we are supposed to visit. But when we run the program
we get subtours and we want to include a while loop of some sort to identify
every subtour and add it as a constraint. Or atleast in anyway eliminate the
subtours. Any ideas? Thank you in advance.






--
View this message in context: http://ampl.996311.n3.nabble.com/Need-help-with-subtours-tp10535.html
Sent from the AMPL mailing list archive at Nabble.com.

[Robert Fourer]

I suggest taking a look at the example files posted with this earlier reply:

https://groups.google.com/d/msg/ampl/7kYcU1_bQHc/kSWGk6POWEYJ

These are for a single minimum tour problem, but the same ideas could be applied to a model for optimizing two routes. The idea is to solve, find a subtour and add a subtour set, and repeat, until there are no more subtours. There is a subtour elimination constraint indexed over subtour sets, so that every time a new subtour is added, a new subtour elimination constraint is automatically added as well.

Bob Fourer
am...@googlegroups.com

=======