The air-cargo consolidation problem with pivot weight: Models and solution methods

In the international air cargo business, freight is usually consolidated into containers, called Unit Load Devices (ULDs). The transportation charge of a ULD depends on whether the total weight exceeds a certain threshold, called the pivot weight. If the total load tendered by a freight forwarder is less than the pivot weight, it gets charged at the under-pivot rate. Any portion of the load that exceeds the pivot weight is charged at the over-pivot rate. This scheme is adopted for safety reasons to avoid the overloading of ULDs. We formulate a mixed integer program, and propose four solution methodologies for the air-cargo consolidation problem under the pivot-weight scheme (ACPW). These are exact solution approaches based on branch-and-price, a best-fit decreasing loading heuristic, and two extended local branching heuristics (a multi-local tree search and a relaxation-induced neighborhood search). The local branching heuristic with relaxation-induced neighborhood search is found to outperform other approaches in terms of solution quality and computational time. Problems with up to 400 shipments and 80 containers are solved to within 3.4% of optimality in less than 20 min.