NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/sci/math/stat/2591

Internet Message Format | 1992-12-14 | 1.9 KB

Path: sparky!uunet!tymix!daffodil!rick
From: [e-mail]
Newsgroups: sci.math.stat
Subject: Re: shortest chain on a sphere / shortest around the world trip
Message-ID: <[e-mail]>
Date: 14 Dec 92 17:21:22 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: BT North America, San Jose, CA
Lines: 34
Nntp-Posting-Host: daffodil

In article <[e-mail]>, [e-mail] (Upmanu Lall, Civil Eng) writes:
|>
|> Does anyone know if this is a solved problem ?
|>  It seems like it ought to be.
|> There are n arbitrary locations on the surface of the earth, each of which must
|> be visited
|> once and only once, starting from any one of them.
|> At the end of the trip one is back at the starting point.
|> It seems to me that the choice of the starting point does not matter,
|> i.e. there is a unique shortest chain, and you should be able to find it
|> irrespective of where you start on it.
|> Is this assertion correct ?
|> Is there an algorithm for determining the shortest path efficiently,
|> and the second shortest, etc ?
|> I recall from a network optimization class taken 2 decades ago, that
|> a chain network is the dual problem to a flow network
|> Can this be used to setup the problem such that one could
|> establich whether the primal or the dual is easier to solve, and to then solve
|> the problem ?
|> Distances are Euclidean on the sphere (or the Earth). LAts and Longs of the
|> points are known , and the number of locations is also known a priori (i.e.
|> this is not a stochastic process).
|>
|> Any references, or suggestions to bodies of literature shall be appreciated.
|> Determinitic  or Monte Carlo techniques would be fine.
|>
|>
|> Thanks very much for your help
|> Please respond to
|> [e-mail]


Try Travelling Salesman Problem in "Introduction to Operations Research" by
Hillier and Liebermann.