Formulations and Branch-and-Cut Algorithms for Production Routing Problems with Time Windows

Abstract

This paper presents a mixed-integer optimization framework for incorporating time windows into production routing problems. This problem is a generalization of vehicle routing, inventory routing, and lot-sizing problems, and formulated as a mixed interlinear program-ming problem. An exact method within a branch-and-cut framework is developed to solve the model. Several families of valid cuts are adapted and a hybrid heuristic to obtain a good upper bound is also developed. The newly proposed(l, S)inequalities link production variables with inventory variables. From the computational results, the effectiveness of the valid inequalities is proved. The newly proposed(l, S)inequalities outperform previously related inequalities. The numerical results for the case study also show that the total cost results in an 11.6% decrease over a heuristic solution after applying the proposed model and algorithm