What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?
Assuming that $p$ and $q$ are fairly large, one would expect that the expected length would mainly depend on the density, with some correction term depending on the perimeter. So it would, to first order, be a function of the following form.

$$ L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$$

Now, you could use experiments on smaller-size problems to figure out what $f$ and $g$ are. First, to estimate $f$, you want to do experiments on a sample without a boundary: the easiest way to do this is to use a $p\times p$ grid with the left side connected to the right and the top to the bottom, forming a torus. To estimate $g$, you can use experiments on a $p \times q$ grid. 

For estimation, you need to solve (exactly or approximately) relatively large TSPs, since the larger the ones you use for the estimation, the better your results will be. You could either use heuristics that come within a few percent, or exact TSP code. See here for some good heuristics. Bill Cook's Concorde TSP solver will find the exact optimum for reasonably large instances (it's the best TSP code available), and can be used without charge for academic research.