（管理科学与工程专业论文）物流配送受扰延迟问题的干扰管理模型研究.pdf

大连理工人学硕士学位论文 摘要 物流配送是整个物流体系中最基本的业务环节，如何及时而满意为客户提供配送服 务是物流服务提供商关注的重要问题。但是在实际的物流活动中，车辆路径条件往往存 在着大量不确定性，如交通事故、道路堵塞、车辆故障以及天气变化等诸多不确定因素， 都会导致道路条件发生变化。这些变化常常超出物流服务提供商最初制定配送计划所设 想的问题范围，使正常的物流活动受到延迟，从而阻碍了原有物流计划的顺利完成，给 物流企业带来负面影响。如何有效的对干扰事件进行处理，使干扰对系统的扰动程度最 小成为物流配送问题的难点。 干扰管理作为一种实时处理干扰事件的方法论，主要针对经常性干扰事件的处理和 管理。它根据各种实际问题和干扰事件的性质，建立相应的优化模型和有效的求解算法， 为决策者在干扰事件发生后及时地提出最优调整计划。本文正是基于干扰管理这一新理 念，以系统扰动最小为目标，对物流配送中发生概率较高、较有代表性的受扰延迟问题 的干扰管理模型进行了研究。本文的主要研究工作如下： ( 1 ) 在对物流配送受扰延迟问题的扰动度量分析的基础上，提出客户满意度、路径 变动和系统扰动的度量方法，并提出物流配送受扰延迟问题的解决思路。 ( 2 ) 根据本文所提出的扰动度量方法，以带有硬时间窗的单车物流配送车辆路径问 题为研究背景，构建物流配送受扰延迟干扰管理模型。这是本文研究的核心。 ( 3 ) 运用混合蚁群算法对干扰管理模型进行求解，实现快速实时生成物流配送受扰 延迟问题干扰管理调整策略。 ( 4 ) 基于本文提出的干扰管理模型，以某物流公司的物流配送受扰延迟问题为实验 算例，验证了干扰管理模型及算法的有效性。 本文提出的物流配送受扰延迟问题的干扰管理模型，有效降低了具有延迟影响的干 扰事件给物流配送计划带来的扰动，最大限度减小客户满意度的下降和成本的损失，对 实际物流配送干扰管理具有一定的参考价值和理论意义。 关键词：物流配送；受扰廷迟；干扰管理；模型 物流配送受扰延迟问题的干扰管理模型研究 d i s r u p t i o nm a n a g e m e n tm o d e lo fd e l a y i n gp 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 n 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 ep r o b l e mw h i c hi sh o w t op r o v i d et i m e l ya n ds a t i s f y i n gs e r v i c e st oc u s t o m e r sh a sb e i n gt h ef o c u st ol o g i s t i c s c o m p a n i e s 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 ee x i s tn u m e r o u su n c e r t a i n t i e s u n c e r t a i n e v e n t ss u c ha sc a ra c c i d e n t ，t r a f f i cj a n ，v e h i c l eb r e a k d o w n ，b a dw e a t h e re t c ，a l w a y sc h a n g e t h ed i s t r i b u t i n gc o n d i t i o n s t h e s ec 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 r e g u l a r l y ，t h e yl e a dt os e r v i c ed e l a y so rc a n c e l l a t i o n s t h eo r i g i n a lp l a ni sd i s r u p t e di nt h i s t i m e ，a n dn e g a t i v ee f f e c t st ol o g i s t i c sc o m p a n i e sf o l l o wb e h i n d o nt h i so c c a s i o n ，h o wt od e a l w i 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 a 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 tc h i e f l y s e t t 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 oe m b o d i e ds c e n a r i o sa n d c h a r a c t e r so fd 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 o g e n e r a t eo p t i m a la a j u s t m e n ts c h e m ef o rd e c i s i o nm a k e r sa ss o o na sp o s s i b l e b a s e do nt h e c o n c e p to fd i s r u p t i o nm a n a g e m e n t ，t h ed e l a y i n gp r o b l e mi ss o l v e d ，w h i c hi sk n o w n a st h e m o s tt y p i c a la n df 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 w i t ht h eg o a lo fm i n i m i z i n gt h e d e v i a t i o n sf r o mt h eo r i g i n a lp l a n ，t h ed i s r u p t i o nm a n a g e m e n tm o d e lo fd e l a y i n gp r o b l e mi n l o g i s t i c sd i s t r i b u t i o ni sc o n s t r u c t e d n 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 ) 0 nt h eb a s i so ft h ed e v i a t i o nm e a s u r e m e n ta n a l y s i s ，t h em e a s u r e m e n tm e t h o d so f c u s t o m e rs a t i s f a c t i o n ，r o u t ea l t e r a t i o na n ds y s t e m a t i cd e v i a t i o na r ep r e s e n t e d t h e nt h e s o l u t i o no ft h ed e l a y i n gp r o b l e mi nd i s t r i b u t i o ni sc o n f i r m e d ( 2 ) a c c o r d i n gt o t h em e t h o d so fd e v i a t i o nm e a s u r e m e n t ，t h ed i s r u p t i o nm a n a g e m e n t m o d e lo fd e l a y i n gp r o b l e mi nl o g i s t i c sd i s t r i b u t i o ni sc o n s t r u c t e du n d e rt h eb a c k g r o u n do f s i n g l ev e h i c l er o u t i n gp r o b l e mw i t hh a r dt i m ew i n d o w t h i si st h ec o r eo ft h ep a p e r ( 3 ) 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 ea l g o r i t h mo fh y b r i da n tc o l o n y s y s t e m ，a n d o b t a i nt h ed 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 ( 4 ) a p p l yt h em o d e l a n da l g o r i t h mt oac a s ew h i c hc o m e sf r o mal o g i s t i c sc o m p a n y t h e r e s u l ts h o w st h a tt h ep r o p o s e dm 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 t h ep r e s e n t e dd i s r u p t i o n m a n a g e m e n t m o d e lo f d e l a y i n gp r o b l e m i n 1 0 9 i s t i c s d i s t r i b u t i o ni sp r o v e dt ob ee f f i c i e n ti nm i n i m i z i n gt h ei m p a c t so fd i s r u p t i o ne v e n t sw h i c h r e s u l tt os e r v i c ed e l a y s i tr e d u c e st h ed r o po fc u s t o m e rs a t i s f a c t i o na n dt h er i s eo ft h ec o s t s k e yw o r d s ：l o g i s t i c sd i s t r i b u t i o n ；d e l a y ；d i s r u p t i o nm a n a g e m e n t ；m o d e l 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定 ，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 导师签名： 也学年月血日 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特另q 加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 z - 大学或者其他单位的学位或证书所使用过的材料。与我一同z - 作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：挝i 磷日期：塑空二丛二2 。 大连理工大学硕士学位论文 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 方法，这类方 法是从干扰事件发生后的状态出发，对整个系统进行重新调整和规划，通过对原方案实 施状态的全局优化调整，实现对干扰事件的快速响应。这类方法虽然能够得到最优调整 计划，但在实际操作中仍存在一些困难，例如，调整方案的实施可能需要耗费大量的时 空和人财物力，虽然能得到一个最优的调整计划，但它有可能触及原计划未考虑到的因 素，给系统带来巨大的扰动，新方案常常在实际中不可行。因此，有必要将原计划情形 考虑在内，通过局部优化调整策略，达到系统扰动最小的目的，同时兼顾偏差成本最低， 这就是干扰管理理念的基本内涵。 关于干扰管理问题，它是近年来国际上管理科学、运筹学和系统工程等领域备受关 注的新的研究方向，具有广阔的应用前景和重要的科学意义。干扰管理l l j 可定义为：在 计划开始阶段，用优化模型和求解算法得出一个好的运行计划；计划实施中，由于内外 部不确定因素导致干扰事件的发生，使原计划变得不可行，需要实时地产生新计划。新 计划要考虑到原来的优化目标，同时又要使干扰带来的负作用最小化。该定义可分为三 物流配送受扰延迟问题的干扰管理模型研究 层意思来理解：制定并执行最优或次优计划；0 识别干扰事件并评估干扰的影响；0 对系统扰动最小的情况下，形成有效的干扰管理新方案。 本文正是以这一研究思路为基础，以物流配送中最常见、发生频率最高的受扰延迟 问题为研究对象，构建相应的优化模型和有效的求解算法，为决策者在干扰事件发生后 及时地提出最优调整方案。在此基础上，根据客户点的需求特点，以客户满意度扰动最 小作为干扰管理最重要的目标，同时兼顾协调车辆行驶路径与干扰偏差成本两个因素， 在满意度扰动尽量小的情况下，减小路径变化和偏差成本增量，建立相应的干扰管理模 型和求解算法，真正实现系统扰动小、可行性高、及时、快速的物流配送受扰延迟问题 干扰调整方案。 1 2 国内外相关研究综述 物流配送受扰延迟问题的干扰管理模型研究要以物流配送车辆路径问题为研究背 景，针对车辆路径条件变化引起的受扰延迟闯题，运用干扰管理理念，构造干扰管理模 型，并通过相应算法实现有效的干扰管理。这其中涉及到两大方面的问题：( 1 ) 物流配 送车辆路径问题；( 2 ) 干扰管理问题。因此以下从这两大方面对国内外相关的研究情况 进行综述。 1 2 1物流配送车辆路径问题国内外研究现状 ( 1 ) 物流配送车辆路径问题的描述及其分类 物流配送车辆路径问题是d a n t z i g 和r a m s e r t 2 1 于1 9 5 9 年提出的，它可定义为：运输 车辆从一个或多个设施到多个地理上分散的客户点，优化设计一套货物流动的运输路 线，同时要满足一系列的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限 制、行驶里程限制、时间限制等) 。其前提条件是客户点位置和道路情况已知，由此确 定一套车辆运输路线，以满足目标函数( 如路程最短、费用最小、时间尽量少、使用车 辆尽量少等) 的要求。 根据研究重点的不同，物流配送车辆路径问题有多种分类方式： 按任务特征，有装货问题、卸货问题、装卸混合问题； 按车辆载货状况，有满载问题和非满载问题； 按车场数目，有单车场问题和多车场问题： 按车辆类型，有单车型问题和多车型问题； 按配送任务是否有时间限制来区分，有一般车辆路径问题和带时间窗的车辆路径问 题，其中时间窗又可分为硬时间窗和软时间窗。硬时闻窗是指任务必须在给定的时闻范 围内完成，否则得到的解视为不可行解，软时间窗指如果任务不能在给定的时间范围内 一2 一 大连理工大学硕士学位论文 完成，则同时给予一定的惩罚； 按已知信息特征，有确定性问题和非确定性问题； 按优化目标数，有单目标问题和多目标问题。 物流配送车辆路径问题属于n p h a r d 问题，考虑的分类属性越多，问题越复杂，其 模型构造和算法也有很大差别。 ( 2 ) 物流配送车辆路径问题的模型及其算法研究进展 由于本文的研究主要以不确定性事件的发生为中心展开，因此着重就确定性车辆路 径问题和非确定性车辆路径问题的研究情况进行综述。 确定性车辆路径问题的模型及其算法 确定性车辆路径问题是指：在路径规划开始之前，规划人员对有关路径规划的所有 信息都是清楚的；在路径构建以后，与路径规划有关的信息不再变化f 3 l 。所谓的相关信 息，包括顾客的所有特征，如顾客的地理位置、所需服务时闻、每个顾客的需求量等。 ( a ) 确定性车辆路径问题模型 按照构造模型时的出发点，确定性车辆路径问题的模型主要有三类：车辆流模型、 货物流模型和集分割模型。 车辆流模型体现了系统中车辆的最优运行方案，它使用图的每条弧或边来对应一个 整数变量，用来计算一辆车经过弧或边的次数1 4 】。这是一种较常用的模型，特别适合于 其解可以表示为与弧相联系的费用和的情形，且当最有关的约束条件是关于在线路内部 客户之间的直接转移时，可以通过对弧集合和费用的适当定义来有效地建模。但这类模 型在处理某些含有其它多个约束条件的实际问题时存在一定的缺陷，例如当一个解的值 取决于线路上顶点的次序或该线路上的车辆类型时。此外，当另外的运营限制是严格的 时候，车辆流模型的线性规划松弛可能是很弱的。 货物流模型明确地考虑通过每条路径的货物量，在这类模型中，每条弧或边对应着 另一个整型变量，用来表示由车辆所运送的经过该路径的货物流量1 5 】。这类模型的求解 与车辆流模型相似，但发展较慢，直到最近才被用来作为构造求解确定性车辆路径问题 精确算法的基础。 集分割模型通常使用大量的0 1 变量，每个都与一条不同的可行路线相联系。b a l i n s k i 等 6 1 最早利用集分割模型来研究车辆路径问题。然而，这类模型与一般的动态规划模型 有着相同的缺点，即使对于规模较小的问题，模型的变量数在大多数慵况下亦是天文数 字。除此之外，确定目标函数中的值往往先要求解大量的n p 难题，这也给问题精确求解 带来困难- 采用列生成技术可部分解决这些困难，如d c s r o s l c r s 等1 7 】采用列生成技术求解 了规模较小有容量和时间窗约束的确定性车辆路径问题。 物流配送受扰延迟问题的干扰管理模型研究 ( b ) 确定性车辆路径问题求解算法 求解确定性车辆路径问题的算法一般分为精确算法和启发式算法两类。 到目前为止，己提出的精确算法的种类较多，具有代表性的研究成果主要有：f i s h c 一 提出的k - 树法；p a d b e r g 等1 9 l 的分枝剪枝法if e m e r o 等【1 0 j 的修正拉朗日松弛及子梯度优 化方法；l o r c n a 等对列生成方法的改进；b p o n c 等【”l 的含有双下标变量约束松弛算法； f i s h e r 等【1 w 还研究了有容量和时间窗约束v r p 的- - - 下标变量算法。 精确算法主要适用于解决问题结构比较清晰、所含各元素之间的关系明确、边界清 楚的良性结构问题。这些问题有判定解的可行性和最优性( 或满意性) 的明确准则，得出 的解能反映解决问题的可行方案，求解工作所需的计算量不大，所需费用不多。另外， 还有许多实际的v r p 不具有良性结构，并且有些闯题不存在严格最优解( 例如，目标之 间相互矛盾的多目标决策问题) 。或者有些问题要得到最优解需花费过大的代价，当采 用精确算法求解这三类问题时难以得到理想的效果，因此这三类问题的解决就需依赖于 启发式算法 求解确定性车辆路径问题的启发式算法很多，按传统的启发式算法分类，以下着重 综述构造算法、两阶段法和改进算法三大类启发式算法。 构造算法是根据一定的准则，每一次将一个不在线路上的点增加进线路，直到所有 的点都被安排进线路为止。如a 蝴w i i 曲d l q 提出的d w 节约算法、g i l l e t t 和m i l l e r t b 提出的扫描算法以及s o l o n 【”】提出的最近邻启发式算法都是构造启发式算法中最为经 典的算法。 两阶段法的基本做法是在第一阶段得到一可行解，第二阶段通过对点的调整，在始 终保持解可行的情况下，每次迭代产生一个解用以替代原来的解，力图使目标函数值得 以改进，一直继续到不能再改进目标函数时为止。如r e n a u d 等【1 1 的p e t a l 算法、l i n t l q 的 2 - o p l 和3 - o p t 交换、o j l 9 1 提出t 拘o r - o p t 交换、t 0 t h 和v i 窟0 i 驯提出的聚类一重排算法等。一 些基于数学规划的算法也属于两阶段法，酋先把问题表达成一个数学规划模型，根据其 模型的特殊构形，利用一定技巧进行分划，进而求解易于处理的子问题。如k o h l 等【丑1 先利用h 掣画松弛技术将有时间窗的车辆路径问题变为较简单的指派问题，然后用 列生成技术来获得问题的近似解。另外还有一些两阶段算法在求解过程中常常采用交 互式优化技术，把人的主观能动作用结合到问题的求解过程中。 改进算法是从一初始解开始通过对当前的解进行反复地局部扰乱以达到较好的 解。基于启发式的并行算法和亚启发式算法都属于此类。亚启发式算法包括禁忌搜索算 法、模拟退火算法、神经网络和遗传算法等方法。2 0 世纪9 0 年代以来，这些亚启发式算 法的应用成为车辆路径问题求解算法研究的新趋势。如g e n d r e a e 等i 捌将禁忌搜索算法应 大连理工大学硕士学位论文 用于车辆路径问题的求解，并取得了较好的效果。另外，模拟退火算法、神经网络以及 遗传算法等亚启发式算法也已经较成功地解决了一些确定性车辆路径问题。 非确定性车辆路径问题的模型及其算法 非确定性车辆路径问题是指：在路径规划开始之前。计划人员并非确切知道有关路 径规划的所有信息，部分信息可能是不确定的、模糊的，甚至是未知的；初始路径构建 以后，信息可能会发生变化1 3 】。很明显，与确定性车辆路径问题相比，非确定性车辆路 径问题是个更一般化的问题非确定性车辆路径问题又可分为模糊车辆路径问题 ( f v r p ) 和随机车辆路径问题( s v p p ) 。 ( a ) 模糊车辆路径问题( f 、 有人把这类闯题定义为标准的车辆路径闯题，因为真实车辆路径闯题的需求往往是 模糊的和不确定性的，这种问题很难找到满意解。 t e o d o r o v i c 等【捌人是最早着手研究这类问题的人。他以模糊数表示客户点的需求信 息，以倾向度为基础建立模糊判定规则，其核心是基- = s w e e p 算法。并省略t s w e c p 算 法的第二阶段，即初始化子路径后对它们的优化过程。 b e r t s i m a s 2 4 - 2 s 1 提出了两种重新优化策略分别为策略a 和镱略b 。在策略a 下，车辆按 同样固定的顺序作为一个预先安排的车辆优化顺序经过所有客户点。然而，车辆仅服务 有需求的客户点，但要经过无需求的客户点，总的期望距离等于预先制定路线的固定长 度与由于车辆容量约束而便车辆返回仓库中心造成的距离迂回长度之和。在策略b 下， 无需求的客户点可以不经过，图1 1 显示了两种策略的区别( 假如每辆车的容量限制是2 ， 有6 个潜在客户需要服务，需求量为0 或1 个单位，且客户点i ，3 没有需求) 。策略b 跳过 了这些客户点，而策略越经过了所有客户点。这两种策略可如下解释：策略a 可用于客 户点需求量得到确定之前，车辆已经到达客户点的情况；策略b 可用于车辆到达客户点 之前，该点的实际需求量已经得到确定的情况。 祝崇隽、刘民、吴澄等【硐以模糊可能性分布，建立了车辆路径问题基于置信度的三 下标流模型，并提出了基于可能性分布的2 - o p t 算法。该算法引入了伪出发点，建立了以 置信度为基础的判定规剐，以遍历为终止条件。从而在全局层次上进行优化，同时避免 过多地扩大搜索空间，该算法已被验证可解决较大规模的问题( 大：j = 2 0 0 个客户点) 。 郭耀煌等i 明根据组合优化、排队论和几何概率方面的知识，分析了需求密集情况下 的一类随机动态v r p 的下界，并研究了一种运作策略的渐近性。 张建勇等i 碉则遥过引入模糊预约时间的概念，从顾客满意度的角度研究了模糊不确 定信息条件下的多目标车辆优化调度问题。后来。他们通过弓l 入决策者主观偏好的概念， 提出了解决模糊需求信息条件下v r p 的一种基于模糊可能性的混合遗传算法，并在最小 一5 一 物流配送受扰延迟问题的干扰管理模型研究 化使用车辆数与车辆行驶距离的目标下，通过随机模拟研究了决策者的主观偏好对最终 决策目标的影畴。 2 2 6 a ) 磺兜安椿自q 缝路 ”薰培a c ) 攘喀b 图1 1f v r p 两种策略的比较示例 f i g 1 1i i i u s i o t mo fd 越皓 n tm a t e g i e sf o rf v r p c o ) 随机车辆路径问题( s v r p ) 如果车辆路径问题中的某些因素是随机的，例如旅行时间的不确定、需求量未知、 颐客是否存在也未知等随机因素，裁形成了随机车辆路径闰题。因此随机车辆路径被人 们看成模糊车辆路径问题的扩展。对这种类型的问题，目前出现的算法大部分可以归纳 为以先验序列为基础的方法。这类问题属于二阶段式求解的问题：在信息不完全( 随机) 的情况下确定先验序列；在获得确定性信息的情况下进行决策。例如，用两阶段方法来 考虑含有随机需求的车辆路径问题时，第一阶段设计出的m 条车辆路径经过每个顾客点 恰好一次，第一阶段结果出来之后，顾客实际需求被确定。顾客的总需求可能超过车辆 容量约束限制，这时第一阶段的设计线路可能变得不可行。第二阶段的一个简单策略可 以按原设计线路行驶，直到车辆容量约束打破，此时再返回仓库中心卸载或补充需求物 品，然后返回到路径失败的地方重新开始顾客服务。 随机模型的选择基于两点：第一阶段的成本和第二阶段的期望成本。先验序列的确 定方法又有两类：一类是按二元可能性理论来确定。另一类则是基于机会约束规划。 一6 一 大连理工大学硕士学位论文 第一类方法中，假定需求分布是二元的( 即在第f 点有单位需求的概率为足，则没有 单位需求的概率为1 一露) 和离散的。根据该假定，可推出先验序列的期望长度、相应的 上下界和渐进特性。l a p o 蹴婵】基于l s h a p e d 方法，提出一个精确算法，并实验求解了客 户点小于5 0 的问题。 另一类方法是s t e w a r t 等刚分别使用机会约束规划，在一定的假定条件下，将随机车 辆路径问题等价转化为确定性车辆路径问题，并找到了解的界，其方法的核心是让出错 返回的概率不超过一定的界限。机会约束规划模型均以确定性车辆路径问题的含有三下 标变量和二下标变量模型为基础，添加可能性约束条件和惩罚函数后建立起来的。所用 的算法也与确定性问题求解算法有不少相似之处。d r o tm 1 3 1 1 就是在建立三下标流机会 约束规划模型和惩罚函数模型后，利用c l a r k w t i g h t 节约算法求解随机车辆路径问题。 第二阶段的策略为：按照先验序列，跳过需求为零的客户，直接访问下一个客户， 如果车辆负荷超过了车辆最大载重量，则返回出发点卸载，并回到出现超载的地方，继 续提供服务。 物流配送车辆路径问题属于n p h a r d 问题，其求解相当复杂，而含有不确定信息的 车辆路径问题的求解显然难度更大。但是这种不确定性的解决方法主要是预先优化法， 即调度者根据未来服务请求、顾客需求、旅行时间等预先制定出基于模糊信息的一种或 多种路径。也就是说，物流配送计划本身就是不确定的，必须随实际情况变化随时做出 优化调整。这种方法在实际运行中的可行性是一个值得质疑的问题，由于系统随时变化， 必然带来巨大的计算量，且容易混淆服务命令，给系统带来混乱和巨大的扰动。因此， 有必要采取更有效的措施，引入干扰管理理念来处理这种不确定性，提高方案的可行性。 1 2 2 干扰管理及其模型与算法国内外研究进展 ( 1 )干扰管理理念的形成与发展过程 关于干扰管理，目前学术界尚无统一明确的定义和界定。但国内外学者也基本形成 了共识。美国学者g a n gy u l l 】对干扰管理的定义为：在计划开始阶段，用优化模型和求 解算法得出一个好的运行计划；计划实施中，由于内外部不确定因素导致干扰事件的发 生，使原计划变得不可行，需要实时地产生新计划。新计划要考虑到原来的优化目标， 同时又要使干扰带来的负作用最小化。c l a u s e n 等【3 2 】也基本是把干扰管理限定在使变化 回归到最初计划这一基本目标之上，使系统扰动最小。国内学者陈安等瞄j 认为干扰管理 是能够使事件回到原始状态的一种管理方法，主要面对的是稍微偏离原计划状态的事 件，而这样的偏离只是一种微小的偏离，没有造成很大的负面影响，可以通过积极的管 理进行纠正。 一7 一 物流配送受扰延迟问题的干扰管理模型研究 本文认为，干扰管理需要根据实际问题和干扰事件的性质建立相应的干扰管理模型， 快速、及时地给出处理干扰事件的最优调整方案；这个调整方案不是针对干扰事件发生 后的状态完全彻底地重新进行建模和优化，而是以此状态为基础快速生成对系统扰动最 小的调整方案，该方案适当考虑费用问题，但并非费用最省。 作为一种实时处理干扰事件的方法论，干扰管理与其它解决不确定性问题的理论和 方法存在本质区别，主要体现在以下几个方面： 管理方法与s c h e d u l i n g 和f e s c h e d u l i n g 方法有着明显的区别。s c h e d u l i n g 和 心s c h e d u l i n g 方法虽然能够实现费用最低，但在策略上对整个系统进行重新规划和安排， 即对原计划的全局优化调整，尽管能得到一个最优的干扰调整方案，但可能要耗费大量 的时空和人财物力，从而导致系统的扰动较大甚至使新方案不可行。我们认为，干扰管 理方法是根据干扰事件产生的状态对原方案的局部优化调整，目标是使系统扰动最小并 适当兼顾节省费用，但并非费用最小。 应急管理的研究范畴不同。干扰事件按照发生的频率、产生的影响和处理时间 的及时性和紧迫性，可以分为经常性的干扰事件和突发性的干扰事件针对突发性干扰 事件进行的研究应属于应急管( e m e r g e n c ym a n a g e m e n t ) 研究的范畴，目前主要研究成 果集中在应对策略和预案 3 4 - 3 7 1 方面，而且更注重突发事件的宏观影响和应急管理策略方 面的研究 3 s - 4 0 。干扰管理主要针对经常性的干扰事件，如航空中的天气糟糕、物流中的 交通堵塞、生产制造中的原材料短缺等事件，研究消除其干扰的策略和措施。 虽然在电工电子学领域已有大量的消除电子系统干扰的抗干扰手段和成果，但 这类干扰问题与经济管理领域的干扰问题有着本质的不同，难以移植应用。 定性决策理论是一种数学决策理论，主要应用于因信息不完整和信息不对称造 成的不确定性问题对工业、农业、交通运输和国防事业等领域进行科学合理的预测。干 扰管理方法侧重于事后通过积极的措施来调整系统，以减小干扰事件对系统造成的负面 影响。 近年来国内外干扰管理方面的研究成果多侧重模型和算法的研究，涉及到航空、供 应链、物流、项目管理等多个领域。美国学者g a n gy u 在航空领域的研究成果尤其具有 代表意义。他针对航空客运中经常遇到的干扰事件，建立干扰管理模型，开发基于启发 式算法的求解模型的c r e w - s o l v e r 系统。该系统在美国“9 1 1 ”事件、暴风雪事件等航运 干扰管理中，为美国大陆航空公司( c o n t i n e n t a la i r l i n e ) 节省了大笔费用，取得了显著的 经济效益。国内学者马辉等【4 l 】讨论了航班调度鲁棒策略和受扰恢复策略，并对比研究了 两种策略的数学模型和算法。p h i l i pt e v e r s l 4 2 以及s m h o n g - m i n h 等【4 3 i 针对如何在供 应链和物流活动中有效降低干扰事件造成的新增成本的方法的研究。p i t ub 等【4 4 _ 4 5 l 在多 大连理工大学硕士学位论文 种假设条件下，对车辆实时调度的干扰管理优化模型及算法进行了探讨。已有研究表明， 干扰管理模型是较为复杂的模型，求解十分困难，属于n p h a r d 问题，下面将着重针对 干扰管理模型和算法方面的研究情况展开分析。 ( 2 )干扰管理模型及其算法的研究进展 根据干扰事件的性质以及实际问题所属的领域，国内外学者尝试了很多种类的模型 来抽象问题。与车辆路径问题模型相似，目前研究的干扰管理模型也主要分为图模型和 数学模型两大类。 图模型 目前干扰管理图模型主要有三类：时空网络模型o i m e - s p a e en e t w o r km o d e l ) 、干扰 恢复博弈树模型( r e p a i rg a m et r e em o d e l ) 和基于p e r t 图( p r o g r a me v a l u a t i o na n d r e v i e wt e c h n i q u ec h a r t ) 的干扰管理模型。 时空网络模型o 枷c s p a n e t w o r km o d e l ) 是一种描述组成网络各要素之间关系的 网络流模型。该模型由h a m 等闱引入航空领域用于解决机组调度问题，其后a h m a d l j a t r a h 等h 7 】将该模型进行修改和扩展，将成本最小网络流问题抽象，构造出基于时空网 络图模型的线性整数规划模型。g a n gy u 等1 1 l 在航空领域的航班调度干扰管理问题的研 究中，在诸如机器故障、天气影响等干扰事件发生造成正常航班取消或延迟的情况下， 在时空网络图上增加虚拟的延迟航班和保护航班作为干扰调整手段，并相应的设定这些 虚拟航班的运作成本和保护费，大大降低干扰造成的损失。 干扰恢复博弈树模型( r e p a i r g a m e t r e e m o d e l ) 是计划调度模型的一种形式，该模型 以博弈树g - ，e ，j 1 ) 为根基树，将结点分为，k 。和屹。三类，且 巧似u u 矿v o - v ，每个结点的关联值定义为h ：y 一砜，该博弈树的值定义为 1 ，k 时的极小极大值m i n i m a x ：v 一正。模型的目标函数为：( g ，p ，占，$ ) ，即深度 为f 的博弈树g - ，e ，g + ，) 时的极小极大值m i n i m a x 的累积运算结果。其中，p 为该 博弈树g 的叶子集元素，g 为期望成本，为干扰恢复诱发成本，j 为此时的系统状态。 干扰恢复模型由j a n e h r h o 蹲l 柏j 提出，以博弈树搜索思想为核心，结合运筹学优化工具， 从增强原计划调度安排鲁棒性的角度对干扰管理问题展开研究。该研究以航空调度领域 为研究背景，提出了一种普遍适用予干扰管理的方法论。 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 图模型是一个有向 一9 一 物流配送受扰延迟问题的干扰管理模型研究 网络图，项目涉及的关系和活动分别用有向弧( a r c s ) 和节点( n o d e s ) 表示。用这种方法把关 系和项目描绘出来构成p e r t 图，还可以很快找到项目的关键路线，利于有效地控制和 管理项目进度。由于活动时间的不确定性，项目的进展必然受到干扰。l i p h l g 等 4 9 采用 p e r t 图建立了非确定性项目网络的风险调度预测模型，提高了预测的准确性。罗守成削 对p e r t 图中各项活动的延误对总工期和总费用的影响进行了研究，提出按照各项活动 的重要性而不仅仅根据延误时间长短来计算延误时间惩罚的方法。 综合以上的分析可以看出，网络图模型的优点是直观性强，容易理解。但图模型对 参数的容纳能力有限，能够使用的求解方法不多，因此该类模型缺乏表达复杂问题的能 力。 数学模型 随着干扰管理的逐步发展和深入研究，针对不同的问题条件，其数学模型也呈现出 不同的模型形式，以干扰造成的偏差成本( d e v i a t i o nc o s t ) 为评估标准之一的数学模型就 是其中的典型代表。式( 1 1 ) 是无干扰时数学模型的一般形式。当干扰发生时，目标函数 和可行解集发生相应的变化，通过多个目标之间的权衡优化达到总目标的优化。根据目 标优先级的高低，采用字典序目标规划结构( l e x i c o g r a p h i cg o a lp r o g r a m m i n gs t r u c t u r e ) 。 式( 1 2 ) ( 1 3 ) 是含有两重优化目标的数学模型，两式分别表示不同的优先级目标规划。 m j n ，仁) s u b j e c tt ox e x 无干扰时目标函数的一般形式 约束条件 n f i n l e xn ：g ( 4 + ，4 一) p 2 ：，g ) s u 嘶e c t 4 t + o ，口x ：2 k 4 - 孑一a i 善。) x口+ 一善o 4 + ，口一2 0j 受扰后含有两重优化标准的目标函数 约束条件 r n j u l l e x 用：夕p 2 ：9 0 + ，口。) 受扰后含有两重优化标准的目标函数 s u b j e c t t ox 萱 1 a ：二：0 ：一i 亍约束条件+ ，4 2 j ( 1 1 ) ( 1 2 ) ( 1 3 ) 大连理工大学硕士学位论文 学者g a n gy u 和x i a n g t o n go i 将该模型应用于最短路问题干扰管理的研究中i “。将 g ( a + ，口一) 露+ | 口+ l + 七一k 。i 含义具体化，根据干扰管理理念来选定系统扰动最小的方案作 -， 为最终方案，即最终的干扰管理方案在所有满足约束条件的方案中，路偏离最小，路线 成本最小。 数学模型的特点是：( a ) 容量大。该类模型对参数的容纳能力强，能够表达大规模的 复杂问题；灵活性强。随着实际应用需求的变化，目标函数和约束条件会随着干扰闯 题条件的变化而发生改变。但这类模型对问题的抽象程度高，从模型本身很难识别问题 原型及其所属领域，且模型求解得到的数据不带任何领域知识和信息，必须把这些数据 还原成用户能够理解的形式，造成模型使用复杂化。 ( 3 ) 干扰管理模型求解算法研究进展 在模型构建的基础上，学者们普遍采用的解决干扰管理问题的求解算法主要分为两 大类：精确算法( e x a c ta l g o r i t h m ) 和近似算法( a p p r o x i m a t ea l g o r i t h m ) 。常用的近似算 法大致有两类；启发式( h e u r i s t i c s ) 算法和拍卖式( a u c t i o n ) 算法。 精确算法 精确算法适合于求解小规模结构较清晰的干扰管理问题。对于复杂的干扰问题，如 果采用精确算法获得最优解通常需要花费很大代价，且难以得到理想结果，因此，解决 干扰管理问题主要依赖于近似算法。下文就近似算法中的启发式算法和拍卖式算法做简 要分析。采用精确算法对干扰管理问题进行研究的主要研究成果有：早期t e o d o r o v i c 等 i 捌采用分枝定界法( b r a n c ha n db o u n d ) 求解了基于网络图的航班延迟的干扰管理模型； 后来w e i 等p 1 - 5 2 l 对分枝定界法进行了改进，用于求解机组干扰恢复整数规划数学模型； k o u v e l i s 等1 5 3 - 5 4