The problem you describe is known as the Orienteering Problem (OP), see for example this [survey][1] (which is takes an operations research viewpoint), and also [this paper by Blum et al][2], which gives a constant-factor approximation algorithm and shows that OP cannot be approximated better than some fixed constant (i.e. OP is [APX-hard][3]). [Bansal et al.][4] showed a 3-approximation. There are some variants to the problem, and the simplest have to do with starting and ending points: you can specify a starting point (sometimes called rooted OP), or starting and ending points. [1]: http://www.inf.unibz.it/dis/teaching/SDB/papers/batch1a.pdf [2]: http://www.cs.cmu.edu/~avrim/Papers/orienteering-sicomp.pdf [3]: http://www.nada.kth.se/~viggo/wwwcompendium/node5.html [4]: http://pages.cs.wisc.edu/~shuchi/papers/timewindows.ps