A novel robust decomposition algorithm for a profit-oriented production routing problem with backordering, uncertain prices, and service level constraints
针对生产路径问题，首次提出以利润最大化为目标、允许取消或延期订单并考虑价格不确定性的鲁棒模型，设计分解算法求解，并通过计算测试验证算法效果。
Abstract The Production Routing Problem (PRP) seeks optimal production and distribution planning that minimises costs and fulfils customer orders. Yet, existing literature often overlooks the potential impact on profitability. Achieving optimal profit does not necessarily imply meeting all customer orders. The cost-to-profit ratio should be considered when serving customer orders, as there are circumstances where it might be more profitable to cancel or backorder certain orders. Thus, this paper proposes, for the first time, a novel extension of PRP that maximises profit where demand is price-sensitive and allows order cancellation and backorders under service level targets. From on-field observations, price is inherently subject to uncertainty; thus, we propose a robust mathematical model for the problem that optimises the worst-case profit. To solve the problem, the paper proposes a decomposition algorithm that splits the problem into a master problem and a set of subproblems, enhanced by valid inequalities and warming up lower bounds to alleviate the model complexity. Through a series of computational tests, we prove the ability of the proposed algorithm to tighten the optimality gaps and alleviate computational time. An additional economic study is conducted to investigate how parameter variation affects profit and how sensitive it is to service level targets.