An effective kernel search and dynamic programming hybrid heuristic for a multimodal transportation planning problem with order consolidation

We study a realistic capacitated multimodal transportation planning problem (CMTPP) faced by logistics companies when trying to obtain a cost advantage in a competitive market. This problem simultaneously considers limited vehicle numbers and order consolidation. Given a set of origin–destination transportation orders with a time window, solving the CMTPP involves determining the delivery paths of these orders on a capacitated network as well as selecting the transportation modes used on these paths. Without violating time windows and network capacity constraints, all customers’ requests must be satisfied exactly, with minimum overall logistics costs. The CMTPP is formulated as a mixed binary linear program based on which an effective kernel search and dynamic programming hybrid heuristic (HKSDP) is proposed, which repeatedly generates feasible solutions. A column generation approach is also proposed to provide a lower bound for the problem which is then used to evaluate the performance of the proposed heuristics. Numerical experiments for various sizes of random instances (with at most 300 orders in a network and 20 nodes) are conducted. The results demonstrate the effectiveness of column generation in obtaining a tight lower bound as well as the efficiency of the HKSDP in achieving a high-quality near-optimal solution. The average optimality gap is approximately 1.04%. We also provide a practical application of the proposed HKSDP to a logistics network in inland China.