(442b) A Branch-and-Cut Algorithm for Continuous-Time Inventory Routing Problems

The Inventory Routing Problem (IRP) integrates inventory management, vehicle routing and delivery-scheduling decisions [1], and is thus of great interest for both academic research and industrial applications. The IRP arises in the context of vendor-managed inventory, where a supplier makes the replenishment decisions for products delivered to its customers. This is often a win-win strategy for both suppliers and customers: suppliers can coordinate shipment made to customers so as to save distribution costs, while customers can benefit by avoiding efforts for explicit inventory control. The IRP is very challenging because three types of decisions for suppliers have to be made simultaneously: (i) when to serve a given customer, (ii) how much to deliver to a customer when the latter is served, and (iii) how to combine customers into vehicle routes [1].

There are two main variants of IRP, namely discrete-time and continuous-time. The discrete-time IRP first discretizes a given time horizon into multiple time periods and then enforces inventory constraints only at the beginning/end of each time period. In contrast, the continuous-time IRP (CIRP) considers inventory in continuous time and requires that inventory constraints are satisfied at any point in time within the horizon. In the literature, the discrete-time IRP has been extensively studied [2][3][4]. The most successful approach for solving discrete-time IRP is presented in [5], where the authors propose a branch-price-and-cut algorithm, solving to optimality benchmark instances with up to 50 customers and up to 5 vehicles. However, this approach cannot be easily generalized to the continuous-time IRP due to complications from having to model features like continuous arrival time, multiple vehicle trips, multiple customer visits, etc.

The CIRP, notwithstanding its significance, has received very little attention in the literature. The work of [6] considered the IRP with driver rest constraints and decomposed it into an upper-level routing problem and a lower-level continuous-time scheduling problem. Another approach was put forth in the work of [7], where the authors proposed a dynamic discretization discovery (DDD) algorithm. The novelty in the DDD approach is that it discovers exactly which times are needed to obtain an optimal, continuous-time solution by solving a sequence of small integer programs. In this work, we model the arrival times at customers as continuous variables and manage the inventory level in continuous time. Based on this, we then propose a novel mixed integer linear programming formulation for the CIRP. We also adapt the well-known subtour elimination constraints (SEC), fractional capacity inequalities (FCI), and rounded capacity inequalities (RCI) into our context to further strengthen the linear relaxation.

We conduct computational studies on a comprehensive suite of 90 benchmark instances [7]. These instances include 5 to 15 customers and 3 to 13 vehicles. Multiple visits at customers and multiple trips for a vehicle are allowed. We assess the effect of strengthening cuts (SEC, FCI, and RCI) on the solution process. We also compare our algorithm’s performance against the DDD approach to demonstrate the effectiveness of our proposed algorithm.

References:

[1] Coelho, L.C., Cordeau, J.F. and Laporte, G., 2013. Thirty years of inventory routing. Transportation Science, 48(1), pp.1-19.

[2] Archetti, C., Bertazzi, L., Laporte, G. and Speranza, M.G., 2007. A branch-and-cut algorithm for a vendor-managed inventory-routing problem. Transportation science, 41(3), pp.382-391.

[3] Coelho, L.C. and Laporte, G., 2013. The exact solution of several classes of inventory-routing problems. Computers & Operations Research, 40(2), pp.558-565.

[4] Coelho, L.C. and Laporte, G., 2014. Improved solutions for inventory-routing problems through valid inequalities and input ordering. International Journal of Production Economics, 155, pp.391-397.

[5] Desaulniers, G., Rakke, J.G. and Coelho, L.C., 2015. A branch-price-and-cut algorithm for the inventory-routing problem. Transportation Science, 50(3), pp.1060-1076.

[6] Dong, Y., Maravelias, C.T., Pinto, J.M. and Sundaramoorthy, A., 2017. Solution methods for vehicle-based inventory routing problems. Computers & Chemical Engineering, 101, pp.259-278.

[7] Lagos, F., Boland, N., Savelsbergh, M., 2018. The continuous time inventory routing problem. http://www.optimization-online.org/DB_HTML/2018/01/6439.html, accessed on April 10, 2019.