In short: no, this usage of would have been is correct, and its meaning is subtly different from would be and were here. It is probably useful to look at this sentence one step at a time, to consider each transformation of the verb separately.
They are not alone when travelling.
A simple statement about a present fact. (The default attitude of a speaker towards a proposition is "this is true", so fairly strong certainty.)
They were not alone when travelling.
The verb is transferred to the past: a simple statement of fact about the past.
They will not have been alone when travelling.
In this transformation, have been is equivalent to were as above; will is added to express "I expect that this will turn out to be true". It calls some attention to the (confident) attitude of the speaker towards this "fact of the past"; one could say that the speaker shows that he is aware that he is giving an estimation, not a completely indisputable fact. But instead of may, he uses will to express that he is quite confident about it.
I do not think this is habitual will/would, because to describe a repeated situation in the past you would simply say they would be alone when travelling. You could do that, and the meaning of the sentence would not change very much, because the speaker's attitude is not that important to the meaning of the whole sentence; but it would still be slightly different.
The condition when travelling makes it a habitual/repeated situation anyway: they were not alone when travelling would express that they were not alone "every time they travelled". So the habitual nature is probably not contained in will/would.
They would not have been alone when travelling.
Here will changes into past subjunctive would. This could be considered a conditional would, as in "if I should be right, they would not have been alone", or some other condition. As an alternative, you could simply say that the past subjunctive can be used with modal verbs to add more uncertainty in general.
I do not think there is a clear boundary between the two. The more general uncertainty as perceived in would where no clear condition is present (explicitly or otherwise) probably originates in that very conditional construction: a condition adds some degree of uncertainty to any proposition, as it will only be true under certain conditions. You could call would "epistemic" when no condition can be easily conceived of, but it is really immaterial.