If a general has movement restrictions, they will also be applied to the troops under their command (a % decrease).

Check your generals, they probably have traits that are slowing them down. They may want to be sent to towns...