TY - JOUR

T1 - Analysis and algorithms for the transtainer routing problem in container port operations

AU - Narasimhan, Ananthapadmanabhan

AU - Palekar, Udatta S.

PY - 2002/2

Y1 - 2002/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036475313&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036475313&partnerID=8YFLogxK

U2 - 10.1287/trsc.36.1.63.576

DO - 10.1287/trsc.36.1.63.576

M3 - Article

AN - SCOPUS:0036475313

SN - 0041-1655

VL - 36

SP - 63

EP - 78

JO - Transportation Science

JF - Transportation Science

IS - 1

ER -