（运筹学与控制论专业论文）基于鲁棒优化的应急管理下的车辆路线问题的研究.pdf

关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学柱申请。本人郑重声明：所呈交的擘位论文是 本人在导师酌指导下独立完成的，对所研究妁课题有新的见解。据我所知，除 文中特别加皑说明、标往和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过酌材料。与我一同工作酌同事对本研充所儆的恬何贡献均已在论文中作 7 明确酌说明井表示7 谢意。 学住中请人( 学位论i 作者) 荽名 孙掣一 2 0b 7 年石 月7 臼 关于学位论文著作权使用授权书 本人经河南大擘审核批准授子硕士学位。诈为学位论文酌作者本人完全 7 解并同意河南大学有关保留、使用学位论文的要求，即河南太学有权向国家 图书馆、科研信息机构、数据收集机构和奉校图书馆等提供学拉论文( 纸质叉 本和电子艾本) 以供公众检索。查阈。本人授权河南大学出于宣扬、展览学校 学术发展和进矸学术交流等目酌，可d 采取影印、缩印、扫描和拷贝等复制手 段保存、正辅学位论文( 氟质丈本和电子文本) 。 ( 涉及保密内容酌学住论正在解密后适用本授权书) 学垃薮得者( 学位论夏作者) 签名：2 l ：牮 一一 z 。叩年6 月7 。 学位论文指导教师釜名：垄垒翅已垫 河南大学硕士研究生学位论文第1 页 摘要 论文主要研究了基于鲁棒优化的应急管理中的车辆路线问题( v e h i c l er o u t i n g p r o b l e m ，简称v r p ) 。 鲁棒优化作为研究不确定优化问题的一种新方法，受到了众多学者的青睐。 论文在对不确定优化问题分析的基础上，对鲁棒优化研究的代表人物s o s y t e r b e n y a l 和b e r t s i m a s 的研究成果进行了总结，重点对鲁棒线性规划和鲁棒离散优 化进行了阐述。研究了不确定优化问题鲁棒优化模型的建立，充分体现了其事先分 析的建模策略，即在问题的优化模型中充分考虑了参数的不确定性，使参数在所给 不确定集合内的所有实现均能满足问题的约束条件，而对其服从何概率分布没有要 求。此后，论文重点阐述了鲁棒优化研究的核心问题，即如何将所建立的鲁棒优 化模型转化为鲁棒对应模型，使初始的不确定优化问题转化为计算易处理的确定性 优化问题，从而采用优化软件对问题进行求解。 随着社会经济的高速发展，各种大规模的自然灾害和恐怖活动等一系列突发事 件同趋频繁，于是针对这些突发事件如何高效的进行应急管理就显得尤其重要。当 突发事件发生后，如何快速而及时的运送救济物资从而挽救更多的财产和生命，这 已经成为一个很重要的研究课题。本文在对已有方法分析的基础上，重点对应急管 理下的车辆路线问题中存在的难点，即需求和旅行时间的不确定性，进行了讨论。 从优化的角度对车辆调度问题进行分析，结合s o s y t e r 鲁棒优化研究框架，把需求 和旅行时间当作不确定参数，把未满足的需求和延迟时间总和的最小化当作目标， 建立了应急管理下的单仓库和多仓库的车辆路线鲁捧优化模型，即鲁棒0 一l 离散优 化。经过推导得到的优化模型的鲁棒对应式最终等价于一个混合整数规划。 编写精确的分枝定界和启发式的遗传算法，在其内完成上述混合整数规划的求 解。通过其实验结果进行比较，显示了本文算法在不同需求和旅行时间下的优异性 能，验证了所建立的应急管理下车辆路线鲁棒优化模型的可行性。 关键词：鲁棒优化车辆路线问题应急管理不确定需求不确定旅行时间 河南大学硕士研究生学位论文第2 页 a bs t r a c t 1 1 | l i st h e s i sm a i n l yf o c u s e s0 1 1t h er e s e a r c ho fv e h i c l er o u t i n gl r o b l e m ( v r p ) i n e m e r g e n c ym a n a g e m e n t o i lr o b u s to p t i m i z a t i o n r o b u s to p t i m j t 础o nh a sb e e nr e m a r k a b l eb y m a n yr e , 始a r e h e r sa san e wm e t h o df o r d e a l i n gw i t hu n e e r t a i ao p t i m i z a t i o np r o b l e m s a f l e fb a y i n ga na n a l y s i s 。o i lu l l c c r l a m o p t i m i z a t i o np r o b l e m s , t h et h e s i si n t r o d u c e st h ei s e a r e hr e s u l t so f s o y s t e r ，b e n - t a la n d b e r t s i m a s ，a n dm a i n l yh a sad e t a i ld i s e r i p t i o n0 1 3 r o b u s tl i n e a rl 竹o g r a m i n ga n dr o b u s t d i s c r e t e o p t i m i z a t i o n t h i st h e s i s a l s oi n t z o d u e e sh o wt om o d e lt h eu n c h a i n o p u m i z a t i o np r o b l e m sa r i dg e t st h er o b u s to p t i m i z l l t i o i lm o d c li n d i c a t i n gt h ep o l i c yo f p r i o r - a n a l y s i s t h a ti st a k i n gi n t ot h ep a r a m e t e ru n e e r t a i n ya c c o u n ti nt h eo t o t i m i z a i t o n m o d e l ，m a i d n gs u r eo f e o n s t a i n ts a t i s f a c t i o no nt h er e a l i z a t i o no fa l lt h ep a r a m e t e r st h o s e m a k cv a l u e si nt h eg i v e nu n c e r t a i ns e t , a n dn o to r d e r i n gt h ep a r a m e t e rt oo b 掣s 咄 p r o b a b i l i t yd i s t r i b u t i 咯a f t e rt l u i t , t h et h e s i sm a i n l yi n l l o d u c c st h ec o l ep r o b l e m , w h i e l a i sh o wt ot r a n s f o r mt h er o b u s to p t i m i z a t i o nm o d e li n t ot h er o b u s te o u n m o n a 1 1 l e p u r p o s ei s t ol l 砌o l mt h ep r i o ru n c e r t a i no p t i m i z a t i o n p r o b l e mi n t o at r a c t a b l e o p t i m i z a t i o np r o b l e m , w h i c h c a l lb es o l v e db yo p t i m i z a t i o ns o f t w a r e w i t ht h el a i g h - s p e c dd e v e l o p m e n to fs o c i a le c o n o m y , as e r i e so fl a r g e - s c a l ea b r u p t a f f a i r st a k ep l a c em o l eo t t e nt h a np a s t , s u c ha sv a r i o u sl a r g e - s c a l el l a t t r a ld i s a s t e ra l i d t e r r o ra c t i v i t ye t c h e n c e ，i ti sp a r t i c u l a r l yi m p o r t a n tt ot h e s ea b r u p ta f f a i r sh o wt ob e e t f i e i e n t l yc a r r yo ne m e r g e n c ym a n a g e m e n t w h e nt h ea b r u p ta f f a i r st a k e sp l a c e ，h o w d e l i v e rr e l i e fs u p p l i e sq u i c k l ya n di nt i m et os a v em o l ep r o p e r t i e sa n dl i f e 耵l i si s b e c o m i n g 如i m p o r t a n tp r o b l e m o nt h eb a s i so fa 1 1 a l r z i n gt h e m e t l a o d st h o s em e n t i o n e d a b o v e ，t h i st h e s i sm a i n l yd i s c u s s e st h ed i f f i c u l t yo ft h ev e l a i e l er o u t i n gp r o b l e mi n e m e r g e n c ym a n a g e n t ，w h i c hi st h eu n c e r t a i n t yo fd e m a n da n dt r a v e lt i m e s t h i st h e s i s a n a l y z e s v e h i c l e r o u t i n gp r o b l e m i n e m e r g e n c ym a n a g e n t f r o mt h e p o 破o f l r o g r a m m i n g , i n e o p o r a t i n gw i t h t h eb e r t s i m a sr e s e a r c hf o r m u l a t i o n r o b u s t o p t i m i z a t i o n d e m a n da n dt r a v e lt i m e si s 雒t h eu n c e r t a i n t yp a r a m e t e r t h em i n i m i z i n g u n m e td e m a n da n dt h et o t a lp e r i o do ft i m ed u r i n gw h i c ho n ei sd e l a y e di s 器t h e o b j e c t i v e t h er o b u s to p t i m i z a t i o nm o d e lo ft h ev e h i c l er o u t i n gp r o b l e mi ne m e r g e n c y m a n a g e n ti sa r o b u s t0 - 1d i s c r e t eo p t i m i z a t i o n a l t e rt h ed e d u c t i o no nr o b u s t0 - 1d i s e t 咖 o p t i m i z a t i o n , t h er o b u s tc o u n t e r p a r t i se q u a lt oam i x e di n t e g e rp r o g r a m m i n gf m a n y t h em i x e di n t e g e rp r o g r a m m i n gi ss o l v e di nt h eb r a n c ha n db o u n da n dg e n e t i c 第3 页河南大学硕士研究生学位论文 a l g r i t h o mf o rt h i st h e s i s r e s u l t ss h o wt h eg o o dp e r f o r m s n c eo nd i f f e r e n td e m a n da n d t r a v e lt i m e sf o rt h ep r o p o s e da l g r i t h o mi nc o n t r a s t t ot h eo t h e ro n a 3 ) a n da l s ov e i l f yt h e f e a s i b l i t yo ft h er o b u s to p t i m i z a t o nm o d e lo nt h ev e h i c l er o u t i n gp r o b l e mi ne m e r g e n c y m a n a g e n t k e yw o r d s ：r o b u s to p t i m i z a t i o n , v e h i c l er o u t i n gp r o b | e m , u n c e r t a i nd e m a n d , u n c e r t s i n ； t r a v e lt i m e ，e m e r g e n c ym a n a g e m e n t 河南大学硕士研究生学位论文j 。第6 页 i 1 引言 第一章绪论 随着经济的全球化，全球经济飞速发展的同时但也导致了一些其它问题。比 如，全球的气候环境的恶化和一些社会问题的加剧。全球气候环境的恶化使得各种 自然灾害的发生日趋频繁，比如台风。地震、洪水、海啸等。而枉会矛盾的激化使 得各种恐怖活动的发生也是与日俱增。但不管是自然灾害还是各种恐怖活动都有一 些共同的特点，那就是这类事件发生的概率小但后果严重通常会危急人民群众的生 命安全和重大财产损失以及这类事件发生的不确定性程度高，我们通常管这类发生 概率小和不确定性程度高的事件叫突发事件。由于突发事件的潜在危害性，需要在 限定的可控时间内处理完毕，否则时间的影响和造成的损失就有扩大的趋势，这就 需要迅速组织多种资源来应对这些突发事件。突发事件的处理最终落实在资源的使 用方面，在资源的管理中需要考虑多种需求问题，如资源的有效调度等。同时突发 事件的应急处置是在资源优化而非过量的基础上进行的。因此资源的调度是应急管 理研究的一项重要内容。- 资源有效的调度，当然离不开车辆路线的选择，如何选择合理的车辆路线， 来保证资源能被合理的使用，这正是车辆路线闯题所研究的内容。车辆路线问题 ( v e h i c l e r o u t i n gp r o b l e m ，简称v r p ) 是1 9 5 9 年由喇g 等人提出的。般的 车辆路线闯题是对一系列出发点和需求点，选择适当的行车路线，在满足一定的约 束条件的情况下，达到一定的优化目标。优化目标通常是运输的费用或距离时间等 而应急管理下的车辆路线问题与传统的车辆路线问题有很大的区别。应急管理下的 车辆路线模型的目标是要在尽可能短的时问里把救济物资运送到救灾现场并且尽 最大可能的满足所有需求，不惜以运费为代价，这是与传统的车辆路线模型最大的 不同。当严重的突发事件发生后，紧急救援的物资能够及时供应这意味着能挽救更 多的财产和生命，为救援工作提供必要的物资保障。例如，当恐怖袭击事件发生后， 需要向存放救援物资的仓库向现场附近的医疗中心，各个医院及医疗救护站急送药 品。紧急医疗设备等，向各个需求点紧急调送救援物资。这时，通常的物流的供应 链很难满足突发事件的需要，当地的救济物资的库存很难应付某种紧急物资的大量 需求而需要调动紧急储备，当这些储备大多以大批量的空运到发生灾害所在城市 的机场，然后需要一些车辆在相对短的时间里把这些紧急救援物资运送到各个需求 点。面对这些突然发生的大量需求，合理的安排车辆运输方案，建立针对应急管理 第7 页河南大学硕士研究生学位论文 背景下的运筹学模型，研究快速有效的算法是非常必要的。 由于突发事件的商度不确定性，使锝应急管理下的车辆路线模型中会含有一些 不确定的参数，对于模型中的这些不确定参数，如何在问题的分析中将不确定性因 素纳入到所建立的优化模型的范畴中去并在此基础上通过采用有效的算法使问题 得以解决就成为一个很重要的课题。在对优化问题的分析过程中，将参数不确定性 因素考虑进去，就有两种不同的思路：一种是采用事先分析技术，即将能够考虑到 的参数不确定因素纳入到优化模型的建立中，使得优化模型的解具有鲁棒性；一种 是采用事后分析技术，典型的方法是灵敏度分析，即在建立优化模型的过程中，不 考虑参数不确定性因素，在得到模型的优化解之后，使得模型参数在一个确定的范 围内发生改变，观察其对优化解的影响程度。如果在设计范围内，问题的解对于参 数变化很敏感，那么表明此时得到的优化解不能满足要求。总而言之，这种事后分 析技术方法相对简单，是一种事后被动的而不是事先主动的处理模型参数不确定性 的方法，这也是该分析策略的最大弱势所在。为了能够更加真实地建立决策环境中 问题的优化模型，最佳的方案是使得数据的不确定性在所建立的优化模型中得以体 现，采取事先分析的建模策略。而鲁棒优化( r o b u s to p t i m i z a t i o n 简称r o ) 的方 法正是一种事先分析的建模策略。鲁捧优化作为运筹学学科领域的一个研究方向是 最近十年才新兴起来，它最早出现在上世纪七十年代，直到二十世纪末才逐渐开始 被许多优化学者关注。它主要是研究含不确定参数的优化问题，当不确定参数在某 一集合内变化时，如何使得优化问题的解对于含有不确定参数的任何实现几乎总是 可行的，其中几乎总是可行的是指当参数呈随机变化时，在一定的概率条件下保证 是可行解。( 即保持解的鲁棒性) 。人们发现诸多领域中的实际问题需要r 0 理论的 建立与发展，如工业工程、结构设计、金融投资等。近年来，随着鲁棒优化的理论 越来越完善，应用的范围越来越广泛，也为应急管理下资源调度的研究提供新的途 径。针对应急管理背景下的车辆路线模型中的不确定的需求和旅行时间，运用鲁棒 优化的思想，不仅会使得到模型更加符合实际情况，而且使得最后得到的车辆路线 具有较强的抗干扰性。 1 2 研究背景 本文是在针对突发事件的前提下研究的车辆路线问题。在现在的日常生活 中，“突发事件”的使用频率越来越高，人们往往将发生在自己意料之外或计划之 外的事件称为“突发事件”。那么，我们这里所谈的突发事件的和人们通常的理 解是有所不同的。从狭义上讲，突发事件是指在一定的区域内突然发生的，规模较 大且对社会产生广泛负面影响的，对生命和财产构成严重威胁的事件和灾难。从广 河南大学硕士研究生学位论文第8 页 义上说，突发事件是指在组织和个人原定计划之外或者在其认识范围之外突然发生 的，对其利益具有损伤性或潜在危害性的一切事件“1 。 突发事件由于发生的规模不同。地点不同、危害性质不周，事前准备不同丽会 产生不同的影响和后果，这些事件的发生具有随机性、不确定性，如果应对不当可 能发展为更大规模的事故，会对生命，财产产生伤害、损失和破坏。对这些事件的 处理都可以看成应急管理的内容 应急管理作为- f - j 综合运筹学、战略管理、信息技术以及各种专门知识的交叉 学科，主要针对突发事件进行决策优化的研究。作为一门新兴的学科，目前还没有 被普遍接受的定义，我们认为应急管理是和突发事件紧密裙联的一个概念。应急管 理是在应对突发事件的过程中，为了降低突发事件的危害，达到优化决策的目的， 基于对突发事件的原因、过程及后果进行分析，有效集成社会各方面的相关资源， 对突发事件进行有效的预警：控制和处理的过程。对突发事件的处理是应急管理 的核心，它表现为对各种资源的组织和利用，在各种方案闻进行选择决策。当突发 事件发生后，事件的各种表现形式及特征都将逐步显露出来，这就要求对事件产生 的各种影响进行整理分析，对事件未来的发展趋势进行预测，根据分析的结果，对 各种应对措施做出相应的决策。因此，当严重的突发事件发生后，如何对各种救援 资源进行有效的调度，这正是应急管理下的车辆路线问题所要研究的主要内容。 1 3 论文研究的问题与方法 本文是在针对突发事件的前提下，研究应急管理下的车辆路线模型。应急管理 下的车辆路线模型不同于常规的车辆路线模型，它的目标不是极小化费用，而是尽 可能的满足各个需求点的需求量和尽快的把救济和医疗物资送到各个需求点，从而 挽救更多的财产和生命。同时由于突发事件具有高度的不确定性，突发事件的这一 特点反映到模型中去就是各个需求点的需求量和需求点之间的旅行时间是不确定 的面对应急管理中车辆路线模型中的不确定的需求和旅行时问，我们不采用传统 的处理不确定的优化模型的随机优化的方法，主要是因为在实际情况下。一般很难 知道需求点的需求量和需求点之问的旅行时间的随机分布，所以对于不确定的应急 管理下的车辆路线模型，我们采用鲁棒优化的方法来处理模型中的不确定参数。那 么，什么是鲁棒优化昵? 简单的说，鲁棒优化是一个含有不确定输入的优化问题的建模方法，是随机规 划和灵敏度分析的补充替换，它假定不确定的参数属于不确定集，；u 是一个有 界闭集，与其它不确定优化方法的最大区别在于： 。? 第一，鲁捧优化强调的是所谓的硬约束，寻求一个对于不确定输入的所有实现 第9 页河南大学硕士研究生学位论文 都能有良好性能的解，即不确定优化问题的解对于任何一个( e u 的实现都必须是 可行的，而其它不确定优化闯题并没有这个要求。 第二，鲁棒优化的建模思想与其它优化方法不同，它是以最坏情况下的优化 为基础，这代表了一个保守的观点。得到的优化方案并不是最优的，但是，当参 数在给定的集合内发生变化时，仍能确保优化方案是可行的，使模型具有一定的鲁 棒性，即优化方案对参数扰动不敏感。 第三，鲁棒优化对于不确定参数没有分布假定，只是给出不确定参数集，不确 定参数集合内的所有值都同等重要。 对于需求和旅行时间的不确定的应急管理下的车辆路线模型，运用鲁棒优化的 思想将原来的模型转化为相应的鲁棒对应模型，通过用求解车辆路线模型的精确算 法和启发式算法来求解鲁棒对应模型，从而获得鲁棒对应模型的解，使得所得到的 车辆路线不会由于需求量和旅行时间的变化，而在实际资源调度时根本不适用。 1 4 研究的必要性 资源调度作为应急管理中一项基本内容，它的研究是必不可少的。如何快速而 准确及时地把各种救济和医疗物资送到各个需求点是资源调度过程中所必需考虑 的问题。是否合理的行车路线对于能否快速而准确及时地把救济和医疗物资送到各 个需求点起着至关重要的作用。应急管理下车辆路线问题的研究对于选择合理的车 辆路线来保证救济和医疗物资能够快速而准确及时地送到各个需求点提供了理论 依据。 基于传统的物流供应链中的车辆路线问题是运筹学中的一类经典问题，在交通 运输和物流管理等领域中有着成功的应用，对这类模型的构造和算法有着大量的研 究。但是对于应急管理下的车辆路线问题，其模型的目标和约束都发生了重大的改 变，传统的基于正常情况下的规范问题的模型和方法都不能适应应急管理的需要。 因此，根据突发事件的特点，建立突发事件应急车辆路线模型，研究和设计快速算 法以及制定特殊的调度模式是运筹学面l 临的新的挑战。 同时由于突发事件具有高度的不确定性，因此在应急管理的背景下建立的车辆 路线的优化模型通常需要考虑到突发事件的这个特点，所以模型中通常会有不确定 的量如果用随机优化的思想来处理这些不确定的量，往往需要假定这些不确定的 量满足某种具体的随机分布，但是由于突发事件所造成的高度的不确定性，使得这 些不确定的量往往仅满足一般的随机分布而不是某种具体的随机分布甚至不满足 任何一种随机分布，这就造成了假设条件与实际不相符的情况。而运用鲁棒优化的 方法来处理这些不确定量，则可以避免这种情况的发生。使得最后所得到车辆路线 河南大学硕士研究生学位论文第l o 页 不会出现因为模型中的不确定的量的各种不同的取值，两让模型中的各种约束条件 完全被违背。反映到实际情况就是面对突发事件的各种不确定性时，能够使得现场 指挥和调度应对更加自如。可以随时根据事态发展掌握的信息，做出正确的决策， 尽可能的挽救人民的生命和财产安全，减少灾害的损失和降低灾害的影响。 2 1 问题简介 第二章：车辆路线问题 车辆路线问题问题首先由线性规划大师嘶g 和黜哪鲫在1 9 5 9 年文献0 1 提出“ 的。自此。很快引起了运筹学、应用数学、图论和组合数学、计算机应用科学、管 理科学、物流科学等领域的专家的极大兴趣，成为运筹学与组合优化领域的一个热 点闯题。通过各学科专家的不懈努力r 进行了大量的理论研究和实验分析，取得了 很大的进展。对该问题一般描叙为，对一系列装货点( 仓库) 和卸货点( 客户或需求 点) ，组织适当的行车路线，使车辆有序地通过他们，在满足一定的约束条件( 如容： 量，时间，里程，优先级等) 的情况下，达到一定的优化目标( 如路程最短，费用最 少，时问最短等) 。由上述对v 髓问题的描述不难看出，旅行商问题( t s p ) 是v l 诤 的个特例。由于g a e f y 已证明t s p 闯题是n p - 难题，因此，v r p 也是n 卜难题。 在v r p 问题中最常见的一些附加条件有“1 ： 。 ( 1 ) 能力约束；与每个需求点所对应的需求县非债值，任意车辆路径上的总重 量不能超过该车的能力负荷。 ( 2 ) 任意路径上所含有的需求点的上界。 ( 3 ) 总时间约束。任意路径的长度不能超过预先给定的界；该长度由需求点间+ 的旅行时间和该路径上的每个需求点的停留时间所构成。 。+ ( 4 ) 时间窗口。必须在时间区间 口，6 访问到某一个需求点，并允许在这个需 求点等待。 ( 5 ) 多个需求点间存在着优先级关系，必须在访河需求点f 之前访问需求点，。 2 2v r p 问题的分类 根据研究的重点不同，v r p 存在着多种分类方式。 按已知信息的特征分，可分为确定性v p , p 和不确定性v r p ，其中不确定性v r p 可以 第1l 页河南大学硕士研究生学位论文 进一步分为随机v r p 和模糊v r p ； 按约束条件分可分为带能力约束的v r p 、带时间约束的v r p 和带时间窗口约束的 v r p ，其中带时间窗口的v r p 又可以分为带硬时间窗口和带软时间窗口： 。 按任务的特征分。有纯装货问题和纯卸货问题( 即集货或送货问题) 以及装卸混 合问题( 即集货、送货一体化问题) 。 按任务的性质分，有对弧服务的问题( 类似中国邮递员问题) 和对点服务的问题 ( 类似旅行商问题) 以及混合服务问题( 如交通车路线安排问题) 。 按车辆载货状况分，有满载问题和非满载问题( 多项任务共用一车) 。 按配送中心与客户分布的关系分，有单中心问题和多中心问题。 按运输车辆的类型数目分，有单类车型问题( 相同容量) 和多类车型问题。 按运输车辆路线的类型分，有车辆开放问题( 车辆路线可以开放，车辆可以 不返回出发点) 和车辆封闭问题( 车辆必须返回出发点) 。 按优化的目标数目来分，有单目标优化闯题和多目标优化问题。 2 3 基本v r p i 商- 题的数学规划模型 基本v r p f 司题可以精确的描述为：假设在一个仓库d 里，有x 辆同种类型的车， 它们的承载量为g ，另外有疗个需求点，每个需求点的需求量为吐( f = l ，一) ，这里 要求每辆车从仓库出发，对这n 个需求点进行服务，每个需求点必须而且只能被服 务一次：每条路线必须起始于仓库为最后一个需求点服务完后返回仓库：每条路线 的总负荷不能超过该辆汽车的最大承载量，每个需求点的货物需求量和允许服务的 时间窗口( 即货物必须在最早和最晚服务时间之间到达客户所在地) 都已知。每个需 求点必须在它的时间窗口内被服务，如果汽车提前到了需求点所在地，也必须等 待，直到允许为该需求点服务为止。 符号表示如下： k 车辆的总数量 疗需求点的个数 口每辆车的承载量 z 需求点i 的需求量 “车辆有需求点f 到需求点，的一般化费用 战需求点f 的最早服务时间 l t , 需求点f 的最迟服务时问 河南大学硕士研究生学位论史第1 2 页 墨一需求点f 的服务时间 ? + 珞从需求点，到需求点7 的旅行对阅 毛“需求点i 的开始服务时闻 ， f l 车辆从需求点垤0 需求点j 20 其它 。 f l 需求点f 被车辆而服务 靠2 1 0，其它 、 以最小化配送费用为目标建立v l m 模型如下， m i n = 勺 盯珥儿q ，y k ，l l 。 ： ： 占l lf j k 。j l k s l 2 j il n ： 五= 矗，w ，七 i 一。：一= ： ，。 t 蚝暑 j 月 。 ： 矗，v j = n 戤( 髟，t 墨+ 勺 ，辜粤筝 i 匾d 筘重醇，j ) e t t s t t s n l ，( 2 3 1 ) ( 2 3 2 ) g - 3 ，3 ) _ ( 2 3 4 ) ( 2 3 5 ) ( 2 3 6 ) q 3 7 ) ( 2 3 8 ) 目标函数是极小化整个配送的一般化费用，约束( 2 3 2 ) 表示的是每条路线的总 的需求量不能超过该辆汽车的最大承载量，( 2 3 3 ) 表示的是对仓库来说总共有k 辆 车，对每个客户来说只有一辆车服务于它，g 3 4 ) ，( 2 3 5 ) 表示对每个客户来说仅 有一辆车为它服务，服务完后这辆车也必须离开，( 2 3 7 ) 表示的是对任意一个客户 来说，这个客户的开始服务时间是这个客户允许的最早服务时问和同一辆车服务的 第1 3 页河南大学硕士研究生学位论文 前一个客户开始服务时间加上前一个客户的服务时间在加上从前一个客户到本客 户的旅行时间的和的最大者；( 2 3 8 ) 是时闻窗口的约束。 一些更加复杂的v r p 的模型都是在一定假设条件下，对基本v r p 模型进行扩充 得到的。很显然，从上面的可以看出，基本的v r p 模型是一个混合整数规划模型， 因此，不难看出v r p 问题是不存在多项式时间算法。 2 4v r p 问题文献综述 在v r p i 问题中，问题的算法与所建立的模型密切相关。由于在现有的文献中，大 部分文献是研究确定性v r p 和不确定性v r p 。因此，下面也按这种分类方式进行讨论。 2 4 1 确定性v r p 问题 确定型的v r p 是现实中最常见的模型。针对确定v r p 的研究主要集中在对它算 法的研究。对确定性v r p 的算法主要分为精确算法和启发式算法。精确算法可以分 为三大类，直接树搜索算法、动态规划方法和整数线性规划【，： ( 1 ) 分枝定界算法。该方法是l a p o r t e q 等人提出的。它利用了v r p 和其放松形 式坍一7 x p ( 旅行商闯题) 之闻的关系。根据l e n s 瞄人所给出的坍的上巩，肘一7 s p 可转化为1 一t s p 关键步骤是，引入( 一1 ) 个伪出点，n = 丹+ 帆一1 ，y = ( 1 ，2 ，刀) ， a = 4 u 织j ) ：f ，j 矿，i - ，办势v 、n 。接下来用分枝定界求解，可求解有2 6 0 个点 的v r p 。 ( 2 ) k 度中心树和相关算法。该方法是c h r i s t o f i d e s 刀等人提出的。对固定m 的 所一t s p 进行k 度中心树松弛。所以该方法需要知道所需车辆数的下界。其模型是从 边的角度建立的，出发点用k 条边来表示，其他点用两条边表示。通过拉格朗日松弛 法，将其中一个约束条件消去，并进一步将原来的最小化问题转化为3 个易于求解的 子最小化问题，然后进行求解。目前，m l f i s h e r s j 对它做了进一步改进，可求解有 1 3 4 个客户的v r p 。 ( 3 ) 动态规划法。动态规划法是由e i l 州等人首先提出的。它针对的也是固 定车辆数的v r p 。通过递归方法求解。为减小问题的计算规模，引入可行性规则或松 弛过程减少状态的数量。其后，c h r i s t o f i e l d s 提出了状态空间松弛，极大地减少了状 态数量。该方法要求：转换函数易于求解，映射出来的范围小，可求得很好的下界， 目前可求解有5 0 个客户的v r p 。 ( 4 ) 集分割和列生成。v r p 的集分割是由b a f i n s k i f i o l 等人首先提出的。它直接考 虑可行解集合，在此基础上进行优化，因此建立的v r p 模型最为简单其缺陷在于， 如果问题所受约束不严格，则所需要计算的状态空间非常大。另外，要确定每个可行 河南大学硕士研究生学位论文第1 4 页 解的最小成本也是件困难的事情。对于其中规模相对较小的约束严格的问题，可通 过线性松弛，引入割平面进行求解。于是, r a o “l 等人引入了列生成方法进行求解。 在该方法中，原闯题被转化为简化闯题，考虑的范围是所有可能的可行解的子集。在 此基础上重复求解。通过引入优化对偶变量向量，对该简化问题松弛，通过计算列 的最小边际成本，确定最优解。其算法本质上是最短路径算法，同时结合了分枝定 界算法d e s r o c h e r 用它求解有1 0 0 个客户的带时间窗口的v r p 问题。 ( 5 ) 三下标车辆流方程。f i s h e r i l 2 1 等人针对带能力约束时间窗口以及无停留时 间的v r p 问题，提出了三下标车辆流方程在该方程中，其中两个下标表示弧或边， 另外一个下标表示特定车辆的序号。基于b e n d e r s 的分解方法，他们提出了_ 种启发 式算法，保证在有限的步骤内找到优化解。f i s h e r 等人用它计算了有5 0 - 1 9 9 个客户的 v r p ，l v i a r t e l l o 和d e s r o c h c r s 分别提出了相应的改进算法。 ( 6 ) 二下标车辆流方程。对于对称的c 啦( 带能力约束的车辆路线问题) d v r p ( 带时间距离约束的车辆路线问题) ，可通过去掉表示车辆序号的下标，引入所需车 辆数的下界，得到一个更为紧凑的方程。它所对应的算法结合了爬山法的思想，其 算法核心仍然是线性规划，若得到的解是分数解，则用分枝定界方法求其整数解。 该方法是s l a p o r t c t ”1 等人提出的，已用它来求解了规模为6 0 的闯题， 总的说来，精确算法基于严格的数学手段，在求解中小规模v p , p 时，精确算法要 优于启发式算法。但在求解大规模v r p 时，启发式算法总可以在有限的时问里，找 到满意的次优解或可行解，这是精确算法难以做到的。因此，在实际应用中，启发 式算法要更广泛。 常用的启发式算法主要有以下几种： ( 1 ) c l a r k e - w r i g h r g 法。该算法由c l d 睁w 啦蛳提出的n 】，该算法不仅是一种 节省算法而且是一种精确的简单启发式算法。它的基本思想是从不可行的路线出， 发，车辆的个数确定了可行路线的条数，通过计算合并任意两条路径层可节省的成 本量，然后对可节省的成本量进行捧序，最后根据排序结果以及可行性条件，对路 径进行归并，直到无法找到更好的解，得到近似或接近最优解c l a r k e - w r i g h t 算法归 并予路径的基本前提是要满足车辆的能力约束，因此该算法适用于c v r p 。 ( 2 ) s w e e p 算法。该算法是由w r m l , g i l l c t t l l 5 1 等人提出豹，即先计算出所要访闯 的点韵极坐标，并按角度大小排序。然后在满足可行性条件的前提下，按角度大小归 并到不同的子路径中。最后再根据t s p 的优化算法对所得到的子路径进行优化一 s w p 通过角度大小对客户节点加以聚类，本质上是将距离近的客户归并到一个 子路径中，同时聚类要满足的可行性条件仍为车辆的能力约束j 因此，该方法也适用 于c v r p 。 ， ( 3 ) 两阶段算法呻l 。它主要面向c v r p 和d v r p 。该算法的求解过程分为两个阶 第1 5 页河南大学硕士研究生学位论文 段：第一阶段按最小路径的原则形成初始解。然后用k - o p t 算法对所得的各子路径分 别进行优化：第二阶段是在各子路径间进行点的交换，以减小总行程，然后再用k o p t 算法对点交换后的子路径进行优化。该算法的优点是，在计算过程中，考虑了所 需要访问的点数量增加的情况方法适用于c v r p 和o v r p 。 ( 4 ) 禁忌搜索算法。禁忌搜索算法是一种通过领域搜索以获取最优解的方法。 g l o v e , d 7 1 曾叙述了它的基本原理。g e n d r e a u t t ”1 等人最先将该方法应用于v r p 。先构 造一系列的解，然后对所得解不断地进行改进。该算法所得的解不一定是可行的， 它们对可行性的偏离程度是通过目标函数里的惩罚函数来体现的。它是针对v r p 的 比较好的启发式算法，可以成功地应用于许多经典的v r p 。其后e t a i l l a r d f i ”1 等人 通过按角度和路径重心对原问题的空间进行分割，再用禁忌搜索结合模拟退火对子 问题进行求解，实现了对问题求解的并行化。 一 7 ( 5 ) 遗传算法。遗传算法是美国m i c h i g a n 大学的j h o l l a n d 于本世纪末提出了一 种新的并行优化搜索方法：遗传算法是一种基于进化论优胜劣汰、自然选择、适者 生存和物种遗传思想的随机优化搜索算法，通过群体的进化来进行全局性优化搜 索。j l a w l c n f , e 2 0 i 最先将该方法用于v r p 的研究，并可有效求解v r p t w 鉴于传统的 遗传算法是个大范围、粗粒度的寻优算法，因此b a m i e r 【2 ”将它与约束满足问题的 技术相结合，通过遗传算法来处理参数的子域( 基因的适应度是通过对解的计算得 到的) ，从而减少搜索空间，降低问题目标函数和遗传算法约束的复杂度。遗传算 法的最大优点是通过群体间的相互作用，保持已经搜索到的信息，这是基于单次搜 索过程的优化方法所无法比拟的。但是，遗传算法也存在着计算速度较慢的问题。 ( 6 ) 模拟退火算法。模拟退火算法的主要思想是模仿固体的退火过程，融化的 固体在逐渐降温的过程中，出现各种随机状态的能量不同，全部接受低能状态，有 条件地接受高能状态，构成了模拟退火算法。形象地说就是在进行下山算法的时候， 为避免局部最优解，而进行一定的有条件的爬山算法，这样可以较为迅速达到全局 最优解或近似全局最优解。模拟退火算法适合大规模的需求固定或随机需求的v r p 问题，在合理的时间内给出近似最优解，但在规模较大的情况下才能体现其优点。 ( 7 ) 重复匹配。该方法是f h p w a r k 阱1 等人提出的首先对每个客户生成一条予 路径，然后提供了总匹配成本和负载改变匹配成本，作为归并路径的依据，同时为满 足自匹配条件的集合提供分割手段，l ：i 利于跳出局部最优。该算法也可求解较大规 模的v r p 问题。 2 4 2 不确定性v r p 问题 不确定性v r p f 习题，顾名思义，主要指的v r p 模型中的一些参数不确定。比如， 客户的需求，车辆数，客户的数量，客户之间的旅行时间等。不确定的v r p 问题相 河南大学硕士研究生学位论文_第1 6 页 对于确定性的v r p 闯题明显更加复杂。处理不确定v r p 的方法主要有随机优化。模糊 优化，鲁棒优化这三种方法。相对于后两种方法，随机优化的方法最常见的处理不 确定的v r p 的方法。 用随机规划建立起来的v r p 模型简称为s v r p 。随机v r p 对于确定性的v r p 来说；， 模型更加复杂，算法也更加复杂。这方面的工作可以参阅文献l 柳。根据v r p 模型中 随机参数的不同，s v r p 可以分为随机需求的v i l p ( v r p s d ) ，、随机客户v r p ( v r p s o 、随 机旅行时问的v r p ( v r p s t t ) 、随机服务时间的v r p ( v r p s s t ) 等。建立s v r p 模型不同予 确定性的v r p ，它的方法主要有机会约束模型( c c p ) 、带资源的随机规划( s p r ) 和把 s v r p 看作一个马尔科夫决策过程来处理。最近在s v r p 建模方法上又有了一些新的方 法。比如，神经动态规划和强制学习的方法。不同的建立s l l r 】i p 模型的方法，使得s v r p 有不同的算法。他们大致可以分为两类：精确算法和启发式算法精确算法包括； 分枝定界( b r a n c h 鼢db o 硼m 、分枝切割( b f a n c ha n dc 、整数l - s h a p e d 法和一般的 动态规划法r 在定的假设条件