how to manage multiple dynamic routing in linux VMs

we currently have 200+ linux VMs (and growing).

we also have 3-4 different internet gateways.

currently they're all in the same subnet (let's call it 10.10.x.x/16)

currently i'm using a pair of soft router (mikrotik CHR) to direct traffic from the VMs to the internet. there are different (sometimes complex) scenarios of where a packet should be directed through which internet gateways.

since they're all in the same subnet, and i don't setup NAT/masquerade, they create asymmetrical packet routing. i was concerned that setting up a basic NAT/masquerade end up exhausting the port allocation for PAT on the soft router.

​

so what is the best / ideal way to control routing on the VMs environment? note that sometimes the routing table changes dynamically depending on scenarios. so i'm trying to avoid using static routing in linux. and i'm trying to avoid setting up hundreds of linux routing tables.