Subj : Re: Travelling Salesman problem -- Finding shortest path in ship
To   : comp.programming
From : Thad Smith
Date : Tue Aug 16 2005 12:51 am

Boris wrote:

> In a shipping warehouse, items need to be picked from the shelved on
> different aisle of the warehouse (Aisles and shelves are similart to
> grocery store aisles). However, an item may be found on multiple
> locations. For example, item_A can be found on aisle 2,3,5 and so on. I
> am calling such items as OPTIONS, meaning I have an option of going to
> one of those aisle (but must go to at least one of those OPTION). There
> are some item that exist in only one location. I call it REQUIRED items
> as you must visit these locations. There will be at least 20 items,
> some of them will be OPTIONS. (sets of options, meaning item_A is in 3
> different locations of which one needs to be picked, item_B is in 2
> different location of which one need to be picked and so on.)
> 
> All I have to do is to highlight the location of the shelves that need
> to be visited. But I need to highlight in a way that overall distance
> should be minimum. The starting point and end point are the same.

Later he writes:

> 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.

First, this is a combinatorial problem.  For each option item, you must 
choose one of its locations.  You have a cost function, overall 
distance, that is used to evaluate a combination.  Although you don't 
need to specify the route, you need to know the optimum route in order 
to determine that the combination is optimum.  You need to know how the 
overall walking distance is determined for any combination of items.

Consider simulated annealing.  Chose an initial solution with random 
choices for each of the option items.  Cycle through the option items, 
reducing the overall distance, when possible, by choosing another 
location for the item.  Repeat cycling though all items until no 
improvement is made in distance.  Then start over with a different 
random allocation and repeat the improvement cycle.  Do this several 
times, choosing the best refined solution over many random starts.

Thad

.