定位路线与库存组合优化问题模型和算法研究

《定位路线与库存组合优化问题模型和算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、长安人学顾t：学位论文都比较少的情况，并且用精确算法来求解问题所需时间较长。所以精确算法在实际情况下很难得到应用，对于这方面的研究有减少的趋势。2)LRPIh]题的启发式算法由于LAP问题和VRPf司题都被证实为NP--hard(non-deterministicpolynomialhard)问题，所以LRP问题也属于NP—hard问题，对于这类问题其核心在于建模和算法求解，一般情况下用精确算法难于解决。所以引入启发式算法，启发式算法的思想是将问题分解为多个子问题，然后依次应用启发式算法或精确算法进行求解。求解定位一路线问题的启发式算法可分为以下四种：①先解决定位一配给问题，再解决运输路线安排

2、问题：②先解决运输路线安排问题，再解决定位一配给问题；③费用降低／插值算法；④路线扩展／交换算法。1．2．2．2IRP问题分类对IRP模型按照计划的长度和需求的类型可以分为以下几类川：(1)单同IRP模型。计划期长度仅为一天(又可分为确定需求或随机两种)；(2)多日IRP模型。计划期长度超过一天，但不超过一个季度或一年(又可分为确定需求或随机两种)；(3)无限期IRP模型，也称为永久路线问题。即一旦确定了车辆的巡回路线，则在以后的配送服务中，车辆的行驶路线不会发生变化。对于定位一路线一库存问题由于国内外研究才刚刚起步，研究文献较少，目前还没有明确的分类标准和分类方法。1．3国内外研究动态1．3

3、．1国外研究现状国外近年来对于LRP问题的研究已经取得了一些成果，目前主要集中在两个方面：一是LRP问题的求解算法研究；二是比较复杂的LRP模型研究，使模型在规模和复杂性方面更接近于实际问题，有利于运用模型来解决实际问题。Tuzun等【8J提出了两阶段禁忌搜索启发式算法求解U之P问题，其算法结构能对解空间进行有效搜索，但其模型未考虑设施容量约束。YupoChan和WilliamB．Carter等【9】人运J羊JSFC(spacefillingcurse)法来求解多设施、多运输车辆的随机型U乇P模型。wu等【10】采5第一章绪论用两阶段模拟退火启发式算法求解具有多种类型车辆且数量给定的LRP问题

4、。Bouhafs，Lyamine111】用模拟退火和蚁群组合算法求解了两阶段定位路线问题。Lin，C．K．Y．和Kwok，R．C．W．[121对模拟退火算法和禁忌搜索算法求解定位路线问题进行了比较。S．C．Liu，S．B．ke【5J建立了考虑库存策略的多站点定位路线问题的数学模型，并用两阶段启发式解法进行了求解。Uu，S．C．和Lin，C．C．113j用禁忌搜索和模拟退火混合启发式算法求解了定位路线和库存组合优化问题。1．3．2国内研究现状国内关于LRP问题的研究文献较少，只有少数几位学者对该类问题进行了研究。汪寿阳、赵秋红是最早在国内开始LRP问题研究的学者，文献114]详细介绍了国外对于集

5、成物流管理系统中LRP问题的研究进展，分析了LRP的主要内容和特征，提出有关求解问题的算法分类，并对以后该领域的研究方向提出了几点建议。张潜、高立群【15l等从算法优化的角度出发，对LRP问题中的定位配给、运输车辆路线安排、定位一运输路线安排三类问题的具体优化方法进行了分析和比较，并在此基础之上提出两阶段启发式算法来求解LRP问题。张长星116J等用遗传算法求解了定位一运输路线安排问题。张潜、高立群【17】等提出了基于最小包络聚类分析及带有控制开关的遗传算法的两阶段启发式算法来解决LRP问题。邱晗光、张旭梅118l运用基于遗传算法、模拟退火算法的改进粒子群算法，对一个开放式定位一运输路线问题进

6、行了求解。但是由于这些文献都没有考虑设施的容量约束，故其算法结构无法实现两阶段的协调。国内对库存路线问题的研究也刚刚起步。袁庆达【19】介绍了多路径的物流配送系统，从决策的三个层次即战略、战术和作业层次，扩展了已有研究的决策范围，构造了描述此类问题特征的数学模型和有效的启发式算法。叶志孥120】针对客户需求小批量、多批次配送的特点，建了VMI模式下的供应商库存补充和配送整合策略优化模型。李建⋯对城市物流系统中随机需求的库存路线问题用遗传模拟退火算法进行了求解。赵达，李军(2006)11】等研究了随机需求的IRP问题，提出了一种基于马尔科夫决策过程与修J下的C—w节约算法的启发式分解算法，并给出

7、了实例计算。汪寿阳在文献[141中已经提出了多方物流运作的水平方向的集成即考虑库存的定位路线问题是未来研究方向之一，但通过检索到目酊国内还没有关于这方面的研究文献。综上所述，目自订在国内外文献中，能有效求解大规模LRP问题的启发式算法较少，尤其是考虑设施容量和车辆容量约束的文献更少。国内还没有关于定位一路线一库存问6长安人学硕I：学位论文题的研究。1．4本文主要研究内容本文研究了定位一路线问题的数