Dynamic reconfiguration is commonly used to accommodate the dynamic behavior of today’s applications. As cloud-based systems become increasingly complex, it is hard and cost-ineffective to manage them manually. Dynamic routers, such as API Gateways or Message Brokers, in combination with auto-scalers can adapt the system to the resource demands, e.g., when a sudden load spike for a specific part of the system is observed. Without taking costs of cloud resources into account, this reconfiguration can lead to significant increase of charges. We propose a self-adaptive and cost-aware dynamic routing architecture called Adaptive Dynamic Routers. The novel architecture performs a multi-criteria optimization analysis to automatically reconfigure the routers and the services of a cloud-based system considering the costs of reconfiguration. This multidimensional auto-scaling of resources takes incoming load as an input, and uses queuing theory to find an optimal reconfiguration solution. We systematically evaluated our architecture with an extensive number of evaluation cases (9600). On average over cases where an overload is predicted, our approach reduces the overload rate by 46.7% and 61.8% for routers and services, respectively.