AbstractAn algorithm for solving a special capacitated multicommodityp-median transportation problem (CMPMTP), which arises in container terminal management, is presented. There are some algorithms to solve similar kinds of problems. The formulation here is different from the existing modelling of thep-median or some related location problems. We extend the existing work by applying a Lagrangean relaxation to the CMPMTP. In order to obtain a satisfactory solution, a heuristic branch-and-bound algorithm is designed to search for a better solution, if one is possible. A comparison is also made with different algorithms.