Improved Benders-and-Price Algorithm for the Multi-Product Assembly Routing Problem with Time Windows : A Domain Decomposition Strategy for the Benders-Master Model

Despite the various industrial applications integrating inbound transportation, production, and inventory, only single-product studies have been conducted addressing the related production and inventory routing problems simultaneously. To meet the optimization requirements of many-to-one assembly systems comprising a plant and multiple suppliers, the multi-product assembly routing problem with time windows (MPARPTW) is investigated in this study. Besides optimizing the assembly of different types of products in a plant to satisfy the periodic market demand within a specific planning horizon, MPARPTW factors in the vehicle routes for collecting many components from suppliers to meet the inventory requirements that are imposed by the production. The MPARPTW was formulated as a mixed-integer linear programming (MILP) model to minimize the setup, production, transportation, and inventory costs. The model was solved using an improved Benders-and-Price algorithm that combines Benders decomposition and the branch-and-price algorithm. The MPARPTW model was decomposed into a lot-sizing Benders-master (BM) model and a vehicle-routing Benders-sub (BS) model. A domain decomposition strategy is developed in this study to further decompose the BM model, thereby generating Benders cuts efficiently and accelerating convergence speed. The numerical experiments demonstrated the significance of the proposed model and algorithm in providing support to plant managers in making decisions or determining plant investment directions. Moreover, the effectiveness and generality of the domain decomposition strategy are also validated