一种求解库存路径问题的拉格朗日松弛法  

A Lagrangian relaxation method for Inventory Routing Problem

作　　者：赵媛媛 段倩倩 ZHAO Yuanyuan;DUAN Qianqian(School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China)

机构地区：[1]上海工程技术大学电子电气工程学院,上海201620

出　　处：《智能计算机与应用》2021年第7期185-190,共6页Intelligent Computer and Applications

基　　金：国家重点研发计划(SQ2019YFB170208);上海市青年科技英才扬帆计划(17YF1428100)。

摘　　要：为了快速解决库存路径问题(Inventory Routing Problem,IRP),提出用松弛与分解结合的拉格朗日松弛算法进行求解。首先对问题进行了详细描述和有效假设,在此基础上,以系统总成本为优化目标,建立了混合整数规划模型。针对此模型,本文先采用拉格朗日松弛算法将IRP分解为2个独立的子问题,然后分别用遗传算法和次梯度算法进行求解,最后通过案例实验表明,与直接求解对偶问题和智能优化算法相比,本文分解算法能在较短的时间内构造一个配送方案,且所求解的质量更好。In order to quickly solve the Inventory Routing Problem,a Lagrangian relaxation algorithm combining relaxation and decomposition is proposed.In the research,the problem is described in detail and valid assumptions of the problem are made.On this basis,the mixed integer programming model is established with the total cost of the system as the optimization goal.According to this model,this paper first uses the Lagrangian relaxation algorithm to decompose IRP into two independent sub-problems,and then Genetic Algorithm and sub-gradient algorithm are used for solving respectively,finally the case experiment result shows that compared with the direct solving the dual problem and intelligent optimization algorithm,the decomposition algorithm in this paper can construct a distribution plan in a shorter time,and the quality of the solution is better.

关 键 词：库存路径问题 拉格朗日松弛 遗传算法 次梯度算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]