Log in

Graphical Models of Probability
Bayesian Networks, Decision Networks, and Probabilistic Relational Models
traveling salesman with a twist 
2nd-Jun-2005 12:20 am
So here is a problem.

Imagine you have a list of cities that a salesman wants to visit, each on a particual date or range of dates.
You know, Moscow: June 1-3; Tokio: June 17; New York: June 19-25, etc. Well, technically instead of ranges I have probability distributions over the dates when the "conference" of interest for the traveling salesman occurs...

Also here is a list of transit station which the salesman can travel through: Paris, Singapour, Washington, whatever.

All these Cities can be I guess arranged in a simple graph bu what is important not every city is connected to another one, there is a network of "railroads" connecting those (I know, there is no railroad between Tokio and New York, but let it be :)). Of course those railroads have lengths (cost functions, and those are probabilistic) associated with those.

What the salesman needs is an optimal path that would make it possible to make o all those conferences or meetings by the dates specified (and i does not matter, what transition he is taking, but it should make sence in terms of lengths of the paths between those cities, that is, he should be choosing the paths hat would make "perfect timing" for him.

I am pretty sure this is a well known "classic" problem, but what is the "classic" name for the problem?
I would really appreciate if you could help me categorize the problem so that I would know where to start my search for an appropriate algorithm.

Thanks guys!

UPDATE: It appears that Hidden Markov Models (which could be actually implemented as a special case of Bayes Nets) provide a nice framework to deal with my problem.
13th-Dec-2005 06:34 am (UTC) - sidebar: Sourceforge
I couldn't log in so I googled for sourceforge and what I felt was my username. And yes, there it was. But: the 3rd listing was this journal.

You're everywhere!

best of the season to y'all
This page was loaded Feb 24th 2017, 10:39 am GMT.