Groupe d’études et de recherche en analyse des décisions


Benders Decomposition for Production Routing under Demand Uncertainty

, et

The production routing problem (PRP) concerns the production and distribution of a single product from a production plant to multiple customers using capacitated vehicles in a discrete and finite time horizon. The PRP is a generalization of the inventory routing problem (IRP) obtained by incorporating production lot-sizing decisions. In this study, we consider the stochastic PRP with demand uncertainty in a two-stage decision process. The decisions in the first stage include production setups and customer visit schedules, while the production and delivery quantities are determined in the second stage. The objective is to jointly minimize the expected total production, inventory, distribution and routing costs. We develop exact solution approaches based on Benders decomposition together with several enhancements for this problem. Two different Benders reformulation schemes are proposed. Furthermore, we compare a standard implementation of the Benders algorithm to one that integrates the Benders cuts within a branch-and-cut framework. This latter implementation is called branch-and-Benders-cut (BBC) and uses only one enumeration tree for the Benders master problem. The Benders master is further enhanced with lower bound lifting inequalities, scenario group cuts and Pareto-optimal cuts. The best version of the Benders decomposition algorithm provides superior results to a branch-and-cut algorithm on the standard formulation when solving a large number of scenarios while the performance of the branch-and-cut algorithm heavily relies on the CPLEX cuts. We further exploit the reoptimization capability of the Benders approach in two stochastic settings, namely, a sample average approximation scheme to handle a large number of scenarios, and a rolling horizon framework for a dynamic and stochastic variant of the PRP. The results show that the computing time of the Benders algorithm using reoptimization is reduced by approximately 40-50% and more than 80% compared to the Benders algorithm without reoptimization and the branch-and-cut algorithm, respectively.

, 30 pages