We want an optimistic heuristic for length of the shortest path from A to B.
Find the nearest waypoint to A. Call it W.
Then max { d(W,B) - d(W,A), 0 } is a lower bound on the length of the shortest path from A to B.
Proof:
By the triangle inequality we have d(W,B) ≤ d(W,A) + d(A,B).
Thus d(A,B) ≥ d(W,B) - d(W,A).
You could apply this idea symmetrically as well to get a slightly better bound. That is, find the nearest waypoint WA to A and the nearest waypoint WB to B and then your lower bound is
max { d(WA,B) - d(WA,A), d(WB,A) - d(WB,B), 0 }
What is nice about this heuristic is that it clearly improves as the density of waypoints increases.