Subject: what problem is it?

From: Tzahi Fadida <[email-masked]>
Date: Mon, 14 Mar 2005 02:14:34 +0200

Hi,
I am trying to charecterise a problem I have for my thesis.
I am not a graphs person so I need some help with this one.
I know its probably at least a TSP problem.
I.e. shortest path a person can take to visit
all his target cities. shortest could translate to 
cab costs or cost to sequentially scan a file(which is what I am working
on).
Now comes the catch, what if you have S salesmans
traveling to all the same cities and if they travel to the
same destination together at the same time they can share a cab and thus
each of them pays 1/S, i.e. the cab still only gets the fair fee
as if only one person traveled. btw, at the start they don't
necessarily start at the same city.

My question is, what is the (closest) problem in the literature?
I heard something about Multiple traveling salesman problem
but I am searching for a specific one where it has my kind
of cab sharing costs. maybe some way to reduce it to
regular TSP... I heard something about MTSP with time
windows but I am not sure it fits.

Aside from the problem, if there is some approximation/heuristic
or anything please tell.

Regards,
	tzahi.

* - * - *
Itzhak Fadida
MSc Student
Information System Engineering Area
Faculty of Industrial Engineering & Management
Technion - Israel Institute of Technology
Technion City, Haifa, Israel 32000
Technion Email: [email-masked]
Alternative Email: [email-masked]
Office Phone(from Israel): 04-8292226
Office Location: Technion, Cooper Bldg. room 427.
* - * - * - * - * - * - * - * - * - * - * - * - * - * - *

WARNING TO SPAMMERS:  see at
http://members.lycos.co.uk/my2nis/spamwarning.html

---

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 14 Mar 2005 11:23:47 +0200

On Mon, Mar 14, 2005, Tzahi Fadida wrote about "[hackers-il] what problem is it?":
>...

I have no knowledge about this problem, sorry, but I just have a
question:
The case where there are very few cities is easy, because you can even
run the exponential algorithm on a modern computer. So let's assume there
are many cities.
In this case, I would guess that a near optimal solution (though perhaps
not THE optimal solution) is for all the people to get to one city, and
from there share a cab that goes through the normal TSP solution. You'd
want to find the best city to meet at, of course, but that sounds like a
fairly simple O(N) algorithm.

But there is one problem in this "solution" - while it guarantees that
each person passes through each city at least once, each person will pass
through some of the cities twice. If you don't allow that, then the
problem becomes more complex, and sounds interestin. What are the rules?

-- 
Nadav Har'El                        |      Monday, Mar 14 2005, 3 Adar II 5765
[email-masked]             |-----------------------------------------
Phone +972-523-790466, ICQ 13349191 |Always go to other people's funerals,
http://nadav.harel.org.il           |otherwise they won't come to yours.

---

From: Tzahi Fadida <[email-masked]>
Date: Mon, 14 Mar 2005 13:05:55 +0200

> > traveling to all the same cities and if they travel to the  same 
> >destination together at the same time they can share a cab and thus  
> >each of them pays 1/S, i.e. the cab still only gets the fair 
> fee  as if 
> >only one person traveled. btw, at the start they don't  necessarily 
> >start at the same city.
> > 
> > My question is, what is the (closest) problem in the literature? I 
> > heard something about Multiple traveling salesman problem
> 
> The case where there are very few cities is easy, because you 
> can even run the exponential algorithm on a modern computer. 
> So let's assume there are many cities. In this case, I would 
> guess that a near optimal solution (though perhaps not THE 
> optimal solution) is for all the people to get to one city, 
> and from there share a cab that goes through the normal TSP 
> solution. You'd want to find the best city to meet at, of 
> course, but that sounds like a fairly simple O(N) algorithm.

Yes its an idea of many, but of course many probably thought about
it before me so reuse is better in this case.

> 
> But there is one problem in this "solution" - while it 
> guarantees that each person passes through each city at least 
> once, each person will pass through some of the cities twice. 
> If you don't allow that, then the problem becomes more 
> complex, and sounds interestin. What are the rules?

I wouldn't mind them going back just that the cost of going back
should be 0 (since we bought "hofshi hodshi"? :) ).

(Also I am currently assuming that he made a sell in every city and thus
allowed back but in real its possible that he won't be allowed back to a

city in any road. I.e. this can only happen if at every change in the
system
e.g. the salesman move from one city to the next I check to see what are
their
results and thus change the graph to reflect the results).

> [email-masked]             
> |-----------------------------------------
> Yahoo! Groups Links

---

From: "leiboviche" <[email-masked]>
Date: Mon, 14 Mar 2005 15:06:47 -0000

I just wanted to note, that if we're speaking of Euclidian or
Euclidian space graph there are some very good approximation schemes
for it (the I think it stands currently of 1.5 approximation) if you
want references - do tell.
BTW Nadav Hare'l has summurized my thoughts of the matter, it was like
a magical story I thought of the "salesmen of the world unite"
sollution and suddenly Nadav wrote it.
--- In [email-masked], Tzahi Fadida <tzahi_ml@f...> wrote:
> Technion Email: Tzahi@T...
> Alternative Email: TzahiFadida@M...

---

From: Tzahi Fadida <[email-masked]>
Date: Mon, 14 Mar 2005 19:53:00 +0200

Let me try a different approach.
I rethought it and maybe what I need is a minimum spanning tree with
a twist. I.e. building m spanning trees in stages and in parrallel.
Lets say I want to build m spanning trees and I have
an input graph of n verticies and z edges in the graph.
lets assume there are no disconnected components.
At each stage we add an edge(or none) to each of the graphs.
If we add an edge to the same city on some subset u of the graphs and
the edge cost
is C_k then the cost for each edge is C_k/|u| and totally C_k.
(the edge cost depends on the city so all incomming edges to a city
have the same cost)
Again note that I must build all the spanning trees
in parrallel and in stages because time matters here.
Simple calculation shows, that the complexity as it is now, is
O(((z+1)^n)^m) which is huge.
The input graph is directed but bidirectional, i.e. if there is an edge
in one direction,
there is an edge in the other direction with different costs to traverse
it.

If I'll translate it to a problem domain it could be seen as salesman
offices
trying to branch out to another city a branch at a time.
The cost of branching is the cost of an edge.
If we have m salesmen offices and they are branching to the same city
at the same time they can share the cost of buying the building.
(the building has space for all salesmen if need be)

Regards,
	tzahi.

> -----Original Message-----
> From: leiboviche [mailto:[email-masked]] 
> Sent: Monday, March 14, 2005 5:07 PM
> To: [email-masked]
> Subject: [hackers-il] Re: what problem is it?
> 
> 
> 
> 
> Euclidian space graph there are some very good approximation 
> schemes for it (the I think it stands currently of 1.5 
> approximation) if you want references - do tell. BTW Nadav 
> Hare'l has summurized my thoughts of the matter, it was like 
> a magical story I thought of the "salesmen of the world 
> unite" sollution and suddenly Nadav wrote it.
> > heard something about Multiple traveling salesman problem but I am 
> > searching for a specific one where it has my kind of cab sharing 
> > costs. maybe some way to reduce it to regular TSP... I 
> heard something 
> > about MTSP with time windows but I am not sure it fits.
> > 
> > Aside from the problem, if there is some approximation/heuristic or 
> > anything please tell.
> > 
> > Regards,
> > 	tzahi.
> > 
> > * - * - *
> > Itzhak Fadida
> > MSc Student