Unless you want to deal the wind speeds slightly down, the only solution I see is to build massive sloped berms on both sides of the road to serve as a windbreak (massive like in several tens of meters in height and more then hundred of meters in width, maybe more). Since that is a desert, you do not have a possibility to reinforce those berms with trees and plants. So you would need to use stone blocks or cement to build them.

In general, it seems more like a civilization-wide effort along the lines of Egyptian pyramids or Great Chinese wall, than a fast-profit business venture. It will also need constant maintenance and repair. Manned stations at certain intervals with people being always ready to clean the sand blockages, install and take down temporary screens, etc.

Another idea that may work is a huge 'crawler'. A huge tortoise-like shape, much to massive to be affected by the wind, similar to a medieval siege engine, but several times bigger. Huge wheels, hidden under the shell, a huge number of oxen or similar animals to push it from inside, storage area for the cargo and people. A rocket equation problem comes in play here - whether the oxen are able to move the weight of the shell, cargo, people AND feed for themselves enough to go from one settlement to the next one.

UPD: What I think will NOT work:

- Lighter screens of any type, similar to windbreaks along our automotive roads. I can't imagine a lightweight material that wouldn't just sail away in such a wind.

- Tunnels. Creating a tunnel under the shifting sand in what is, effectively, a constant sandstorm doesn't seem a safe proposition to me. Not only the pressures on the ceiling would be constantly changing, you will also not be able to create a reliable ventilation system for it. Any sort of ventilation channels would get clogged with sand all the time.

- Sailing. The speeds you mention are several times higher then the speeds deemed safe for sailing at sea.