Inventory routing with heterogeneous vehicles and hazardous material backhauling

• Inventory routing problem with delivery and backhauling. • Multi-depot, multi-commodity, heterogeneous vehicles, split delivery. • Branch-and-cut and matheuristic algorithms for large-size instances. • Case study at Hydro-Québec to demonstrate the performance of the model. Efficient coordination of distribution and backhauling is a critical challenge for many industries. This paper is motivated by a real-world case study at Hydro-Québec, a large-scale utility company in North America, and introduces an inventory routing problem that integrates inventory management and vehicle routing under several operational constraints. The problem involves distributing multiple commodities to customer sites while backhauling hazardous materials to depots. The objective is to minimize delivery, collection, and inventory holding costs using a fleet of capacitated heterogeneous vehicles, while ensuring that hazardous materials are transported separately from regular delivery commodities. In each period, a customer’s delivery and backhauling can be split and satisfied by multiple vehicles. We propose a mathematical formulation, introduce valid inequalities, and solve the resulting model using a branch-and-cut algorithm. To tackle large-size instances, a two-phase decomposition matheuristic is developed. To highlight the value of split delivery and backhauling, we compare the solutions from our model with those when split delivery is prohibited and when backhauling is optimized independently. In addition, we investigate the order-up-to level policy and the case when stockout is allowed. An extensive numerical study is conducted on synthetic instances to evaluate the performance of the models and solution approaches. The heuristic algorithm solves the synthetic instances in less than two hours with an average optimality gap of less than 2 %. Finally, a case study is conducted on the Hydro-Québec network to demonstrate the real-world applicability of the model and quantify the benefits to the company. Our proposed model reduces the total routing costs by 21 % compared to the case where backhauling is not integrated and split delivery is not allowed.