（载运工具运用工程专业论文）应急物流配送车辆调度优化研究.pdf

摘要 近些年来，我国大规模突发性公共事件发生频繁，如1 9 7 6 年的唐山大地震、1 9 9 8 年 的长江的大洪水、2 0 0 3 年的“s a r s 、2 0 0 5 年的重庆毒气泄漏事件和松花江水的重大污 染、“禽流感”、2 0 0 8 年初的南方雪灾、汶川大地震、甲型h 1 n 1 流感和2 0 1 0 年4 月1 4 日青 海玉树发生的7 1 级地震等突发事件造成的巨大损失，给人们留下了惨痛的记忆。现代社 会的高速发展，使人口、资源、环境、公共卫生等各方面的社会问题日益尖锐，导致各 类突发事件爆发更加频繁，危害加剧，受灾范围扩大。 应急物流是以提供自然灾害、公共事件等突发性公共事件处理过程中所需的应急救 灾物资为目的，以追求时间效益最大化和灾害损失最小化为目标的特种物流活动。因此， 在突发事件处置过程中，必须快速建立应急物流系统，保障突发灾害处置中所需的应急 救援物资供应，以资解决或处理居民基本生活、死者安葬、伤者救助、卫生防疫、灾后 重建、恢复生产、恢复秩序等事项，否则受灾面积、人员、损失将会持续扩大，灾害会 变得更加严重。因此在突发事件发生时建立应急物流系统，迅速地将救援物资送达物资 需求点，直接影响到整个突发性公共事件救援行动的成效。本文研究的应急物流车辆调 度问题是在满足应急物流时间要求的前提下，更合理的安排车辆的运行路线，最大程度 的节约运输成本对于提高应急物流效率是很有意义的。 本文首先分析了应急物流系统的特点、研究内容和运作流程。同时，就车辆调度问 题进行了分析，介绍了车辆调度问题的提出、分类、典型问题的数学模型以及基本解决 方法。并在此基础上提出了应急物流车辆调度问题，分析该问题与车辆调度问题( v e h i c l e r o u t i n g p r o b l e m ，v r p ) 的区别，并建立了单车型、非满载、纯卸、单配送中心多受灾点 的微观应急物流车辆调度优化问题的数学模型，同时选择了求解该问题的算法一蚁群算 法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 。在应用蚁群算法对问题进行求解时，对蚁群算法的原 理、特点、数学模型和算法实现步骤进行分析的基础上，针对算法的不足，分别通过对 初始解的启发、状态转移规则和信息素更新策略的改进，改进了蚁群算法。并采用面向 对象的c + + 语言对基本蚁群算法程序进行修改来对算例进行求解。结果证实了该算法在 求解该类问题的可行性和有效性。 关键词：应急物流，车辆调度问题，蚁群算法 a b s t r a c t i nr e c e n ty e a r s ，c h i n ao c c u r r e dal o to fl a r g e - s c a l ep u b l i ce m e r g e n c yf r e q u e n t l y , s u c ha s t h et a n g s h a ne a r t h q u a k ei n19 7 6 ，t h ew o r s tf l o o d i n go fy a n g z ir i v e ri n19 9 8 ，t h ec r i s e so f s a r si n2 0 0 3 ，t h ep o i s o ng a sl e a k e do fc h o n g q i n ga n dt h ew a t e rs e r i o u sp o l l u t i o n e do f s o n g h u ar i v e ri n2 0 0 5 ，t h ea v i a ni n f l u e r n z a ，t h es o u t hs n o wd i s a s t e ri nt h eb e g i n n i n go f2 0 0 8 ， t h ew e n c h u a ne a r t h q u a k e ，t h ei n f l u e n z aav i r u ss u b t y p eh 1n 1 ，t h er e c e n t7 1m a g n i t u d e e a r t h q u a k eo c c u r r e di nq i n g h a iy u s h u o na p r i l14 ，2 010a n ds oo n ，w h i c hn o to n l yr e s u l t e di n g i g a n t i cl o s e s ，b u ta l s ol e f tad e e p l yg r i e v e dm e m o r yi np e o p l e sm i n d d u et ot h eh i g h s p e e d d e v e l o p m e n to fm o d e ms o c i e t y ，t h es o c i a lp r o b l e m sa b o u tp o p u l a t i o n ，r e s o u r c e ，e n v i r o n m e n t p u b l i cs a n i t a t i o na n ds oo nb e c o m em o r ei n c i s i v e l y , a n dk i n d so fp u b l i ce m e r g e n c i e so c c u r m o r ef r e q u e n t l y , m o r ed a n g e r o u sa n dt h ei n f l u e n c i n gs c o p eb e c o m e sm u c hw i d e rt h a nb e f o r e t h ee m e r g e n c yl o g i s t i c ss y s t e mi sas p e c i a ll o g i s t i ca c t i o ni no r d e rt op r o v i d et h e e m e r g e n c ym a t e r i a l st od e a l 埘也i n c i d e n t s ，t h e r ea l et w oa i m st h a te m e r g e n c yl o g i s t i c s s y s t e m sw a n tt or e a c h t h ef i r s ti s t od e a l i n g 、析t hi n c i d e n t sa tt h eb e s te a r l ys t a r t - t i m e t h e s e c o n di st or e d u c et h et o t a lc o s to fd e a l i n gw i t l lt h e s es u d d e np u b l i ci n c i d e n t sa si tc a l l s o w h e np u b l i ce m e r g e n c yb r o k eo u t ，t h ee m e r g e n c yl o g i s t i cm u s tb ee s t a b l i s h e di no r d e rt o s u p p l ya b u n d a n tl a s h - u pm a t e r i a l st or e s o l v eo rd e a lw i t hs a t i s f y i n gt h ee s s e n t i a ld e m a n do f t h er e s i d e n t s ，b u r y i n gt h ed e a t h ，r e s c u i n gt h es o u n d ，s a n i t a r ye n g i n e e r i n g ，t h er e e s t a b l i s h m e n t a f t e rt h eb a l e ，r e s u m i n gp r o d u c t i o na n dg e t t i n gb a c kt h eo r d e ra n ds oo n ；o re l s e ，t h ea r e ao f c a l a m i t i e sa n dl o s so fl i v ea n da s s e t sw o u l db ee x p a n d e dc o n t i n u o u s l y s ot h a tt h e e s t a b l i s h m e n to fe m e r g e n c yl o g i s t i cw h e nt h ee m e r g e n c yb r o k eo u tc o u l dr e n d e rt h eb a i l o u t m a t e r i a l sb ed e l i v e r e dt ot h es p o t sw h e r en e e dt h e m , w h i c hw o u l dh a v ea l le f f e c tu p o nt h e o u t c o m e so ft h ew h o l es u c c o r t h i sa r t i c l es t u d i e st h ev e h i c l er o u t i n gp r o b l e mf o re m e r g e n c y l o g i s t i c sd i s t r i b u t i o n , w h i c hi sb a s e do ns a t i s f i e dt h et i m el i m i t i e do fe m e r e g e n c ym a t e r i a l s d i s t r i b u t i o n ，t h ea r r a n g e m e n to fv e h i c l e s r o u t i n gi sm o r er e a s o n a b l et ou l t i m a t e l yr e d u c et h e c o s to ft r a n s p o r t a t i o n ，w h i c hi sv e r ym e a n i n g f u lf o ri m p r o v i n gt h ee f f i c i e n c yo fe m e r g e n c y l o g i s t i c f i r s t l y , t h i sa r t i c l ep r o p o s e da n da n a l y z e dt h ec o n c e p to fe m e r g e n c yl o g i s t i c sa n dt h e c h a r a c t e r i s t i c s ，t h er e s e a r c hc o n t e n ta n dt h eo p e r a t i o nf l o wo fl o g i s t i c ss y s t e m m e a n w h i l e ，t h e a r t i c l ea n a l y z e dt h er e l a t e dp r o b l e m so fv e h i c l er o u t i n gp r o b l e m ，i n c l u d i n gt h ei n t r o d u c t i o n ，t h e c l a s s i f i c a t i o n , t h em a t h e m a t i c a lm o d e lo ft y p i c a lp r o b l e m sa n dt h eb a s i cs o l u t i o nm e t h o d s b a s e do nt h ed i s c u s s i o no fv e h i c l er o u t i n gp r o b l e m ( v r p ) a n de m e r g e n c yl o g i s t i c s ，t h i sa r t i c l e p r o p o s e dt h ev e h i c l er o u t i n gp r o b l e m f o re m e r g e n c yl o g i s t i c sd i s t r i b u t i o n a n dt h e n ，i t a n a l y z e dt h ed i f f e r e n c e sb e t w e e nt h i sp r o b l e ma n dv i 冲p r o b l e m a n de s t a b l i s h e dt h et y p i c a l m a t h e m a t i c a lm o d e lo ft h ev r po fu n f u l l yl o a d e de m e r g e n c yl o g i s t i c sd i s t r i b u t i o n ，s i m u l t a n e o u s l yc h o s ea n tc o l o n yo p t i m i z a t i o n ( a c o ) t os o l v et h i sa r t i c l es o l v e dt h ep r o b l e mb ya c o ， i ta n a l y z e da c o sp r i n c i p l e ，c h a r a c t e r i s t i c ，a n de s t a b l i s h e di t sm a t h e m a t i c a lm o d e la n dt h e n a n a l y z e dt h ee x e c u t i v es t e p so f t h ea l g o r i t h m s b a s e do nt h ea n a l y s e sb e f o r ea n dt h ed e f e c t s o fa c oi nt h i sa r t i c l e ，t h r o u g ht h ei n s p i r a t i o no ft h ei n i t i a ls o l u t i o n ，i tu p d a t e dt h ep h e r o m o n e o nt h ec h o i c eo fs t r a t e g ya n dp o b a b i l i t yo ft r a n s f e rt om e n da c o a tt h ee n do ft h i sp a p e r , o b j e c t - o r i e n t e dc + + l a n g u a g ew a sa p p l i e dt oc o m p i l et h ec o m p u t a t i o n a lp r o c e d u r et o i m p r o v e da c o t oc a r r yt h ee x a m p l e t h er e s u l tc o n f i r m e dt h i sa l g o r i t h mi sf e a s i b l ea n dv a l i d f o rs o l v i n gt h i sk i n do fp r o b l e m k e yw o r d s ：e m e r g e n c yl o g i s t i c s ，a n tc o l o n yo 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 l e m 长安大学硕上学位论文 第一章绪论 1 1 研究背景和意义 在人类社会快速发展的同时，人类赖以生存的环境也在不断恶化，世界各地自然灾 害、人为灾害等各类突发事件爆发频繁，影响范围和规模都不断扩大。近几年，中国也 成为世界上自然灾害多发的国家之一，突发事件发生频繁，如1 9 7 6 年唐山大地震、1 9 9 8 年长江的大洪水、2 0 0 3 年s a r s 事件、2 0 0 5 年重庆毒气泄漏事件和松花江水的重大污染、 禽流感、2 0 0 8 年南方雪灾、“5 1 2 汶川大地震、甲型h 1 n 1 流感以及最近青海玉树县发 生的7 1 级地震等严重地威胁到了人们的生命和财产安全。 当突发灾害发生时，为了防止受灾范围、人员和财产损失的不断扩大，需要提供大 量的应急救灾物资来满足伤者的救助、卫生防疫、灾后重建和恢复生产等各方面的需求。 有些突发性灾害发生的时间、强度或者地域等是可以预测的，如洪水、台风、洪涝灾害 等；而更多的突发性灾害是难以预测和预报的，如地震、山体滑坡、泥石流、突发性传 染病、大面积食物中毒、火山爆发等，即使有些突发性灾害可以预测，但因为预测时间 与灾害发生时间间隔很短，赈灾的应急救灾物资很难实现其时间效应和空间效应，即很 难实现应急物流过程。而且当突发事件发生时，受灾地区往往没有储备应急救灾物资， 或者储备的应急救灾物资数量和种类有限。因此，在突发事件发生时如何快速有效地实 现应急物资的运输成为了一个非常重要的研究课题。 近几年，特别是s a r s 事件之后，我国政府已经意识到在经济快速发展的过程中， 加强自身对突发事件的管理，建立快速有效地应急物流系统的重要性。 为了确保突发事件发生时，应急救灾所需物资和生活用品的及时供应，减少灾害损 失，2 0 0 6 年1 月8 日，国务院颁布了国家突发公共事件总体应急预案，要求全国各地 建立健全应急物资检测网络、预警体系和应急物资生产、储备、调拨及紧急配送体系， 完善应急工作程序，加强对物资储备的监督管理，及时予以补充和更新。该预案编制是 依据宪法及有关法律、行政法规制定的，编制的目的是提高政府保障公共安全和处置突 发公共事件的能力，最大程度地预防和减少突发公共事件及其造成的损害，保障公众的 生命财产安全，维护国家安全和社会稳定，促进经济社会全面、协调、可持续发展【l 】。 2 0 0 9 年5 月1 1 日，国务院根据中国国情，建立了有中国特色的减灾救灾工作机制， 新闻办发表了中国的减灾行动白皮书，其中指出，为了完善国家应急物资储备体系， 我国已经建立了以物资储备仓库为依托的救灾物资储备网络。目前，我国已经在沈阳、 第一章绪论 天津、郑州、武汉、长沙、广州、成都、西安、哈尔滨、合肥等设立了1 0 个中央级生活 类救灾物资储备仓库，并在不断建设和完善中央级救灾物资、防汛物资、森林防火物资 等物资储备库，部分省、市、县建立了地方救灾物资储备仓库，抗灾救灾物资储备体系 初步形成【l 】。 目前，我国研究应急物流系统的学者越来越多，但主要都是针对应急救灾机制的建 立、应急物资的保障、应急物资配送中心的选址、紧急状态法律法规的制定等定性问题 来进行研究的，而关于应急物流配送车辆调度问题的研究很少。应急物流配送车辆调度 问题是应急物流研究的一个重要组成部分，是整个应急物流系统的实现阶段。应急物流 是普通物流的一个特例，与普通物流有相同之处，也有不同之处。普通物流的主要原则 是经济效益原则，而应急物流主要体现应急物资的时效性，再考虑经济效益原则圆。因 此本文重点针对突发事件发生后，研究应急物流配送车辆调度问题，建立相应的数学模 型，通过改进蚁群算法来求解该模型，为救灾指挥中心制定应急物流配送车辆调度方案 提供科学决策的依据。 1 2 国内外研究现状 国外对应急物流系统的研究起步较早，而国内近几年才开始有针对地对一些问题进 行了研究。以下分析国内外对应急物流系统的研究现状。 1 2 1 国外研究现状 1 9 8 4 年，k e m b a l l c o o k ，s t e p h e n s o n 等提出了通过增强应急物流管理来提高应急救 灾物资的运输效率。 1 9 8 8 年，k n o t t 在线性规划理论的基础上，对突发事件中食品供应的车辆路线规划问 题，进行了深入研究。 1 9 9 2 年，r a t h ie ta l 等采用传统优化算法针对指派问题提出了l p 模型，但该模型求得 的结果容易陷入局部最优，解决突发事件应急物资配送问题时具有较强的局限性【4 1 。 1 9 9 6 年，舢in a g h a n i 等将应急物流配送车辆调度问题描述为有时间窗限制的多物 品、多模式网络流问题，该研究假设应急救灾物资可以完全满足需求，以运输成本最小 化为目标函数。 1 9 9 8 年，w a e l 在博士论文中提出突发灾害发生时的应急物资运输问题属于 c t d a p ( t h ec o m b i n e dt r i pd i s t i b u t i o na n da s s i g n m e n tp r o b l e m ) ，并使用整数规划方法建立 了应急物资模型，但是该模型计算比较复杂，花费时间较长，在解决突发事件应急物资 2 长安大学硕士学位论文 管理时，实用性较差。 1 9 9 9 年，p h i l i p 对突发物流和订单分割对物流总成本的影响进行了比较研究。 2 0 0 0 年，f i e d f i c h 等研究了在时间、救灾物资的数量等资源有限的情况下，通过资 源的有效使用提高应急救灾的质量，以死亡人数最小作为目标函数，提出了地震发生后 向多个受灾地区分配、运输应急救灾物资的最优计划模型1 5 】。 2 0 0 0 年，g u l a y 等提出了一种分层多标准方法解决直升机在应急救灾中的调度问题， 在派遣的直升机和飞行员的数目都满足需求的前提下，使运输成本最低。 2 0 0 2 年，k o n s t a n i n o s 等研究了基于适时决策支持系统的公路网事故响应模型，该模 型以突发事件响应时间最短作为目标函数【6 】。 2 0 0 3 年，j a ey o u n gc h o i 研究了在路网状况不确定的情况下如何分配有限的救援资 源( 如救护车或其它救援车辆) 将伤员送到医院，目标是使伤员的存活率最大。 2 0 0 3 年，s y o z ok u b o 等提出了由一定数量的气垫船组成的应急救灾运输系统，并利 用该系统对1 9 9 5 年神户发生的地震进行了救援仿真。 2 0 0 4 年，o z d a m a r 等以受灾点得到的救援物资未满足率最小为目标，进行应急物流 规划，通过反复的求解运输规划而得到一个最优方案。 2 0 0 7 年，g w o h s h i u n gt z e n g 等运用模糊多目标规划方法，纳入公平满意度，建立 了紧急救援物资的配送模型，避免了在应急物资配送中对某些区域的配送偏差太大。 1 2 2 国内研究现状 国内近几年才开始有针对地对应急物流系统的一些问题进行了研究，主要包括应急 救灾机制的建立、应急物资的保障、应急物资配送中心的选址、紧急状态法律法规等定 性问题。 1 9 8 9 年，郭耀煌教授、李军博士及其学生们针对多车场、多车型、纯装纯卸、装卸 混合非满载等问题进行了研究，但研究中都没有涉及应急调度部分。 1 9 8 9 年，刘春林、戴更新、何建敏等主要从理论上研究了突发事件发生时，紧急救 灾物资的调度问题，主要考虑了应急物流的时间紧迫性。因为应急物流一旦开始，就有 应急物资的消耗，决策者必须在很短的时间内制定有效的应急物资车辆调度方案吲。 1 9 9 9 年，何建敏、刘春林将非线性比例路径问题的求解转化为一系列线性目标最短 路径问题的变权迭代问题，并给出了在给定应急网络系统限制期的情况下，以时间为区 间数的赋权图的最小风险路径的选取算法来求解路径问题。 第一章绪论 2 0 0 0 年，何建敏、刘春林两位学者在国家自然基金的框架下，从非路径角度分两种 情况分析了单受灾点、多出救点的组合优化救援方案的求取问题。一种是：当救灾点到 受灾地区所需时间均为普通实数时，基于“时间最短 和“时间最短前提下，救灾点数 目最小 ，提出了单目标和多目标函数问题及其求解方案；另一种是：当救灾点到受灾 地区所需时间为区间数时，提出了“使得应急开始时间不迟于时间窗的可能度最大的方 案 的求解方法【8 】。 2 0 0 1 年，这两位学者针对应急物资车辆调度问题中存在时间紧迫性与应急救灾点数 目相互矛盾的特点，提出了时间窗下的多救灾点组合模型，并运用模糊优化方法来求解 应急物流车辆调度问题，以及在满足约束条件下，给出了一个使应急物流开始时间最早， 且救灾点数目最少的折中方案。 同时期，这两位学者根据应急物流连续性的特点，讨论了在应急物资需求约束条件 下多救灾点的一类应急物资调度问题，并根据应急物流开始时间最早前提下救灾点数目 最少以及时间窗内救灾点数目最少，给出了相应的应急物流车辆调度模型，并从理论上 证明了该模型求解方法的正确性。 2 0 0 5 年，计雷等提出了应急物流救灾物资运输问题是最小化运输时间与运输费用的 多目标组合优化问题，但是没有对该问题的模型和实现方法进行深入研究【9 】。 现在，我国也有许多学者基于“救灾点个数最少 和“应急开始时间最早”，建立 了在多资源多出救点的应急物流系统中的多目标的应急物流车辆调度模型。 1 2 3 存在的问题 从上面的分析我们可以看出，目前国内外学者对应急物流研究的较少，研究成果主 要集中在应急救灾物资的运输调度、应急救灾物资的保障措施、应急救灾物资运输调度 方案的选择、多出救点组合救援单受灾点的车辆调度问题等方面。同时在研究中也存在 着一些不足，主要表现在以下几个方面： 1 ) 大多数学者研究时建立的模型都是从商业物资运输问题的框架着手，即以成本 最小化为目标函数。忽略了突发事件发生的特定场景和一些特殊的要求。 2 ) 在突发事件发生时，会有一些随机因素发生，如突发事件发生后避难人群的疏 散、沿路建筑物的倒塌、道路的阻断等。在研究中，这些随机发生的因素都将导致车辆 运行时间的延长，但是很难将它们考虑进模型中。 3 ) 在突发事件发生时，实际能调用的车辆数、应急救灾物资供应量、车场等可能 4 长安大学硕士学位论文 是不定的，是随时间的变化而变化的。而在研究中，模型中的这些参数大都固定不变。 4 ) 我国每年发生灾害都很多，目前基本没有对我国应急物流配送车辆调度优化模 型进行系统地、深入地、定量地进行研究，并对突发事件的决策还存在应对迟缓、缺乏 科学依据等问题。 1 3 应急物流概述 1 3 1 应急物流的内涵和特点 1 应急物流的内涵 应急物流( e m e r g e n c yl o g i s t i c s ) ：是指以提供突发性自然灾害、公共卫生事件等突发 事件所需应急救援物资为目的，以追求时间效益最大化和灾害损失最小化为目标的特殊 物流活动【3 1 。 2 应急物流的特点 应急物流是普通物流活动的一个特例，它除了具有普通物流系统的六个基本要素 ( 即流体、载体、流向、流速、流量和流程) 外，应急物资的需求有很强的时间约束性， 这是因为突发事件发生后，为了减少各种损失，必须追求时间效益的最大化。因此，应 急物流系统有七个基本要素：流体、载体、流向、流速、流量、流程和时间2 3 ，1 0 1 。 与普通物流活动相比，应急物流有如下特点： ( 1 ) 突发性：应急物流是由突发事件引起的，由于突发事件发生突然，发生的时 间一般是不可预知的。因此应急物流所发生的时间很难事先进行准确预测。 ( 2 ) 时间约束的紧迫性：由于突发事件发生突然，变化剧烈，而应急物资多是为 了抢险救灾，时关生命，时关全局，应急物流的速度直接影响着突发事件造成的危害的 大小。因此，客观上要求应急物流车辆调度决策和组织管理快速、有效，从而保证在最 短的时间内将应急救灾物资送到受灾点。 ( 3 ) 不确定性：应急物流是由突发事件引起的，突发事件的持续时间、影响范围、 危害强弱等因素是无法进行准确估计的，因而应急物流所需提供的应急救灾物资的种 类、数量、时间、供应地和需求点也随之不确定。 ( 4 ) 非常规性：应急物流是由政府组织的非常规活动，应坚持特事特办的原则。 即在执行的过程中可以根据特殊情况省略普通物流活动中的一些环节，从而确保应急物 流活动协调一致，进而保证救灾物资及时准确地送达受灾点。 ( 5 ) 弱经济性：应急物流的最大特点是时间约束的紧迫性，因此在应急物流中， 5 第一章绪论 为了控制灾情的蔓延、减小灾民痛苦、减少财产损失等，通常以时间效益作为主要原则， 其次才考虑经济原则。 ( 6 ) 社会公益性：应急物流是政府组织的非常规活动，活动中有的救灾物资是政 府向社会团体或者个人征用的( 如运输车辆) ，有的救灾物资是社会团体或者个人捐助 的( 如救灾款，食品，医药) ，因此应急物流活动中的社会公共事业物流多于企业物流， 它主要体现了应急物流的社会公益性。 1 3 2 应急物流的研究内容 应急物流的主要研究内容如图1 1 所示 图1 1 应急物流系统的研究内容 由此可知，应急物流系统研究的内容很广泛。其中应急物资的运输与配送是应急物 流过程中最后一个环节，也是影响应急救灾活动效果的一个至关重要的环节。本文将通 过对这一环节的应急物流车辆调度问题的研究，从而在保障救灾活动救助效果的前提 下，实现应急物流过程中的经济性的目标，最大程度地减少突发事件带了的损失。 1 3 3 应急物流的运作流程 应急物流的运作流程如下图1 2 所示：应急物流系统涉及应急物流协调指挥中心、 物资供给端、物资需求端和应急物资配送中心等几个部门。应急物流协调指挥中心通过 应急物流信息平台和技术支持平台对采购部门、运输保障部门和物流中心管理部门等部 门进行协调指挥，指挥、控制和管理各部门的作业，并向各部门发送指令，同时接受各 部门的实时回馈信息，实现各部门信息的双向传递。最终将供用点所提供的应急救灾物 资进行分拣、加工、包装后配送到受灾点。 6 长安大学硕士学位论文 逦萝一p 一掌一薹一掌 、 一 、 i 里1 l 竺塑鳖! ! ! l 图1 2 应急物流运作流程 物流 一垡堕 1 4 研究的主要内容概述 本论文研究内容如下： 第一章：绪论： 首先阐述应急物流研究的背景以及研究意义；其次探讨国内外学术界在应急物流车 辆调度领域的研究动态和成果，以及研究的不足和存在的问题；并分析应急物流的内涵 和特点、研究内容、运作流程；最后，介绍本文的研究内容。 第二章、车辆调度基本问题的分析： 本章分析了车辆调度的基本问题，包括v r p 问题的提出、分类、用于研究v r p 问 题的两种模型一有容量约束的v r p 问题和有时间窗约束的v r p 问题的模型、以及求解 v r p 问题的基本方法。 第三章、应急物流车辆调度模型的构建： 通过研究应急物流配送车辆调度问题，分析了应急物流车辆调度问题与v r p 问题 的区别。在分析、界定问题的基础上，构建了应急物流车辆调度的数学模型，并分析了 该问题的研究目标和模型需要的基本信息，最后确定了本文解决该问题所选择的算法一 蚁群算法。 第四章、基本蚁群算法的数学模型及应用： 在分析蚂蚁算法的基本原理及特点的基础上，构建了基本蚁群算法的数学模型并对 相关参数的设置进行了分析。 第五章、基于蚁群算法的应急物流车辆调度计算模型和程序设计： 首先分析了应急物流车辆调度问题的求解思路，为了更好地应用蚁群算法求解应急 7 第一章绪论 物流v r p 问题，针对蚁群算法的不足，分别通过改进转移规律、改进信息素更新规则 和对初始值的启发对蚁群算法进行改进。并提出求解应急物流车辆调度问题的算法设计 和实现步骤，采用算例进行测试，以验证利用改进蚁群算法求解物流车辆调度问题的可 行性和有效性。 结论与展望： 文章的结论与展望部分，在介绍了本文的研究成果同时，分析了本文研究存在的不 足以及未来的研究方向。 8 长安大学硕士学位论文 第二章车辆调度基本问题分析 2 1 车辆调度问题的定义 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 定义为：已知一系列客户、配送中 心，在满足一定约束条件( 如货物的需求量、发送量、交发货时间、车辆最大载质量限 制、行驶里程限制等) 下，组织合理的配送路线，使配送车辆有序地完成所有的配送， 达到一定的目标( 如行驶总里程最短、行驶费用最小、时间尽量少、使用车辆数尽量少 箜【l l 】 可 。 自1 9 5 9 年d a n t z i g 和r a m s e r 提出v r p 问题以来，很快引起了应用学科的专家和运 输计划制定者和和管理者的重视，从此，v r p 问题成为运筹学、组合数学、运用数学、 物流科学、计算机等组合优化领域研究的热点问题。 2 2 车辆调度问题的分类 随着国内外各科学者对v r p 问题研究的不断深入，v r p 问题的理论体系也在不断 完善。根据其构成要素和分类标准不同，v r p 问题分类如下： 1 ) 按物流中心的数目不同，可分为单物流中心问题和多物流中心问题。 2 ) 按配送任务特征不同，可分为纯装问题( p u r ep i c ku p ) 、纯卸问题( p u r ed e l i v e r y ) 和装卸混合问题( c o m b i n e dp i c ku pa n dd e l i v e r y ) 。 3 ) 按配送车辆的载货状况不同，可分为满载问题、非满载问题、以及满载和非满 载混合问题。 4 ) 按用户需求性质不同，可分为确定性问题( 客户固定，包括位置和需求量或者 供应量固定) 和随机性问题( 客户不固定) 。 5 ) 按客户对货物取( 送) 时间的要求不同，可分为带时间窗的车辆调度问题( v e h i c l e r o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，v r p t w ) 和无时限车辆调度问题( 指客户对货物的 取走或送达的时间无具体要求) 。 v r p t w 问题指客户要求将需求的货物或供应的货物在规定的时间窗内送到或取 走，也称为有时限问题。v r p t w 问题又分为带硬时间窗车辆调度问题问题( v e h i c l e r 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 s ，v r p h t w ) 和带软时间窗车辆调度问题 ( v e h i c l er o u t i n gp r o b l e mw i t hs o f tt i m ew i n d o w s ，v r p s t w ) 。 v r p h t w 问题是指客户要求必须在规定的时间窗内将货物送到或取走，既不能提 前也不能拖后。v r p s t w 问题是指客户要求尽量在规定的时间窗内将货物送到或取走， 9 第二章车辆调度基本问题分析 也可以提前或拖后，但当提前或拖后时，配送企业会受到一定的经济惩罚。 6 ) 按车辆类型数不同，可分为单车型问题( 指所有配送车辆的类型和最大载质量相 同) 和多车型问题( 指配送车辆的类型和最大载质量不完全相同) 。 7 ) 按车辆对车场的所属关系不同，可分为车辆开放问题( 指配送车辆完成配送任务 后可以不返回其发出车场) 和车辆封闭问题( 指配送车辆完成配送任务后必须返回其发出 车场) 。 8 ) 按优化目标数不同，可分为单目标问题( 仅考虑一个配送目标) 和多目标问题( 同 时考虑多个配送目标) 。 2 3 车辆调度问题的模型 根据车辆调度问题的类型，v r p 问题有许多子问题，不同的子问题的数学模型也是 有差异的。用于研究的基础v l 姆模型是有容量约束的车辆调度问题( c a p a c i t a t e dv e h u c l e r o u t i n gp r o b l e m ，c v r p ) 和v r p t w 的模型。 2 3 1c v r p 问题的数学模型 典型的c v r p 问题是配送车辆从单一的物流配送中心出发，寻找路程最短行车线 路，这组行车线路要求从配送中心出发，依次对地理上分散的多个顾客进行配送服务， 并要求每个顾客有且仅有一辆配送车辆对其服务，每辆配送车辆的载质量不能超过车辆 的最大载质量，且完成配送任务后必须返回物流配送中心。 ( 1 ) 基本假设条件 1 ) 假设c v r p 是确定性问题，即物流配送中心和所有顾客位置、需求量或供应量 已知： 2 ) 假设c v i 冲是非满载、单车型问题，即所有的配送车辆规格一致、最大载质量 相同，同时每个顾客的物资需求量小于配送车辆的最大载质量，在满足最大载质量限制 的条件下，多项配送任务可以共用一个配送车辆。 3 ) 假设c v a p 是车辆封闭问题，即配送车辆完成配送任务后必须返回配送中心。 4 ) 运输路网为完全网络，即所有网点之间都有线路连通； ( 2 ) c v r p 问题的模型 c v r p 模型表述如下：设有一个物流配送中心编号为0 ，拥有m 辆车，最大载质量 为q ，车辆行驶距离的单位成本是c ，现需要完成个顾客点的配送任务，求满足条件 的最小费用的行车路线。令g ：( v ，d ) 为一无向图，其中v = 圪，k ，) ，为 1 0 长安大学硕士学位论文 物流配送中心，k ，e e9 为个顾客点；顾客的物资需求量为q ( i = 1 ，2 ，n ) ， 且q q ；d 是连接所有客户需求点和物流配送中心的边集，吒d ( k ，巧v ，且 i _ ，) 是连接两网点间的距离。 定义变量如下： f 1 车辆k 从行驶到 x u k 2 1 0 否则 。5 f 1 顾客点矿的任务由车辆k 完成 2 1 0 否则 ； 目标函数：m i n z = 啄 ( 2 1 ) 约束条件： 虼= l k = l nm = i m q 虼q i = 1 ，2 ，n j = o ，l ，2 ，ee e 9n i = 0 ，1 ，2 ，e e 9n ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) 式( 2 1 ) 表示车辆在配送过程中总费用最小； 式( 2 2 ) 、式( 2 3 ) 、式( 2 4 ) 保证每个顾客都有且仅有一辆车提供服务； 式( 2 5 ) 表示车辆在配送过程中，对任何一辆车而言所装货物的总重量不会超过其 车辆本身的最大载质量； 式( 2 6 ) 保证了所有车辆从物流配送中心出发，最后回到物流配送中心。 2 3 2v r p t w 问题的模型 v r p t w 问题又分为v r p h t w 问题和v r p s t w 问题。本文先以v r p s t w 为例进 行建模。 v r p s t w 问题是指客户要求尽量在规定的时间窗内将货物送到或取走，但也可以 提前或拖后，当提前或拖后时，配送企业会受到一定的经济惩罚。 ( 1 ) 基本假设条件 = 嘞 m 糊 脚 七v 叶 m h ：豆 = 卉黾 m 纠瑚 第二章车辆调度基本闯题分析 与c v r p 问题的基本假设条件相似，只是问题的约束条件增加了时间窗的约束，从 而运行费用有所变化。 ( 2 ) v r p s t w 问题的模型 v r p s t w 模型表述如下：设有一个物流配送中心编号为0 ，现需要完成个顾客点 的配送任务，求满足最小费用的行车路线。令g = ( y ，d ) 为一无向图，其中v = v o ，k ， ) ，为物流配送中心，k ，e e e9 为个顾客点；d 是连接所有客户需求点和物 流配送中心的边的集合，吒d ( k ，巧v ，r i ) 是连接两网点间的距离。 m 一物流配送中心用来完成个顾客点的配送任务的最大车辆数； 一表示需要完成的配送任务的数目； 以一表示边集d 中的某边的长度，其中j ，j f = o ，1 ，e e e 9n ；f _ ，； q 一表示顾客k 的货物需求量，其中i = 1 ，2 ，且q q 只互一表示配送车辆将货物送达顾客点k 的时间； c 一表示车辆行驶单位距离的运输成本； 【e z ，z 卜一为顾客点k 要求货物送达的时间范围，其中e 互是顾客k 要求货物送到 的最早时间，工正是顾客形要求货物送到的最晚时间； ( 尺互) 一为惩罚函数，表示车辆在【e 互，工互】之外将货物送达顾客点k 所增加的罚 金成本。，足分别表示提前或拖后将货物送达顾客点杉的惩罚系数。 定义变量如下： f l 车辆七从k 行驶到以 瓠2 1o蔷则 _ f l 顾客点的任务由车辆k 完成 虼2 1o 否则 。 目标函数： m i n z = + 只( j j c 巧) ( 2 7 ) 厶一一厶一 可v 厶一 i 、，一7 惩罚函数： j 足( e 互- a t , ) r 互 三互 1 2 长安大学硕士学位论文 约束条件： m 虼= 1 扛1 ，2 ，n k = l = l i = 0 k = l nm = l j = 0 女= l m q 虼q ，= 0 ，1 ，2 ，n i = 0 ，1 ，2 ，n v k ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 式( 2 7 ) 表示车辆在配送过程中总费用最小； 式( 2 8 ) 表示车辆提前或拖后到达顾客需求点的惩罚函数； 式( 2 9 ) 、式( 2 1 0 ) 、式( 2 1 1 ) 保证每个顾客都有且仅有一辆车提供服务； 式( 2 1 2 ) 表示车辆在配送过程中，任何配送车辆都不能超载； 式( 2 1 3 ) 保证了所有配送车辆从物流配送中心出发，最终都要回到物流配送中心。 式( 2