The aim of this paper is to develop an approach for evaluating various maritime transportation routes in light of ongoing disruptions and evolving global factors, including changes in demand, fluctuations in fuel prices, geopolitical shifts, and environmental considerations. For each alternative route, a profit maximization liner shipping problem with speed optimization is solved. Both edge-based speed optimization and maximum transit time of commodities are considered. We have proposed a mathematical programming formulation followed by an efficient hybrid approach for the optimization problem. The hybrid approach utilizes a population-based heuristic to optimize the route and an exact algorithm to optimize commodities and speed. A thorough analysis is made on the costs associated with the different alternative routes. Although the approach can be applied to different regions of the world and under the variation of several factors, we focus on the Asia–Europe trade route and on the evolution of the market demand. The comparison is made between a route going through Suez Canal and the alternative route of going through the Cape of Good Hope. Besides the high efficiency of the solution procedure, we have found that the Cape of Good Hope route can be economically interesting especially if there is demand in some African ports and if vessels of less than 20,000 TEU capacity are used.