A branch-price-and-cut algorithm for the inventory routing problem with time windows
Gizem Ozbaygin  1@  , Esra Koca  2@  , Hande Yaman  3@  
1 : Faculty of Engineering and Natural Sciences, Sabanci University
Istanbul -  Turkey
2 : Faculty of Engineering and Natural Sciences, Sabanci University
Istanbul -  Turkey
3 : Faculty of Economics and Business, KU Leuven
Leuven -  Belgium

The inventory routing problem is an integrated inventory and transportation planning problem that jointly determines the replenishment plans of the retailers and routing decisions of the supplier. Although the supplier is the central decision maker in such a system, the retailer should have some power on manipulating the delivery times in practice (consider, e.g., the food distribution of the companies to the supermarket chains). With this motivation, we study the inventory routing problem with time windows where the retailers can be visited only within specific time intervals. We develop a mathematical model involving both arc and route-based variables. Since the number of routes and the number of capacity constraints in our model are exponentially many, we employ column and cut generation to solve the LP relaxation at each node of the branch-and-bound tree, i.e., we propose and devise a branch-price-and-cut algorithm to solve the problem. To improve our formulation, we use some valid inequalities originally derived for the lot sizing problem. We also adopt several techniques to enhance the performance of our algorithm such as heuristic pricing, early pruning, and hierarchical branching. We generate a set of test problems based on the well-known Solomon benchmark instances, and perform computational experiments to evaluate the benefits of our algorithmic enhancements as well as to provide insights into the effect of various parameter choices on the difficulty of the problem.


Online user: 1 RSS Feed