Traveling sales person problem

[spence7607]

Hello everyone,

I am currently working on a traveling salesperson problem. My problem has 1 node/depot and 13 delivery destinations. I have most of it completed but need to add a constraint in solver that after 6 deliveries the truck returns to the node/depot. attached is my .xls file. How do I set this up? My first thought is to simply add a Line in T11 and V11 with the constraint that T11=0 in solver but then solver will not run the alldifferent for the rest of the cities. I'm not looking for someone to do it for me just some help on setting up the constraints. I'm not sure how to set up a sub-tour for the problem. Hopefully I post this in the correct area. Thank you for your help.

[spence7607]

Bump No response

[zbor]

Do you enter those routes in T column manually?
If you put 0 after 11 what will be next route (now is 6)?

Please Login or Register  to view this content.

[spence7607]

The numbers in the T column should be entered by solver (as my changing cells), representing each customer from the array, to minimize the travel distance. T11 was added by me to take into account the return to the DC before heading out to the next 6 deliveries. This is were I'm having difficulty. I need solver to calculate the shortest route but with T11 needing to be 0 (representing the DC) I can't figure out how to add the constraint that each customer be visited only once. Without the return to the depot at T11 I can run it as Evolutionary and use $T5$:$T17$=alldifferent, but by throwing that return to depot in it wont run since T11=0 isn't a valid constraint for the alldifferent function. Is there some other way to make the cells do the same function as the =alldifferent?

[Alf]

Interesting problem but I've not managed to solve it yet, on the other hand I'm not sure I can do so. As you say the problem is with the "Alldifferent" setting. I can't manage to set any constraints to those cell because excel complains.

And if I test splitting the range in two parts setting each part as "Alldidderent" then I just get numbers 1 to 6 twice instead of 1 - 13.

By the way I'm using the setup described in this youtube link:

https://www.youtube.com/watch?v=-E3rSoClgMI

Don't know if you are familiar with it.

When you get a solution could you please post this in this thread as I would really like to see how this kind of problem could be solved.

Alf