Wouldn't have been alone

Solution 1:

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.

Solution 2:

This answer is essentially a replay of a chat conversation (starts here) about this very question.

Firstly, the would does not express conditionality, it expresses doubt. It is an example of epistemic modality. The speaker (B) cannot say that the merchants did not travel alone, he is expressing a hypothesis. The sentence is also tagged with this modality in a non-grammatical way, by starting with I think. So, the next obvious question is: why two lots of epistemic modality? Well, that's just one way English speakers hedge, for example:

It's maybe possible
I maybe could go
It's possible you might not be the best person for the job

So, why then, is have there? Why not just

I think they wouldn't be alone when travelling.

In this context, it is entirely fine to use this construction. That is because we already know the discussion is about the past, so it's fine to assume that the hypothesis is talking about a past event. However, would can be used to when talking about the future, e.g.

If I were you, I wouldn't go up there

Also, would is being used to emphasise doubt, so imagine if B were less doubtful, and didn't use have:

I think they won't be alone when travelling.

Suddenly B is talking about the future! So, have is added in as an additional marker to make sure we know that B is talking about the past.

In conclusion B is saying

They won't have been alone when travelling.

But with double hedged words.

Solution 3:

Would, and its negative, can be used to describe habitual past actions. In your example, wouldn’t have been alone indicates that those concerned travelled in company on most, if not all, occasions.