Branch-price-and-cut for the production routing problem with time windows
针对带时间窗的生产路径问题，提出分支定价切割算法，在测试中优于现有方法，并解决了62个此前未解的基准实例。
Production routing problems (PRPs) are integrated planning problems that combine vehicle routing and lot-sizing decisions. Given a discrete finite time horizon and a set of customers, the basic PRP consists of deciding for each period if and how much to produce, the inventories at the supplier and the customers, and the vehicle routes. The latter include the decisions on which customers to serve and the quantities delivered. The objective is to minimize the total cost over the planning horizon consisting of production, inventory, and routing cost. In this paper, we consider the PRP with time windows (PRPTW) and propose a branch-price-and-cut (BPC) algorithm for its solution. The BPC relies on a path-based formulation that explicitly specifies which demands are satisfied by which deliveries and employs several families of valid inequalities. The performance of the BPC is assessed in an extensive computational study on existing benchmark instances for the related inventory routing problem with time windows (IRPTW) and newly created instances for the PRPTW. Our BPC outperforms the current state-of-the-art BPC for the IRPTW, closing 62 previously open instances. Finally, we derive managerial insights from our PRPTW instances.