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

Ananthapadmanabhan Narasimhan, Udatta S. Palekar

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)63-78
Number of pages16
JournalTransportation Science
Issue number1
StatePublished - Feb 2002

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'Analysis and algorithms for the transtainer routing problem in container port operations'. Together they form a unique fingerprint.

Cite this