（管理科学与工程专业论文）基于服务质量的物流保障网络路径规划研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 未来高技术战争中军用物资需求品种繁多、数量巨大、时间紧迫，为确保战 争胜利，参战部队必须获得迅速及时、安全可靠、经济有效的物资保障服务，为 此对物流保障系统提出了更高的服务质量要求。物流保障网络是服务于现代化战 争，以基地、仓库等保障实体为依托，以各种运输保障通道为连接，以满足部队 需求为目标，把各种保障资源按一定的要求和原则合理部署，在空间上成网络化 布局的物流保障系统。 网络路径规划技术是当前研究的热点之一，军事领域的物流保障网络路径规 划技术研究更引起军内外学者的广泛注意，在现有物流保障网络设施基础上，通 过对物资运输路径进行规划，对提高我军物资保障能力，确保战争胜利具有关键 作用。 本文在综述网络路径规划技术研究现状的基础上，重点研究了物流保障系统 的定义及建模、物流保障网络及服务质量参数体系、关键网络资源调度策略、网 络路径规划技术等内容，主要研究工作如下： 在分析物流保障系统组成结构、基本功能及影响要素的基础上，给出了物流 保障网络的建模与分析方法、网络化模型以及明确物流保障网络路径规划技术的 研究范围。 提出了建立物流保障网络服务质量参数体系基本原则。在研究分析计算机网 络、通信网络、交通物流网络服务质量参数基础上，建立了物流保障网络层次模 型，即网络拓扑层、网络传输层、网络应用层；提出了各个层次上的服务质量参 数，包括任务完成率等若干新的参数，建立了物流保障网络服务质量参数体系。 在分析保障物资分割运输属性的基础上，讨论了单任务网络路径规划问题。 根据物资流在网络上传输时完全不可分割、基于时间可分割、基于空间可分割三 种属性，考虑用户对物资保障的规模性、时效性、安全性、经济性等服务质量要 求，运用运筹学、图论、计算机仿真等理论和方法，分别建立基于不同传输性质 的网络路径规划模型，设计相应的算法，求解满足网络拓扑属性约束和服务质量 要求的网络路径规划方案。 针对多个保障任务可能同时发生的情形，研究了多任务网络路径规划问题。 首先，根据不同保障任务对关键网络资源使用需求程度以及对整个保障网络系统 效能的贡献度为基础，提出了一种基于综合度量的关键网络资源调度策略；其次， 结合物资流在网络上的传输属性，提出了基于传输时间的独立路径问题；最后， 给定任务集合，以任务完成率为优化目标，建立了多任务网络路径规划模型，利 用多蚁群并行优化原理，设计了多任务网络路径规划的算法，并且针对每一个任 第i 页 国防科学技术大学研究生院博士学位论文 务，搜索网络时空资源相互独立的优化路径，求解任务完成率最高的网络路径规 划方案。 主题词：物流保障网络，路径规划，服务质量，蚁群优化，综合度量 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t i nt h ef u t u r eh i g l l - t e e hl o c a lw a r f a r e , t h ev a r i e t yo f m i l i t a r ym a t e r i a lr e q u i r e m e n t s i sv a r i o u s ，t h ea m o u n ti sh u g ea n dt h es c h e d u l ei st i g h t t oa s s u r et h ev i c t o r yo f w a r f a r e ， e a c hu n i to ft h ef o r c em u s tb es u p p o r t e dn o to n l yi nt i m eb u ta l s or e l i a b l ya n d e f f e c t i v e l y ，w h i c hr e q u i r e st h el o 西s t i e ss u p p o r ts y s t e mt op r o v i d eh i g h e rs e r v i c eq u a l i t y al o g i s t i c ss u p p o r tn e t w o r k ( l s n ) ，w h i c hs e w v e sm o d e r nw a r f a r e , c o n s i s t so fs u p p o r t e n t i t i e ss u c ha sb a s e sa n dw a r e h o u s e sa n di sc o n n e c t e db yt r a f f i cn e t w o r k s l s n d i s p o s e sv a r i o u ss u p p o r tr e s o u r c e sa c c o r d i n gt os o m er u l e sa n dr e q u i r e m e n t sa n dc o m e s i n t ob e i n gan e t w o r kl a y o u ts y s t e m r e c e n t l y , n e t w o r kp a t hp l a n n i n gi st h er e s e a r c hf o c u si nt h ef i e l do fn e t w o r k a p p l i c a t i o n , e s p e c i a l l ym i l i t a r yl o g i s t i c ss u p p o r tn e t w o r k b a s e do ne x i s t i n gl s n ， o p t i m i z a t i o no fp a t hp l a n n i n gi so fk e ys i g n i f i c a n c et oi m p r o v et h es u p p o r ta b i l i t ya n d a s s u r et h ev i c t o r yo fw a r f a r e b a s e do ns u m m a r i z i n gt h ec u r r e n tp r o g r e s so np a t hp l a n n i n gt e c h n i q u e so fl s n ， t h i st h e s i ss t u d i e st h ed e f i n i t i o na n dm o d e l i n go fl s n ，t h es e r v i c eq u a l i t yp a r a m e t e r s s y s t e m , t h ek e yn e t w o r kr e s o t l r c cs c h e d u l i n ga n dt h ep a t hp l a n n i n go fl s n t h em a i n r e s u l t sa r ea sf o l l o w s b ys y s t e m a t i c a l l ya n a l y z i n gt h es t r u c t u r e ，f u n c t i o n sa n df a c t o r sa f f e c t i n gl s n ，t h i s t h e s i sp r o p o s e sam o d e l i n ga n da n a l y s i sm e t h o do fl s na n dd e f i n e st h er e s e a r c hb o u n d o fp a t hp l a n n i n go fl s n s o m eb a s i cp r i n c i p l e sf o rp a r a m e t e r ss y s t e mo fs e r v i c eq u a l i t ya r ep r e s e n t e d b a s e do nt h es e r v i c eq u a l i t yo fi n t e m e t ，c o m m u n i c a t i o nn e t w o r ka n dt r a f f i cn e t w o r k ，a t h r e e l a y e r sp a r a m e t e r ss y s t e mo fs e r v i c eq u a l i t yo fl s ni sp r o p o s e d ，i e ，t h en e t w o r k t o p o l o g yl a y e r , t h en e t w o r kt r a n s p o r t a t i o nl a y e ra n dt h en e t w o r ka p p l i c a t i o nl a y e r s o m en e wi n d e x e ss u c ha st h em i s s i o np e r f o r m a b i l i t ya r ep r o p o s e d t h ep a t hp l a n n i n gp r o b l e mw i t hs i n g l et a s ki ss t u d i e dc o n s i d e r i n gm a t e r i a l s p a r t i t i o na t t r i b u t e s t a k i n gi n t oa c c o u n tt h eq u a n t i t y , t i m e ，r e l i a b i l i t ya n dc o s te ta l ，f o r i n d i v i s i b l et r a n s p o r t a t i o n ，p a r t i t i o n - t r a n s p o r t a t i o nb yt i m ea n dp a r t i t i o n - t r a n s p o r t a t i o n b ys p a c er e s p e c t i v e l y ，t h i st h e s i sp r o p o s e sp a t hp l a n n i n gm o d e l ，d e s i g n sa c c o r d i n g a l g o r i t h m sa n do b t a i n ss a t i s f i e ds c h e m e sw i t hn e t w o r kt o p o l o g yc o n s t r a i n sa n ds e r v i c e q u a l i t yc o n s t r a i n su s i n gm e t h o d so fo p e r a t i o n a lr e s e a r c h , g r a p ht h e o r y ，c o m p u t e r s i m u l a t i o ne ta 1 t h ep a t hp l a n n i n gp r o b l e mw i t hm u l t i t a s k si ss t u d i e d f i r s t l y , b a s e do nt h eg r a d e f o ru s i n gt h ek e yn e t w o r kr e s o u r c 鹃a n dt h ec o n t r i b u t i o nf o rs y s t e me f f i c i e n c y ，ak e y n e t w o r kr e s o u r c es c h e d u l i n gs t r a t e g yb a s e do nc o m b i n e dm e a s u r e m e n ti sp r e s e n t e d s e c o n d l y ，a c c o r d i n gt ot r a n s p o r t a t i o na t t r i b u t eo fm a t e r i a lf l o w ，距i r r e l a t e dp a t h p r o b l e m b a s e do nt r a n s p o r t a t i o nt i m ea n d s p a c ei sp r e s e n t e d l a s t l y ，g i v e na s e to ft a s k s ， 第i _ i i 页 国防科学技术大学研究生院博士学位论文 a 抽：l i i l ga tt h em i s s i o np e r f o r m a b i l i t y ，t h i st h e s i se s t a b l i s h e sam u l t i t a s k sp a t hp l a n n i n g m o d e la n dd e s i g n sa na l g o r i t h mb a s e d0 1 1t h ep r i n c i p l eo fm u l t i - a n tc o l o n i e sp a r a l l e l o p t i m i z a t i o n , w h i c hs e a r c h e st h ei r r e l a t e dp a t ho nt i m ea n ds p a c ef o re a c hm i s s i o na n d o b t a i n sas e to f p a t hp l a n n i n gs c h e m e sw i t hm a x i m a lm i s s i o np e r f o r m a b i l i t y k e y w o r d ：l o g i s t i c ss u p p o r tn e t w o r k 【l s n ) ，p a t hp l a n n i n g ，q u a l i t yo f s e r v i c e ，a n tc o l o n yo p t i m i z a t i o n ，c o m b i n e dm e a s u r e m e n t 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 公路等级划分表17 表2 2 铁路等级划分表18 表2 3 飞行区等级指标1 8 表2 4 美军军用物资分类1 9 表2 5 服务质量参数层次表。3 0 表3 1 网络流不可分割的路径规划算法时间复杂度分析5 4 表3 2 网络流不可分割的最小时延路径规划方案。5 7 表3 3 网络流不可分割的最可靠路路径规划方案5 7 表3 4 网络流不可分割的最小费用路径规划方案。5 8 表3 5 网络流不可分割的不同物资量路径规划方案5 8 表3 6 基于改进遗传算法的最小时延路径规划方案( 一) 6 2 表3 7 求解网络流不可分割的路径规划问题的算法搜索效率比较6 2 表3 8 网络流时间可分割的最小时延路径规划方案6 9 表3 9 网络流时间可分割的最可靠路径规划方案6 9 表3 1 0 网络流时间可分割的最小费用路径规划方案6 9 表3 1 1 网络流时间可分割的不同物资量路径规划方案6 9 表3 1 2 基于改进遗传算法的最小时延路径规划方案( 二) 7 1 表3 1 3 求解网络流时间可分割的路径规划问题的算法搜索效率比较7 2 表3 1 4 网络流空间可分割的最小时延路径规划方案7 7 表3 1 5 网络流空间可分割的最可靠路径规划方案7 7 表3 1 6 网络流空间可分割的最小费用路径规划方案7 8 表3 1 7 网络流空间可分割的不同物资量路径规划方案一7 8 表3 1 8 基于改进遗传算法的最小时延路径规划方案( 三) 8 0 表3 1 9 求解网络流空间可分割的路径规划问题的算法搜索效率比较8 0 表4 1 多任务网络路径规划算法时间复杂度分析1 0 4 表4 2 保障任务及服务质量参数10 5 表4 3 多任务网络路径规划方案1 0 6 表4 4 多任务网络路径规划算法性能比较1 0 8 表5 1 战役物流保障网络边附加属性1 1 4 表5 2 物资不可分割的运输保障方案1 1 7 表5 3 物资时间可分割的运输保障方案1 1 8 表5 4 物资空间可分割的运输保障方案1 2 0 第页 国防科学技术大学研究生院博士学位论文 表5 5 保障任务及服务质量参数表1 2 1 表5 6 多任务运输保障方案1 2 2 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 论文研究内容及结构关系1 3 图2 1 区域保障设施分布图2 3 图2 2 区域枢纽网络示意图2 3 图2 3 带节点属性的网络扩展示意图2 3 图2 4 基于节点扩展的区域网络示意图2 3 图2 5 网络无缝连接示意图2 4 图2 6 网络传输一致性示意图2 4 图2 7 保障网络服务质量参数层次关系图3 0 图2 8 路段传输容量示意图。3 2 图2 9 路段传输时延示意图3 3 图2 1 0 路段传输费用示意图3 5 图3 1 物流保障网络示例图5 6 图3 2 网络流不可分割的物资量与最优值关系5 8 图3 3 交通网络传输示意图“ 图3 4 网络流时间可分割的物资量与最优值关系7 0 图3 5 网络流空间可分割的物资量与最优值关系。7 9 图4 1 网络单元上的时空资源示意图8 4 图4 2 网络时空资源占用示意图( 一) 8 5 图4 3 网络时空资源占用示意图( 二) 8 6 图4 4 网络路径和参数度量空间的映射关系9 5 图4 5 网络路径和服务质量要求映射到参数度量空间上的点。9 6 图4 6 物流保障网络示例图10 5 图5 1 节点带属性的物流保障网络1 1 2 图5 2 战役物流保障网络1 1 3 图5 3 物资不可分割的运输路径图1 1 7 图5 4 物资时间可分割的运输路径图1 1 9 图5 5 物资空间可分割的运输路径图1 2 1 第页 国防科学技术大学研究生院博士学位论文 第一章绪论 本文研究基于服务质量的物流保障网络路径规划问题。首先从网络拓扑来看， 网络单元上附加有多个不同性质的属性，对网络流传输形成约束；其次从网络应 用来看，保障物资传输必须满足用户服务质量要求。因此，该问题是物资在网络 上传输过程中满足约束的路径规划问题。这项研究起源于智能交通系统、计算机 网络系统、应急救援系统、军事后勤保障系统等多个应用领域，虽然在不同的应 用领域模型不尽相同，但在满足多个约束，为用户提供服务质量保证方面是一致 的。目前，网络路径规划问题有些已经解决或通过改进现有模型及算法可以解决， 但是，仍然存在一些具有挑战性的问题，特别是在军事领域的应用，需要展开深 入的研究。本文针对这些亟待解决的问题，在现有成果的基础上，从理论和应用 两个方面开展相关研究，包括路径规划理论、模型和算法研究，关键网络资源调 度策略分析以及军事运输保障应用研究。通过这些研究旨在提高物流保障服务水 平和保障服务能力。 1 1 课题研究背景及意义 未来战争中，需要通过后勤保障迅速及时、安全可靠、经济有效地向战区大 规模集结军事力量，并形成决定性优势。由于任务繁重导致运输速度、运输准确 度和运输强度等要求非常高，必须立足已有的保障网络资源，综合运用各种运输 力量，优化运输网络，规划运输保障路线，充分满足作战应用需求。因此，网络 路径规划技术是物流保障系统为满足部队用户需求并提供服务质量保证的重要手 段之一【1 ，2 1 。 在冷兵器时代，军用物资保障品种简单、范围小、易于组织，主要采用基于 人力、畜力、风力的陆运和水运方式，运输保障路线选择主要依靠将领的经验进 行决策。1 8 世纪产业革命以来，相继出现了火车、汽车、蒸汽动力船舶、飞机等 运输工具，并由此掀起了各种运输网络建设的高潮，触发了战争模式的巨大变革。 与此同时，战争模式的变革反过来又对物流保障网络提出了更高的要求。二战以 后的历次战争，逐渐从根本上改变了以往战争模式，保障物资种类之繁多，范围 之宽广，消耗数量之巨大，组织运输之艰难，超乎想象。例如，2 0 0 3 年3 月美国 发动了旨在推翻萨达姆政权的伊拉克战争，其军用物资运输保障工作实际上早在 第1 页 国防科学技术大学研究生院博士学位论文 “9 l l ”事件后的2 0 0 1 年1 2 月就已经展开，历时1 年零三个月，2 5 0 万种军用物 资的生产、采购、存储、配送把物流保障推向一个空前复杂的高度【3 】。随着现代战 争的发展，与之相适应的保障网络逐渐呈现以下四个方面的特点：网络资源紧缺 化、服务要求多样化、保障布局层次化、应用商业化。 第一，物流保障网络资源相对紧缺的特点。保障网络建设随着社会不断发展 进步，已经形成了四通八达的公路网、铁路网、航空网、水路网、管线网及其它 运输通道。目前，我国从经济建设和军事应用的角度都提出了加快基础设施建设 战略方针，交通网络运输能力得到极大的提耐4 1 ，在一定程度上缓解了保障网络资 源紧缺的局面。但是，未来战争对保障物资种类、数量的需求，运输保障的迅速、 安全、经济等方面的服务质量要求，以及保障目标点的不确定性和突发性，使得 运输网络资源仍然相对紧缺【5 】。物资保障是战争取得胜利的关键要素之一，反过来， 对战争胜利的渴望又导致了物资需求无止境，难以从根本上解决紧缺问题。因此， 如何立足于现有保障网络资源，调和部队需求和网络资源相对紧缺的矛盾，实现 网络运输最优化，是网络路径规划必须解决的问题。 第二，物流保障网络服务多样化。飞速发展的现代化物流能力推动了战争向 快速、高消耗方向发展；不断变革的战争模式对物流能力又提出了更高的要求。 一般来说，物流保障网络服务多样化包括以下两个方面的含义：一方面是面向应 用的服务多样化；另一方面是面向需求的服务多样化。面向应用的服务多样化主 要指不同的物资运输保障本身具有不同的服务质量要求。例如正常情况下被装给 养对保障时效性、经济性具有明确的要求，而弹药等危险物资运输则对保障可靠 性非常敏感，此外，一些大型整件装备运输对线路容量具有特别的要求。面向需 求的服务多样化指同样的应用服务可能有不同的服务质量要求。例如平时的军火 仓库弹药基数配备只需要在正常计划时间内，安全可靠的运达即可，而在双方交 战状态弹药告急的情况下，可能对保障的时效性提出非常高的要求，甚至在可容 忍的范围内降低保障的可靠性要求。因此，未来战争条件下，物流保障网络必须 能够为不同级别用户提供多样化、差别化的服务。 第三，物流保障呈现网络层次化的特点。网络层次化主要指物流保障网络是 一个多层次多模式的网络。首先，网络是由不同的运输网络组成的综合保障网络， 各种运输网通过一些枢纽节点连接成更大规模的网络。例如，二战后美国国防部 通过对国防铁路运输需求分析，在国家铁路网上确立了一个具有战略意义的铁路 运输通道系统，它构成了一个整体的、相互连接的铁路网，能够迅速地在全国范 围内运送国防物资和国防装备。随后，在2 0 世纪5 0 年代初，艾森豪威尔就任美 第2 页 国防科学技术大学研究生院博士学位论文 国总统后，提出了兴建国防公路网计划。这一计划的执行，使美国建成了四通八 达的公路网。这样，通过一些关键性的铁路枢纽、河海港岸、航空中枢及其它交 通设施，组成了从军队驻地、物资储备基地到世界各地的庞大的物流保障网络【2 】； 其次，即使在同质网络中，仍然存在层次化的趋势，如公路网络中的国家高速公 路骨干网，省级公路网等，而铁路网未来发展逐步区分为客运网和货运网。网络 层次化发展的趋势对网络资源的调度、网络路径规划提出了更高的要求。 第四，物流保障应用逐步走向商业化的道路。应用商业化主要指未来的物流 保障不再是军队一揽子包办的业务，而应该逐步交由商用网络来承担。例如，美 军把所有的保障物资分为十类，除了第五类军火弹药主要由军方运输保障之外， 其余九类保障物资已经部分甚至全部交由商业公司的运输保障【l 】。 物流保障网络的上述特点，对传统的网络资源调度分配策略及路径规划技术 提出了新的挑战和新的研究方向。传统的策略由于片面追求单方面的目标而浪费 耗大量的网络资源，由此造成资源利用率低，任务调度顾此失彼，易陷入局部最 优，难以满足作战需求，甚至迟滞作战行动。现代化的物流保障日益强调服务的 多样化、差异化和满意度，“服务质量 被提升到一个空前的高度，主要表现在 以下两个方面： 首先，从部队用户的角度来看，战场态势瞬息万变，作战模式复杂多样，保 障物资运输属性各不相同，执行作战任务特殊性，希望获得相匹配并尽可能好的 服务。 其次，从物流保障系统的角度来看，为每一个保障任务制定运输保障方案， 把有限的网络资源分配给最需要服务、最能产生“效益”的部队用户，即通过提 供差别化的物流保障服务，尽可能使每个部队用户在满足约束条件下获得最好的 服务，保障作战任务顺利执行，并且使整个保障网络的资源计划达到最优状态。 综上所述，现代化战争对物流保障网络服务提出了更高的要求，基于服务质 量的网络路径规划技术不再以满足用户单个方面的需求为唯一目标，而是综合考 虑约束满足、用户满意、资源利用等要素，以任务完成为目标。目前，我军在这 方面的理论研究尚处于探索阶段，实际应用中缺乏统一的领导机构，各种运输方 式衔接松散，网络资源缺乏有效的整合，运输路径选择基本处于人工决策阶段， 凭借经验判断，容易陷入局部最优，难以实现用户满意度最大化和保障资源利用 率最大化。本文研究目标是通过对网络路径规划理论与应用研究，为每个任务制 定运输保障方案，提高保障网络资源的优化水平，使之能够提供与现代化战争相 适应的服务水平。研究成果对于整合物流保障网络资源，提高网络传输性能，提 第3 页 国防科学技术大学研究生院博士学位论文 升物流保障服务质量，具有重要理论和现实意义，其政治、经济、军事效益显著。 1 2 物流保障网络路径规划问题 物流保障网络路径规划问题应用于军事领域具有鲜明的特色。首先，军用物 资通过保障网络运输，形成网络流。从流的角度来看，计算机、通信等信息网络 中传输无形数据流，而物流保障网络是一个非同质的混合网络，传输有形的物资 流，其传输机制更加复杂多样；其次，军用物资的空间移动通过运输工具实现。 从路径选择的角度来看，和一般的车辆路径问题有相似之处，但区别在于不同运 输网络上的运输工具属性具有根本区别，其移动范围往往仅限于一定的局域网络 中，如铁路机车只能在铁路路网上运行，无法延伸到其它路网，使得网络路径规 划问题更趋复杂。 保障部门在制定军用物资运输方案时，主要涉及以下三类不同的问题： 第一类问题根据单个任务目标，在满足某个约束条件下，搜索关于目标参数 的最短路径，这类问题可以归为单任务约束最短路径规划问题。 第二类问题根据单个任务需求，在源点和目标点之间搜索满足多个服务质量 要求的网络路径，这类问题可以归为单任务多约束网络路径规划问题。 第三类问题根据多个任务需求，在多个源点和多个目标点之间搜索网络路径 集合，一方面尽可能满足单个任务的服务质量要求；另一方面使任务完成率最大 化，这类问题可以归结为多任务多约束网络路径规划问题。 在网络资源无限制的情况下，通过搜索源点和目标点对之间关于目标参数的 最短路径，很容易为每一个保障任务规划可行路径或最优路径，但一般情况下， 网络资源通常是有限的，需要解决路径规划问题。而该问题即使只包含一个约束， 也是n p c o m p l e t e 完全问题【6 】，当网络规模非常大时无法通过经典的解析方法求 解。因此对多约束网络路径规划问题，目前主要依靠智能优化算法求解。 1 3 网络路径规划问题研究现状 迄今为止，国内外研究网络路径规划技术主要集中在计算机网络、通信网络 的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 路由问题，交通、物流领域的车辆路径问题， 这些问题有一个共同的特点，数据流、交通流、物资流在网络传输过程中，不仅 受到网络单元自身属性的约束，还必须满足用户服务质量要求。 第4 页 国防科学技术大学研究生院博士学位论文 物流保障系统中，各种类型的交通工具运载军用物资在保障网络上移动形成 物资流运输过程中，一方面受到了路网属性的约束，如最大传输容量的限制；另 一方面必须满足用户的服务质量要求，需要选择合适的路径到达目的地。因此， 网络路径规划技术可应用于研究保障物资运输的路线选择问题。 基于服务质量的物流保障网络路径规划研究主要从以下几个方面展开：物流 保障网络分析与构建；物流保障网络服务质量参数体系研究：关键网络资源调度 策略分析；网络路径规划理论、模型及算法等。面对未来战争日益庞大的物资保 障需求，从运输路径优化的角度提高物资输送能力，是提高我军保障能力的重点 研究方向之一。 1 3 1 物流保障网络服务质量参数研究现状 服务质量参数是描述物流保障网络满足用户需求能力的参数体系。服务质量 的概念最早来源于服务管理行业【j 7 剐，大量的研究表明商业领域良好的服务质量是 顾客满意度的主要途径之一，而满意度又是维护老顾客、保持行业竞争优势的基 础【9 ，l o 】。随后，各个行业逐渐接受并开始重视提高服务质量，但是绝大多数研究工 作只给出服务质量参数定性描述，而在定量研究方面，主要有信息领域的服务质 量参数研究，包括计算机网纠11 1 、通信网络【1 2 】的q o s 服务质量框架体系，交通、 物流领域的服务质量参数体系研究【1 3 1 。因此，本节重点对信息网络服务质量参数 和物流网络服务质量参数进行综述。 1 3 1 1 信息网络的服务质量参数研究现状 研究信息网络服务质量通常是基于端到端的网络模型，提出可量化的数据传 输指标，如带宽、分组丢失率、端到端时延、抖动等，这些指标又称为服务质量 参数【l l ，1 4 15 1 。 带宽是指网络在单位时间内传输的数据总量，即数据传送率。严格地说，带 宽是指网络的带宽，它与应用程序实际吞吐量是有区别的，由于网络和协议的开 销，应用程序的吞吐量应比网络的带宽要低，带宽是最重要的服务质量参数，对 其它的服务质量参数有着重要影响。 分组丢失率是指在两个时间参考点传输时丢失的分组数与己发送的分组总数 的比值。计算机网络中的分组丢失主要是缓冲器业务太多，排队时间长溢出丢失， 有线网络中的分组丢失主要是由网络拥塞引起的。 端到端时延指业务流的分组从发送端传输到接收端所需的平均经过时间。产 第5 页 国防科学技术大学研究生院博士学位论文 生时延的因素很多，包括分组时延、排队时延、交换时延和传播时延。 抖动即时延的变化，是指同一业务流中不同分组所呈现的时延不同。它一般 是因为业务流中相继分组的排队等候时间不同引起的。对需要给用户一个稳定的 帧速率的实时多媒体应用来说，将抖动限制在一定的范围内很重要。 从系统的观点来看，各种系统如通信系统、信息系统等具有明显的层次结构， 系统的服务质量取决于但不限于每个层次的服务质量，对每个层次上服务质量参 数的准确定义是描述整个系统服务的基本前提。就q o s 分层模型而言，k n a h r s t e d 等人提出的三层模型是各种分层模型的基础【l l 1 6 1 ，模型包括应用层、系统层、设 备层三个层次，在每一层次上提出相应的q o s 参数来描述该层次上的服务，最终 完整地描述了整个系统的服务质量。多媒体应用是信息网络典型的q o s 服务，其 应用层q o s 参数描述对应用服务的要求，包括记录速率、标称数据速率、压缩模 式、画面大小、要求的视频帧速、要求的数据速率、最大端端时延、采样频率、 采样量化、编码方法、数据速率、同步等参数。系统层q o s 参数描述由q o s 导出 的对通信、信息服务及操作系统服务的要求，包括报文长度、报文间隔、最大系统 端端延迟、延迟抖动、报文丢失率、连续报文丢失长度、保证程度、控制任务优 先级、代价等参数：网络层q o s 参数则描述对于网络服务的要求，包括最大传输 单元、令牌桶速率、令牌桶容量、最大传输速率、最大网络端端延迟、延迟抖动、 丢失敏感度、要求带宽保证的质量等参数【1 5 1 。 除了以上针对应用提出的q o s 参数之外，还有学者针对网络传输可靠性提出 度量参数，b a r b e r i s 等提出了用网络吞吐量超过给定阈值的概率作为度量网络性能 可靠性的度量参刻 】。p a r k 、b o n a v e n t u r a 等提出了基于传输时延的网络性能可靠 性度量参数【1 3 1 9 j 。 1 3 1 2 交通、物流网络的服务质量参数研究现状 交通、物流领域的服务质量参数研究在国外经历了四十多年的发展历程。上 个世纪六十年代开始，一些学者开始研究物流服务问题，提出了服务质量的概念， 最具代表性的研究是w d p e r r a u l t 提出以时间、地点、效用为基础的7 r s 理论， 该理论认为，物流服务是指企业能在恰当的时间( r i g h tt i m e ) 和正确的场合( f i g h t p l a c e ) ，以合适的价格( r i g h tp r i c e ) 和方式( r i g h tc h a n n e lo rw a y ) ，为正确的客户( r i g h t c u s t o m e r ) 提供合适的产品和服务( r i g h tp r o d i c e ) ，使客户个性化需求( r i g h tw a n to r w i s h ) 得到满足，价值得到提高的活动过程【2 0 】。该理论从服务提供者的角度出发， 在时间、地点等方面提供更加精确化的服务，创造更高价值，但是这个时期的研 究没有关注客户是如何理解服务质量，即特定的产品和服务质量是否就是客户感 第6 页 国防科学技术大学研究生院博士学位论文 知的质量【2 1 1 。因此，这种依据服务提供者对自身所提供服务做出的评价，是缺乏 客观性的，需要一个从客户角度来研究服务质量。到上世纪八十到九十年代， 些学者开始围绕服务质量的量化问题展开研究，比较重要的成就是m e n t z e r 等人提 出了物流服务包括实体配送服务和营销服务两个方面，提出了实体配送服务 ( p h y s i c a ld i s t r i b u t i o ns e r v i c eq u _ a l i t y ，p d s q ) 测量表【功。随后，一些学者在此基础 上进一步发展和完善了p d s q 测量表【2 3 ，硎。在解决服务质量量化问题之后，本世 纪以来学者们开始围绕顾客满意度展开研刭2 5 1 ，顾客满意度需要一些定性化的参 数描述，并且与不同的行业、不同的文化背景密切相关。 相比较而言，国内关于物流服务质量的学术研究起步较晚，差距明显。早期 的研究主要是围绕运输服务提出了一些发展思路t 2 6 1 ，随后不同行业从不同的角度 展开了服务质量的研列2 7 - 2 9 ，也有研究者建立了物流服务质量评价体系【3 0 1 ，并对 国外物流服务质量研究进行了综述【3 ，但所有这些研究主要提出一些定性化的参 数评价服务质量水平，还缺乏一套完整的参数体系。 物流保障网络服务质量是基于军事应用背景提出的概念，从网络和运输保障 两个角度研究物流保障网络的服务质量。首先，物流保障系统不再是链式结构， 而是趋向于网络化的结构【3 2 ，3 3 】：其次，运输是达到一定服务质量的基本要求【3 4 1 。 目前，还没有文献对物流保障网络服务质量展开研究，迫切需要构建物流保障网 络服务质量参数体系，完整描述物流保障网络提供服务的能力，整合物流保障网 络结构，优化网络资源配置。 1 3 2 网络资源调度策略问题研究现状 资源调度是早期在项目管理中为实现资源利用最大化而发展起来的一种优化 技术【3 5 3 6 】，并且伴随着通信系统、计算机系统、网格计算系统迅速发展逐渐成为 网络的重要支撑技术之一阳目前，网络资源调度主要针对网络上有限的网络容 量或者带宽资源进行合理分配，而关于网络资源调度策略尚没有通用方法。一般 由具体优化问题提出相应的策略，或者根据不同的优化目标采用不同的策略，从 而决定不同的资源调度分配顺序。 国外在网络资源调度策略研究方面起步比较早，已经取得了一定的研究成果。 先来先服务策略被广泛用于网络带宽分配，数据包或者网络流获得带宽分配优先 权完全决定于到达时间【3 引。公平排队调度策略是另个应用比较广泛的资源调度 策略f 3 9 删，一些学者在此基础上进一步提出了加权公平调度策略【4 ，最大最小公 平调度策吲4 2 】等扩展公平排队调度策略。而最早期限优先调度策略则是以围绕数 第7 页 国防科学技术大学研究生院博士学位论文 据包或网络流到达目标点的期限为准则进行资源分配的【4 3 一j 。 国内研究网络资源调度研究起步比较晚，主要借鉴引进国外比较成熟的策略 进行研究，有学者从时间和成本的角度进行综合优化提出了相应的策略【4 5 1 ，也有 学者从网络资源消费的角度提出调度策略 4 6 1 。总之，网络资源调度策略具有较强 的针对性，有必要对物流保障网络上的关键网络资源调度策略进行深入研究。 1 3 3 网络路径规划问题研究现状 网络路径规划问题最早从图论、简单网络最短路径问题发展而来【4 7 铷】，考虑 网络约束，产生约束路径规划问题【5 l 5 2 1 ，考虑多个目标，产生多目标路径规划问 题【5 3 1 。此外，多元商品流问题以及联合运输路径规划问题，也是网络路径规划的 扩展问题。 最短路径问题是网络优化领域的核心子问题之一，主要研究网络上附加单个 属性的单目标优化问题【5 4 ，随着最短路径问题广泛应用，网络附加的属性也由最 短距离发展到各种各样的属性，如以时间作为网络的属性，产生最快路径问题【5 5 】； 危险品的运输需要选择最安全可靠的路径，或者风险代价最小的路径，产生了最 可靠路径问题、最小风险路径问趔5 6 】【8 3 】【5 7 1 ，此外，还有学者引入随机理论，产生 了最短期望路径问题【8 2 1 。在研究最短路径问题的同时，提出了很多可行的算法， 最经典的是d i j k s t r a 算法【5 8 1 ，f l o y d 算法 s o l ，f o r d 算法【5 9 1 ，基本上所有单属性单目 标最短路径问题都可以用确定性的算法求解。 约束路径规划问题是最短路径问题的扩展，也是网络优化领域的基本问题之 一【6 0 6 ，主要研究网络上附加多个属性的路径规划问题。约束路径规划问题包括 最简单的约束最短路径问题【3 8 】和多约束路径规划问题【9 3 6 2 1 。前者只考虑一个属性 约束，一个目标参数；后者考虑了多个属性约束，一个目标参数。约束路径规划 问题应用范围非常广泛，如一些学者在研究海运集装箱的运输路线选择问题时， 考虑了航线的容量、装载质量限制、以及重空箱等属性约束，求解最小费用的运 输路线【6 3 ，6 4 1 ，获得了满意的研究结果。针对该问题更多的研究集中在信息网络领 域，考虑网络时延、吞吐量、时延抖动、带宽等多个属性约束，求解决满足多个 服务质量要求的网络路由问题【6 5 ，吲。大量研究表明，多约束路径规划问题是n p 问题，不能用解析的方法求解，只能用近似算法、智能算法或者仿真的方法获得 解决方案1 6 7 - 6 9 1 。 多目标路径规划问题是最短路径问题的另一扩展问题，也是网络优化领域的 重要问题之一。该问题主要研究多个优化目标的路径规划问题1 7 0 , 7 1 1 。目前多数学 第8 页 国防科学技术大学研究生院博士学位论文 者倾向于通过加权的方法把多个目标转换成单目标问题求解【5 9 1 ，或者搜索p r a t o 空 间的可行解1 6 0