Custom Post Type in Permalink Structure

I’m looking for the best way to add a taxonomy slug into the permalink structure.

For example, for example, for a “Format” taxonomy with choices Bio, Photos, Videos:

Permalink Structure: /%category%/%format%/%postname%/

Category: John Travolota

Format: Bio


Post without a “Format” taxonomy chosen:

This plugin seems to target this issue, however any post without a “Format” chosen results in a 404 error.

Thanks in advanced!