Improved Integer Programming-Based Neighborhood Search for Less-Than-Truckload Load Plan Design

Less-than-truckload (LTL) carriers operate networks of consolidation terminals, and route each customer shipment through a sequence of transfer terminals. At each terminal stop, a shipment is unloaded from an inbound trailer and reloaded onto an outbound trailer. A load plan determines the specific path of terminals to be used to transfer freight moving between each origin and destination. The design of the load plan determines the line-haul transportation and handling costs required to serve customers. This paper develops an effective neighborhood search heuristic for solving a natural integer programming model for LTL load plan design. During each iteration of the heuristic, a modified version of the integer programming model is solved to find improving changes freight transfer paths for a subset of the origin-destination terminal pairs. Unlike existing approaches in the literature, the modified model solved here allows the simultaneous rerouting of freight destined for multiple terminals during each neighborhood search iteration, yet remains computationally practical. Computational experiments using data from a large U.S. carrier show substantial cost improvements generated by increased freight consolidation, in the order of 6%–7%, accounting for over $300,000 per week.