The problem of minimizing the time taken to load the containers from the container stack yard onto the ship is called the transtainer routing problem. We first do a theoretical investigation of the problem to understand the structural properties of the problem. We then use these results to prove that the problem is NP-Complete. The problem is then formulated as an integer program. A branch-and-bound based enumerative method is developed to obtain an exact solution to the problem. An algorithm to solve the matching problem on a line at the root node of the branch-and-bound tree is developed. Several lower bounds to prune the size of the tree are also developed. A result which states that there cannot exist a polynomial time heuristic with a bounded worst case unless P = NP is proved. Based on this result, an enumerative heuristic with a worst-case performance ratio of 1.5 is designed. Computational tests on randomly generated problems are conducted to evaluate the exact and heuristic algorithms.
ASJC Scopus subject areas
- Civil and Structural Engineering