Subj : Re: Travelling Salesman problem -- Finding shortest path in ship
To   : comp.programming
From : Duane Bozarth
Date : Mon Aug 15 2005 03:24 pm

Boris wrote:
> 
> The definition of 'Overall distance' is the distance from start point
> to end point (which are same). So, the shipper may go to any aisle
> first, but the overall walking dstance should be minimum when he gets
> back to the start position.
> 
> The only hesitation I have is that in TSP, you must visit every
> location once. In my problem, you don't have to because of OPTIONS of
> going to one of multiple location for certain items.

Yes, there're more DOF in your problem than the "classical" TSP,
granted.

Seems like first would be to find the maximum number of items on same
aisle although how important that is depends on the geometry--does the
'bot have to traverse the entire length of the aisle to move laterally
or are there N crossovers or is there (for example) overhead access that
makes additional routes possible?

Seems like you have too large a number of unspecified constraints (or
even the list of what are/aren't constraints) to get far on any
specifics at this point and the more I think of it at present the more
questions I have as opposed to possible solutions.

However, it sounds like a classic warehousing problem and I while it's
not an area of expertise I would expect there would have been
significant applicable research published.  I can't say how frequent the
mulitple stocking points is, however, and whether that really makes your
situation very unique or not.

.