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

Thad,

Can you elaborate more on simulated annealing? Will that give me the
best solution to the problem?

Thanks,
Boris

Thad Smith wrote:
> 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

.