Inventory routing with heterogeneous vehicles and hazardous material backhauling
针对加拿大魁北克水电公司的实际案例，研究多商品配送与危险品回程的库存路径问题，提出分支切割算法和两阶段分解启发式算法，在合成算例中平均最优性差距低于2%，并证明集成回程和拆分配送可降低21%的运输成本。
• 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.