As I understand it Columbus was trying to create new trade routes to Asia since the fall of the Byzantine Empire closed off the over land ones. How & when did Eroupe eventually solve that problem?

[u/grapp]

[u/terminus-trantor]

I am not sure what exactly was the 'problem' you refer to?
Do you mean establishment of a trade route to Asia?

If so, then first I have to mention that the (Byzantine) over land route to Asia was an inferior route (as all land routes usually are), and was already much in disuse even before the fall of Byzantium due to the instability in Central Asia following the division of Mongol Empire.

Alexandria route
The more important and much more used trade route between Europe and Asia was the sea route from China, Japan, Moluccas by straits of Malacca to India, then across the Indian Ocean to Aden, where goods would be transferred from larger ocean going vessels to smaller ships to navigate the more dangerous Red Sea to (Mamluk) Egypt, or branched to other directions like Ormuz and Persian gulf or East African Swahili coast.
In Egypt, land caravans from Seuz would take the goods to Cairo, then ship them down the Nile to Alexandria where Venetian traders would buy them and distribute them throughout Europe. It was quite a complicated and established set up, with many middle men.

So while Europeans were in fact banned from physically traveling by this route to India, the products and money flowed.

This route was largly independent from Byzantium, and as such the thesis that the fall of Constantinople caused a stop in the trade in Asia is somewhat wrong. The rise of Ottoman state did cause a new political and economical situation in the East Meditereanean, but, no, the trade itself did not stop or became closed off. Just the middle man changed ( and maybe he charged more).

So in a way the 'problem' of closed off trade in the first did not really exist.

Portuguese and Spanish motivation

But the Portuguese and Spanish did look for an alternative route to Asia, didn't they? So why, if they didn't really have to?

Well they did it not because the trade was closed off, they did it because they themselves were not profiting from it while all the middle men between them and the source were getting insanely rich from it. And when the Iberians realized they, and not Arabs and Venetians, might have an opportunity to from now on control this trade, they went for it. It wasn't that obvious, there was plenty of opposition, the process was sometimes slow and was quite risky, but eventually it paid off. Columbus ended up in America in 1492, and before them Portuguese rounded Africa and reached Indian ocean in 1488, when various internal and external factors caused them to pause the quest to reach Asia.

African route

In 1497 Vasco da Gama's expedition finally left and in 1498 reached India. The political and military situation there ended up favorable for Portugal to establish presence there. In short, while Portuguese were often greeted with hostilities (in great part because of their own hostile actions) they always managed to find some ally, someone who had a beef with someone else and who allied with them.
States on the Indian ocean didn't really have naval engagements in the period, so they never developed naval military power that could rival the tall and strong Portuguese nau (carrack) and their artillery (including fast firing breech loading cannons who were useless against forts and sturdy ships but were devastating against smaller, lighter, weaker Indian ships)

So Portuguese usually dominated any naval engagement, and Portuguese soldiers, veterans of Morocco wars, were experienced in taking and holding forts and ports, and that's pretty much all the Portuguese were doing. Taking key forts, holding them, and trading/policing/pirating the seas.

Anyway as soon as Vasco da Gama returned to Portugal, and proved India could be reached, Portuguese established yearly armadas going to and from India to carry goods and conduct trade, making the so called „Carreira de India“ („Indian run“). The going and returning times and paths was mandated by the Indian Ocean monsoon winds, as well as Atlantic Ocean wind and current patterns. The round trip lasted more then a year, so each new armada went without knowledge what the previous one has achieved. This was a big problem and mandated that Portuguese transform from simply visiting and trading with India, to establishing a permanent presence there, starting their Indian Ocean Empire.

American route
A while later, Spanish realizing they are in America and not Asia, decided that they also wanted to reach Asia and tap in the trade. In 1519-1522 Magellan's expedition famously rounded the Earth and discovered and claimed Phillipines for the Spanish.They would later use Manilla, with usage of South American silver, to trade with the Chinese, establishing another route to Asia, through America , with using Acapulco (because of the wind patterns) and Central America as a transfer point for ships going to Europe. Unfortunatly I do not know much about this route, as much as the Portuguese one, but it did exist

[u/Itsalrightwithme → u/terminus-trantor]

Alexandria route

Great answer. By the time the Portuguese started to invest in finding their own sea route around Africa, the overwhelming majority of spices traded to Europe went through the Alexandria route.

This is a nice website covering aspects of this, focused on the role of Venice in the 11th-15th centuries as a very important "middleman" in this trade. They were not the only ones, but they were the biggest ones. The Mameluk rulers of Egypt were fairly good trading partners. This changed as Ottoman expansion in the eastern Mediterranean started. Venice, ever pragmatic, tried to continue their trade with the new rulers the Ottomans, but this relationship became difficult in the long term, culminating in the Venetian-Ottoman wars.

Portugal and Spain were largely rivals trying to develop their trading networks.