物流配送优化(第五-七章)

1,第五章OVRP及其求解算法,实际背景配送公司租用车辆进行配送时，其行驶路线往往是开放式的：送货情形，租用的车辆在完成送货任务后一般无需返回配送中心；取货情形，租用的车辆直接前往线路上的第一个客户点，依次将沿途各客户点的货物装上车，送往配送中心。在回程运输中：沿原去程路线返回，并按相反的顺序将各客户点的货物取回配送中心时，一般也属于OVRP。,2,研究意义租用车辆的费用往往与租用的车辆数和车辆负载时的行驶距离成正比，因此对其车辆行驶路线进行优化就显得非常重要。在当今的外援经济（outsourcingeconomy）潮流中，越来越多的企业租用车辆进行配送。案例美国联邦快递的住宅投递服务：自备投递车辆在完成当天的最后一轮投递任务后无需返回快递总站。报纸的住宅投递问题：报业公司与投递者签订投递合同时，只涉及从报业公司至最后一个投递点的行驶距离，最后一个投递点以后的路程不予考虑。,3,根据所包含的约束条件，问题又可进一步分类。主要类型归纳如下：DCOVRP路程长度OVRPPD装载能力取送作业COVRPOVRPPDTW时间窗OVRPTW,4,OVRP与闭合式VRP的比较两者都属于NP-难问题。虽然目前已有许多求解闭合式VRP的好算法，但都不能直接用于求解OVRP，因两者的解相距甚远：Syslo等证明：从网络中的一个最小的哈密顿圈中去掉其最大的边，并不能得到最小的哈密顿路径。最近，Letchford等(2006)进一步阐明了这个事实：一般来说，对于相同的输入数据，OVRP的最优解与闭合式VRP的最优解是有很大不同的，如下图所示：,5,闭合式VRP的最优解OVRP的最优解闭合式VRP最优线路与开放式VRP最优线路比较,6,求解算法尽管以往有过一些有关的案例描述及其研究报道，但从理论上对其进行系统的研究近几年才开始2000年起，国际上陆续发表了一些研究论文，涉及COVRP,DCOVRP,OVRPTW.算法类型：精确算法（基于分枝切面，branch-and-cut）；经典启发式算法（含有最小生成树的两阶段法）；禁忌搜索算法；门槛接受法（thresholdaccepting）；自适应大规模邻域搜索法;记录更新法（record-to-recordtravelalgorithm）每提出一个新算法，其性能和求解质量都得到了不同程度的改进,7,求解OVRPSTW的TS算法（2007）在已有的相关工作基础上提出。以类型(a)和类型(b)两种软时间窗类型为例对算法进行测试。一体化的惩罚函数：,与Repoussis等(2006)提出的求解OVRPHTW的算法（基于经典启发式）进行比较：软时间窗下，车辆使用数和(或)行驶距离获得节省。TS比基于经典启发式的算法效果好。,8,对类型(a)和类型(b)两种软时间窗类型的计算结果进行比较和分析。类型(b)中的“车辆行驶距离”通常比类型(a)中的要长。因需要在“提前服务惩罚”和“额外线路长度”之间权衡。类型(b)中的解空间比类型(a)中的大，导致求解难度加大。,9,第六章库存路径问题(InventoryRoutingProblem,IRP),概述案例：加油站的汽油配送问题。定义：卖主管理再补给策略（Vendor-managedresupplypolicies）的配送计划问题（供应商管理库存的配送计划问题）。VRP：由顾客提出定单，配送公司按照定单要求编排配送车辆路线进行送货。IRP：由配送中心决定在何时、将何数量的货物、送给何客户；没有客户定单，而是由配送中心在确保客户不缺货的情况下安排配送；,10,所处理的是固定客户在较长一段时间内的配送问题，今天的配送决策将影响到以后的配送安排。目标：在确保客户不缺货的情况下使计划期内的总成本最小。由配送中心决定在何时、将何数量的货物送给客户的灵活性将有利于减少配送成本，但这种灵活性也使得确定一个好的配送计划的难度加大。卖主管理再补给策略的应用领域“客户”是同一公司中的组成部分、固定服务的客户：石化工业（汽车加油站）；家庭用品业（超市、连锁商店）；饮料业（自动售货机）；汽车工业（零件配送）；,11,趋势：使用卖主管理再补给策略的行业越来越多。限制条件：库存远程监测技术。信息技术的发展为解决此问题创造了条件。问题描述（IRP）配送中心在计划期T内为n个客户服务；客户i的货物消耗速度为ui（在现实中是一个随机数）最大库存量为Ci；在时间0（初始），客户i的库存量为Ii0；配送中心备有装载能力为Q的车辆若干辆；目标：确定何时、将何数量、按何线路、送给何客户，才能在确保客户不缺货的情况下使计划期内的日平均成本最小。,12,库存路径问题的另一种形式：特点：允许“缺货”。也被称为“库存-运输整合优化”（Inventory-TransportationIntegratedOptimization,ITIO)。问题描述（以单周期离散随机需求为例）：参考文献：傅成红,符卓.单周期离散随机需求的库存-运输整合优化.系统工程,2007,(1):9-12.配送中心在单周期内为n个客户服务；每个客户必须送货,无初始库存;客户售出每单位产品获利h（若缺货则损失h），若不能售出则亏损l;目标：确定客户送货量和配送线路，使订货期望损失和运输费用之和最小。,13,模型订货期望损失模型设客户j的销售量为r的概率为Pj(r)，当订货量为Qj时的期望损失：,ITIO总费用模型（不含使用车辆的固定成本）,14,求解由存贮论知，最佳订货量Qj可由下式求出：,设客户j可选订货量(等于或小于最佳订货量Qj)为Qjv(v=1,2,V)，则相应的订货期望损失为C(Qjv)。ITIO总费用模型变为：,构造了一个自适应单亲遗传算法来求解该问题。,15,编码方案将染色体分为两段：前半段表示各客户订货选择，后半段表示客户服务路径安排。以8个客户点的ITIO问题为例，若每个客户有最佳(记为1)和次优(记为2)两种订货选择,则2-2-1-2-1-1-2-1|6-2-1-3-8-5-4-7代表一个染色体的编码。客户服务路径采用的是基于客户点编号的符号编码。基因变异与重组对编码前半部分采用多点变异，后半部采用多点基因换位来实现染色体变异和重组。自适应控制（如前所述）,16,算例：以12个客户点的配送问题为例。计算结果：,17,第七章货物配装问题,概述单辆车配装问题多辆车配装问题求解方法,18,7.1概述,一般来说，在直达配送运输中此问题较为重要。货物：轻质货物、重质货物、货物价值不同；限制条件：车辆载重量、车辆容积；车辆数量（单辆车配装、多辆车配装）；一票（种）货物只能装在同一辆车中、可以分别装在多辆车中；配装目标：使所装载的货物的总价值为最大？(运力不足时)如何配装，达到满载满容，提高货车平均静载重？（运力充足时）,19,7.2单辆车配装问题(背包问题),货物i的装入量xi可选有n种货物，货物i共有mi件，每件价值为ci，重量为wi，体积为vi。车辆的载重量为W，容积为V。问各种货物应装载多少件，才能在既不超载又不超过容积限制的条件下，使所装载的货物总价值最大？整数规划模型,20,动态规划模型(1)每装一种货物作为一阶段，共分为n阶段。(2)设变量，Sk：第k阶段初车辆拥有的载重量，Rk：第k阶段初车辆拥有的容积，xk：第k种货物的装载件数。Dk(xk)：0xkminmk,Sk/wk,Rk/vk且为整数。(3)状态转移方程：Sk+1=Sk-wkxkRk+1=Rk-vkxk(4)指标函数：dk(Sk,Rk,xk)=ckxk(5)指标递推方程,21,货物i只有装或不装两种选择有n种（票）货物，货物i的价值为ci，重量为wi，体积为vi。车辆的载重量为W，容积为V。问应选择装载哪几种货物，才能在既不超载又不超容的条件下，使所装载的货物总价值最大？整数规划模型设,22,7.3多辆车(m辆车)配装问题,设Wj和Vj分别为第j辆车的载重量和容积；需要运送的n种货物的重量和体积分别是wi,vi(i=1,2,n)。若货物i被装入第j辆车中，则xij为1，否则为0。如何配装才能使所有车辆的载重量和容积都得到充分利用？整数多目标规划模型：,23,s.t.,24,7.4求解方法,精确算法问题可分别归结为标准的整数规划、0-1规划、动态规划、以及整数多目标规划等问题，可以用相应的精确算法求解。但在配装货物种类、车辆类型较多时，求解难度和计算量都会比较大。启发式算法可参照求解各种背包问题的启发式算法。简易法：先安排车辆装运容重最大和最小的两种，再选容重次大和次小的，依此类推。为了使装载平稳和降低车辆重心，保证运行安全，一