How about drawing the arrowhead on the middle of the line? (And not drawing it on short lines. The arrowheads on the long lines will reveal whether 'departures' or 'arrivals' are depicted)