Route optimization

Hi,

I am trying to generate scripts for route optimization, that is in what order a machine should operate on different sites with lowest cost of transportation.

I alreday have generated the matrix with distances between all sites.

And the problem now is how to generate the lists of all possible routes.

That is all possible combinations of in which order the sites can be operated.

Does anyone have a clue?

Thank you in advance

Sten-Gunnar

Sten-Gunnar:

This is one of the "classic" computer science problems; try looking up the "Traveling Salesman Problem". If you typically do not have more than a few deliveries to complete you should be able to "brute force" this problem with recursion in SQL Server 2005. This is interesting enough that a mock-up of this might be fun. The main word of caution for this problem is that this problem is viewed being of order N! (n factorial) -- basically of exponential order; therefore, if you are trying to solve this for "many" destinations I don't expect you to find a good solution.

Dave

|||

Look up "traveling salesman problem" or "traveling salesperson problem"

If there are N sites, and every pair of sites is a finite distance

apart, there are N! routes, which is a very large number for N bigger

than 10 or 12. For 20 sites, there are 2,432,902,008,176,640,000 routes,

and I doubt you want to try to enumerate all of them.

You will find a great deal of information on this problem if you search

for it.

-- Steve Kass

-- Drew University

-- http://www.stevekass.com

Sten-Gunnar@.discussions.microsoft.com wrote:

> Hi,

>

> I am trying to generate scripts for route optimization, that is in what

> order a machine should operate on different sites with lowest cost of

> transportation.

>

> I alreday have generated the matrix with distances between all sites.

>

> And the problem now is how to generate the lists of all possible routes.

> That is all possible combinations of in which order the sites can be

> operated.

>

> Does anyone have a clue?

>

> Thank you in advance

>

> Sten-Gunnar

>

>

|||

Thanks Dave and Steve.

What I have found so far in terms of code is this

http://technology.amis.nl/blog/?p=1221

Sten-Gunnar