For those interested, I've created a simple mechanic that allows for random monster encounters during the travel step. It takes advantage of the "No Event" cards. The only downside is that you may need to wait to set up the main quest, as the encounter may use some of the same map pieces. I built it to incorporate most of the current expansions.

I've altered these random encounters to be based off of the travel icon they occur at. There are 5 possible encounters per travel icon. The rewards have also been significantly changed.

Link to encounters for range 2 and 3.

Link to encounters for range 4 and 5.

Link to encounters for range 6.