An approach is described for aiding managers of a container-transshipment seaport in understanding the balance between the number of containers to undergo security inspection and two alternative objectives: first, the vessel cost as measured by the concomitant departure delays of outbound vessels and, second, the port costs as measured by the total number of container moves. Security concerns heightened by the events in the United States on September 11, 2001, have resulted in the U.S. Customs Services seeking partnerships with foreign ports so that some containers bound for the United States might undergo security checks before they enter that country. However, outbound-vessel departure delays and additional container moves in the yard associated with security checks could create significant costs and negatively affect the competitive position of a port. A best-first optimal search procedure, A*, is used to solve a simplified container-yard management problem for transshipment seaports. A methodology is developed to optimize transshipment-container movements from inbound vessels to outbound vessels through yard-storage areas when a subset of the containers must be moved to an inspection area for a security check. It is assumed that the container stow plans for the inbound and outbound vessels are known and that the containers to be inspected have been determined by regulatory agencies before ship arrival. Modeling details and extensions of the problem are discussed. Due to the intractability of the generic A* technique for problems of realistic size, a fast heuristic based on simple rules is developed for a simplified transshipment model. Finally, a modified A* algorithm incorporating both fast optimal rules and a branching procedure is introduced.