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

Author/Creator ORCID

Date

2018-01-26

Department

Information System and Decision Sciences

Program

Information System and Decision Sciences

Citation of Original Publication

Qiu, Y., Wang, L., Fang, X., Pardalos, P. M., & Goldengorin, B. (2018). Formulations and Branch-and-Cut Algorithms for Production Routing Problems with Time Windows. Transportmetrica A: Transport Science, 14(8), 669-690. https://doi.org/10.1080/23249935.2018.142715

Rights

Public Domain Mark 1.0

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