Minimum Length Hamiltonian Path Pair in O(n^2) or better
Since you said a $O(n^2)$ time algorithm would still be useful, there is a straightforward dynamic programming algorithm that runs in time $O(n^2)$.

In particular, a subproblem is specified by a pair of points $(A',P')$; the problem is to find the best pair of paths from $A' \to B$ and $P' \to Q$, using only points that are to the right of both $A'$ and $P'$.  To solve each subproblem, you only have to look at the solution to two subproblems: in particular, to $(Z,P')$ and $(A',Z)$, where $Z$ is the point immediately to the left of the rightmost of $A',P'$.  Therefore, each subproblem can be solved in $O(1)$ time.  As there are $O(n^2)$ subproblems, the $O(n^2)$ running time follows immediately.