International airfreight forwarders are faced with the problem of consolidating shipments for effcient transportation by airline carriers. The use of standard unit loading devices (ULDs) is a solution adopted by the airfreight industry to speed up cargo loading, increase safety, and protect cargo. We study the airfreight consolidation problem from the forwarders perspective where a decision on the number of ULDs used and the assignment of shipments to ULDs is optimized. The cost of using a ULD consists of a fixed charge and depends on the weight of the cargo it contains. A ULD is charged at an under-pivot rate if the total weight is below a threshold limit, called the pivot-weight. Additional weight is charged at the over-pivot rate. We propose a solution methodology based on Lagrangian relaxation that is capable of providing high quality solutions in reasonable computational times. Besides, a high-quality lower bound, we propose four heuristics to generate feasible solutions, all based on the solution of the subproblems. The first, takes the solution of one of the subproblems and solves a restricted version of the original problem (LagHeur). Although, it yields high quality, almost optimal solutions, this approach takes long computational time. As a remedy, we restrict the solution to the root node and collect the best feasible solution that is generated (LagHeur0). The other two heuristics are a heuristic based on solving two knapsack problems (2knap) and a best-fit greedy heuristic (best-fit). Problems with up to 80 ULDs and 400 shipments are solved to within an average of 1%, 2%, 2% of optimality in less than 5s, 10s and 400s by best-fit, 2knap and LagHeur0, respectively.
Supervisor: Samir Elhedhli