Routing models and solution procedures for regional Less-Than-Truckload operations

Less-Than-Truckload (LTL) carriers are required on a daily basis to solve Intra-Group Line-Haul (IGLH) problems. IGLH problems require the determination of routes to service required pickups and deliveries (i.e., 28-foot trailers) at End-Of-Line (EOL) terminals. The objective is to minimize total costs, given that tractors are able to simultaneously transport two trailers and that all pickups and deliveries must be accomplished. In this paper, an approximate IGLH solution approach is presented. Given pickup and delivery requirements together with relevant distance data, a matching network is constructed in which nodes correspond to sets of pickups and deliveries and links to routes. A minimum weight non-bipartite matching algorithm is solved over this network and the result is an IGLH solution. This solution is improved by again applying a minimum weight matching algorithm, this time to a matching network in which nodes correspond to routes and links to improved routes. Finally, the routes are sequences so as to achieve balance at each EOL terminal (i.e., empty trailers must be delivered or picked up as necessary to ensure that each EOL terminal has the same number of pickups and deliveries) and to minimize the inventory of empty trailers. The new IGLH solution procedure is tested on randomly generated data and on data provided by a large LTL carrier. Computational tests show that near-optimal solutions are generated rapidly.