Hexaly establishes new records for the Inventory Routing Problem (IRP)

The Inventory Routing Problem (IRP) is a variant of the Vehicle Routing Problem (VRP) with inventory management. A product, generally liquid or fluid, has to be shipped from a supplier to several customers over a given time horizon. Each customer defines a maximum inventory level. The supplier monitors each customer’s inventory and determines its replenishment policy, guaranteeing that no stockout occurs at the customer (vendor-managed inventory policy). Shipments from the supplier to the customers are performed by a vehicle of a given capacity. Hexaly improves the literature’s best known solution for 4 out of 11 instances of the Inventory Routing Problem.

Input data

We focus on the real-life Inventory Routing Problem (IRP) instances provided for the 2016 ROADEF/EURO Challenge. This challenge was organized by the French Operational Research and Decision Support Society (ROADEF) and the European Operational Research Society (EURO) in collaboration with the leading industrial and medical gas company Air Liquide. The number of customers ranges from 12 to 99, and the time horizon goes up to 840 hours (35 days). The instances are available on the Challenge website.

New records for the Inventory Routing Problem (IRP)

We compare the solutions provided by Hexaly after 30 minutes with the Challenge’s best known solutions, also established with a running time limit of 30 minutes. We ran the solver on a computer equipped with an Intel i7-11800H (8 cores, 2.3 GHz, 16 threads) and 32GB RAM to obtain these results.

Hexaly improves the best known solution on 36% of Inventory Routing Problem (IRP) instances from the Challenge (4 out of 11), with improvements up to 3%. The table below presents Hexaly’s results compared to the best known solutions.

Customers Horizon (h) Best known Hexaly Gap
V_1.1 12 720 0.027466 0.027485 0.1%
V_1.2 12 720 0.027304 0.027477 0.6%
V_1.3 53 240 0.013279 0.013505 1.7%
V_1.4 64 240 0.015495 0.015464 -0.2%
V_1.5 54 240 0.011877 0.011841 -0.3%
V_1.6 54 840 0.012812 0.012880 0.5%
V_1.7 99 240 0.01289 0.012621 -2.1%
V_1.8 99 82 0.007756 0.007756 0.0%
V_1.9 99 840 0.015279 0.015815 3.5%
V_1.10 89 240 0.018941 0.018371 -3.0%
V_1.11 89 840 0.028666 0.028957 1.0%
Gaps to the literature’s best known solutions.

Are you interested in trying out Hexaly? Get free trial licenses here. In the meantime, feel free to contact us; we will gladly discuss your optimization problems.

Share