But showing every connection is unwieldy and takes quite a bit more space.
Don't reinvent the wheel: http://en.wikipedia.org/wiki/File:Wire_Crossover_Symbols_for_Circuit_Diagrams.png
You could mark the intersections with a connecting dot (or, if space permits, something like a roundabout / traffic interchange icon).
Alternatively, use the "staggered" approach, something like this:
This would look kind of similar to how you've drawn, for instance, Montgomery - Columbus - Atlanta as well as Birmingham - Huntsville - Nashville, so it would fit the map.
Would adding text explaining the mechanic help?
"Show, don't tell" ;)
In my opinion, including a "manual" with a map should be a last resort; sure, it works, but it's far from an elegant solution.