Solution:

Denote by $X_{1}, X_{2}, \ldots, X_{n}$ the cities in the country and let $X_{i}$ be connected to exactly $m_{i}$ other cities by direct two-way airline. Then $X_{i}$ is a final destination of $m_{i}$ direct routes and an intermediate stop of $m_{i}(m_{i}-1)$ non-direct routes. Thus $r = m_{1}^{2} + \ldots + m_{n}^{2}$. As each $m_{i}$ is at most $n-1$ and $13 \cdot 12^{2} < 2014$, we deduce $n \geq 14$.

Consider $n = 14$. As each route appears in two opposite directions, $r$ is even, so $r \geq 2016$. We can achieve $r = 2016$ by arranging the 14 cities uniformly on a circle and connect (by direct two-way airlines) all of them, except the diametrically opposite pairs. This way, there are exactly $14 \cdot 12^{2} = 2016$ routes.