带软时间窗的需求随机库存-路径问题

《带软时间窗的需求随机库存-路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学硕士学位论文1.5国内外研究现状1.1国内研究现状需求随机，长期计划，硬时间窗限制[5]目前在国内有关库存和运输方面的研究主要是西南交通大学李军教授的论文，他针对随机需求IRP的马氏性、长期性以及随机性的特殊结构将随机需求IRP描述为一个马尔可夫决策过程，以无限期折扣模型收益最大为目标进行优化。运用随机模拟技术对状态转移矩阵进行模拟，从而得到各个客户的配送量，并采用修正的C-W节约算法对有硬时间窗的路径问题进行求解。1.5.2国外研究现状国外对库存-路径问题的研究要早于国内，而且研究文献更为丰富。根据需求的性质

2、、计划期的长度以及时间窗限制的类型可分为以下几类：(1)需求确定，短期计划，无时间窗限制[67]−Dror,Ball和Golden的文献首先给出在计划期内的每一天中每个客户出现缺货的概率、每次配送的运输成本、缺货损失的期望成本，然后计算出使整个期望成本最小的每个客户的最佳库存补货日期t。如果t落在短期计划区间内，则在短期计划内一定要为该客户补货，如果某一客户不在最佳补货日期t补货而是在第t天，则用c表示其引起的未来费用增加值。如果t落在短期计划区外，则用g表示在短期计划内的第t天为客户补货所带来的未来收益增加值。通过c和g

3、可以反映出短期计划决策对长期计划决策的影响。最后使用整数规划的方法首先确定客户补货的日期和提供补货服务的车辆，然后求解一个VRP问题给出每辆车的行驶路线。[8]Chien,Balakrishnan和Wong采用通过信息传递，考虑前一天的优化结果对次日的影响，对于连续几天库存/配送情况进行模拟。假设每个客户的日最大用量已知，则通过送货单位收益和缺货单位损失可以计算日利润，这种方法也正是以日利润最大化为目标的。这种方法将问题描述为整数规划模型，解决如何向客户分配供应的有限5华中科技大学硕士学位论文库存、车辆调度及路线选择问题，

4、并运用拉格朗日对偶上升法(Lagrangeandualascentmethod)解该整数规划。(2)需求确定，长期计划，无时间窗限制[9]Gallego和Simchi-Levi对直接配送方式的长期效果做出了评价，并得出结论:对于所有IRP问题，当存在大量的需求接近或大于一辆货车运输能力的客户时，采用直接配送方式是合理的。这样许多复杂的IRP问题，可以做出合理的选择，得到解决。(3)需求随机，短期计划，无时间窗限制[2]Federgruen和Zipkin所研究的是将单一货物从单个供应方配送到多个客户(One-Many)的IR

5、P问题，其中，供应方的库存有限，计划期长度为一天，并假设客户需求为随机变量，系统总成本既考虑运输费用也考虑了由库存保管费及缺货损失费用构成的库存费用。提出的方法主要是从车辆调度问题(VRP)的优化方法中发展而来的，在建立的非线性整数规划模型中，目标函数是当日的总成本最小；约束条件包括供应商库存能力限制、客户库存能力限制及变量非负等。由于受到库存能力限制并考虑库存成本与缺货成本，并非每天向所有客户送货，为了简化问题，引入一条虚拟路径，所有得不到送货的客户均包括在此路径内。非线性整数规划能够将配送优化问题分解为库存分配问题和旅

6、行商问题，通过前者优化库存成本和缺货成本，后者则优化运输成本。其解法的主要思路是首先确定一个初始可行解，然后通过相互交换不同配送路线中的客户改变条件，反复迭代，不断优化结果。[10]Golden,Assad和Dahl采用启发式算法解决问题，即在充分满足所有客户存货需求的前提下使总成本最小。在这种方法中，定义了“需求迫切性”，即库存能力与实际库存水平之比。首先，分别计算每个客户的需求迫切性，并将之与事先确定的标准(最小值)进行比较，直接排除比值低于该标准的客户。其次，根据需求迫切性与所需送货时间的最高比率，选择客户直接配送。

7、然后，通过反复迭代建立一个大型旅行商问题。其中，全程时间(TMAX)的初始值不得超过配送车辆数量与日工作时间的乘积。在耗时达到此限制或者所有客户需求均己满足之后，不能再向其他客户送货。在6华中科技大学硕士学位论文不允许送货不足的条件下(即只要送货，必须完全满足收货客户的需求)，得到一组可行路径，共同构成最终的优化配送线路；若此条件无法满足，则减少TMAX的值，再使用上述启发式算法。[11]Jaillet等人为了解决周期为两周的IRP问题，引入了滚动周期方法，即规划中以两周为周期，但在实际中，只执行其中第一周的规划。他们采用

8、了与上述Dror等人相似的方法确定对每一客户送货的最佳时间，进而得出为其送货的最佳频率；在规划中，只考虑最佳送货时间在随后两周内的客户，这正是与Dror等人的方法的主要区别。在解决计划期内的客户配送时间分配问题时，还要考虑增量成本，也就是在确保以后的配送方案仍为最优的前提下，改变配送时间(即不在最优配送