An Algorithm for Solving Capacitated Multicommodity <Emphasis Type="Italic">p</Emphasis>-median Transportation Problems

An algorithm for solving a special capacitated multicommodity p-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 the p-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.