An exact algorithm for a multi-plant production routing problem

Purpose Simultaneous decision-making of production, distribution and routing in a supply chain with wide applications in the real world leads to more productivity and lower costs. The purpose of this study is to address a production routing problem (PRP) by considering multiple plants and products under the maximum-level policy, as well as a homogenous transportation fleet over a defined planning horizon. Design/methodology/approach To address this challenge, the authors begin by reformulating and strengthening the existing mixed-integer linear programming model. This is achieved by incorporating valid inequalities and reducing the number of decision variables, thereby enhancing the model’s efficiency. To mathematically validate our reinforced model, the authors perform computational experiments on single-product, multi-vehicle PRP benchmarks – benchmarks that have been previously solved using the Branch-and-Cut algorithm. Furthermore, because of the NP-hard nature of the multi-plant multi-product multi-vehicle PRP (MMMPRP) model, the authors develop an exact decomposition algorithm named logic-based benders decomposition to effectively solve a new, compatible data set. Findings The benchmark experiments demonstrate that the modified model, which incorporates transportation constraints based on network flows, is capable of obtaining optimal or near-optimal solutions for large instances, even with up to 50 customers, in a reasonable amount of time. Overall, it performs approximately 8.4 times faster than the Branch-and-Cut algorithm and finds improved lower bounds for nine-period instances. In comparison, numerical experiments conducted on MMMPRP instances show that the logic-based benders decomposition algorithm outperforms the modified model, particularly for larger instances. A sensitivity analysis aimed at identifying more effective parameters reveals that the number of plants and products with only small fluctuations have the most and least impact, respectively, on the complexity of the MMMPRP model. Originality/value This model and solution approach are effective for supply chains in sectors such as food, medicine, various merchandise, postal services and goods delivery, aiming to minimize the total costs of setup, production, inventory and routing.