2010届本科毕业设计(论文)
题目：基于粒子群算法的库存——路径问题研究
学院：经济与管理学院
专业：工业工程
班级：0601班
姓名：许洁
指导教师：吴斌
起讫日期：2010.04-2010.06
南京工业大学本科生毕业设计（论文）
基于粒子群算法的库存——路径问题研究
摘要
库存——路径问题(Inventory Routing Problem，IRP)是供应商库存管理（VMI）模式下的核心问题，通过协调库存控制与运输调度，使库存和运输等综合物流成本最低。本文深入分析IRP问题国内外研究现状，对IRP问题的分类、各种建模方法及求解方法进行总结。在此基础上研究了多周期确定需求下的库存路径问题，建立了混合整数规划模型。研究了粒子群算法对该模型的优化求解；基于整数编码方法，使用随机初始化的方法产生初始解，为了提高算法的性能，引入四种惯性权重调整策略和两种学习因子调整策略。基于Matlab 编程进行实验仿真，使用离线性能和在线性能对算法进行评价。讨论了算法的迭代次数、惯性权重调整策略等参数对算法性能的影响，找出了解决该类问题的适合参数。并与遗传算法、经济订货批量法的优化结果进行了比较，结果表明粒子群算法是求解IRP问题的有效算法。
关键词：库存路径问题，粒子群算法，数学建模，Matlab编程
Research on Inventory Routing Problem Based on Particle Swarm Optimization Algorithm
ABSTRACT
Inventory routing problems (IRP) are core issues of V endor Managed Inventory (VMI), which aims to minimize the integrative cost of inventory and transportation through coordinating inventory control and transportation plans. This paper firstly surveys the current research of IRP at home and abroad, then summarizes and classifies all kinds of IRP model and optimization algorithm .Next, a kind of multi-period inventory routing problem with determinate need is studied, and a mixed integer programming model based on the problem is built. Particle swarm optimization (PSO) algorithm is proposed to optimize the model. The solution is encoded in integer and is initialized randomly .In order to improve the performance of PSO, four kinds of strategies which are used to adjust the parameter of inertia weight of the PSO algorithm and two kinds of learning strategies are incorporated into the algorithm. The algorithm is implemented in Matlab, and it is evaluated by two criterions: on-line performance and off-line performance. The effect of different parameter values about iteration, inertia weight and so on are discussed in the experience，and the appropriate parameters are found. A comparison with the traditional economic order quantity and genetic algorithms shows that the particle swarm optimization outperforms others and is effective for solving IRP.
Key Words：Inventory-Routing Problem; Particle Swarm Optimization; Mathematical Model; Matlab Programming
目录
摘要 (Ⅰ)
ABSTRACT (Ⅱ)
第一章绪论 (1)
1.1选题背景和依据 (1)
1.2 国内外研究现状 (2)
1.2.1国外研究现状 (2)
1.2.2 国内研究现状 (5)
第二章库存路径问题的模型及算法 (7)
2.1库存路径问题的定义 (7)
2.2库存路径问题的分类 (8)
2.3库存路径问题的模型 (11)
2.3.1 类似EOQ公式的模型 (11)
2.3.2 混合整数规划模型 (12)
2.3.3 随机动态规划模型 (14)
2.4 库存路径问题的求解方法 (15)
2.4.1 两阶段启发式算法 (15)
2.4.2 马尔可夫决策过程 (16)
第三章库存路径问题的粒子群优化算法 (17)
3.1粒子群算法介绍 (17)
3.2库存路径问题的数学模型 (19)
3.3粒子群算法优化求解库存路径问题 (20)
3.3.1编码方法 (20)
3.3.2粒子群算法初始化 (21)
3.3.3粒子群算法速度更新 (22)
3.3.4算法主要步骤 (23)
3.4实验仿真 (24)
3.4.1参数设置对优化结果的影响 (24)
3.4.2与其他算法的比较 (28)
第四章总结与展望 (30)
4.1论文总结 (30)
4.2研究展望 (30)
参考文献 (32)
附录 (36)
致谢 (42)
南京工业大学本科生毕业设计（论文）
第一章绪论
1.1选题背景和依据
20世纪后期随着科学技术的不断进步和经济的全球化，市场需求不断复杂多样化，原本只针对企业个体的管理思想已被基于顾客为中心的供应链管理思想。企业之间由单纯产品质量、性能方面的竞争转向企业所在的供应链之间的竞争。企业间通过参与合作获得更大的竞争优势，实现自身长远发展。供应链的管理理念强调企业应将有限的资源用于发展自身的核心竞争力。通过终端客户需求的拉动，使得整个供应链上的信息流、物流、商流得以和谐的运作，从而发挥整条供应链的最大效用，以达到提高企业的竞争力与适应力的目的。
在整个供应链管理中，物流作为“第三利润源”更是倍受企业和学术界关注。应用供应链管理的思想现代物流管理的范围早己超出了单个企业的范畴，已向上、下游不同企业联合协作、共同进行物流管理(即供应链管理)的方向发展（图1.1所示）。但在零售商管理库存（Retailer Managed Inventory，RMI）的传统库存管理模式运作中由于供应链中信息在不同阶段之间传递的过程中发生扭曲，使得在供应链内，由零售商到供应商订货量的波动逐层递增，即牛鞭效应（Bull-whip effect）。
为解决这一问题，近年来，在国外出现了一种新的库存管理方法——供应商管理用户库存方式（V endor Managed Inventory，VMI），这种库存管理策略打破了传统的各自为政、条块分割的库存管理模式，以系统的、集成的思想进行库存管理，使整个供应链系统获得同步化的运作，增强了企业的敏捷性和响应性，可有效解决因信息扭曲而引起的牛鞭效应。该库存管理策略的核心问题之一就是库存路径问题（Inventory Routing Problem，IRP），即如何联合优化配送和库存这两个往往被独立考虑的物流环节，对一系列已知需求量的客户，组织适当的送货频率，送货对象和行车线路，在不违反任何约束条件下，使得库存和运输的总成本达到最小。由物流成本悖反原理可知，库存和运输成本不可同时减小所以库存路径问题是典型的NP难题，使用传统的优化方法很难得到问题的最优解或满意解，因此构造高质量的启发式算法成为研究该问题的主要发
第一章绪论
展方向。
图1-1基于供应链思想的物流管理模式
1.2 国内外研究现状
自二十世纪八十年代后期提出库存路径问题后，在系统工程、计算机、管理科学、交通运输等多个领域都有国内外的学者做出研究。2000年以前的IRP 文献主要研究单周期、两层供应链拓扑结构（主要是一对多）、单品种、确定需求情况，通常给定车辆数或不限，决策方式则集中在确定固定的配送频率，目标只考虑客户库存成本(一般不考虑中心库存成本)。2000年以来，随机需求IRP、三层级IRP、取送结合IRP受到更多研究的重视。
本文借鉴其他文献的研究方法，就不同计划期的研究这一问题分类介绍库存路径问题的国外研究状况。国内的相关研究起步比较晚，研究也没有国外系统，所以本文以写作年限的先后做出描述。
1.2.1国外研究现状
（1）计划期为一天
南京工业大学本科生毕业设计（论文）
Federgruen和Zipkin（1984）[1]将IRP视为计划期为一天的规划问题，并利用求解VRP的方法来求解。假设一个工厂，产品库存有限，在运输成本、库存成本与缺货成本综合最小的情况下，有效率的将产品分配给所有的顾客。因为可获得的产品数量有限，在库存保管费用与缺货成本平衡下，不是所有的顾客每天都分配到产品。因此作者将问题建构为非线性的整数规划问题，在模型里设置了一个包含所有未被服务的顾客的虚拟空线路，并将非线性整数规划为您提分解为两个子问题一个是库存分配问题，其主要考虑的是库存保管费用与缺货成本最小；另一个是对每一辆车的TSP问题，其主要考虑的是使运输成本最少。在取得一个初始可行解后，反复将线路间的顾客作交换，对初始解进行了改善。Federgruen（1986）[2]将产品特定为易逝品，如粮食、血液等，因此除之前考虑的成本之外，系统目标函数值还设计到过期成本。论文给出了两类配送策略，第一类采用直接配送策略，通过单纯形法求解库存分配问题；第二类采用零担配送策略通过VRP问题得到原问题解。Golden等人[3]采用启发式算法解决周期为一天的IRP问题，即在充分满足所有顾客库存需求的前提下使总成本最小。在开始求解前，首先计算客户剩余库存与预期需求能力的比率，来定义客户的“需求紧迫性”。若是客户“需求紧迫性”小于设定的标准值，此顾客将排除此次配送。其次，根据“需求紧迫性”与所需送货时间的最高比率，选择客户直接配送，通过反复迭代建立一个大型的TSP。在总旅行时间符合最大旅行时间的限制下，反复进行TSP求解，不断的加入新的顾客直到最大旅行时间的限制，或是没有新的顾客可以加进来为止。Chien（1989）等[4]研究的尽管也是周期为一天的问题，但其不将每一天视为独立时间周期，而是用前一天的优化结果调整次日的收入，模拟连续几天的库存和运输情况，通过单位送货收益和单位缺货损失计算日利润。在建立的混合整数规划模型中，以日利润最大化为目标，并通过拉格朗日松弛法求解。
（2）计划期为多日
即计划期长度超过一天，但不超过一季度或一年(又可以分为需求确定或随机需求两种)。Dror和Golden (1985，1996) 等人[5,6]研究了基于(s,S)库存策略的以年为周期的随机需求IRP问题；模型中将客户的需求定义为独立同分布服从于正态分布的随机变量，并且考虑当前周期做出的决策对于该周期后的库存/
第一章绪论
配送优化问题的影响，近而提出改进方法，将IRP分解为两阶段问题。他们利用周期内的客户日缺货概率，计算每个客户的平均配送成本、期望缺货成本以及使总成本最小的最优配送周期t’。若t’在上述规划周期内，则在此周期内必须完成该客户的配送，并可计算出周期内每天的成本Ct；若t’不在上述规划周期之内，则可以计算出周期内的预期收益Gt。在第一阶段，通过整数规划模型来解决总成本；第二阶段要解决的即是旅行商问题(TSP)或者是车辆调度问题(VRP)。上述方法在路径优化方面得到了Trudean和Dror(1992)[7]的改进，Dror 和Levy(1986)[8]也用类似的方法提出了以周为周期的IRP问题的解决方法，同时还运用节点一弧互换(node&arc exchange)方法减少计划期的成本。Dror和Ball(1987)[9]将以年为周期转化为一个较短周期(天)的随机需求IRP问题，强调了短期决策对于长期成本的影响。基于此本文提出了一种混合整数规划，并涉及了启发式算法进行了求解。Campbell等人(1998)[10]假设顾客每天的需求是随机且彼此独立的已知其联合概率密度函数为F，供应商能够计算每个顾客，在时间点t的存货水准X，并且要考虑在实际应用上的限制，例如:车辆配送工作时间的限制、配送到顾客点的时间窗限制、车容量与顾客储存空间的限制。由于顾客的需求为变动的，所以顾客点可能会有缺货的情况发生，当发生缺货时给予其处罚成本，将缺货视为流失的需求而不再进行补货。在最佳的配送策略下使期望的总成本最小(或是期望收益最大)。Bard等人[11]研究了一个基于(s，S)库存策略，计划期为两周的有卫星工厂的IRP(SFIRP)问题，首先在第一周确定每天服务的客户群，通过对客户群进行调整已达到每天需求量平衡，然后在此基础上重复上述流程进行下一周的计划。此文特殊之处在于车辆在计划期内可以在就近的卫星工厂装载货物，不需返回到配送中心。
（3）计划期为无限期
无限期IRP模型，也称为永久路线问题(Permanent Routing)，是即一旦确定了车辆的巡回路线，则在以后的配送服务中，车辆的行驶路线不会发生变化。Larson(1988)[12]和Webb(1995)[13]分别对战略型IRP问题(SIRP)进行了研究。文章首先用客户需求的均值将问题转化为一个确定需求下的SIRP，并设计了启发式算法对最小车辆数进行了估计，而后设计了一个线性规划对估计值进行了修正得到了系统长期运行的最小成本或最小的车队数量。Barnes-schuste和
南京工业大学本科生毕业设计（论文）
Bassok(1997)[14]验证了直接配送策略的有效性，给出了长期运行成本(库存与配送成本之和)的一个下界，通过模拟证明了当需求服从正态分布且其均值与车辆的运载能力接近时，直接配送策略是一种好的运输策略。Wendy 等人(1999)[15]研究了一个多品种、车辆容量无限的随机需求IRP问题，他建立了基于(Si，Ti)的多品种周期盘点库存策略与旅行商问题(TSP)结合的数学模型，给出了求解的启发式算法，并给出了该问题的下界。
2000年以后，在继续构建高效率求解方法的同时，IRP本身的研究得到了深入，随机需求IRP、三层级IRP、取送结合IRP受到更多研究的重视。后文在对IRP特征描述，模型建立，求解方法中都会列举相关最新的文献。
1.2.2 国内研究现状
以摘要IRP为关键字搜索2000年后相关文献，截止到2010年3月，在中国知网(CNKI)上检索到直接与IRP相关文献是38篇。
袁庆达从决策的三个层次即战略、战术和作业层次扩展了已有研究的决策范围，构造了描述此类问题特征的数学模型和有效的启发式算法[16]；叶志坚等人对模型采用一系列简化求解，并分析了参数敏感性，但没有考虑车辆路径问题[17]；杜文等人对1-M随机IRP进行分析，并重点论述了如何转化为CCL求解[18]；刘立辉和钱燕云[19]采用确定性方法研究了随机一对多配送网络IRP问题。建立了具有随机需求的、多产品的库存与运输整合优化数学模型，提出了两阶段法的改进启发式方法，通过二者之间的反复迭代，较好地解决了库存与运输的整合优化问题。赵达等[20]以零售商系统下随机需求的IRP为研究对象，提出了一种基于马尔可夫决策过程与修正的C-W节约算法的启发式分解算法。杨信丰等人[21]考虑客户对配送时间的要求和车辆行驶时间的不确定性，建立了以车辆配送总行驶距离最小化为目标的机会约束规划模型，并构造了求解该模型的单亲遗传算法；傅成红等人[22]也用这个方法求解单周期随机需求IRP。唐加福等人[23]讨论了多产品、单分销商、多用户的分销网络中，分销中心在租赁车辆外包模式和多次直接运输策略下的配送计划问题，设计开发了基于部分链的遗传算法；娄山佐等人[24]建立一个组合经常性库存成本、安全库存成本和随机路径成本模型后，引入了一种基于Monte-Carlo抽样求解路径期望成本方法、
第一章绪论
协调参数的遗传算法。朱晨波[25]等人研究了直接配送的三层级IRP(实际上路径问题被简化)，用MDP方法建模求解；武秀焕、李延晖[26]研究随机需求库存路径问题，考虑其马尔可夫、随机等特性，将IRP描述为一个MDP，在运用非线性背包问题的求解方法得到初始解构成直接配送线路的基础上，设计一种局部搜索法进行优化。
南京工业大学本科生毕业设计（论文）
第二章库存路径问题的模型及算法
2.1库存路径问题的定义
VMI由数目有限的上游企业对众多下游企业的流通库存进行统一管理和控制，主动安排合理的补货，降低供应链上供需双方的运作成本。VMI是个复杂的大系统，具体运作需要相当繁杂的作业来制定客户补货策略和车辆调度计划，避免出现缺货的情况，发生潜在销售损失的风险，或是出现货物囤积过多，造成多余的库存维持费用。库存路径问题，实质是实现是库存控制与运输计划之间的协调，它将隔断的信息孤岛集成起来，在供应商与客户之间架起信息协调桥梁，在单个供应商对多个分散客户库存进行统一管理的模式下，制定使得供应商的运输成本与客户库存成本总和最低的最佳运输计划和最优库存策略，这里的成本包括订货成本、库存成本、缺货损失成本和运输成本等。本文将IRP 问题定义如下（这种定义只适合两级供应链模式）：
考虑单一（多个）配送中心（供应商）向分散在不同地理位置的多个（单个）客户按照其实际需求（随机或确定）进行产品（单一或多种产品）运送，在计划期间内（或无限时间内）满足一定的约束条件（如客户服务水平、时间窗约束、客户库存能力、车辆总数以及运载能力）下，安排客户补货时间、数量以及车辆行驶路线等，使得平均系统总本（包括订货成本、库存保管成本、缺货损失成本和固定及变动运输成本等）极小。
根据上述定义IRP问题的数学表达如下：
向量D表示客户的需求结构；
向量I(D)表示在满足约束条件下的一组库存策略，即客户的补货时间、数量；
向量T(D)表示约束条件下的一组运输策略，即车辆的行驶路线；
Ct(I(D)，T(D))表示给定计划期t，t=1, 2,…,H，在采取库存策略与运输策略，条件的系统成本，则IRP问题可以表示为：
min { ∑Ct（I（D），T（D））} (2-1)
s. t. I(D)∈Ω(2-2)
第二章 库存路径问题的模型及算法
T(D)∈π (2-3)
其中， Ω、π分别表示库存与运输策略的可行域。总的来说库存路径问题所需解决的要点有以下三个方面：
1）补货频率及补货时刻
2）最优配送量的确定
3）运输线路的确定
2.2库存路径问题的分类
由于IRP 问题的复杂性，使得对该问题的分类种类较多。可以按决策层次，需求类型，产品种类，路径、按配、补货策略，拓扑结构，时间特性，车辆因素等做出分类，表2-1做出了详细的分类：
表2-1 IRP 问题分类 战略层
SIPR-战略型库存-路径问题 IRPSF-有卫星工厂的库存-路径问题
决策层次 战术层 IRP-一般的库存-路径问题
需求类型
D-确定型 S-随机型 产品种类
S-单品种 M-多品种 路径策略
S-静态 D-动态 分配策略
S-静态（不拆分） D-动态（拆分） 补货策略
R-客户补货 S-系统补货 两层 1-1-一对一 1-M-一对多（M-1-多对一）
M-M-多对多
拓扑结构 三层 1-1-1 1-1-M 1-M-M M-1-M M-M-M （注
M 代表多）
计划期
F-有限 I-无限 时间特性 时间约束 T-有时间窗约束W-不存在时间窗约束
车辆数量
L-有限 U-无限 车辆因素 承载能力 C-有限 U-无限
南京工业大学本科生毕业设计（论文）
（1）拓扑结构
早期的IRP研究主要集中在两层级系统，主要包括1-M（M-1可以认为是其颠倒结构)和M-M两种结构形式。下面给出最常见的两层拓扑结构1-M如图示：
图2-1两层拓扑结构示意图
近年，三层级系统IRP引起了研究者的兴趣。如Sombat等人研究的M-1-M IRP[27]。Vidyarthi等人考虑的IRP涉及M-M-M[28]。Zhao等人[29]针对1-1-M IRP 展开研究。Shen和Honda[30]研究了1-M-M的IRP，还允许车辆及存货在同层级内横向转移。下面给出一个简单的三层拓扑结构：
图2-2 三层拓扑结构示意图
（2）计划期
大致上，对应计划期为单周期(日、周)、有限长周期(月、季)和无限计划期
第二章库存路径问题的模型及算法
(多年)的决策层次是作业型、战术型和战略型。单周期IRP一般只解决单次的库存分配和配送路径，通过单周期的连续滚动扩展来研究长周期(多个连续单周期、无限计划期)IRP。有限周期IRP或战术型IRP基本上是为了解决一段时间内如何协调库存和运输来应对供应、需求互动的问题。对于无限长周期，一般用于工厂、中心的选址，以及运输车队的规模等战略决策。
（3）客户需求
客户需求货物一般设定为单品种，有时虽然研究多品种，但通过约定一辆车只装载一种货物转化成单品种。需求变化的情况可以分为两种:一种是呈周期变化，另一种是随机需求。随机IRP更加符合现实情况。Berman和Larson[31]考虑客户需求是随机过程，特别类似维纳过程(Wiener Process)，而且约定配送量在车辆到达客户后才知道。
（4）供应能力
供应商能力有限时，需求可能只部分满足会产生缺货。对于缺货，假设发生缺货惩罚成本(应急直接送货实际是支付惩罚成本)，允许延迟供货时，按照缺货量及延迟时间计算缺货成本。
（5）补货策略
确定需求时，通常不许缺货，主要采用(0，R)策略，或者称为ZIOP策略即当库存降低至零时补货(假设提前期可以忽略)，采用这种策略主要是基于确定需求的EOQ思想，这样有利于降低库存成本。随机需求时，为了简化，多数文献只考虑客户库存，并假定缺货不补则必须惩罚。(R-1,R)策略，主要用来应对随机需求，这样的策略在实际中可行，也有利于IRP问题的求解。
（6）运输(配送)模式
前面提到，IRP侧重于作业层面决策，因此，一般设定车辆数固定或者不考虑车辆数限制以便于后期求解VRP。有时IRP也把最小化车辆数作为目标。对车辆类型的设定，约定有限装载能力，并用同类型车辆实施配送；三层级IRP 涉及到上下两个层面的运输(配送)车辆时，都认为上车辆装载能力大于下游车辆，这样更加符合实际情况。客户补货量可以整体配送，也可拆分配送(单个客户同一周期需求由多辆车分别实施配送)。对于三层级IRP，还涉及货物通过中心的方式，可以分为:中心整车转运(无库存)、中心配送(有库存)。已经有文献研
南京工业大学本科生毕业设计（论文）
究货物取送结合的复杂IRP[32-35]。
2.3库存路径问题的模型
对IRP的研究，国内外学者主要是利用EOQ公式、混合整数规划和随机动态规划等方法建立IRP模型，从而也就形成了类似EOQ(EOQ-liked)的模型、混合整数规划模型和随机动态规划模型这三大类IRP模型。
2.3.1 类似EOQ公式的模型
EOQ模型作为一种经典的解决物流问题的方法，广泛应用于对IRP的研究与建模。BURNS（1985）建立了一个类似于EOQ公式的模型来解决战术层的IRP。他们主要研究的是无限期、一对多的单一物品配送系统。需方需求率确定、所有客户的库存维持费用相同且运输费用仅与距离相关，分别研究了直达运输和零担运输这两种运输模式下使库存和运输费用最小的配送策略。还建立了一个类似于EOQ公式的模型，并用解析法对模型进行了分析。HALL(1985)为单一品种、需求确定、多源点单汇点的多对一的采购系统建立了一种类似的EOQ 模型，并使用四舍五入近似取最合理的频率来对IRP进行分析；BLU-MENFELD 等(1985)研究的是多品种、多源点、多汇点的多对多的货运网络，建立了一个综合平衡库存、运输和生产准备费用的类似EOQ公式的模型；DAGANZO(1988)所建立相似的模型，但所考虑的问题则更加细化:需方的需求己知，生产和运输能力无限，车辆行驶路线长度不受限制以及大吨位货车的行驶区域也不受限制。DAGANZO等（1985，1987）分别从不同的角度为单一品种、需求确定、考虑库存费用和与行走距离有关的运输费用的一对多和多对多配送系统建立类似于EOQ的模型；EL-HOUS-SAINE等[36]为具有一个配送中心和一系列需求确定的零售商的配送系统建立一种类似于EOQ的模型，同时把单一车辆路径问题拓展为多车辆路径问题，并使用基于近似于列生成(column generation)的算法，解决其产生的一系列子问题。
采用类似EOQ公式的模型所刻画的IRP，理解较为直观，也易于求解，但是有时使用这种方法所求得的配送时间间隔可能为任意的非负实数，这在实际运作中不好操作或者可能导致操作过程不合理，可将由EOQ公式求得的值四舍
第二章库存路径问题的模型及算法
五入，取近似值为最合理的频率，或在离散频率集中寻优或利用POT特性规则来获得理想解，这些都是对特定问题的一种近似处理。
2.3.2 混合整数规划模型
在解决IRP时，使用纯整数规划模型和0-1整数规划模型获得的最优解不是很理想，所以大多数学者侧重于建立混合整数规划模型来解决这类问题。SPERANZA(1994) [37]运用实例证明了建立混合整数规划模型较建立纯整数规划模型的优越性。后期学者分别建立了单周期配送系统下，随机客户需求的，或者是有固定供应能力的中心仓库和多个有确定需求的客户的非线性混合整数规划模型，前者的成本包括可变运费、有库存保管费用和缺货损失费用构成的非线性库存费用，后者还涉及未被满足的需求支付惩罚费用。随着研究深入，多周期IRP可以通过将长时段(如每年)的多周期问题简化为短时段(如每天)的单周期问题。通过引入惩罚因子和激励因子来反映相邻周期决策的相互影响，并且建立了相应的混合整数规划模型。最新的研究是通过在线实时信息来了解配送系统的随机需求信息，然后通过设定滚动范围(rolling horizon)的方法建立了一个混合整数规划模型，并对3种实时的滚动范围进行了比较，得出了一个基准的滚动范围。
下面给出一个简单的MIP整数规划模型，假设条件如下：
(l)每个供应商供应一个配件型号；
(2)每种配件在每个时间段的需求确定；
(3)不允许有积压存货(或缺货)；
(4)任何两个地点间运行时间确定并且已经给定；
(5)每条路线的长度不能超过限定的长度；
(6)每个时间段载量一定的货车数量不限；
(7)所有货车的载量和费用相同；
(8)在每个时间段开始时所有的货车都停放在同一个中心仓库并在每次运输后结束回到仓库；
(9)运输成本包括固定成本和可变成本，可变成本和路程的长度对应成比例固定成本是每次出行要支付的费用；
南京工业大学本科生毕业设计（论文）
(10)在特定的时间段一辆或多辆货车可能会到一个供应商那里运货，允许分配运货；
(11)每种配件的具体持有成本已知；
(12)计划期有限并已给出。
模型可以等形于以下阐述的一个MIP 。设在时间段t 内所需货车的最大数量为Jt ，供应商0表示仓库，供应商m+1表示装配车间，本文令：
d i ，t =在时间段t 内对配件i 的需求量，i=1，2，…，m ，t=1，2，…，T K = 一次出行的固定费用
V = 每单位路程的运行费用
C = 货车的载运量
c i ，j = 供应商i 与j 之间的行车距离，i 和j=1，…，m+1
h i = 配件i 的库存储存费用i=l ，2，…，m
I i = 配件i 的初始库存量i=l ，2，…..，m
对决策变量的定义如下：
?íì其他后直接到访问供应商内访问完供应商在时间段如果货车,
0,1j
i t k x ijkt ?íì其他
内到访供应商在时间段如果货车,0,1i
t k y ijkt a ikt =时间段t 内货车k 从供应商i 那里已提取的货运量
a it =时间段t 内从供应商i 那里的将要提取的货运总量
s it =时间段t 内配件i 的库存水平
u ikt =分路线排除约束函数的虚拟连续变量
因此，下面给出了解决IRP 的MIP 模型
minV ????==+=+=′T t J k t k j i m i m j ij x c 11,,,1010+????==+==+′T t J
k t k m m i T t it i x k s h 01
,,0,110
(2-4) 0t k i t i t k i y d a ,,,,,￡￡ }{t k m i ""?",,,1L
2-5) ?=k
t i t k i a a ,,, }{t m i "?",,1L
(2-6)
?￡k
t k i c a ,, t k "", (2-7)
第二章 库存路径问题的模型及算法
??==J
t k i t k i j J t k j i y x x
,,,,,,,, (2-8) }{t k m j i m mx u u t k j i jkt t k i ""?"-￡+-,,,1,,1,,,,,L (2-9)
t i t i t i t i d a s s ,,,1,-+=+ (2-10)
}{t k m i x t k i ""?"=,,,1,0,,0,L (2-11)
}{t k m j x t k j m ""?"=+,,,1,0,,,1L (2-12)
}{t m j i x x t k j i t k m "+?"3+,1,1,0,,,,,,,0,1L (2-13)
?"" ,,,,,,, (2-14) 0,3t i s (2-15) }{m i I s i i L ,1,0,?"= (2-16) }{1,0,,,,,,?t k j i t k i x y (2-17) 目标函数(2-4)中包括出行费用、库存储存费用和每次出行的固定费用三部分，固定费用用来计算货车费用和与每次出行有关的其它费用。分路线排除约束函数(2-8)去除那些没有连接但具有相同参数的行程，约束函数(2-13)对一辆货车能够装运的零配件的数量进行了限定。(2-10)为库存平衡等式，约束函数(2-7)限定了每条路线都小于或等于最长路线L 。 2.3.3 随机动态规划模型 建立顾客需求未知的动态系统模型是IRP 研究的难点。有关研究要追溯到GLOVER 等的研究，他们所探讨的重点主要集中于时间间隔未知情况下的动态配送问题。而后，BLANCHINI 等(1993)对这类问题进行了重新考虑，建立了离散时间状态下配送系统的随机动态规划模型。对于库存路径随机动态规划模型，研究较多的学者是以BLANCHINI 为核心的研究团队。BLANCHINI 等(1996)在建立随机动态规划模型时将单品种、多对多的物流系统看成是一个网络，其中，节点代表具有一定的存贮能力和需求，弧则代表运输路线，并且弧上的流量随时间变化而变化，而客户的需求则是一定范围内的某个随机值。其后，他们又在此基础上扩展了模型的限制条件，增加了对节点存储能力、弧的运输能 南京工业大学本科生毕业设计（论文） 力以及客户需求最大值的限制，并求解出可以满足所有顾客需求的最优的初始库存水平。进一步地，他们通过对2个独立的凸规划问题进行求解来建立随机动态规划模型，并指出这2个独立的凸规划问题可以归纳为一个简单运筹学问题与一个典型的NP-Hard问题(1997)。虽然现有的很多文献已经表明:采用随机动态规划模型可以很好地刻画现实状况，有利于IRP的解决，但是，由于动态规划需要处理大量数据，并且约束条件是指数增长的，很难应用于实际问题。因此，现有的随机动态规划模型多数只是侧重于理论研究。此外，随机动态规划模型对于一些更复杂的问题，如多商品流或系统有限延迟的情况，都还无法刻画。 2.4 库存路径问题的求解方法 IRP求解方法主要集中在启发式方法的研究上，其中两阶段式算法应用最广泛，下文会详细介绍。最近亚启发式(meta-heuristics)也是热点如遗传算法(Genetic Algorithm)、禁忌搜索法(Tabu Search)、模拟退火(Simulated Annealing)、大规模邻域搜索法(Large scale neighborhood search)等现代启发式方法的使用，本文第三章使用亚启发式算法求解IRP问题。现在也有文献把IRP看作为马氏过程，用马尔可夫决策过程(Markov Decision Process，MDP)建模求解。 2.4.1 两阶段启发式算法 IRP问题使用的启发式算法很多，如VRP三下标模型在绝大多数IRP求解中得到应用和扩展[38]。类似的整数规划[39,40]、拉格朗日松弛(Lagrange relax)[41]、分支-定界(branch-bound)[42]、分支-定价(branch-price)[43]、C-W节约法[44]，两阶段启发式算法等。其中两阶段启发式算法应用最多。两阶段法的基本思路是先把客户按照一定的限定分成多个分区，再把供应商与分区一起看成VRP确定配送线路；也可以先确定配送线路，再确定分配给客户的配送量。前者就是在解决了库存问题的前提下优化路径问题，后者就相反，先解决路径问题在求解库存问题。 在两阶段法中首先要固定分区策略(Fixed Partition Policy，FPP)预先将客户划分到不同区域中，形成策略集φ，对每个分区指派一辆车送货。即：1）将分 第二章库存路径问题的模型及算法 布于某区域的所有客户划分到一系列子区域中，对子区域的服务（送货）是彼此独立的；2）当某个子区域中的一个客户被服务时，此区域中的其它客户也须同时依次得到服务，也就是每个子区域中的所有客户都采用相同的配送频率。在考虑车辆运载能力的前提下，φ中的最优策略是指具有最小的平均总库存和运输费用的策略。确定φ的最优策略显然是NP难题，因为这需要寻找一个供货方与某个区域中的所有客户之间的哈密尔顿回路。 接下来介绍一下客户分区常使用的方法。客户的分区可以根据客户点的地理空间分布、配送需求量或者时间、频率，但是很明显的如果强调空间上的邻近，减少运输成本但增加库存成本，强调配送需求、频率，减少库存成本但增加运输成本，所以分区要综合考虑运输成本和库存成本。很多文献提出了较为合理的分区方法，如先考虑了依据时间的顺序分组，这样每个区域中零售商都具有相近的订货周期，可以节省库存费用，其次考虑了根据地理位置对其进行改进，这样又可以节省运输费用，具体算法可参见文献[45]。线路的确定可以利用已有的VRP研究成果。 2.4.2 马尔可夫决策过程 因为IRP的层级之间库存存在转移，客户还要面对消费者需求，各级库存的量随时间变化具有马氏性，所以，一些学者提出用MDP的思想来解决IRP。马尔可夫决策过程是基于马尔可夫过程理论的随机动态系统的最优决策过程，它是确定性动态规划与马尔可夫过程结合的产物。在该决策过程中，决策者周期地或连续地观察具有马尔可夫性的随机动态系统，序贯地做出决策。即决策者根据每个时刻观察到的状态，从可用的行动集合中选用一个动作做出决策，而系统下一步的状态是随机的，并且其状态转移概率具有马尔可夫性，其后，决策者再根据新观察的状态再做出新的决定，一次次反复地进行，直到找到最优解。
相关主题
文本预览