Analysis and Algorithms for the Transtainer Routing Problem in Container Port Operations

Ananthapadmanabhan Narasimhan and Udatta S. Palekar
Additional contact information
Ananthapadmanabhan Narasimhan: Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
Udatta S. Palekar: Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801

Transportation Science, 2002, vol. 36, issue 1, 63-78

Abstract: 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.

Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.36.1.63.576 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:36:y:2002:i:1:p:63-78

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().