  Multiple product attributes like dimensions, weight, fragility, liquid
content etc. determine the package type used by e-commerce companies to ship
products. Sub-optimal package types lead to damaged shipments, incurring huge
damage related costs and adversely impacting the company's reputation for safe
delivery. Items can be shipped in more protective packages to reduce damage
costs, however this increases the shipment costs due to expensive packaging and
higher transportation costs. In this work, we propose a multi-stage approach
that trades-off between shipment and damage costs for each product, and
accurately assigns the optimal package type using a scalable, computationally
efficient linear time algorithm. A simple binary search algorithm is presented
to find the hyper-parameter that balances between the shipment and damage
costs. Our approach when applied to choosing package type for Amazon shipments,
leads to significant cost savings of tens of millions of dollars in emerging
marketplaces, by decreasing both the overall shipment cost and the number of
in-transit damages. Our algorithm is live and deployed in the production system
where, package types for more than 130,000 products have been modified based on
the model's recommendation, realizing a reduction in damage rate of 24%.
