In order to solve empty repositioning problems, different heuristics
have been applied as the solution methodologies. Chang
et al. (2008) test their Branch-and-Bound (B&B) heuristic on a
transportation systems with 12 consignees and 8 shippers, 2 local
container depots and 1 container terminal, and up to 985 containers.
Bandeira, Becker, and Borenstein (2009) implement decomposition
and prioritization approaches on a 4 depot case with 4 to 8
clients. They test and analyze the performance for different sizes
of container fleet from 48 to 216 containers. Their computational
time ranges from 9 to 8800 CPU seconds. Bandeira et al. (2009)
show that the suitable number of containers is highly dependent
on the system parameters, and uncertainty makes the decision more difficult. For an integrated forward and backward planning
of container fleet, Song and Dong (2012) analyze their shortestpath
algorithm on two small and medium sized instances with 8
and 24 locations, 24 vessels, and 80,000 containers. Their solution
method in both cases provides better performance compared to
the state-of-the-practice method, and the heuristic is only 3.3%
worse than the exact algorithm in solving the small sized case.
Even though it takes almost triple of computational time compared
to the practice, in less than one hour the proposed heuristic provides
a solution 89% better than the state-of-the-practice.