学习型变邻域搜索算法求解运输-装配协同优化问题

Learning Variable Neighborhood Search Algorithm for Transportation-assembly Collaborative Optimization Problem

针对运输-装配协同优化问题,建立其整数规划模型,提出一种融合分解策略的学习型变邻域搜索算法(learning variable neighborhood search with decomposition strategy,LVNS_DS)对其求解。为降低问题的求解难度,设计一种分解策略将原问题分解为路径规划问题和装配线平衡问题;应用LVNS算法对2个子问题进行求解;通过合并子问题解可得原问题的完整解。相比常规VNS算法,LVNS算法依据邻域动作概率值来转换邻域结构,依据邻域动作产生的贡献来动态地更新其概率值,LVNS算法能以较大的概率值选择适于当前搜索阶段的邻域动作,从而易于找到子问题的优质解。通过不同规模算例的仿真实验,验证了运输-装配协同优化的有效性和LVNS_DS算法的有效性。

Aiming at transportation-assembly collaborative optimization problems,an integer programming model is established,and a learning variable neighborhood search with decomposition strategy(LVNS_DS) is proposed.To reduce the difficulty of solving the problem,a decomposition strategy is designed to decompose the original problem into a path planning problem and an assembly line balance problem.LVNS is used to solve the two subproblems,and the subproblem solutions are merged to obtain the complete solution of the original problem.Compared with the conventional VNS,LVNS transforms the neighborhood structure according to the neighborhood action probability value,and dynamically updates the probability value according to the contribution of neighborhood action.Therefore,LVNS algorithm can select the neighborhood action suitable for the current search stage with high probability value to easily find the high-quality solution of the subproblem.Through the simulation experiments of different scale examples,the importance of transportation assembly collaborative optimization and the effectiveness of LVNS_DS are verified.