Liner shipping fleet repositioning consists of moving vessels between services in a liner ship- ping network in order to better orient the overall network to the world economy, and to ensure the proper maintenance of vessels. Thus, fleet repositioning involves sailing and loading activities subject to complex handling and timing restrictions. The objective of the problem is cost minimization, which translates nearly directly into the minimization of CO2 emissions and pollution. Additionally, it is important that all cost elements, including the ones that are only loosely coupled with activity choices, can be accurately modeled. Numerous liner shipping fleet repositioning problems are solved each year by the world’s shipping firms without the assistance of any decision support, even though humans can require between two to three days to find a reasonable solution. Finding optimal repositionings is important in helping shipping firms move towards their goal of greater eco-efficiency.