We consider a large-scale multi-depot multi-commodity Inventory Routing Problem (IRP) to model the packaging return logistics of a major European car manufacturer. No algorithm is known to properly scale to our context. We propose a Large Neighborhood Search (LNS) based on common routing neighborhoods and two new ones: the reinsertion of a customer and a commodity in the IRP solution. We also try to bypass the heavy computations of the LNS leveraging recent ideas in Machine Learning for Operations Research in structured prediction.