An integrated load-planning problem with intermediate consolidated truckload assignments

This article considers an integrated load-planning problem where decisions on how commodities with unique origin–destination nodes are routed over a given transportation network, along with decisions on their explicit consolidation and assignment to capacitated truckloads, are addressed. In a logistical context, a commodity may refer to a shipper's load handled by a freight forwarder who works as an intermediary between the shippers and carriers. A compact formulation that addresses the load consolidations from many shippers into truckloads and the associated transportation decisions explicitly is first provided. Then, to develop efficient solution algorithms, four compound neighborhood functions and a branching scheme are suggested. Each compound neighborhood function has two main components, level change and content change, with the latter based on various schemes of combining simple neighborhood functions. The compound neighborhood functions and branching strategies enable the solution space to be efficiently searched. Two heuristic algorithms (one with deterministic and the other with probabilistic features) and a tabu search algorithm are also developed. The two components of compound neighborhood functions provide the means to efficiently incorporate intensification and diversification characteristics into these algorithms. Extensive computational results illustrating and comparing the relative efficiency and effectiveness of the algorithms and the compound neighborhood functions are reported. The alternative compounding schemes and the search strategies provided in this study are potentially useful in other problem domains as well.