🚀 go-pugleaf

In article <13DEC199216365553@cc.utah.edu>, lallu@cc.utah.edu (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
|> ulall@pub.uwrl.usu.edu


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