Improved branch-and-cut algorithm for the inventory routing problem
Jørgen Skålnes  1, *@  , Magnus Stålhane  1@  , Henrik Andersson  1@  , Guy Desaulniers  2@  
1 : Norwegian University of Science and Technology [Trondheim]  (NTNU)  -  Website
NO-7491 Trondheim -  Norway
2 : Groupe d'études et de recherche en analyse des décisions  (GERAD)  -  Website
HEC Montréal 3000, chemin de la Côte-Sainte-Catherine Montréal (Québec) Canada H3T 2A7 -  Canada
* : Corresponding author

The inventory routing problem is a problem that arises in a vendor managed inventory context. Each customer has an inventory with a maximum holding capacity and a periodic demand. The decision maker has to make sure the customers have enough products in their inventories to satisfy demand in each time period of the planning horizon. Thus, the decision maker has to decide which customers to serve in which time periods, how much to deliver of a product once a customer is visited and how to route the fleet of vehicles in order to minimize transportation cost and inventory holding cost. We propose an improved branch-and-cut algorithm combining the current state-of-the-art valid inequalities with new families of valid inequalities using the concept of delivery patterns. A delivery pattern contains information about which periods a customer is visited. Based on this we can calculate tighter upper and lower bounds on the quantity delivered to a customer given a certain delivery pattern. Preliminary results show that the new algorithm increases the lower bound considerably and on average reduces the solution times. A full computational study on how the different valid inequalities impact the lower bounds and solution times will be presented.

Online user: 1 RSS Feed