The inventory-routing problem (IRP) integrates two well-studied problems, namely, inventory management and vehicle routing. Given a set of customers to service over a multiperiod horizon, the IRP consists of determining when to visit each customer, which quantity to deliver in each visit, and how to combine the visits in each period into feasible routes such that the total routing and inventory costs are minimized. In this paper, we propose an innovative mathematical formulation for the IRP and develop a state-of-the-art branch-price-and-cut algorithm for solving it. This algorithm incorporates known and new families of valid inequalities, including an adaptation of the well-known capacity inequalities, as well as an ad hoc labeling algorithm for solving the column generation subproblems. Through extensive computational experiments on a widely used set of 640 benchmark instances involving between two and five vehicles, we show that our branch-price-and-cut algorithm clearly outperforms a state-of-the-art branch-and-cut algorithm on the instances with four and five vehicles. In this instance set, 238 were still open before this work and we proved optimality for 54 of them.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem



    Published in:

    Transportation science ; 50 , 3 ; 1060-1076


    Publication date :

    2016




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English



    Classification :

    Local classification TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



    A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem

    Desaulniers, Guy / Rakke, Jørgen G. / Coelho, Leandro C. | British Library Online Contents | 2016




    A Branch-and-Price Method for a Liquefied Natural Gas Inventory Routing Problem

    Gronhaug, R. / Christiansen, M. / Desaulniers, G. et al. | British Library Online Contents | 2010


    A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem

    Archetti, C. / Bertazzi, L. / Laporte, G. et al. | British Library Online Contents | 2007