From Newsgroup: comp.programming

Why does the salesman have to travel, when he can sell everything from home ? On Monday, August 15, 2005 at 9:08:12 PM UTC+3, Boris wrote:

I am not sure if the following problem falls under Travelling Salesman Problem. If so, what approximation algorithm can I use to get the best solution. Here is the problem.
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.
I do not need to give a walking pattern, I just need to tell them which locations to be visited. In a case when there are only REQUIRED items,
I do not need to do any calculations. The trick comes when there are
OPTION items.
Because I do not need to tell them the walking route, I do not think it
is a travelling salesman problem, but I may be wrong. I would really appreciate for any help to generate an algorithm of my problem.
Thanks in advance,
Boris

--- Synchronet 3.20a-Linux NewsLink 1.114