Formulations and branch-and-cut algorithms for multi-product multi-vehicle production routing problems with startup cost. (15th May 2018)

• Record Type: Journal Article
• Authors: Qiu, Yuzhuo; Wang, Liang; Xu, Xiaoling; Fang, Xuanjing; Pardalos, Panos M.
• Is Part Of: Expert systems with applications. Volume 98(2018)
• Page Start: 1
• Page End: 10
• Publication Date: 2018-05-15
• Subjects: Routing -- Production planning -- Branch-and-cut -- Generalized (l, S) inequalities; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.01.006
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: MILP models for multi-product multi-vehicle production routing problems with startup. Branch-and-cut algorithm with relax-and-fix heuristic. Big-bucket versus small-bucket formulation. Comparison with multi-product multi-vehicle inventory routing problems. Case study for multi-product multi-vehicle production routing problems with startup. Abstract: In multi-product multi-vehicle production routing problems (MMPRPs), it is necessary to accurately model the capacity utilization of multiple products to obtain feasible production plans. Thus, start-up variables are required to model the capacity consumed or cost incurred when a machine starts a production batch, or when a machine switches from one product to another. In this work, we present a mixed integer linear programming model of the MMPRP with the startup cost (MMPRPSC), which is an extension of the single-item multi-vehicle production routing problem. It also generalizes the multi-item multi-vehicle inventory routing problems by incorporating production decisions. This formulation is tightened with three families of valid inequalities in which the generalized ( l, S ) inequalities are used in these problem settings for the first time. Using the formulation and valid inequalities, we implement a branch-and-cut algorithm for the solution of the MMPRPSC. Computational experiments also confirm the effectiveness of the valid inequalities. The computational results of a case study show a 15% percent decrease in the total cost.