（计算机应用技术专业论文）行驶时间延迟的物流配送干扰管理模型及算法.pdf

大连理工大学硕士学位论文 摘要 物流配送作为物流体系中最基本的业务环节，关系到物流企业的效率与效益。物流 企业通过制定完善的配送计划来为客户提供及时有效地服务。但是在实际的物流活动 中，车辆路径条件往往存在大量不确定因素，如交通事故、交通阻塞、天气变化等，使 得原有物流计划无法顺利完成，给物流企业带来负面影响。如何有效的处理系统中的不 确定因素，使其对系统的扰动程度最小成为物流配送问题的难点。 针对上述问题，本文采用干扰管理思想这一新理念，针对物流配送中经常出现的行 驶时间延迟干扰问题进行研究。干扰管理作为一种实时处理干扰事件的方法论，主要针 对经常性的干扰事件来进行管理。它根据不同实际问题和干扰事件的性质，建立相应的 优化模型及有效的求解算法，为决策者在干扰事件发生后及时地提出最优调整策略。 本文的主要研究工作如下： 1 在对物流配送行驶时间延迟问题分析的基础上，以带有时间窗的单车场车辆路 径问题为研究背景，并引入虚拟客户的概念，将物流配送系统的扰动最小化作为目标函 数，构建了物流配送中行驶时间延迟的干扰管理模型，并给出模型的数学表示。其中， 目标函数中的对于配送系统的扰动，本文将相关文献中提出的客户角度扰动、道路网络 变动和道路配送成本三方面的度量方法进行了改进，并在此基础上提出了整个配送系统 的扰动度量方法。 2 通过建立数学模型，将问题抽象为线性规划问题，并可以借助计算机对问题进 行求解。在模型基础上，本文设计了求解干扰管理模型的遗传算法，实现快速生成行驶 时间延迟问题的干扰管理调整策略。并通过解决某物流公司的受扰实例与s o l o m o n 标准 算例，验证了干扰管理模型及算法的有效性与可行性。 本文提出的多目标优化模型同时兼顾客户满意程度、道路网络变化、道路配送成本， 有效降低了行驶时间延迟干扰事件对物流配送计划的扰动，使得调整计划更加具有实用 性，对实际物流配送干扰管理具有一定的理论意义与参考价值。 关键词：物流配送；行驶时间延迟；干扰管理；多目标优化 d i s r u p t i o nm a n a g e m e n tm o d e la n da l g o r i t h mf o ru r b a nd i s t r i b u t i o n s y s t e mu n d e rd i s r u p t i o n so ft r a v e lt i m ed e l a y a b s t r a c t d i s t r i b u t i o ni st h em o s te l e m e n t a r ys e c t i o ni nl o g i s t i cs y s t e m t h el o g i s t i e su s u a l l y e m p h a s i z ep l a n n i n g - m a k i n gad e t a i l e da n dc o m p l e t eb l u e p n n tf o ra c t i o n st og a i nt h eh i g h e s t s a t i s t i e d h o w e v e r ，i np r a c t i c a lo p e r a t i o n s ，t h e r ea r en u m e r o u su n c e r t a i ne v e n t sw h i c ha l w a y s c h a n g e 也ed i s t r i b u t i n gc o n d i t i o n s ，s u c ha sc a ra c c i d e n t ，t r a f f i cj a r n ，b a dw e a t h e re t c t h e s e c h a n g e su s u a l l yc o m eb e y o n dt h eo r i g i n a ld i s t r i b u t i o np l a n n l ec h a n g e sm a k et h ei n i t i a lp l a n d e v i a t ef r o mi t si n t e n d e dc o u r s ea n de v e nm a k ei ti n f e a s i b l e o nt h i so c c a s i o n h o wt od e a l 、撕t hd i s r u p t i o n ss oa st om i n i m i z et h ei m p a c t st ol o g i s t i c ss y s t e mb e c o m e st h ek e yi s s u e b a s e do nt h ec o n c e p to f d i s r u p t i o nm a n a g e m e n t ，t h et r a v e lt i m ed e l a yp r o b l e mi ss o l v e d ， w h i c hi sk n o w na st h em o s tt y p i c a la n df r e q u e n tp r o b l e md u r i n gd i s t r i b u t i o n s d i s r u p t i o n m a n a g e m e n ta sam e t h o d o l o g yo fh a n d l i n gd i s r u p t i o n si nr e a lt i m e ，d i s r u p t i o nm a n a g e m e n t c h i e f l yh a n d l e ss u c hk i n do fi n c i d e n t st h a th a p p e n sf r e q u e n t l y a c c o r d i n gt ot h ec h a r a c t e r so f d i s r u p t i o n s ，t h ec o r r e s p o n d i n gm o d e la n di t sa l g o r i t h ma r ec o n s t r u c t e dt og e n e r a t eo p t i m a l a d j u s t m e n ts c h e m ea ss o o na sp o s s i b l e t h em a i nr e s e a r c h e si nt h i sp a p e ra r ea sf o l l o w s ： 1 o nt h eb a s i so fd i s t r i b u t i o ns y s t e mu n d e rd i s r u p t i o n so fv e h i c l et r a v e lt i m ed e l a y a n a l y s i s ，i no r d e l t od e a lw i t ht h ed i s r u p t i o ne v e n t s ，w h i c ho c c u ri nv e h i c l er o u t i n gp r o b l e m s w i t ht i m ew i n d o w s ，ad i s r u p t i o nm a n a g e m e n tm o d e lf o rt h ep r o b l e mi sc o n s t r u c t e dw i t ht h e m a t h e m a t i cp r e s e n t e d i nt h eo b j e c t i v ef t m c t i o n ，t h ed i s r u p t i o nm e a s u r e m e n tm e t l l o di s p r e s e n t e d , w h i c ht a k e sc u s t o m e ru n s a t i s f i e di n d e x ，d e v i a t i o nf r o mt h eo r i g i n a lt r a n s p o r t n e t w o r k ，a n dt r a n s p o r tc o s ti n t oc o n s i d e r a t i o n s 2 s o l v et h ed i s r u p t i o nm a n a g e m e n tm o d e lb yt h eg e n e t i ca l g o r i t h m ，a n do b t a i nt h e d i s r u p t i o na d j u s t m e n ts c h e m er a p i d l yi nr e a lt i m e a p p l yt h ea l g o r i t h mt oac a s ew h i c hc o m e s f r o mal o g i s t i c sc o m p a n ya n dt h es o l o m o n sd a t as e t 1 1 1 er e s u l ts h o w st h a tt h ep r o p o s e d m o d e la n da l g o r i t h ma r ea v a i l a b l ea n de f f e c t i v e n l ep r e s e n t e dd i s r u p t i o nm a n a g e m e n tm o d e lo ft r a v e lt i m ed e l a yp r o b l e mi nl o g i s t i c s d i s t r i b u t i o ns h o w st h a tt h em o d e l sm u l t i p l eo b j e c t i v e sc a l lb em e t s i m u l t a n e o u s l ya c c o r d i n gt o t h ed i s r u p t i o ne v a l u a t i o nc r i t e r i o n s k e yw o r d s ：l o g i s t i cd i s t r i b u t i o n ；t r a v e lt i m e d e l a y ；d i s r u p t i o n m a n a g e m e n t ；m u l t i - 。o b j e c t i v ei n t e g e rp r o g r a m m i n gm o d e l ； 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：i 至i 垦塑! 亟垄垂兰兰望至塾塑垒丝i ! 垄重丝1 矍丝垦盏主至 作者签名： 一一j 哮二袭一日期：立竺上年j 三月j 乙日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：垒刍至垒堕! 望壁垂丝兰望盘塑圭重i ! 五重! 笙丝丝造蔓墨 作者签名： ! ! 牢盘日期：丝2 年匕月立日 导师签名：垒叠垒日期：刭年笠月上z - 日 大连理工大学硕士学位论文 1绪论 1 1问题的提出 物流配送是整个物流系统中最基本的业务环节，关系到物流企业的效益与效率。如 何为客户提供及时有效地服务是物流服务提供商在经营方面必须解决的重要问题。物流 企业通常强调配送计划的制定，详细完整的计划可以使配送过程获得更高的经济价值， 同时能够使客户达到最满意的结果。但是现实世界中充满了不确定因素，如交通事故、 道路堵塞、车辆故障以及天气变化等，使得在配送之初制定的计划在执行过程中变得不 再具有最好的经济价值，有时甚至由于某些因素而变得不再可行。这些对系统造成影响 的不确定因素，通常被称为干扰因素。这些干扰常常超出物流服务提供商最初制定计划 所设想的范围，若不能完善的处理，会阻碍原有物流计划的顺利完成，给物流企业带来 负面影响。如何针对物流配送中的干扰做出快速、准确的判断并且及时提出解决方案， 对于保证物流配送环节的正常运行具有很大的意义。 对于处理不确定干扰因素，人们已经有了许多不同的策略，但都可以归结为两大类： 预先优化与实时重新建模。预先优化的思想是：根据以往经验对未来可能发生的不确定 因素进行预测与估计，并在此基础上建模并求得最佳的方案。这样求出的方案对于一些 特定干扰具有一定的鲁棒性，从而达到解决不确定因素的目的：实时重新建模的思想是： 在初始制定的执行过程中遇到不确定的干扰因素后，根据系统中新的状态或变化等信息 来动态调整初始计划以应对干扰事件。 但是物流配送中的不确定因素多种多样，具有不可预知性，并且出现的频率也比较 高，因此预先优化的方法常常很难达到理想的效果。通常在处理物流配送受扰问题的研 究中需要采用实时重新建模优化的方法，例如s c h e d u l i n g 和r e s c h e d u l i n g 方法：这种方 法是从干扰事件发生后的状态出发，对整个系统经行重新建模调整和规划，通过对原方 案的全局优化调整，实现对干扰事件的快速响应。这种方法可以得到针对干扰因素得到 费用最优的调整计划，但是由于可能触及原计划未考虑到的因素，最优的调整方案常常 会与原始方案产生很大的背离，使得调整方案在现实中实施的代价很大，有时甚至是不 可行的。因此，有必要将原计划情形考虑在内，通过局部优化调整策略，达到系统扰动 最小的目的，同时兼顾物流配送成本最低，这正是干扰管理理念的基本内涵。 关于干扰管理是近年来国际上管理科学、运筹学和系统工程等领域备受关注的新的 研究方向，具有广阔的应用前景和重要的科学意义。目前学术界尚无统一明确的定义和 界定。但国内外学者基本形成了共识，美国学者y ug a n g 对干扰管理定义为：在计划 行驶时间延迟的物流配送干扰管理模型与算法 开始阶段，用优化模型和求解算法得出一个好的运行计划；计划实施中，由于内外部不 确定因素导致干扰事件的发生，使原计划变得不可行，需要实时地产生新计划。新计划 要考虑到原来的优化目标，同时又要使干扰带来的负作用最小化。干扰管理思想处理干 扰事件的方法( 1 ) 制定初始最优执行方案并执行；( 2 ) 识别执行过程中出现的干扰事 件并评估其影响；( 3 ) 在保证干扰对系统扰动最小的情况下，形成有效地干扰管理方 案。 本文正是以干扰管理思想为理论基础，针对物流配送中经常出现的车辆行驶时间延 迟的问题展开研究。为了使物流配送系统在干扰事件调整过程中达到多方满意，本文从 客户角度的扰动程度、道路网络干扰程度、道路配送成本三方面对系统的扰动进行辨识 和度量。从最小化客户不满意程度、道路网络干扰程度以及道路配送成本这三方面构建 了行驶时间延迟的物流配送干扰管理模型。通过建立模型并求解得到了系统扰动小、可 行性高的物流配送受扰延迟问题的干扰管理调整方案。 1 2 国内外相关研究综述 本节将首先介绍论文相关领域的知识，随后总结国内外研究进展，并在此基础上提 出本文的主要研究工作。 物流配送问题以车辆路径问题( v i 冲) 的研究作为基础，而物流配送干扰管理问题 则是在物流配送基本问题之上运用干扰管理的概念构造并求解模型。这其中涉及到两大 方面的问题：( 1 ) 车辆路径问题；( 2 ) 干扰管理问题。因此从这两个方面国内外的相 关研究情况进行综述。 1 2 1 车辆路径问题 车辆路径问题是由d a n t z i g 和r a m s e r l 2 】于1 9 5 9 年提出的，它可以定义为：运输车辆 从一个或多个设施到多个地理上分散的客户点，优化设计一套货物流动的运输路线，同 时要满足一系列的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行 驶里程限制、时间限制等) 。其前提条件是客户点位置和道路情况已知，由此确定一套 车辆运输路线，以满足目标函数( 如路程最短、费用最小、时间尽量少、使用车辆尽量 少等) 的要求。 根据研究的重点不同，车辆路径问题有很多不同的种类：按照任务类型有集货问题、 送货问题、集送一体化问题；按照车辆装载情况有满载问题、非满载问题；按照车场数 目有单车场问题、多车场问题；按照车辆类型有单车型问题、多车型问题；按照配送任 务是否有时间限制有一般车辆路径问题和带时间窗的车辆路径问题，其中时间窗又有不 大连理工大学硕士学位论文 同的类型，硬时间窗和软时间窗。现实的物流配送问题常常会涉及到许多不同类型的混 合问题，因此现在的研究的重点也集中在多种类型的混合问题上。 车辆路径问题属于n p h a r d 问题，对于不同问题模型和算法也有比较大的差别。车 辆路径的算法大致可以分为两类：( 1 ) 处理确定性问题的算法，即需要处理的问题中 的所有条件都是确定已知的；( 2 ) 处理非确定性问题的算法，即处理的问题中有些因 素可能是未知的或者可能发生改变，需要针对此类未知因素进行处理。 ( 1 ) 确定性车辆路径问题的模型及算法 确定性车辆路径问题是指：在路径规划之前，规划人员对有关路径规划的所有信息 都是清楚地，可以做到了然于胸，并且在制定好计划后的执行中，各个信息也不在发生 变化【3 】。所谓的相关信息，包括客户的所有特性，如客户的地理位置、需要服务的时间、 需求量等。 确定性车辆路径问题模型 确定性车辆路径问题的模型主要有三类：车辆流表示法( v e h i c l ef l o wf o r m u l a t i o n ) ， 物流表示法( c o m m o d i t yf l o wf o r m u l a t i o n ) ，集分割模型。 车辆流模型是最常用的一种模型，它使用图的每条弧或边来对应一个整数变量， 用来计算一辆车经过弧或边的次数t 4 。这是v r p 的基本类型中较常用的模型，特别适 合于其解可以表示为与弧相联系的费用和的情形，且当最有关的约束条件是关于在线路 内部客户之间的直接转移时，可以通过对弧集合和费用的适当定义来有效地建模。 物流表示法用图的每条弧或边对应着另一个整型变量，用来表示由车辆所运送 的经过该路径的货物流量【5 j 。这类模型的求解算法与车辆流模型相似，现在也作为构造 求解确定性车辆路径问题精确算法的基础。 集分割模型则使用大量的0 1 变量，每个都与一条不同的可行路线相联系。 b a l i n s k i 等【6 j 最早利用集分割模型来研究车辆路径问题。然而，这类模型与一般的动态 规划模型有着相同的缺点，即使对于规模较小的问题，模型的变量数在大多数情况下亦 是天文数字。 每一种模型都适用于一些特定的问题，常常根据问题的特点来选择适合的模型来建 模求解。 确定性车辆路径问题的求解算法 求解车辆路径问题的算法通常分为两类：精确算法和启发式算法。 到目前为止，已提出的精确算法的种类较多，具有代表性的研究成果有：f i s h e r r l 提出的k 树法；p a d b e r g 等【8 j 的分枝剪枝法；f u m e r o 等【9 】的修正拉朗日松弛及子梯度优 行驶时间延迟的物流配送干扰管理模型与算法 化方法；l o r e n a 等【1o 】对列生成方法的改进；l a p o r t e 等】的含有双下标变量约束松弛算 法；f i s h e r 等【1 2 l 还研究了有容量和时间窗约束v r p 的三下标变量算法。 精确算法主要适用于解决问题结构比较清晰、所含各元素间的关系明确、边界清楚 的良性结构，需要花费比较大的工作量。另外，许多实际的v r p 问题都不具有良性结 构，因此还需要依赖于启发式算法。 求解确定性车辆路径问题的启发式算法很多，按传统的启发式算法分类，以下着重 综述构造算法、两阶段法和改进算法三大类启发式算法。 构造算法是根据一定的准则，每一次将一个不在线路上的点增加进线路，直到所有 的点被安排进线路为止。如c l a r k e 和w r i g h t 1 3 j 提出的c w 节约算法、g i l l e t t 和m i l l e r 1 4 】 提出的扫描算法以及s 0 1 0 m o n 【1 5 】提出的最近邻启发式算法都是构造启发式算法中最为 经典的算法。 两阶段法的基本做法是在第一阶段得到一可行解，第二阶段通过对点的调整，在始 终保持解可行的情况下，每次迭代产生一个解用以替代原来的解，力图使目标函数值得 以改进，一直继续到不能再改进目标函数时为止。如r e n a u d 等【1 6 】的p e t a l 算法、l i n 1 7 1 的2 - o p t 和3 o p t 交换、o r 【1 8 】提出的o r o p t 交换、t o m 和v i g o 1 9 】提出的聚类重排算法 等。一些基于数学规划的算法也属于两阶段法，首先把问题表达成一个数学规划模型， 根据其模型的特殊构形，利用一定技巧进行分划，进而求解易于处理的子问题。如k o h l 等【2 0 】先利用l a g r a n g i a n 松弛技术将有时间窗的车辆路径问题变为较简单的指派问题，然 后用列生成技术来获得问题的近似解。另外，还有一些两阶段算法在求解过程中常常采 用交互式优化技术，把人的主观能动作用结合到问题的求解过程中。 改进算法是从一个初始解开始，通过对当前的解进行反复地局部扰乱以达到较好的 解。基于启发式的并行算法和亚启发式算法都属于此类。亚启发式算法包括禁忌搜索算 法、模拟退火算法、神经网络和遗传算法等方法。2 0 世纪9 0 年代以来，这些亚启发式 算法的应用成为车辆路径问题求解算法研究的新趋势。如g e n d r e a u 等【2 l 】将禁忌搜索算 法应用于车辆路径问题的求解，并取得了较好的效果。另外，模拟退火算法、神经网络 以及遗传算法等亚启发式算法也已经较成功地解决了一些确定性车辆路径问题。 ( 2 ) 非确定性车辆路径问题的模型及算法 非确定性车辆路径问题是指：在路径规划开始之前，计划人员并非确切知道有关路 径规划的所有信息，部分信息可能是不确定的、模糊的，甚至是未知的；初始路径构建 以后，信息可能会发生变化【3 】。很明显，与确定性车辆路径问题相比，非确定性车辆路 大连理工大学硕士学位论文 径问题是一个更一般化的问题。非确定性车辆路径问题又可分为模糊车辆路径问题 ( f v p d ) 和随机车辆路径问题( s v r p ) 。 不确定性车辆问题的模型与确定性问题的基本类似，其模型根据问题类型也分为车 辆流表示法，物流表示法，集分割模型。下面主要介绍解决非确定性车辆路径问题的算 法。 模糊车辆路径问题( f v r p ) 有些学者将这类问题定义为标准的车辆路径问题，因为真事车辆路径问题的需求等 信息往往是模糊的、不确定的，这类问题是很难找到最优解的。 t e o d o r o v i c 等【捌人是最早着手研究这类问题的人。他以模糊数表示客户点的需求 信息，以倾向度为基础建立模糊判定规则，其核心是基于s w e e p 算法，并省略了s w e e p 算法的第二阶段，即初始化子路径后对它们的优化过程。 b e r t s i m a s 2 3 - 2 4 提出了两种重新优化策略分别为策略a 和策略b 。在策略a 下，车 辆按同样固定的顺序作为一个预先安排的车辆优化顺序经过所有客户点。然而，车辆仅 服务有需求的客户点，但要经过无需求的客户点，总的期望距离等于预先制定路线的固 定长度与由于车辆容量约束而使车辆返回仓库中心造成的距离迂回长度之和。在策略b 下，无需求的客户点可以不经过。 祝崇隽、刘民、吴澄等【2 5 】以模糊可能性分布，建立了车辆路径问题基于置信度的三 下标流模型，并提出了基于可能性分布的2 - o p t 算法。该算法引入了伪出发点，建立了 以置信度为基础的判定规则，以遍历为终止条件，从而在全局层次上进行优化，同时避 免过多地扩大搜索空间，该算法已被验证可解决较大规模的问题( 大于2 0 0 个客户点) 。 郭耀煌等【2 6 】根据组合优化、排队论和几何概率方面的知识，分析了需求密集情况下 的一类随机动态v r p 的下界，并研究了一种运作策略的渐近性。 张建勇等r 2 7 贝l j 通过引入模糊预约时间的概念，从顾客满意度的角度研究了模糊不确 定信息条件下的多目标车辆优化调度问题。后来，他们通过引入决策者主观偏好的概念， 提出了解决模糊需求信息条件下v r p 的一种基于模糊可能性的混合遗传算法，并在最小 化使用车辆数与车辆行驶距离的目标下，通过随机模拟研究了决策者的主观偏好对最终 决策目标的影响。 随机车辆路径问题( s v r p ) 如果车辆路径问题中的某些因素是随机变化的，例如行驶时间可能出现延迟、需求 量可能在配送过程中变化等随机因素，就形成了随机车辆路径问题。因此随机车辆路径 被人们看成模糊车辆路径问题的扩展。对这种类型的问题，目前出现的算法大部分可以 归纳为以先验序列为基础的方法。这类问题属于二阶段式求解的问题：在信息不完全( 随 行驶时间延迟的物流配送干扰管理模型与算法 机) 的情况下确定先验序列；在获得确定性信息的情况下进行决策。例如，用两阶段方 法来考虑含有随机需求的车辆路径问题时，第一阶段设计出的聊条路径经过每个顾客点 恰好一次，第一阶段结果出来之后，顾客实际需求被确定。顾客的总需求可能超过车辆 容量约束限制，这时第一阶段的设计线路可能变得不可行。第二阶段的一个简单策略可 以按原设计线路行驶，直到车辆容量约束打破，此时再返回仓库中心卸载或补充需求物 品，然后返回到路径失败的地方重新开始顾客服务。 随机模型的选择基于两点：第一阶段的成本和第二阶段的期望成本。先验序列的确 定方法又有两类：一类是按二元可能性理论来确定，另一类则是基于机会约束规划。 第一类方法中，假定需求分布是二元的( 即在第点有单位需求的概率为只，则没有 单位需求的概率为1 - 尸，) 和离散的。根据该假定，可推出先验序列的期望长度、相应的 上下界和渐进特性。l a p o r t e 隆阳基于l - s h a p e d 方法，提出一个精确算法，并实验求解了 客户点小于5 0 的问题。 另一类方法是s t e w a r t 等【2 9 】分别使用机会约束规划，在一定的假定条件下，将随机 车辆路径问题等价转化为确定性车辆路径问题，并找到了解的界，其方法的核心是让出 错返回的概率不超过一定的界限。机会约束规划模型均以确定性车辆路径问题的含有三 下标变量和二下标变量模型为基础，添加可能性约束条件和惩罚函数后建立起来的。所 用的算法也与确定性问题求解算法有不少相似之处。d r o rm 瞄就是在建立三下标流机 会约束规划模型和惩罚函数模型后，利用c ia r k _ w r ig h t 节约算法求解随机车辆路径问 题。 第二阶段的策略为：按照先验序列，跳过需求为零的客户，直接访问下一个客户， 如果车辆负荷超过了车辆最大载重量，则返回出发点卸载，并回到出现超载的地方，继 续提供服务。 车辆路径问题本身就属于n p h a r d 问题，其求解相当复杂，而含有不确定信息的车 辆路径问题的求解显然难度更大。这种不确定性的解决方法主要是预先优化法，即调度 者根据未来服务请求、顾客需求、行驶时间等预先制定出基于模糊信息的一种或多种配 送方案。也就是说，物流配送计划本身就是不确定的，必须随实际情况变化随时做出优 化调整。这种方法在实际运行中的可行性是一个值得质疑的问题，由于系统随时变化， 必然带来巨大的计算量，给系统带来混乱和扰动。因此，有必要采取更有效的措施，引 入干扰管理理念来处理这种不确定性，提高方案的可行性。 大连理工大学硕士学位论文 1 2 2 干扰管理及其模型与算法研究 不确定性是客观世界的本质属性和普遍规律，它使我们的世界始终处于动态、活跃 和复杂的变化之中。不确定性事件的发生是不可避免的，甚至常常是不可预见的，因此 它们总是对人们事先所制定的计划造成或多或少的干扰。干扰管理针对经常性干扰事件 的特点与性质，建立相应的优化模型和有效的求解算法，为决策者在干扰事件发生后及 时地提出最优调整计划。近年来，干扰管理问题已成为国际上管理科学、运筹学和系统 工程等领域备受关注的新的研究方向，具有广阔的应用前景和重要的科学意义。 对于物流配送系统的干扰管理研究，国外在这方面起步较早，研究成果多侧重于模 型与算法，在该领域取得了显著的经济效益，国内这方面的研究相对滞后。本节将分析 干扰管理与其他不确定性决策方法的区别，并从干扰管理的理论与方法、干扰管理的应 用研究两方面概括干扰管理的研究进展。 ( 1 ) 干扰管理与其他不确定性决策方法的区别 针对不确定性事件，国内外学者从多个侧面进行研究，并形成相应的理论和方法， 如s c h e d u l i n g 和r e s c h e d u l i n g 方法、应急管理等，干扰管理和这些方法有着明显的差别： 干扰管理与s c h e d u l i n g 和r e s c h e d u l i n g 方法： 干扰管理是针对干扰事件产生的状态对原方案进行局部优化调整，目标是使扰动最 小且兼顾节省运输等费用，但可能并不是费用最少的方案。s c h e d u l i n g 和r e s c h e d u l i n g 方法则是从干扰发生后的状态出发，对系统进行全局优化调整，以达到费用最省得目的， 但是可能对系统产生比较大的扰动，而是新方案不可行。这在航班延误的处理中体现的 尤为明显。航班延误之后，如果采用s c h e d u l i n g 和r e s c h e d u l i n g 方法对所有航班重新规 划和安排，虽然能够得到一个费用最优的航班的飞行安排，但是需要耗费大量的人财物 力，并且可能导致大部分乘客重新购票或换乘航班，对乘客而言扰动很大，将会导致新 的飞行方案不可行。 干扰管理与应急管理： 干扰管理和应急管理也有着明显的不同。尽管应急管理也是以干扰事件作为研究对 象，但是干扰事件按照发生的频率、产生的影响和处理时间的及时性和紧迫性，可以分 为经常性的干扰事件和突发性的干扰事件。干扰管理主要针对经常性的干扰事件，如工 业生产中的暂时缺货现象、交通运输中出现的堵塞现象以及航班的延迟等，研究消除其 干扰的策略和措施。而诸如“9 1 1 事件”、“s a r s 事件 等突发性的干扰事件往 往具有连锁反应和处理时间的及时性和紧迫性等特点，因此属于应急管理的研究范畴， 其成果主要集中在突发事件的应急对策和预案方面【3 h z 。 干扰管理与不确定性决策理论： 行驶时间延迟的物流配送干扰管理模型与算法 不确定性决策理论作为一种数学决策理论，主要是针对信息不完整和不对称等造成 的不确定性问题进行科学合理的预测和决策，已在工业、农业、交通运输和国防等领域 得到较广泛的应用；干扰管理则侧重于干扰事件发生后对原计划的调整，减小干扰带来 的负作用。 ( 2 ) 干扰管理理论与方法研究进展 干扰管理模型的研究进展 国内外学者根据干扰事件的特点以及实际问题所属领域，提出了许多解决实际问题 的干扰管理模型。这些干扰管理模型，可以大致分为两类：一类为图模型，另一类为数 学模型。其中与模型又可以细分为：时空网络图模型、基于p e r t 图的干扰管理模型。 i 图模型 时空网络图模型( t i m e s p a c en e t w o r km o d e l ) 是一种描述组成网络各要素之间关 系的网络流模型。该模型由h a n e 等【3 3 1 提出并用于求解航空机组的调度问题，j a r r a h 等【3 4 】 学者将该模型进行修改和扩展，将成本最小网络流问题抽象，构建出基于时空网络图模 型的线性规划模型。g a n gy u 等【l 】在航空领域的航班调度问题研究中，在时空网络图上 增加虚拟的延迟航班和保护航班作为干扰管理方案，并相应的设定这些虚拟航班的运行 成本和保护费用，使受到类似机械故障、天气影响等原因造成的航班取消或延迟造成的 损失大大降低。 p e r t 图( p r o g r a me v a l u a t i o na n dr e v i e wt e c h n i q u ec h a r t ) 是一种出现于2 0 世纪 5 0 年代后期的网络计划技术。p e r t 图模型是一种有向图，通过描述各项作业及其关系， 找出项目的关键线路，可以有效的控制和管理项目进度。l ip i n g 等 3 5 1 采用p e r t 图建立 了非确定性项目网络的风险调度预测模型，提高了预测的准确性。罗守成【3 6 j 对p e r t 图 中各项作业的延迟对总工期和费用的影响进行了研究，提出按各作业的重要性而不仅仅 是根据延误时间长短来计算延迟时间惩罚的方法。 i i 数学模型 随着干扰管理的逐步发展和深入研究，针对不同的问题条件，其数学模型也呈现出 不同的模型形式，以干扰造成的偏差成本( d e v i a t i o nc o s t ) 为评估标准之一的数学模型 就是其中的典型代表。式( 1 1 ) 是无干扰时数学模型的一般形式。当干扰发生后，目标 函数和可行解集发生相应的变化，通过多个目标之间的权衡优化达到总目标的优化。式 ( 1 2 ) ( 1 3 ) 是含有两重优化目标的数学模型，两式分别表示不同的优先级目标规划。 m i nf ( x )无干扰时目标函数的一般形式 s u b j e c t t ox x 约束条件 ( 1 1 ) 大连理工大学硕士学位论文 m i n l e x p l ：g ( 口+ ，a 一) 尸27 ( 石) x xj s u b j e c t t ox + a + 一口一= x o a + ，a 一0i m i n l e x p l ：f ( x ) 尸2 j g ( 口+ ，口一) x xl s u b j e c t t ox + a + 一口一= p 口+ ，a 一0i 受扰后含有两重优化标准的目标函数 约束条件 受扰后含有两重优化标准的目标函数 约束条件 ( 1 2 ) ( 1 3 ) 学者g a n gy u 和x i a n g t o n gq i 将该模型应用于最短路问题干扰管理的研究中【1 】。将 甙矿，a - ) = k + l a + l + k 。l a i 的含义具体化，根据干扰管理理念来选定系统扰动最小的方案作为 最终方案，即最终的干扰管理方案在所有满足约束条件的方案中，路偏离最小，路线成 本最小。 数学模型的特点是：( a ) 容量大。该类模型对参数的容纳能力强，能够表达大规模的 复杂问题；( b ) 灵活性强。随着实际应用需求的变化，目标函数和约束条件会随着干扰问 题条件的变化而发生改变。但这类模型对问题的抽象程度高，从模型本身很难识别问题 原型及其所属领域，且模型求解得到的数据不带任何领域知识和信息，必须把这些数据 还原成用户能够理解的形式，造成模型使用复杂化。 干扰管理算法的研究进展 在模型构建的基础上，干扰管理模型求解算法可以分为精确算法和近似算法。常用 的近似算法大致有两类：启发式算法和拍卖式算法。 i 精确算法。代表性研究成果有：t e o d o r o v i c 等【37 】提出的解决航班干扰问题的分支 定界法、q i 等1 3 8 提出的求解机器调度干扰问题的动态规划算法、杨磊等【3 9 】提出的解决 t s p 扰动恢复问题的轮换算法等。精确算法可以得到最优的结果，但是由于需要耗费比 较长的时间，在问题规模比较小的时候可以很好的解决问题，但是当问题规模增大时， 则无法再满足干扰管理实时性的要求。因此在干扰管理问题的精确算法方面成果相对较 少。 行驶时间延迟的物流配送干扰管理模型与算法 启发式算法。运用启发式算法求解干扰管理模型的研究成果较多，代表性的成 果有：l a r s e n 等【4 0 】提出的局部搜索算法、s m i t h 等】提出的优先选择的迭代搜索算法、 h u i s m a n 等【4 2 】提出的聚类重排算法、王明春等【4 3 】提出的禁忌搜索算法等。 启发式算法可以通过运用经验等启发式信息以及实验分析来求解问题。干扰管理的 核心思想是新方案相对于原方案的扰动最小，因此启发式算法可利用原方案中的信息， 采用局部优化调整的方法使系统的扰动最小。此外，在求解具体问题时，启发式算法可以 经过少量的计算，在较短的时间内得到问题的最优解或近似最优解，因此启发式算法非 常适合于求解复杂性、实时性较强的干扰管理问题。然而，也正是由于干扰管理具有较 强的实时性，因此启发式算法的求解速度还有待于提高。 i i i 拍卖式算法。拍卖式算法由b e n s e k a s 【4 4 】于1 9 7 9 年提出，是一种对偶算法，在 搜索方式上与传统方式有很大不同。它模仿现实的拍卖过程，利用“一对一 式的，z 个 主体对n 个对象同时叫价这样的竞争机制，最终实现总价值( 总目标) 最大化。拍卖式算 法最初用于调度问题1 4 5 - 4 7 】，1 9 9 1 年被b e r t s e k a s 应用于解决最短路问题【4 8 1 ，后来又被用 于解决运输问题1 4 9 。f r e l i n gr 【5 1 1 综合了拍卖式算法中“前向算法”和“后向算法的 优势，研究出“双向结合式”的拍卖式算法。j i n g q u a nl i ，p i t ubm i r c h a n d a n i 等1 5 2 j 将可 能存在的可行网络考虑在内，改进“双向结合式”的拍卖式算法，提出并行连续型拍卖 式算法，成功运用于公交车干扰管理问题的研究。该算法的最大特点是并行计算，可以 用不同的处理器同时计算不同路径，并能够共享价格矢量，大大提高了求解的速度和结 果满意度。这一特点决定了拍卖式算法在计算大型网络模型方面更具优势，随着网络规 模的扩大，其计算速度优势愈加明显。但该算法相对适用于解决网络弧值为正的情况， 在解决弧值为负的时候仍存在困难，需要其它算法的支持。 ( 3 ) 干扰管理在物流配送方面的应用研究进展 目前，国内外干扰管理的研究涉及到航空【5 3 5 4 1 、供应型5 5 - 5 6 1 、项目管理【5 7 - 5 9 1 等多个 领域，在航空领域的研究成果显著并且具有代表意义。本节将主要介绍在物流配送领域 的研究进展。 干扰管理在物流配送方面的研究起步较晚，研究进展也较其他领域有所落后。物流 配送方面的主要研究成果有： z e i m p e k i s 等1 6 0 j 提出了处理城市物流配送中干扰问题的管理系统框架，对物流配送 中的干扰问题进行了分类，并设计了解决车辆延迟问题和车辆抛锚问题的管理系统，系 统的核心是决策支持模块，当干扰发生后，目标函数为延迟费用最小和被服务的客户数 量最大。 大连理工大学硕士学位论文 p o t v i n 等【6 l 】以快递公司为研究对象，针对经常遇到的新增客户需求和行驶时间干扰 的问题，构建以车辆行驶时间、客户延迟服务时间及返回中心库房延迟时间加权总和最 小的目标函数。在模型求解中，提出了时间窗容忍度的概念，即遇到干扰后车辆允许有 一定的延迟时间。实验表明，在偏离原计划的情况下，对原计划进行一定程度的容忍常 常会获得更好的结果。 h u i s m a n 等 4 2 1 提出解决具有旅行时间延迟的多车场车辆调度问题的鲁棒性方法，运 用聚类一重排算法，按车场对客户进行分配，将多车场问题转化为单车场问题。其目标 函数包括三部分：车辆使用数、客户服务时间延迟数的百分比及延迟费用。 l i 等【6 2 】提出解决具有单供货点的车辆重新调度问题的决策支持系统，其目标函数为 车辆运行费用和延迟费用成本最低。其原理为干扰事件发生后，从配送中心安排后备车 辆来解决受干扰的线路。他们建立了重新调度的数学模型，目标函数为车辆运行费用和 延迟费用成本最低。设计了后备车辆处理方案，并采用城市中固体废物回收处理的车辆 调度问题验证了该方法的可行性。 h u 和t i a n 6 3 j 采用了w a s p l i k ea g e n t 策略来解决d v r p ，将d v r p 看作是两阶段问 题，第一阶段决定何时响应客户需求，第二阶段采用优化算法针对客户需求变动重新生 成配送路线。 王明春等【4 3 】针对v r p t w 中发生的需求量变动和时间窗的变化，将其干扰管理模型 的目标函数定义为网络运行的费用及与原计划偏离所需费用的加权和，采用交换法与禁 忌搜索算法相结合的方法对干扰管理模型进行求解。实验表明，他们提出的方法能够在 较短的时间内对干扰进行恢复。 王旭坪等【6 8 】针对多车场v r p t w 中有顾客时间窗和发货量变化的问题，建立目标函 数中包括客户满意度、道路偏离两方面，采用字典序多目标优化模型，并通过遗传算法 验证了其有效性。 1 2 3国内外同类研究总结 在物流配送车辆路径问题方面：针对确定性v r p 国内外的研究相对比较成熟，包 括不同类型问题的界定、模型的构建己形成了一套较完备的理论体系；在求解算法方面， 已经得到了许多优秀的算法，现在研究的热点集中于提高算法的效率，包括并行计算等 方面的研究。确定性v r p 的相关理论为非确定性v r p 奠定了良好的理论基础，并提供 了许多具有参考价值的解决方案与算法。 非确定性v r p 是目前物流配送领域研究的热点和难点问题。其研究主要集中于模