Shipment Consolidation with Multiple Shipping Methods Under Nonlinear Cost Structures

We study a shipment consolidation problem commonly faced by companies that outsource logistics operations and operate in a commit-to-delivery mode. It involves delivering a given set of orders to their destinations by their committed due times using multiple shipping methods at the minimum total shipping and inventory cost. The shipping cost is generally nonlinear in shipping quantity and can be represented by a subadditive piecewise linear function. We investigate two shipping scenarios, one involving long-haul shipping only and the other involving joint long-haul and short-haul shipping. We develop analytical results and solution algorithms for the shipment consolidation problem under each shipping scenario. The problem under the first shipping scenario is shown to be strongly N P -hard. We find that a simple policy, called the First-Due-First-Delivered (FDFD) policy, which assigns orders with earlier delivery due times to shipping methods with earlier destination arrival times, is very effective. This policy enables us to develop a polynomial time algorithm, which not only solves the problem under the concave shipping cost structure optimally but also achieves a performance guarantee of 2 for the problem under the general subadditive shipping cost structure. For the problem under the second shipping scenario, we extend the FDFD policy for long-haul shipping and derive another policy, called the No-Wait policy, for short-haul shipping. We use these policies to develop a polynomial time algorithm and analyze its performance guarantee. Our computational experiments show that the algorithm significantly outperforms a commercial optimization solver, and its performance is robust across different parameter settings that reflect various practical situations.