Multiple traveling salesman / Vehicle routing problem - subtour elimination constraint

[Greg Netols]

Hi i am working on a MTSP problem where i have 3 vehicles leaving a warehouse to make deliveries at 7 other hospitals. 

Currently i have my first four constraints working. But i can't / dont understand how to create the sub tour elimination constraint. I also currently have a constraint that eliminates sub tours of 2 nodes but none that will prevent longer sub tours.

please help. Here is my dat and mod file.

#mod

param hospital;

param m;

param CTruck;

set HOSP = 1..hospital;

set DEST = 2..hospital;

param D{HOSP,HOSP};

param T{HOSP,HOSP};

var x{i in HOSP, j in HOSP}, binary, default 0;

#var u{2..hospital} >= 0;

minimize objective_function:

sum {i in HOSP, j in HOSP} x[i,j]*D[i,j];

subject to depart: # m trucks leave peoria

sum{j in HOSP} x[1,j] = m;

subject to return: # m trucks return to peoria

sum{j in HOSP} x[j,1] = m;

subject to noreturn{i in HOSP}: # trucks can't depart and arrive to same location

x[i,i] = 0;

subject to singleentrance{j in DEST}: # all nodes are entered exactly once

sum{i in HOSP} x[i,j] = 1;

subject to singleexit{i in DEST}: # all nodes are exited exactly once

sum{j in HOSP} x[i,j] = 1;

 

#subject to subtourelim:

subject to notwocycles{i in DEST, j in DEST: i <> j}: # no two node cycles that don't include 1

x[i,j] + x[j,i] <= 1;

dat

param hospital :=8;

param m:=3;

param CTruck:= 5000;

param D:=

1 1 0

1 2 43.2

1 3 69.3

1 4 84.4

1 5 133

1 6 48.3

1 7 49.2

1 8 67.5

2 1 43.2

2 2 0

2 3 34.6

2 4 84.7

2 5 134

.........

.........

.......

....

...

..

.

[Robert Fourer]

An example of a subtour elimination constraint is given in the attachments to this post:

https://groups.google.com/d/msg/ampl/mVsFg4mAI1c/ZdfRHHRijfUJ.

That formulation is based on having a list of subtours. An example of a formulation that generates all subtours is found in this Frequently Asked Question:

http://ampl.com/faqs/how-can-i-get-ampl-to-index-over-the-power-set-consisting-of-all-subsets-of-a-set/

(Generating all subtours is only practical for very small problems, however.) For your problem you will presumably need subtour elimination for each of the 3 vehicles.

Bob Fourer
am...@googlegroups.com

=======

[waho...@gmail.com]

Dear 

Do you have an ampl code for MTSP ?

I would apreciate it if you can help

best regards,

[Greg Netols]

I should have it somewhere. Message me again if I don't get back to you in 1 week.

[AMPL Google Group]

This post give you some guidelines about subtour elimination https://groups.google.com/forum/#!msg/ampl/mVsFg4mAI1c/ZdfRHHRijfUJ

--
Paras Tiwari
am...@googlegroups.com

{#HS:522075505-330#}

On Sun, Feb 11, 2018 at 3:06 PM UTC, <am...@googlegroups.com> wrote:

I should have it somewhere. Message me again if I don't get back to you in 1 week.

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[janog...@gmail.com]

how are you?, do you still have the code?, i have an issue with a similar model and i want to see the difference between both of them. if you have it fine, and if you dont, its fine too :)

[AMPL Google Group]

We don't have a complete running models. You can find the references at https://groups.google.com/forum/#!msg/ampl/mVsFg4mAI1c/ZdfRHHRijfUJ and https://ampl.com/faqs/how-can-i-get-ampl-to-index-over-the-power-set-consisting-of-all-subsets-of-a-set/.

--
Dr. Paras Tiwari
am...@googlegroups.com

{#HS:597140821-9695#}

[Greg Netols]

Hi Jose,

I have the code however i only have it in PDF form. It was written for an engineering project in college and i no longer have access to the data and mod files, but i do have the hard copy report. Check the attached pdf and let me know if you have any questions.