This paper considers a coordinated global shipment matching problem in which a global operator receives shipment requests from shippers and three local operators provide local transport services in different geographical areas. While local operators make local matching decisions, the global operator combines the matched local services into itineraries to provide integrated transport for shipments. To handle the interconnecting constraints between different operators, a Lagrangian relaxation heuristic approach is developed. Under the proposed approach, the original problem is decomposed into local operator-related subproblems. These subproblems are optimized iteratively under local constraints as well as under the incentives imposed by the global operator to meet interconnecting constraints. The experiment results show that with the proposed approach, global transport planning that requires coordination among different operators to achieve a common goal can be realized.