An integer programming model and directed Steiner-forest based heuristic for routing less-than-truckload freight

Less-than-truckload (LTL) freight transportation is a vital part of Canada’s economy, with revenues running into billions of dollars and a cascading impact on many other industries. LTL operators have to deal with large volumes of shipments and uncertainty in demand patterns. In an industry that already has low profit margins, it is therefore vitally important to make good quality routing decisions without expending a lot of time. The optimization of such LTL freight networks results in large scale mathematical programming problems. In this paper, we present a novel Integer Linear Programming (ILP) formulation and heuristics for routing LTL freight. Experiments in collaboration with our industry partner indicate that our proposals can significantly lower routing costs for Canadian LTL operators. In addition, our approach can be useful for generating load plans on larger American LTL networks.