Improved Load Plan Design Through Integer Programming Based Local Search

We present integer programming models of the service network design problem faced by less-than-truckload (LTL) freight transportation carriers and a solution approach for the large-scale instances that result in practical applications. To accurately represent freight consolidation opportunities, the models use a fine discretization of time. Furthermore, the models simultaneously route freight and empty trailers and thus explicitly recognize the efficiencies presented by backhaul lanes. The solution approach can generate the traditional service network designs commonly used by LTL carriers but also enables the construction of designs that allow more flexibility, e.g., that allow freight routes to vary by day of week. An iterative improvement scheme is employed that searches a large neighborhood, each iteration using an integer program. Computational experiments using data from a large U.S. carrier demonstrate that the proposed modeling and solution approach has the potential to generate significant cost savings.