This construction is used to talk about repeated past actions.
In your sentence you can use any of would part/parted/used to part.
The word "will/would" has dozens of uses, and there are several possible interpretations. These include
1) It is indirect speech equivalent of the direct speech The two men said "When the train reaches Cairo we will part"
2) The two men were fated to part when the train reached Cairo.
3) The two men regularly travelled on the train and they regularly parted when they reached Cairo.
4) At that time, the men's journey on the train and their parting in Cairo were in the future.
As ever, context helps to clarify which is meant.
(I am neither a teacher nor a native English speaker.)
Interested in Language