We present a general technique for obtaining bounds on the deviation of the optimal value of some stochastic combinatorial problems from their mean. As a particular application, we prove an exponential rate of convergence for the length of a shortest path through n random points in the unit square. This strengthens a previous result of Steele (Steele, J.M. 1981. Complete convergence of short paths and Karp's algorithm for the TPS. Math.Oper.Res.).