（管理科学与工程专业论文）动态车辆路径问题实时策略与技术支撑分析.pdf

西南交通大学硕士研究生学位论文 摘要 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是物流运输研究领域内 一个非常重要的问题。传统v r p 研究都是静态模型，即在安排车辆路径之前 所有的相关信息都已经知道并且确定。这种静态模型显然不能适应于存在诸 多不确定因素的实际运输系统：因此对包含不确定性信息的动态车辆路经问 题( d y n a m i cv e h i c l er o u t i n gp r o b l e m ，d v r p ) 的研究就成为必要。同时，近 十年来信息科技与计算机软硬件技术的飞速发展也为动态v r p 应用于实际 提供了坚实的技术支撑平台，使得动态v r p 的研究拥有了实际的价值。 本文主要从理论研究的方法论和实际应用中的技术手段两大角度对动态 v r p 做出了一个比较全面的分析。首先通过比较动态v r p 与传统静态模型 的区别来突显动态v r p 研究的主要目标、自身的特点和在研究中需要关注 的因素，并根据不同动态模型中不确定信息的特性首次划分了两大动态v r p 的研究方法。接着介绍了衡量不同v r p 动态程度大小的动态度的概念，分别 给出了有时间窟限制和无时间窗限制条件下动态度的计算公式。本文的核心 是利用排队论模型设计一种新的路径实时优化策略，计算出其系统时间并用 数据仿真实验来验证其在实际情况中的表现。最后对诤动态模型在实际应 用中各环节自身运行及相互问协调沟通所需要的技术支撑平台作一个概要性 的介绍。 关键词：动态车辆路径问题：a p r i o r i 优化方法：排队论：全球卫星定位系统 西南交通大学硕士研究生学位论文i i a b s t r a c t v e h i c l er o u t i n gp r o b l e m ，o r 冲，i sav e r yi m p o r t a n ts u bp r o b l e mi n b o r ni n m a n y d i s t r i b u t i o ns y s t e m s r e s e a r c ho nc o n v e n t i o n a lv r pi sn o r m a l l yb a s e d u p o n s t a t i cm o d e l ，i nw h i c ha l lr e l e v a n ti n f o r m a t i o nr e g a r d i n gr o u t sc o n s t r u c t i o n i s k n o w nb e f o r et h er o u t i n g p r o c e s sa n d w i l ln o tc h a n g e d u r i n g t h eo p e r a t i o nc o u t s e n e v e r t h e l e s s ，t h e r ee x i s ta1 0 to f u n c e r t a i nf a c t o r si nt h et e a la p p l i c a t i o nt h i sf a c t c o m b i n e dw i t ht h ee v e ri n c r e a s i n gf o c u so n j u s t - i n t i m el o g i s t i c s ，w h i c hc a l l sf o ra m o r ef l e x i b l ea n dt i m e l ym a n n e ro ft h ed i s t r i b u t i o ns y s t e m s r e n di tn e c e s s a r yt o g i v em o r ea t t e n t i o nt ot h ed y n a m i cc o u n t e r p a r to f t h ec o n v e n t i o n a l l ys t a t i cv r p b e c a u s ei t i n c o r p o r a t e ss t o c h a s t i ca n dd y n a m i cf a c t o r s i nt h es a m et i m e w i t ht h e r a p i dd e v e l o p m e n t i n t e l e c o m m u n i c a t i o n sa n d c o m p u t e r h a r d w a r e s o f t w a r e r e l a t e dd o m a i n s ，t h ea p p l i c a t i o n so f d y n a m i cv e h i c l er o u t i n g p r o b l e m ，o rd v r p ， d r a wm o r ea n dm o r ea t t e n t i o nn o to n l yw i t h i nt h es c i e n t i f i cc o m m u n i t y ，b u ta l s o f r o mt h ed i s t r i b u t i o na n d t r a n s p i r a t i o ni n d u s t r y t h i st h e s i sf o c u s e so nt w oa s p e c t so fd v r pt h ef i r s to n ei st oc l a s s i f yv a d o u s m e t h o d o l o g i e so fd v r ps t u d y ，a c c o r d i n g t ot h en a t u r eo fd y n a m i c s t o c h a s t i c i n f o r m a t i o ni ne a c hm o d e l ，i n t ot w o l a r g eg r o u p s ：t h ea p r i o r io p t i m i z a t i o n a p p r o a c h a n dr e a l t i m e o p t i m i z a t i o n m e t h o d sf u r t h e rm o r e ，an e wr e a l t i m e r o u t i n gs t r a t e g yi sp r o p o s e da n d t e s t e db yd a t as i m u l a t i o n t h es e c o n dp u r p o s eo f t h et h e s i si st op r o v i d eac o m p r e h e n s i v ea n a l y s i so ft e c h n o l o g i c a li s s u e si nt h e i m p l e m e n t a t i o no f d v r p k e y w o r d s ：d y n a m i cv r p ：a - p r i o r io p t i m i z a t i o n ；q u e u et h e o r y ；g p s 西南交通大学硕士研究生学位论文第1 页 1 1 问题的提出 第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 ) 是指，对一系列发 货点和( 或) 收货点，组成适当的行车路径，使车辆有序地通过它们，在满 足一定约束条件( 如货物需求量，货物需求时间，车辆容量) 下，达到一定 的目标( 如行驶里程最短，费用极小，时间最少使用车辆数尽黄少等) ，参 阅【1 】i 2 】， 9 】。由于与运筹学理论研究和实际，卜产牛活有紧密联系，在过去的 4 0 年啦面，v r p 得到了广泛的研究和应用，已从最初的交通运输领域拓展到 t 、l k 管理、电力工程、通讯工程及超大规模集成电路设汁等方面。 在以往的研究中，人们一般假定在构造路衽之前，所有的信息( 包括顾 客信息、车辆信息、路况信息和线路制定青信息) 都足确定的，安排的路径 也是柯l 对同定的，这类v r p 被称为静态v r p 。仳匙在实际的路径0 q 题i h 这些信息中银多_ i l f 是随机和带有动态性的，并n 伴随着路线的执行过程同时 到来。j 静态v r p 相对随，把这类带钉随机性、动态性的车辆路径0 d 题毒l ：为 动态v r p 。卜面给出几个实衔i 的动态v r p 的例了： 1 供暖燃油配送系统 北荚和欧洲的很多家庭在冬季是靠燃油来为事内供暖的，需蚤燃i l f i 配送 公司的服务。燃油配送公司的通常做法是根据用户f ：一次加油的时问和此段 时问的灭气情况来大致估计此用户f = 前燃油的库存情况。“j 估计到此j f j 户的 库存低于某个水平( 如2 0 ) 时，即把此用户列入下一次配送的名单之内。 如果完全按照这种做法这个系统就是一个静态v r p ，但是实际情况并非如此， 每天都会有一部分顾客因为燃油用尽而打电话到配送公司要求得到最即的服 务。出现实际情况与原先估计偏差的原因主要有天气情况的突然变化( 如气 温的突然降低导致供暖燃油的剧烈消耗) 、用户供暖房间面积的突然增加( 如 亲戚朋友的来访) 等等。经验数据表明一个供暖燃油配送公司大约有2 0 的 用户需求都是这种动态需求。由于存在动态的、不确定的因素，所以这个系 统就成为一个动态v r p 的模型。 亘堕塞塑查堂堕主塑塞生堂焦笙壅篁! 蔓 2 长途邮件快递业务 长途邮件快递公司( 如u p s 、f e d e x 、d h l 等) 在世界范围内提供邮件 包裹的快递业务。业务流程如下图所示： 卡车 火车 矧1 1 长途邮件快递业务 如图，整个、i k 务大毁分成邮件的收集和分送两夫过程。在邮件分送过程 基本j ：足一个静态路径问题，阕为分送车辆人员在出发之前就已经知道所 有的邮件接收者的确切信息。邮件的收集过程则是一个动态路径问题，当邮 件收集车辆人员出发去收集邮件时，并不知道所青的颤客信息，实际。 ：很 大一部分顾客都是动态顾客。 3 货物急送业务 货物急送业务是动态集送货一体化车辆路径问题( d y n a m i cg e n e r a l p i c k - u p a n dd e l i v e r yv e h i c l e r o u t i n gp r o b l e m , d g p d p ) 的一个应用模型。运 输公司通过电话接收动态需求，然后派车辆到顾客处去收集货物，再转运到 顾客指定的地点去卸货。在货物急送业务中顾客往往需要立即得到服务，所 以不能像处理静态v r p 那样把当天收到的顾客需求编入次日的工作计划中。 西南交通大学硕士研究生学位论文第3 页 4 出租车服务 城市里面随处可见的出租车服务是一类典型的动态v r p 例子。在出租车 服务问题中，提前预约来要求服务的静态顾客的数日可以忽略不计，绝大部 分顾客都是要求“招手即停”的动态顾客。在服务完一个顾客后，出租车司 机通常的做法有停留在原地等待下一个顾客，返回到一个他认为比较容易招 揽到顾客的地方等待，或者沿着道路慢开来搜索下一个动态顾客等等。 5 紧急服务 救护车、警车以及救火车等的出动都属于紧急服务的范畴。紧急服务车 辆首要的也可以说唯一的目标就是在第一时间内赶到现场进行紧急服务( 救 护伤员、侦察现场、对失火建筑进行救火等) ，所以在绝大部分情况f 都是 接到一个任务后就真接行驶到目的地，而不是等待多个任务后到达后再进行 路释安排。圉此，对紧急服务的研究多集中在眼务车辆最佳等待位置的选择 i 二。 除_ r 需求有可能是动态的外，其它很多闲素也使现实情况中人部分的车 辆路径问题都或多或少地带有动态成分。这些瞰素包括变化的道路拥挤情况 导致的行驶时问的不确定性、车辆在行驶过程中自身的故障导毁的服务延迟 以及距离加油站的远近不同造成的时间延迟等等。 槲统计，各圜运输成本占园民生产总值的1 0 1 5 苊右。这就意味着 运输系统的效率提高一点就可咀节约很多成本。同时最近十年来计算机和 通信技术的发展，特别是地理信息系统、数字地图技术、全球卫疆定位技术、 无线通信技术等的成熟，也为动态车辆问题应用到实际提供了可行的技术支 撑。综，：所述，对于动态车辆路径问题的研究不仅有理论f ：必要，而且也具 有r 实际麻用的可能。 1 2 研究现状 动态v r p 的研究在过去的1 0 1 5 年里面逐渐兴起，各种专著和杂志上 出现了一批研究动态随机v r p 的论文，下面列举出其中比较重要的一些。 p s a r a f i i s 是最早研究动态v r p 的学者之一，他在( 4 s 1 中比较了v r p 静态 与动态模型的主要区别，在【5 0 】中分析了动态心的研究现状并对未来的研 西南交通大学硕士研究生学位论文第4 页 究前景做出了展望。p o w e l l 和j a i u e t 等在1 5 2 1 中集中分析了随机v r p 模型， 对j a i l l e l 首先提出的a d r i 嘶优化方法( 见2 2 节) 做出了补充和扩展。 b e r t s i m a s 和s i m e h i l e v i 在 2 2 1 中分析了各种已有的动态v r p 算法的鲁棒性 和渐进特性。他们对动态v r p 的理论分析加深了对各种算法结构的认识，并 且建立了对其表现的评价体系。他们还指出如果计算机运算速度还不够支持 实时策略的运行要求的话，那么a 口f i o r i 优化方法可以作为一种比较好的替 代方法。g e n d r e a u 和p o t v i n 在【4 4 】指出动态v r p 还有很多问题急需研究，特 别是对构造行车路径至关重要的需求预测方面的研究还没有一个满意的模 型。他们建议在动态v r p 中采用并行算法以加快求解速度：同时他们还提出 r 在不确定性环境下做撮坏情况分析的必要性。 国内对动态v r p 的研究开始的比较晚，从9 0 年代中后期开始才陆续 有相关学术文章发表。其中西南交通大学郭耀煌教授主持的国家自然科学基 金项口“不确定信息条件下动态车辆路径问题研究”是对动态v r p 进行的 一个比较全而深入的研究。该项项目的研究从2 0 0 1 年开始， 要日标是： 通过对v r p 中不确定性囡素的系统分析，建立不确定性信息条件下动态 v r p 的多目标模型，设汁可实时处理小确定性信息的肩发式雨】并行的、暖启 发式算法，开发效率高、速度快、适应性强、交互性好的实用动态车辆路径 安排系统。浚项研究i i 要研究内容包括以f 叫个方面： ( j ) 动态v r p 中不确定性闻素的系统分析。通过对v r p 中夫最不确 定模糊圳素的分析来研究它们之间的交玎影响、选择干扰和有限迭加原 理，以提高路径安排方案的可靠性和适应性。 ( 2 ) 信息不确定条件下的动态v r p 模型研究。改变以往研究中车辆在 由某车场或服务点驶往下一车场或服务点的途中，不周出现新的信息而改变 目的地的一般假设，建立车辆在途中可以改变目的地的一对多、多对多的动 态v r p 模型体系：在分析各种不确定性因素相互影响和有限迭加的基础上， 综合考虑车辆、顾客、路况和路径制定者等方面出现的不确定性，建立包含 多种不确定性因素，满足车辆、路网容量、交通规范约束，考虑运输企业和 顾客要求的实用多目标动态v r p 模型。 【3 ) 算法研究。根据上面提出的模型提出一套算法体系，包括：a ) 将 西南交通大学硕士研究生学位论文第5 页 静态v r p 的传统启发式算法进行修正和拓展，以适应处理不确定性信息的 需要；b ) 利用遗传算法、模拟退火算法和神经网络的学习算法等亚启发式算 法在优化领域表现出全局寻优、适应性强、速度快等优点，将它们应用于动 态v r p 研究领域，并将着力设计基于自适应的并行亚启发式算法，并用计 算机进行模拟对比。 ( 4 ) 应用研究。研制实用、方便、快捷的软件系统，并应用于交通运 输企业和交通管理部门。 目前，通过该项目的研究，已经有几篇比较重要的关于动态v r p 的学术 论文发表。郭耀煌，谢秉磊，郭强在 7 中首次比较详细地定义了随机v r p 问题并对其特性、分类等作了全面地分析。郭耀煌等还在该文中对随机v r p 的策略进行了讨论，并提出了随机动态v r p 今后的几个研究方向。张建勇， 谢秉磊，李军在 1 2 中把模糊预约时间的概念引入到v r p 的研究中，从顾 客满意度的角度分析了模糊不确定信息条件下的多目标车辆优化路径问题。 1 3 本文的目的和体系结构 本文的目的主要有j 个。首先是对动态v r p 本身的一些基本概念和研究 【1 闲该给予关注的方面以及研究方法做一个全面的介绍：并提出ri 爰分动态 v r p 复杂程度的动态度的概念。本文的第二：个目是摹于现有研究方法的基础 卜提出一种新的动态v r p 行车路线实时调整策略，来缩短顾客的平均等待时 间以提高其满意度。本文的最后一个目的是想比较全面地分析一下动态v r p 在实际应用中的技术保障。 下面介绍一下本文的大致结构： 第l 章绪论，作者在1 1 节中通过介绍v r p 的研究历史并列举出几个实 际的动态v r p 例子来说明研究动态冲的理论意义和实际需要；接着在1 2 节中对动态v r p 在国内外学术界的研究现状进行了分析介绍。 在第2 章中作者对一些有关动态v r p 的基本问题做出了介绍。首先 在2 1 节中通过比较传统静态v r p 比动态v r p 的异同来给出一个作者认为 西南交通大学硕士研究生学位论文第6 页 比较恰当的动态v r p 的定义，并归纳出了动态v r p 的一些特点：然后在2 2 节中分析了动态冲研究领域中两类比较常用的研究方法。 作者在第3 章中提出用一个统一的量化标准来刻画动态v r p 的动态复杂 程度以使得不同动态v r p 实例间可以相互比较，并把这个标准定义为动态 度。3 1 节和3 2 节分别给出了无时间窗约束和有时间窗约束条件下的动态度 公式，接着在33 节中把实际问题中一些典型的动态v r p 例子分成了动态性 较弱、中等、较强三大类，并在3 4 节中讨论了动态v r p 动态度与优化目标 之间的关系。 在第4 章中，作者通过利用4 1 节给出的相关背景知识；在4 2 节建立了 动态v r p 的排队论模型，并求出了其系统时间的一般公式：在43 节中提出 了一种新的实时路线调整策略，即中点重定位策略。紧接着在第5 章中用一 个仿真实例来验证了这种实时策略系统时间理论计算值与实际结果之间的一 致性，并通过与顺穿服务策略的比较显示了中点重定位策略更能减少颐客的 平均等待时间，从而提高服务的质最。 最后往第6 尊中作者分别在6l 节、6 2 节和6 3 节比较全面地分析了动 态v r p 在实际应用中三个关键环节( 运输车辆的定位，运输车辆与调度中心 之间的无线通信以及调度中心的策略制定平台) 需要的技术支撑。 西南交通大学硕士研究生学位论文第7 页 第2 章动态车辆路径问题概述 本章的目的是对动态v r p 本身的一些基本概念和研究中应该给予关注 的方面以及研究方法做一个概要性的介绍。首先在2 1 节中通过比较传统静 态v r p 与动态v r p 的异同来给出个作者认为比较恰当的动态v r p 的定 义，并归纳出了动态v r p 的一些特点；然后在2 2 节中分析了动态、，r p 研 究领域中两类比较常用的研究方法。 2 1 动、静态车辆路径问题的比较 动态v r p 是在静态v r p 的研究基础之上发展起来的。通过比较静、动 态v r p ，可以更好地揭示出动态v r p 的特征以及研究该闷题时应该关注的 方而。为此，先介绍一下传统静态路径问题。 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 是一切路径问题的原础。 t s p 可以夫致描述为：旅行商从驻地 i 发去访问一系列已经汁划确定的城 市后返回原地，应如何安排其旅行路线，才能使得总的旅行距离最短( 也可 以是旅行费用最少或旅行时问最短等) 。静态v r p 可以看怍是t s p 的扩展 和延仲丰要表现存静态v r p 中般有辆运输车辆，所以要制定出胛条 行车路线去服务一组确定的颐客。这m 辆车可以从同一个中心车场 发，也 可以从币同地点m 发。另外，运输车辆的载货量的限制，、与某辆车服务的累 汁需求超过它的载货量时，邪么这辆车必须返回车场去重新装货或者卸货。 如图2 1r 扣第条路经所示，当运输车辆服务完需求1 2 时，车 ：的剩余供 货毓载最已小能满足需求1 3 ，所以它必须返回车场去重新装货卸货然后再 驶向1 3 。在实际情况中还有很多附加的限制使得问题变得更加复杂。例如， 服务需求开始时刻的时间窗限制，工作日总长时问的限制等等。芙于静态心 的更详细讨论和研究，请参考【1 】， 8 】，【2 7 】，【3 0 。 堕塑壅塑查堂塑主塑塞竺兰竺鲨塞塑! 里 口车场。需求点一行车路线 陶2 1 静态车辆路释问题 小难看f ，静态路径问题都有一个共同点，就是存制定路线的时候旅行 商所要防问的城价真者运输车辆所要服务的顾客都已经确定。柑反地，如果 往路线制定时存在着不确定腻素，那么这个问题就可以看作动态路径问题。 借鉴p s a r a f l i s 在【4 8 】中对动、静态路径问题的区别，作者把具有以f 两条性 质巾任意一条的v r p 问题定义为动态v r p ： 1 并非所有有关路线制定的信息都在制定过程开始之前就已经知道，这 些相关信息包括顾客信息，如地理位置、现场服务时间、需求量等，也包括 系统信息，比如两地之间的旅行时间等等； 2 一些有关路线制定的信息并不是确定的，有可能会随着时间的变化而 改变。 在实际v r p 问题中，大鼍存在着，j 二述定义所描述的现象，阔2 2 给出了 一个例子。两辆货车从同一车场去执行任务，其中预先需求( 车辆出发之前 就已经确定的需求) 用白色的小圆圈表示，实时需求( 车辆出发后才收到的 需求) 用黑色的小圆圈表示。单实线箭头表示计划路线，即计划者在车辆从 车场出发之前根据预先需求设计好的路线。双实线箭头表示实时需求到来时 运输车辆的当前行驶路段。虚线箭头表示根据实时需求做出的改进路线。把 嚣零交通大学碾童礤究熊学位论文骛9 页 实时需求攒入已经安排好的路线的理想情况跫插入藤不影响后瑟灼预先需求 被执行的顺穿，并且因为插入造成的延迟最小。圈2 - 2 中靠右的鄢条彳亍车路 线就是一种比较理想的状况。毽是在实际情况中，矮入实畦需求的l 壬务往往 很复杂，甚至需要照新安排以詹的路线。图2 2 左边的行牢路线中，插入实 孵霉袋鞋基车赣裁绕了程一个缀大熬弯。 翻车场计划路线 。援先( 静态) 嚣求= 爿卜运戆枣蜓瓣“黪行驶黪段 实时( 动态) 需求改进路线 澍2 2 动杰车辆路衽蔺题 一羧寒谖，一令路径耀蘧越复杂，缀割靛条释越多，矮人动态器裳裁会 变得越i 嗣难。例如，如果两个车辆路径问题在其他方而的条件都一样， 是 一个有对闻窝隈麓，一个没有，释么磊有靖翔蜜陵涮静车辆爨径润题中矮灭 一个动态需求就会比往没有时曲j 窗限制的车辆路径问题中插入要难得多。在 实鞒鲍搡 乍中，一个动态需求甚至可蘸两为没有合适酌插入点丽被拒绝。攘 多情；兄下，这个动态需求可以选择延迟到下一个t 作f l 被服务。但是在某些 实际例子中，例如长途部件快递服务，运营纛采取这种策略往往要冒着顾客 被竞争对手捻走嬲缝险。 从上面的例子中可以看出动态v r p 有很多自身的特点和研究中需要关 注豹魏方，主要表现在： l 。时阉霆素燮关重要。 在静态v r p 中，时间因素可能不是一个需要重点考虑的因豢，但是在动 嚣素交运大学颈女獗究生学位论文露 o 页 态v r p 中就变得黧关重爰。调度中心镶要实时地知道( 至少在新的需求到来 时刻) 所有运输车辆所处的位置，才能对行率路线做出动态调整。 2 闷戆可篷燕开藏麓。 静态v r p 孛，酵阕尺度上簌圭是蠢雾豹。瑟一条嚣车疼线舞始并续素于 同一个或者不同的车场。然而在动态v r p 中，时间尺度往往是无界的，行车 路线径蓬不楚一条开始并结泰予车场豹封阂爨线，蕊是祭开藏躲爨经。 3 糗采艴售惑具奏遗；确定投的。 静态v r p 中所有的相关信息都被假定是已知并且不会改变的。但是在实 际情况中，未来静信息不可能跫确定煮疑豹。狠多情i 觅下来来静信意盍h 动态 顾客等是完全不知道的，当然也有可能知道某些顾客的概率信息。 4 近期事件虑该得到优先考虑。 静态v r p 中由于所商的事件都是确定的并珏不会随时问改变，所以近期 和远缎的事转邦被综合程一起褥到同等灼考虑。但是在动态v r p 中，黑为信 息随时都在淑变，所以明智的做法是把注意力放在近期的事件 二。如粜仅根 据曩藜掌握熬不竞全摹患撬骰全鼹鼓长期灼俊纯，鄂么瑗在得到麴优馋绫暴 在将米很可能闲为新的动态信息的到来而变成次优或者甚至成为劣解。 5 要建立信怠更薪的机制。 在动态v r p 巾，蚤耪输入懿信怠簸嚼聱霹裴笈裳改变，羹：遗还会不叛有 新的信息到来所以建立信息更新的机制就盟得很蘸要。而在静态v r p 中， 由于稼惫一经输入虢己缀确定，掰香就没有必要建立这种受薪橇糊。 6 ，重叛安搀强务弱撬霉蹶窿，重赣分派运输车辆帮蹩可以考惠豹擞法。 动态v r p 中，由于不断有毅的需求产生。同时已经被安排的灞求也可能 要求撤消服务。面对这些新酌情况，调度中心有可能需要熏新制定服务顺序 或翥蘸瓤分派另外靛车辆去服务某个默宾。 7 计划制定翥需要更快的计算速度。 襁静态环境中，由于只需要制定一次计划，所以计划制定者可以花上几 令小瓣寒褥要令燕覆量熬簿。经是裁麓态v r p 孛，运羧攀辆鹣司枫蒜要褥 西南交通大学硕士研究生学位论文第1 1 页 到计划制定者实时的指令。这就迫使计划制定者在报短的时间，比如几分钟 内完成一次路线或者车辆分派的调整。因此，计划人员需要具有更快计算速 度的软硬件资源。 8 需要具有推迟服务的机制。 当某个需求的某些属性例如地理位嚣等可能对服务其他需求造成严重 延迟时，需要建立推迟服务这个需求的机制。具体的做法可以采取时间窗约 束或者惩罚函数。 9 优先考虑的目标是减少顾客的等待时间。 传统静态v r p 的目标往往是最小化运输车辆行驶的总距离或者总时间 等。然后在动态v r p 中，硕客能否得到及时地服务是首要的考虑困素，所以 动态v r p 的主要目标应该是最小化顾客的平均等待时闻。 j 0 时间约束需要更加宽松。 秆j 比静态v r p ，动态环境中的时问限制，如对某个需求的培晚开始服务 时间等，往往定的宽松。这样做是斟为存实际操作中往往更愿意一定程度地 去违反时间限制来接受个新增的顾客，而不是尉为违反既定的时问限制去 拒绝他。 l1 车队车辆数璧的灵活性降低。 存静态v r p 中往往可以控制车辆的数最来达到最优解。但是在动态环境 f | 于对未来需求的不确定性，往往需要配备后备车辆，这就使得自由决 定车队车辆数量的灵活性有所降低。 1 2 往往要考虑排队模型 当动态顾客的增加超过车辆服务的能力时，等待服务的顾客会越来越多。 这时需要从排队论的角度去考虑整个系统运转是否能够平稳的运转而不瘫 痪。 2 2 动态车辆路径问题的优化方法 动态姆本身是一大类问题，同时其优化方法也是多种多样。尽管如此， 亘宣壅迥大学硕士研究生学位论文第12 页 作者认为根据不同动态v r p 研究模型中动态信息的性质，可以将这些优化方 法分为两大类，既2 2 1 节中的a - p r i o r i 两阶段优化方法和2 2 2 节中的现场 一次性优化方法。 2 2 1 a - p r i o r i 两阶段优化方法 在某些动态v r p 例子中，路线调度人员在制定行车路线以前虽然不知道 哪些顾客需要服务以及服务数量的多少这些确切信息，但是却掌握了一些概 率信息。例如在供暖燃油配送系统这个例子中，对于某个顾客i ，配送公司可 以根据其上次添加油料的时间、其储油罐的容量以及近一段时间来的天气状 况等信息来判断此顾客最近几天需要重新添加油料的概率b 是多少。因此可 以先对所有顾客需求都乘以相应的概率因子，然后用解静态v r p 的方法来得 到一条预先的优化路线，或称为a - p r i o r i 优化路线，这也是a - p r i o r i 两阶段优 化方法的第一阶段。a p r i o r i 优化思想最早由j a i l l e t 在 4 3 冲提出，在这篇文 章中他定义了一个应用a - p r i o r i 方法求解的概率旅行商问题( p r o b a b i l i s t i c t r a v e l i n gs a l e s m a np r o b l e m ，p t s p l 。p t s p 不同于传统静态t s p 的地方在于 旅行商从驻地出发前并不知道有哪些城市需要访问。任意一个城市j 是否需 要被访刚都是以一个概率只( 0 p ，1 ) 给出的，也就是说城市，需要被访 问的概率是p ，不需要被访问的概率是l - 岛。这样就可以求出一条基于这些 概率信息的预先优化路线，如图2 3 ( a ) 所示。其中灰色的小圆圈表示该城市 还没有被确定是否需要旅行商去访问。当旅行商开始去执行路线时，所有的 点都将确定需不需要被访问。对于不需要被访问的点，旅行商可以摘单地将 其从旅行路线中去除而直接去访问下一个需要访问的节点如图2 3 ( b ) 所示。 其中黑色小圆圈表示最后需要被访问的城市，白色小圆圈表示最后不需要被 访问的城市。这个过程就是a p r i o r i 两阶段优化方法的第二阶段，即根据实 时顾客信息对第一阶段的预先优化路线进行调整。 要塞至塑杰兰塑主墅塞兰兰堡鲨壅篓! 兰蔓 ( a ) p t s p 预先俊化路线( b ) p t s p 实际技簿路线 圈2 3 p t s p 的a 一州o r i 两阶段优化方法 j a i l l e t 把p t s p 归纳成一个糇数非线性规划模裂，继而又转化成一个整数 线性规划模型，鬣磊用与瓣接缝t s p 类觳黪分支定爨方法来求辩这令夔数矮 划模型。他还证明虽然动态规划看起来似乎是解决p t s p 的一个很自然的选 择，爨是实际i 麓态溉划并冬戆舞到一令耩疆蕊续繁。受到释健绕t s p 豹路 线构造、路线改进方法的启示，他提出r 很多启发式算法。其中一个叫做“超 级节缝赣洼”豹爨线稳逡算法，藏是在著名豹c w 节约葵法曙。拘摹确 ：褥 来的。至于路线改进算法，j a i l l e t 提 f _ i 了一个改进版本的l - o r 哇方法，使其可 班赢翊于p t s p 的求解。 受到j a i l l e t 麓囊发，b e f | s i m a s 等东 2 3 中定义_ f 摄率车辆鹃径润遂 ( p r o b a b i l i s t i cv e h i c l er o u t i n gp r o b l e m ，p v r p ) 。p v r p 区别于静杰v r p 的唯 一再露点袭予需求不是确定豹，霭是淡一个糍率籍怒给密鹣。b e r t s i m a s 等爨 出了两种不同的策略，如图2 q 所示。2 - 4 ( a ) 是根据6 个需求点各自需要服 务与番静概率信惠计算磁来酶预先优化路线。假设运输车辆韵额定载鬣为2 个单能量，每个需求点的需求量都是l ( 如果有需求的话) 。并假定最后的 实际情况是2 、5 两点不需要服务，在2 4 b ) 、2 - 4 c ) 中雨白色圆圈表示。第 二阶段实时调整策略a 的做法怒完全按照预先优化路线采访阀鼹有暖鬈，但 是只对有需求的顾客进行服务。所以在2 - 4 ( b ) 中，除了在服务完顾客3 后需 要返回车场踅毅装货毂赞然瑟在簿驶要44 去执霉任务羚，其路线和联先优 化路线完全一致。在第二阶段实时调熬策略b 中，服务车辆将不访问没有需 西南交通大学硕士研究生学位论文第14 页 求的顾客，而直接转向下一个需要服务的顾客，2 4 ( c ) 中不需要服务的2 、5 两个顾客就被车辆绕过。策略a 和策略b 各有自己应用的场合。当运输车辆 只有行驶到顾客处时才能知道此顾客需不需要服务时，自然应该采用a 策略。 如果运输车辆能够提前知道顾客是否需要服务时，那么就可以采取b 策略绕 开不需要服务的顾客。 5 5 ( a ) p v r p 预先优化路线 ( b ) p v r p 实时调整策略a( c ) p v r p 实时调整策略b 图2 - 4p v r p 预先优化路线和实际执行策略 显然在动态强中的概率信息不仅仅局限于顾客是否需要服务，还包括 其他因素，比如不确定的旅行时间、顾客的需求量等等。g e n d r e a u 等在【4 l 】 中提出了包含更多概率因素的随机车辆路径问题( s t o c h a s t i c v e h i c l e r o u t i n g p r o b l e m ，s v r p ) 并把s v r p 分成6 类子问题，下面简要地介绍一下： 1 ) t s p s c ( t s pw i t hs t o c h a s t i cc u s t o m e r s ) 西寝童塑大学硕士研究生学位论文第15 页 顾客存在与否概率b 给出。实际上t s p s c 就等价于p t s p 。 2 ) t s p s t ( t s p w i t hs t o c h a s t i ct r a v e lt i m e s l 在这个问题中，顾客是确定的，但是网络中弧段的长度是一个随机变量， 即两点之间的旅行时间不是确定的。问题的目标一般是最大化运输车辆在规 定的期限内完成任务线路的可能性。 3 ) m - t s p s t ( m t s p s t w i t hs t o c h a s t i ct r a v e lt i m e s l 将t s p s t 扩展到m 辆运输车辆这m 条行车路线都开始和终止于同一 个车场。通常每辆车都被赋予一个启动成本来最小化使用车辆的数量。 4 ) v r p s d ( v r p w i t hs t o c h a s t i cd e m a n d s ) 顾客的需求量是一个随机量。v r p s d 是s v r p 中被研究的最多的一类问 题。 5 ) v r p s c ( v r p w i t hs t o c h a s t i cc u s t o m e r s ) 顾客存在j 否概率_ 口，给出。可以看作足t s p s c 的扩展版本。 6 ) v r p s c d ( v r p w i t hs t o c h a s t i cc u s t o m e r sa n dd e m a n d s ) v e p s c d 是v r p s c 和v r p s d 的综合版本，顾客的存在与需求量都是以 概；缸信息给出的，实际卜就相当于p v r p 。 通过l 二面的p t s p 、p v r p 等几个具体问题，可以看 5a p r i o r i 优化方法 的核心思想就是先根据将来事件的概率信息来做出一个预先的计划，然后在 第_ = 阶段得到确切的信息后通过调整这个预先计划去执行任务。具体到车辆 路径问题，a p r i o r i 两阶段优化法就是计划者根据未来的需求、服务数景、旅 行时间等概率信息先设计一条预先行车路线，当运输车辆得到确切的信息后 再根据这条预先行车路线做出适当的调整。同时a 嘶嘶两阶段优化方法的 应用范围也有一定的局限性，只有拥有一个相对固定的顾客群并且能够计算 出每个顾客将来需求概率信息，才能够使用这种方法求解。 西南交通大学硕士研究生学位论文第1 6 页 2 2 2 现场一次性优化方法 在很多实际的动态v r p 例子( 如紧急服务、出租车服务等) 中，既不存在 固定的顾客群，而且每个顾客需求又都带有很大的随机性，无法对其概率进 行统计。对于这类问题a 砸o r i 两阶段优化法就显得无能为力，而往往采取 现场一次性优化方法。所谓现场一次性优化方法，就是指事前并预先设计行 车路线，而是等到动态实时需求到来时才作安排。下而介绍几种常用到的现 场一次性优化方法策略： 1 ) 先来先服务策略( f i r s t c o m e f i r s ts e r v e d ，f c f s ) f c f s 策略根据的是先来后到的服务原则，顾客被服务的顺序和他们到 来的顺序保持一致。当运输车辆服务完一个需求后，如果此时已有新的需求 在排队等待服务，那么运输车辆就将立即驶向最先开始等待的那个顾客去进 行服务；如果此时没有新的需求，则运输车辆将停留在原地等待，直到有新 的顾客到来再开始行动。 2 ) 邻近优先策略( n e a r e s tn e i g h b o r , n n ) 存n n 策略中，当运输车辆服务完一个需求后，它将优先服务距离这个 需求最近的顾客。如果没有新的顾客，那么和f c f s 策略一样，运输车辆将 停留在原地待命。 3 ) 分批旅行商策略( n - s i z e dt r a v e l i n gs a l e s m a np r o b l e m ，n t s p ) n t s p 策略把排队等候服务的动态颐客按到来的先后顺序编组每组中的 数目为n 个。对于组内的顾客，先用诸如c w 节约算法之类的优化方法进行 一次路线安排，得到一条优化的行车路径；组与组之间则按照f c f s 的顺序 进行服务。与f c f s 和n n 策略不同的是，n t s p 策略处理的对象并不是单个 的需求，而是一个包含n 个顾客的需求组。通过对组内路线进行优化，可以 减少运输车辆行驶的总距离；但是同时也增加了颐客等待服务的平均时间。 4 ) 空间填充曲线策略( s p a c e f i l l i n g c u r v e ，s f c ) 所渭空间填充曲线，就是一条能够将某个二维平面区域完全填充满的一 维曲线，如图2 5 所示。 嚣囊交遗大学醺女酶究燮学位谂文第1 7 茭 f 挂) 簇麟 ( b )( c 1 图2 - 5s i e r p i n s k i 空问壤充曲线 魁2 5 绘出了一种空闯填充曲线的恻子。( a ) 中所示为这车中s i e r p i n s k i 空 间填充曲线的基本形状，( b ) 为将( a ) 中的基本形状缩小后复制5 份得到的扩展 臻形，趔斌捞数方法可以憋国) 中黪盟线扩鹱成( e 。憋这个扩展过程不断的循 环f 去，最脂得到的极限曲线就是s i e r p i n s k i 空问填充曲线，它可以将雅个 爱方= | ；懿维孚纛甄域壤突潢。s f c 繁酶兹激涟裁蹩用一条不薮霆复瞧蹶， 逆时针空间曲线来扫描服务区域，并按照扫描的顺序来服务顾客，如图2 - 6 琢示。荚子空蠲壤究静线策瞎委洋缨鹣态容可戳参考 5 6 】 阁2 - 6 空间填充曲线策略 西南交通大学硕士研究生学位论文第18 页 5 ) 分区策略( p a r t i t i o n i n g p a r t ) p a r t 策略的思想是把整个服务区域分成若干个小的子区域，首先集中 服务某个子区域内的顾客，当完成这个子区域内所有的任务后再转向下一个 邻近的子区域服务。图2 7 给出了一个p a r t 策略的示意图。 f 1 - - _ - _ j i t 一 _ _ + 图2 7 分区策略 西南交通大学硕士研究生学位论文第19 页 第3 章动态车辆路径问题的动态度分析 与静态v r p 的复杂程度只取决于顾客数量和他们的空间分布相比，动态 v r p 的情况就要复杂的多，因为动态事件的数量和它们到达时间的早晚也是 需要考虑的重要因素。因此，用一个统一的量化标准来刻画动态v r p 的动态 复杂程度以使得不同动态v r p 实例间可以相互比较就成为必要。作者把这个 标准定义为动态度，用符号甜表示。首先在3 1 节和3 2 节中分别提出了无 时间窗约束和有时间窗约束条件下的动态度公式，接着在3 3 节中把实际问 题中一些典型的动态v r p 例子分成了动态性较弱、中等、较强三大类并在 3 4 节中讨论了动态v r p 动态度与优化目标之间的关系。 3 1 无时间窗限制的动态度 为了简化分析在分析没有时问窗限制的动态v r p 的动态度d d 时，只 考虑静态顾客的数量、动态顾客的数量以及动态顾客到达的时间这3 个困素。 静态顾客通常被认为是在一个工作日开始之前就已经确定的顾客；而动 态颐客则是在一个工作日开始之后到来并且需要在这个工作日被服务的顾 客。如果动态顾客的数量占整个顾客群体的比例越高，直观上我们就会觉得 问题的动态程度越高。基于这种考虑，可以很直观的定义动态度村为动态顾 客数壤与全部顾客数量的比值： 5 薏 式中”站盎一动态需求的数目： n 全帮一全部需求的数目 ( 3 - 1 ) 从式( 3 1 河以看出o s 耐有菇 - 1 ，并且略础越大，问题的动态程度越高。 西南交通大学预士研究生学位论文 第2 0 页 当d 散= 1 时，所有的顾客都是动态顾客；当础有簸= o 时，所有的需求都是 静态的，实际上就是一个静态v p , p ，所以可以把静态 v r p 看作是动态啦 的一个特例。 这样来定义动态度虽然很直观方便，但是并没有考虑到动态需求到来的 时间所以并不能很充分的刻画实际问题的动态特性，圈3 3 给出了一个例 子。 0 t l t 2t 3k