Transportation networks have become the major lifeline of modern societies, not only ensuring individual well-being, but fostering economic growth through fast and reliable transportation activities. Furthermore, the direct relationship between transportation and economic productivity and the steady rise of transnational commercial agreements represent a unique opportunity for developing countries to boost their economies. This paper presents a long-haul, transnational, cross-border transportation problem with transhipments applied to a transportation carrier in Colombia, Latin America. The company faces a combination of challenges that are still rare in the literature such as time windows, a vast fleet and different transportation regulations among different countries. The problem is solved using a combination of simulation and a metaheuristic, which was tested by using two types of heuristics to generate the initial feasible solution. The proposed methods proved its superiority over the solution approach applied by the carrier, showing that significant gains can be obtained.