I work for an airline. Normally it takes no less than 6 month from the GO to maiden flight. It depends on many factors, but simplified, it goes like this:
When Commercial teams look for new opportunities, they prepares a "business case" balancing the profitability of the route and costs. Main board evaluates the proposal and gives the GO.
It is very hard to open a new route before 6 months, as all airplanes are assigned to other routes with already-sold tickets. Assigning aircraft into the new route requires a very delicate coordination to maximize each aircraft's utilization and avoid unused ground times.
Having that, you can start to sell tickets. At the same time, legal, maintenance, operations and airports teams have to run to get in place all certifications, personnel, permits, contracts and requires stuff for the route.
(Prior to all this, it is important you have an available slot in the origin/destination airports, otherwise it could take much longer.)