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

G-2021-52

The consistent production routing problem

, et

This paper introduces the consistent production routing problem in a setting with multiple plants and products. The problem consists in finding minimum-cost production-routing plans that also meet specific consistency requirements. In our context, consistency is defined as the degree to which some specified features of the solution remain invariant over time. We consider four forms of consistency, namely: driver, source, product and plant consistency. For each of these consistency requirements, there is a target maximum value defining the decision-maker's tolerance to deviations from a perfectly consistent solution. These targets are enforced as soft constraints whose violations need to be minimized when optimizing the integrated production and routing plan. We present a mathematical formulation for the problem and an exact branch-and-cut algorithm, enhanced with valid inequalities and specific branching priorities. We also propose a heuristic solution method based on iterated local search and several mathematical programming components. Experiments on a large benchmark set of newly introduced instances show that the enhancements substantially improve the performance of the exact algorithm and that the heuristic method performs robustly for production routing problems with different consistency requirements as well as for standard versions of the problem. We also analyze the cost-consistency trade-off of the solutions, confirming that it is possible to impose consistency without excessively increasing the cost. The results also reveal the impact of the first time period when optimizing and measuring the consistency features we study.

, 33 pages