（交通运输规划与管理专业论文）动态车辆路径问题的模型和算法研究.pdf

北京交通大学硬士学位论文y 8 7 8 五2 6 摘要 现代物流业的飞速发展为车辆路径问题( v e h i c l er o u t i n g p r o b l e m s ，v r p s ) 的研究提供了广泛的现实背景，同时现代通信及 信息技术的发展使实时处理车辆路径问题成为可能。随着对车辆 路径问题的研究的深入，以往静态车辆路径问题的模型和算法理 论体系已经不能满足现实中处理各种动态信息的需求，需要建立 一套新的动态车辆路径问题的模型和算法体系，动态车辆路径问 题已经成为现阶段车辆路径问题研究的热点。 本文在动态车辆路径问题现有研究成果的基础上，重点研究 了动态车辆v r p s 和动态网络v r p s 这两类动态车辆路径问题主 要工作如下： ( 1 ) 总结了动态车辆路径问题的现有研究成果，阐述了动 态车辆路径问题的定义、特点和分类，以及动态车辆路径问题的 模型和现有求解算法。 ( 2 ) 在对动态车辆v r p s 进行描述和界定的基础上，分析了 车辆动态性的原因，提出了一个新的问题车辆循环使用动态 车辆路径问题，建立了该问题的基于直观描述的数学模型，制定 了求解该问题的“制定整体优化计划+ 实时局部优化调度”的两阶 段策略，设计和实现了求解该问题的禁忌搜索+ 局部搜索算法。 ( 3 ) 在对动态网络v r p s 进行描述和界定的基础上，研究了 基于概率网络的软时间窗动态网络v r p s ，建立了该问题的基于直 观描述的数学模型，并设计和实现了求解该问题的遗传算法。 ( 4 ) 通过编制程序和实验计算分别验证了求解上述两类动 摘要 态v r p s 的算法的正确性和有效性。 关键词：动态车辆路径问题：动态车辆v r p s ；动态网络v r p s ；禁 忌搜索算法；局部搜索算法；遗传算法 2 北京交通大学硬士学位论文 a b s t r a c t t h e 触d e v e l 叩m e mo fl o 百s t i c sg i v e st h cs t u d yo fv e h i c l e m u t i n g p r o b l e m s ( v r p s ) a 伊e a t r e “i s t i cb a c k g r o u n d a tt h es 锄e t i m e ，t h ed e v e l o p m e n to fm o d e mc o m m u n i c a t i o na n di n f 0 蛐a t i o n t e c h n o l o g ym a k e si tp o s s i b l e t od e a l 、) l ，i t l lt h ev e h i c l er o 砸n g p r o b i e m si nr e a l 血n e s ot l l es t u d yo f 1 cv c h i c l er o u t i n gp r o b l e m si s g e t t i n gd e 印e lt h e0 1 dt h e o r ys y s t e mo fm o d e l sa l l da 1 9 0 r i t h m sf o r t h es t a t i cv c h i c l er o u t i n gp r o b l e m sc a nn o ts a l i s 匆t h er c q u e s to f d e a l i n gw i t h 廿l ed y n a m i ci n f o r m a t i o n an e wt h e o r ys y s t e mo f m o d e l sa i l da l g o r i t h sf o rt h ed y n 啪i cv e h i c l em u t i n gp r o b l e m s s h o u l db ee s t a b l i s h e d t h es t u d yo fn l ed y n 啪i cv e b i c l er o m i n g p r o b 】e m si st h ef o c u so fv r p sn o w 0 nt h eb a s i so ft h ef o m l e rs t u d y i i l gr e s u i t so ft 1 1 ed y n 锄i c v e h i c l er o 嘶n gp m b l e m s ，m i sp a p e rf o c l l s e so nt w ok i n d so fd y n 锄i c v e h i c l er o u t i n gp r o b l e m s ，i e d y 删m i cv e h i c l ev r p sa i l dd ”锄i c n e t w o r kv r p s t h i sp 叩e rm a i n l yi n c l u d c st i l en e x tc o n t e n t s ： ( 1 ) 1 h sp 印e rs 岫m a r i z e st l l ee x i s t i n g 矗u i t so ft l l es t u d yo n t l l ed y i l a i i l i cv e l l i c l e r o u t i n gp r o b l e m s ，e x p a t i a t e st h ed e f i i l i t i o n ， c h a r a c t e r s ，c a t e g o r i e sa 1 1 d1 1 1 ee x i s t i r i gm o d e i sa n da l g o r i 血m so fm e d y n 啪i cv e h i c l er o u t i n gp m b l e m s ( 2 ) 0 nt h eb a s i so fd e s c r i b i n ga n dr e s t n c t i n gt l l e d y n a m i c v e h i c i ev r p s ，t l l i sp 印e ra i l a l y z e st h ev 曲i c l e sd y n a m i cr e a s o n s ，p u t s f o n v a r dan c wp r o b l e mo fv e h i c l ed e c y c l ev r p s ，a n dm e nb u i l d s 血e m o d e lo ft h i sp m b l e m 谢t i ls o 矗t i l n ew i i l d o 、v sb a s e do nn a t u r a l d e s c r i p d o n ，t h 主sp a p e ra l s od e s i 盟sa 铆os t a g es t r 缸e g y ：“ma ：k i n g i n t e g r a lo p 妇l i z i n gp l a l lp l u sr e a lt i m e a t l dp a r t o p t h i l i z i n g 北京交通大学硕士学位论文 s c h e d u l i n g ) 锄dt l l e nd e s i g l l sa l l da c c o m p l i s h e st h ct a b us e a r c h a l g o m h m ( t s a ) p l u sl o c a ls e a r c ha l g o r - t h mf o rt l l et w os t a g e st o s o l v et 1 1 i sp r o b l e m ( 3 ) o nt l l eb a s i so fd e s c r i b i n ga i l dr e s t r i c t i n g 让l ed y n a m i c n e t w o r kv r p s ，t h i sp a p e rs t u d i e st h ed y n 肌i cn c “r o r kv r p sw i t h p r o b a b i l i t y e t w o r k 卸ds o f tt i m ew i n d o w s ，b u i l d st h em o d e lo ft h i s p r o b l e mb a s e do nn a t u r a ld e s c r i p t i o n ，l e nd e s i g n sa n dr e a l i z e st h e g e r l e t i ca l g o r i t h m ( g a ) f o rt l l i sp r o b l e m ( 4 ) t h i sp a p e rp r o v e st l l er i g h 协e s sa n de 行色c t i v e n e s so f t h e s e a l g o r i t l l m sf o rt h et w ok i n d so fd y n a n l i cv e h i c l em u t i n gp r o b l e m s t l l r o u g l lc o m p u t a t i o n 出e x p e r i e n c e s k e yw o r d s ：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 s ；d y n 枷i cv e l l i c l ev r p s ； d y n a m i cn e t 、v o r kv r p s ；t 曲us e a r c ha l g o r i t h r n ；l o c a ls e a r c ha i g o r i t h m ； g e n e t i ca i g o r i t h m 2 北京交通大学硕士学位论文 1 绪论 1 1 选题背景和研究意义 车辆路径问题( v e h i c l er o u t i n gp m b l e m s ，v r p s ) 是指对一 系列发货点或收货点，组织适当的行车路线，使车辆有序地通过 它们，在满足一定的约束条件( 如货物需求量、发送量、交发货 时间、车辆容量限制、经济行驶里程限制、时间限制等) 下，达 到一定的目标( 如路程最短、费用最小、时间尽量少、使用车辆 尽量少等) 【”。该问题由d a n t z i g 和鼬i i n s c r 【2 】于1 9 5 9 年首次提出， 它将运筹学理论研究和实际生产生活紧密联系起来，显现出旺盛 的生命力，是运筹学领域四十多年研究最活跃、成果最精彩的方 向之一。 v r p s 自提出以来已经历了三个阶段： 第一阶段：经典的v r p s 。这个阶段的v r p s 一般都基于如下 假定：在构造路径之前，所有的信息( 包括顾客信息、车辆信息、 路况信息和路径制定者信息) 都是确定的，路径制定者对所有信 息掌握在胸，并且信息均与时间无关，处理的多为某个地方的实 际问题，可移植性差。 第二阶段：基于数学规划的v r p s 。这一阶段人们利用精确 的数学规划建立数学模型，然后求解数学规划，取得了较好的效 果。虽然数学规划是精确的。但它仅能求解小规模的确定的v r p s 。 第三阶段：基于人工智能的v r p s 。这一阶段人们利用模拟 退火算法、遗传算法等一些人工智能算法求解v r p s 。这一阶段 动态车辆路径问题的模型和算法研究 处理的问题是大规模的、随机的，可移植性较好，避免了较繁的 计算，取得了很好的效果。 但是，即使是发展到第三阶段，绝大多数关于v r p s 的研究 仍然基于前述信息确定的假定，安排的路径也是相对固定的，这 类v r p s 被称为静态v r p s 。但是，客观世界存在着大量的不确定 性，反映在v r p s 中，主要有不确定的顾客需求、不确定的顾客 需求时间、线路制定者决策的主观偏好性、交通拥挤、车辍故障 等。这些不确定信息随着时间的推移出现，需要动态改变车辆的 运行路线，对已安排好的车辆路径进行及时调整。这时，静态v r p s 的理论和方法不再具有处理这些问题的能力，需要研究一整套新 的求解动态v r p s 的理论和方法。由此可见，动态v r p s 更贴近 实际生产和生活，再加上通信和信息处理技术的发展使得实时处 理随机和模糊信息、动态安排车辆路径成为可能，从而促使v r p s 研究的重心从静态v r p s 转向动态v r p s 。文献 3 1 中有关动态运 输问题的研究，集中了动态v r p s 的些成果，并将动态v r p s 的思想和模型应用到邮件速递、产品配送、生产计划等许多方面。 目前关于动态车辆路径问题的研究多集中在需求不确定的车 辆路径问题上。且国内仅有谢秉磊、郭耀煌、李军以及袁健等人 在该问题上取得了一定的研究成果。国内外关于其他不确定信息 条件下的动态车辆路径问题的研究成果相对较少。因此，本文将 动态车辆v r p s 和动态网络v r p s 作为研究对象，具有很强的理 论意义。 现代物流业已经被普遍认为是“第三利润源”，v r p s 是物流 管理研究中的一项重要内容。选取恰当的车辆路径，可以加快对 北京交通大学硕士学位论文 客户需求的响应速度，提高服务质量，增强客户对物流环节的满 意度，降低物流服务商的运作成本。目前，v r p s 的研究成果在 运输系统、物流配送系统、快递收发系统中都已得到广泛应用。 本文对动态v r p s 的研究也将主要以现代物流业中的车辆路径问 题为背景，力图解决现实问题。由此可见，动态v r p s 研究的具 有很强的现实意义。 综上所述，v r p s 研究具有很强的理论和现实意义，而动态 v l 冲s 比静态v r p s 更复杂，更能反映实际情况，更有利于解决现 实问题。所以，动态v r p s 的研究有着更强的理论和现实意义。 1 2 动态车辆路径问题概述 1 2 1 动态车辆路径问题的构成要素和定义 本文将以现实物流系统的车辆路径问题为背景深入研究动态 车辆路径问题。在物流系统的车辆路径问题中，动态车辆路径问 题主要包括货物、车辆、物流中心、客户、运输网络、约束条件 和目标函数等要素。 ( 1 ) 货物。其主要属性包括：品名、包装、重量、体积、要 求送到( 或取走) 的时间和地点、能否分批配送等属性。 ( 2 ) 车辆。其主要属性包括：车辆的数量、类型、装载量、 一次运送的最大经济行驶距离、停放位置等。 ( 3 ) 物流中心。也称为物流基地、物流据点，是指进行集货、 分货、配货、配装、送货作业的配送中心、仓库、车站、港口等。 ( 4 ) 客户。客户的属性包括需求( 或供应) 货物的数量、需 动态车辆路径问题的模型和算法研究 求( 或供应) 货物的时间、需求( 或供应) 货物次数及需求( 或 供应) 货物的满足程度等。需求( 或供应) 货物的时间我们一般 称为时间窗( n m e w i n d o w ) 。时间窗又分为硬时间窗( h a r d t i m e w i n d o w ) 和软时间窗( s o rt i m e w i n d o w ) 。硬时间窗是指 货物必须在指定的时间窗内送到，不能提前，也不能拖后，如果 在硬时间窗外送到，客户将会拒收货物。软时间窗是指货物尽量 在时间窗内送到，但允许提前或拖后，只不过提前或拖后时会受 到一定的惩罚，惩罚量与提前或拖后的时间有关，可以是线性， 也可以是非线性。另外，提前的惩罚系数一般小于拖后的惩罚系 数。 ( 5 ) 运输网络。运输网络是由顶点( 指物流中心、客户、停 车场) 、无向边和有向弧组成的。边、弧的属性包括方向、权值和 交通流量限制等。 ( 6 ) 约束条件。动态v r _ p s 满足的约束条件主要包括： 满足所有客户对货物品种、规格、数量的要求； 满足客户的时间窗要求； 遵守运输网络通行规定( 如单行道、货车白天禁行等) ： 车辆装载货物的重量不允许超过车辆的标记载重； 车辆的行驶距离不允许超过最大经济运输距离； 在物流中心现有运力范围内。 ( 7 ) 目标函数。动态v r p s 目标函数相对复杂，可以采用 v r _ p s 传统的目标函数，比如运输总成本最小、距离最小、时间 最少等，但往往使用诸如通过率、服务率、顾客满意度等的目标 函数，同时还可以将这些目标函数与传统的目标函数结合，形成 4 北京交通大学硕士学位论文 多目标函数。 上述要素中，车辆数量的不确定性、客户需求的不确定性以 及运输网络的不确定性均是v r p s 动态性的主要体现。正是上述 诸多要素及其属性的不确定性，使现实的车辆路径问题成为一个 非常复杂的系统。所以必须将这些要素放到一个系统中考虑，由 此将动态冲s 定义为【4 】：在车辆、客户需求以及路网状态等系 统信息实时更新的情况下，安排车辆路径以满足系统要求达到的 目标。这个定义不仅考虑到顾客需求的变化，还考虑到旅行时间、 天气以及其他因素的变化，同时对求解问题的目标也作了拓展。 1 2 2 动态车辆路径问题的特征 对动态v i 冲s 的认识经历了一个漫长的过程，w i l s o n 早在2 0 世纪7 0 年代就对动态v r p s 中的一类重要问题一一动态 d i a l - a 耐e 问题( 又称为d i a l - a - b u s ，一种电话叫车服务方式，用 户通过电话拨进的方式请求“门到门”的服务) 进行了研究，取 得了一定成果，但没有总结出动态v r p s 这类问题的一般特征。 直到1 9 8 8 年，p s a r a 衔s 才将动态v r p s 定义为“安排车辆路径以 满足实时出行的顾客需求”，并将动态v r p s 与静态v r p s 进行了 比较。后来，p o w e l l 、p s a r a m s 、b e n s i m a s 、g e n d r e a u 等又在他们 的著作中对动态v r p s 的特征作了一些描述。综合p 剐触i s 等对 动态v 1 姆s 的认识，一般认为动态v r p s 具有如下特征1 4 j ： ( 1 ) 制定路径和执行路径计划的过程中可接受新信息。静态 v r p s 中的所有信息都是已知的，路径制定和执行时不考虑出现 新的顾客、道路堵塞、天气变化等情况，强假设条件使其具有很 动态车辆路径问题的模型和算法研究 大的局限性。而动态v r p s 不仅考虑已知信息，还考虑可能在路 径制定和执行的任一时刻出现的信息，具有很强的灵活性。 ( 2 ) 未来信息可能是不精确或未知的。静态情况下几乎没有 “过去”、“现在”和“未来”之分。而动态问题中，在实时信息 出现之前，并不能确定地掌握这些信息，可能只掌握它们的统计 规律或模糊规律，甚至连这样的信息也不可能得到。 ( 3 ) 要求快速响应接收的新信息。静态路径系统对处理信息 的时间要求并不很高，可以花费几个小时获得要求解问题的结果。 而动态路径系统需要实时处理新接收的信息，通过启发式方法快 速计算，重新安排车辆路径，并将结果及时通知司机和顾客。 ( 4 ) 目标函数往往非常复杂。静态v r p s 要求优化的目标函 数比较简单，经常选用的目标函数主要有：总里程最短、车辆的 总吨位公里数最少、综合费用最低、准时性最高、运力利用最合 理、劳动消耗最低等。而动态v r p s 通常使用基于多阶段( 诸如 通过率、服务率等) 的目标，而不能使用静态v r p s 基于单阶段 的目标。 1 2 3 动态车辆路径问题的分类 根据国外一些学者以及国内少量学者对动态v r p s 的研究成 果的总结，将动态v r p s 按动态信息的种类分为以下五类1 4 】： ( 1 ) 动态需求v r p s 。这类问题由需求预测产生的不确定性 ( 比如需求量、需求时间的不确定性) 导致，目前对动态v r p s 的研究主要集中在该类问题上。 ( 2 ) 动态车辆v r p s 。这类问题由对提供服务的车辆、司机 6 北京交通大学硕士学位论文 预测的不确定性引起。在安排车辆路径的过程中，除了要考虑顾 客需求外，服务资源和服务设施的不确定性也构成了类重要的 动态v r p s 。 ( 3 ) 动态网络v r p s 。这类问题由交通网络性能的不确定性 引起。交通网络性能的不确定性可能涉及旅行时间( 因天气变化 或交通堵塞) 或网络容量的不确定性。 ( 4 ) 由未来时间段网络管理和运作的不确定性引起的动态 v r p s 。这类问题是相当复杂的，因为预测未来某一时刻系统管理 与运作发生的变化是十分困难的。 ( 5 ) 由提供的数据具有偏差引起的动态v r p s 。所有模型的 输入数据都可能存在误差，如何处理这些误差仍是一个难题，与 ( 4 ) 相同，目前还没有这方面的研究。 除了按动态v r p s 中出现的不确定信息进行分类外，还可按 动态v r p s 的模型进行分类【4 】： ( 1 ) m a r k o v 决策模型。其代表是m i l l k o f r 提出的求解动态 调度问题的m a d k o v 决策模型等。 ( 2 ) 排队论模型。如p e t e r 等提出的求解交通堵塞的排队论 模型，s 讪h a r t 等提出的求解单车辆装卸混合问题的排队论模型， b e r t s i m a s 等提出的求解动态旅行修理员问题和多车辆有容量约 束的动态车辆路径问题的排队论模型等。 ( 3 ) 网络模型。如p a l 瞰a 提出的求解动态旅行商问题的网 络模型等。 动态车辆路径问题的模型和算法研究 1 3 动态车辆路径问题的现有求解方法综述 由于动态v r p s 的问题规模一般较大，而且算法需要实现对 实时信息的短时间响应，一般的最优化方法往往不能适应，所以 现阶段解决动态v r p s 的方法几乎都建立在人工智能算法的基础 上。人工智能算法随着车辆路径问题研究的深入有很多改进算法 或者混合算法产生，但基本方法主要包括以下几类【5 l ： ( 1 ) c 1 a r k e w r i g h t 算法。该算法是由c l a r k e 和w r j g h t 【6 j 提 出的，用来解决车辆数不固定的v r p 。该算法最初按所需访问的点 数n l ( 不含出发点) 生成同样数量的路径，计算合并任意两条路 径后可节省的成本量j 。= c 。+ c 。，一。然后对可节省的成本量进 行排序。最后根据排序结果以及可行性条件，对路径进行归并( 这 里的归并是指：去掉分别位于原来两条路径中的弧( i ，1 ) 和( 1 ， j ) ，用( i ，j ) 代替) ，直到无法找到更好的解。这种算法的复 杂度为0 ( n 2l o gn ) 。在p a e s s e n s 的研究结果中，通过使用适当 的数据结构来降低它的复杂度。 ( 2 ) s w e e p 算法。该算法是由g i l l e t t 【7 j 等人提出的：即先计 算出所要访问的点的极坐标，并按角度大小排序。然后在满足可 行性条件的前提下，按角度大小归并到不同的子路径中，最后再 根据t s p 的优化算法对所得到的子路径进行优化。 ( 3 ) c h r i s o f i d e s 一i n g o z z i t o t h 【8 j 两阶段算法。它主要面 向c v r p ( 带能力约束) 和d v r p ( 带时间距离约束) 。该算法的求 解过程分为两个阶段：第一阶段按最小路径的原则形成初始解， 然后用k o p t 算法对所得的各子路分别进行优化。第二阶段是在各 北京交通大学硕士学位论文 子路径间进行点的交换，以减小总行程，然后用k 一0 p t 算法对点交 换后的子路径进行优化。该算法的优点是：在计算过程中，考虑 了所需要访问的点数量增加的情况。 ( 4 ) 禁忌搜索算法。g e n d r e a u 【9 1 等人最先将该方法应用于 v r p 。先构造一系剜的解，然后对所得解不断地进行改进。该算法 所得到的解不一定是可行解，它们对可行性的偏离程度是通过目 标函数里的罚函数来体现的。该算法求解过程中的邻域，是通过 g e n i1 ( g e n e r a l i z e di n s e n i o n ) 过程得到的。它是针对v r p 的 比较好的启发式算法，可以成功地应用于许多经典的v r p 。其后， e t a i l l a r d 通过按角度和路径重心对原问题的空间进行分割，再 用禁忌搜索结合模拟退火对子问题求解，实现了问题求解的并行 化。 ( 5 ) 遗传算法。j l a w r e n c e 【l o j 最先将该方法用于v r p 的研 究，并可有效求解带时间窗口的v r p 。鉴于传统的遗传算法是个大 范围、粗粒度的寻优算法，b a m i e r 将它与约束满足问题( c s p ) 的技术相结合，通过遗传算法来处理c s p 参数的子域( 基因的适应 度是通过对c s p 解的计算得到的) ，从而减小搜索空间，降低c s p 问题目标函数和遗传算法约束的复杂度。张涛等人则是通过遗传 算法来保证搜索的全局性，用3 一o p t 算法来加强局部搜索能力，得 到针对v r p 的混合算法。这类算法目前已可以求解较大规模的问题 ( 1 9 9 个客户) 。 ( 6 ) 重复匹配方法。该方法是由p w a r k 【1 1 1 等人提出的：首 先对每个客户生成一条子路径，然后提供了总匹配成本和负载改 变匹配成本，作为归并路径的依据，同时为满足自匹配条件的集 9 动态车辆路径问题的模型和算法研究 合提供分割手段，以利于跳出局部最优该算法也可求解较大规模 的问题( 1 9 9 个客户) 。 根据动态信息的随机和模糊性，动态v r p s 又有随机v r p s ( s v r p s ) 和模糊v r p s ( f v r _ p s ) 之分，并且有很多相关的研究 成果，这些研究成果中设计的算法也几乎都建立在上述某种人工 智能算法的基础上。 随机v r p s 主要是针对如下背景的配送问题：每天要访问的 客户或节点的数量和位置是固定的，但每个客户每天的需求是不 同的，并各自满足一定的可能性分布或随机分布。如果限于时间 或资源的关系，调度员无法等到获得所有信息后才做决策。对这 种类型的问题，目前出现的算法大部分可以归纳为以先验( 即定) 序列为基础的方法。该方法分为两个阶段：在信息不完全( 随机) 的情况下确定先验序列：在获得确定性信息的情况下进行决策。 因此，其随机模型的选择基于两点：第一阶段的成本和第二阶段 的期望成本。先验序列的确定方法又有两类：一类是按二元可能 性理论来确定，另一类则是基于机会约束规划。第一类方法假定 需求分布是二元( 即在第i 点有单位需求的概率为p i ，则没有单位 需求的概率为1 珏，1 、离散的。根据该假定，可推出先验序列的 期望长度，相应的上下界和渐进特性。m i c h e lg c n d r e a u 等人以该 理论为基础，得到目标函数和惩罚函数，以c l a r k w 啦舢算法生 成初始解，然后用禁忌搜索算法对初始解进一步优化，可以求解 规模为4 6 的问题。另一类方法是分别使用机会约束规划，在一定 的假定条件下，将s v r p 转化为等价的、确定性的v r j ) ，并找到 了解的界，其方法的核心是让出错返回的概率不超过一定的界限。 些室奎塑查兰堡主兰壁兰塞 一一 机会约束规划模型均以确定性v r p 的三下标流和二下标流模型 为基础，添加可能性约束条件和罚函数后建立起来的。所用的算 法，也与确定性的算法有不少相通之处。如m d r o r 就是在建 三下标流机会约束规划模型和罚函数模型后，利用c l a r k w r i g h t 算法进行求解的。 第二阶段的策略为：按照先验序列，跳过需求为零的客户， 直接访问下一个客户，如果车辆负荷超过了车辆最大载重量，则 返回出发点卸载，并回到出现超载的地方，继续提供服务。 在随机v r p 中，还存在l r p ( l o c a t i o nr o u t i n gp r o b l e m ，位 置路由问题) 和需求可切分的s v r p 等类型的问题。l r p 需要在仓 库( 出发点) 运作成本已给出的情况下，确定它们的位置，使仓库 运作成本最小化，同时还要给出最优配送路径。g l a p o r t e 等人 给出的方法也是基于两阶段法，第一阶段确定仓库位置和设计路 径，第二阶段采用出错返回方式，并分别建立了基于约束和基于 边界罚函数的模型，最后用分枝定晃法进行求解。 b b o u z a i e n e a y a r i 等人对需求可切分的s v r p 问题，利用d r o r 等建立的模型和算法求解：总之，到目前为止，其他类型的s v r p 模型和求解算法都是以s v r p 为基础的。 模糊强s 问题中，某些待服务的客户节点需求信息没有 或无法给出准确的描述，这样，需要引入模型和算法来解决这类 问题。d t c o d o m v i c 等人是最早着手研究这类问题的人：他以 模糊数表示客户点的需求信息，以倾向度为基础建立模糊判定规 则，其核心是基于s w e e p 算法，并省略了s 、 吧e p 算法的第二阶段， 即初始化子路径后对它们的优化过程。祝崇俊、刘民、吴澄等人 动态车辆路径问题的模型和算法研究 以模糊可能性分布，建立了v r p s 的基于置信度的三下标流模型， 并提出了基于可能性分布的2 o p t 算法。该算法引入了伪出发点， 建立了以置信度为基础的判定规则，以遍历为终止条件，从而在 全局层次上进行优化，同时避免过多地扩大搜索空间。该算法已 解决较大规模的问题( 大于2 0 0 个客户) 1 5 】o 从求解策略来看，动态v r p s 的算法可分为两大类 4 l ：一类 是重新优化策略，另一类是局域优化策略。 重新优化策略实际上就是动态问题的静态求解，即一旦接收 到确定的实时信息，就从头开始重新寻找最优车辆路径。b e l l 【1 2 】 等研究运送大宗商品的车辆路径问题，p s a r a 丘i s 【1 2 l 解决动态单车 辆d i a i - a - r i d e 问题时均采用这种策略。但遗憾的是，该方法最多 只能解决出现1 0 个需求的小规模问题。 局域优化策略是事先根据已知的信息制定初始路径，当接收 到实时信息后，用局域方法改进初始路径。尽管局域优化策略获 得的路径计划可能劣于重新优化策略，但是节约了大量的计算， 适用于实际的车辆调度系统，故对基于局域优化策略算法的研究 较多。w i l s o n 求解动态d i a l 廿r i d e 问题的插入法，r o y 等、m a d s e n 1 4 l 等求解运送残疾人问题的插入法，g b n d r e a u 等【1 51 6 1 求解信使服务 问题的一种禁忌搜索算法均采用了局部优化策略。 1 4 本文的主要研究内容 动态车辆v r p s 、动态网络v i 冲s 以及动态需求v r p s 是典型 的动态v r p s ，动态需求v r p s 是现阶段研究的热点，但对其他两 类问题的研究很少，已有的研究成果也缺乏实际应用性。本文将 北京交通大学硕士学位论文 在深入分析动态车辆v r p s 和动态网络v r p s 这两类问题各自特 点的基础上，从强调问题的实际应用性出发，构造上述问题基于 直观描述的、切合实际的数学模型，进而构造上述问题的实时求 解策略，并设计求解上述问题的现代优化算法，最后通过理论分 析和数值计算对求解策略和算法的性能进行评价。 论文第一章通过对静态车辆路径问题与动态车辆路径问题的 对比分析，说明了研究动态车辆路径问题的理论和现实意义，进 而阐明了动态车辆路径问题的定义、构成要素、特征和分类，并 对动态车辆路径问题的现有求解算法进行了综合评述。 第二章将研究软时间窗动态车辆v r p s 。在对动态车辆v r p s 进行描述、界定的基础上，通过对车辆动态性原因的分析，提出 求解该问题的“制定计划整体优化+ 实时跟踪局部优化”的两阶段 策略，建立该问题的数学模型，设计求解该问题的禁忌搜索和局 部搜索算法。 第三章将研究基于概率网络的软时间窗动态网络v r p s 。在对 动态网络v r p s 的特征进行描述的基础上，对本文将要研究的动态 网络v r p s 做出界定，建立该问题的基于直观描述的数学模型，并 设计求解该问题的遗传算法。 第四章将总结本文的主要工作和研究结论，并对需要进一步 研究的问题进行说明。 动态车辆路径问题的模型和算法研究 2 动态车辆v r p s 的模型和算法研究 2 1 本文对动态车辆v r p s 的描述 目前，对动态车辆v r p s 的研究主要是基于不确定车辆数的车 辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hu n c e r t a i nv e h i c l e n u m b e r ，u m v r p ) 的研究。它们对u m v r p 的描述基本如下f 1 7 l ：假设 有n 个城市，每个城市的位置坐标和货物需求已知，车辆的负载能 力一定，但车辆数不确定。l j m v r p 是对车辆( 每辆车一条路径，开 始和终止都在起始点) 所要访问的城市进行排序，使用尽量少的 车辆数使所有城市都满足要求，且总旅行成本最小。假设每个城 市被分配到某一辆车，访问一个城市的一辆车也必须离丌那个城 市，每辆车所访问的城市的需求总和不能超过车辆的能力。 总结目前国内对这类问题的研究成果，发现它们几乎都存在 如下弊端： 第一，将静态v r p s 中车辆数固定的静态信息转变为车辆数不 确定的动态信息，然后在目标函数中增加使用车辆数最少的约束， 例如，最少车辆数由m = 吼q ( 所有客户需求之和除以车辆标 r i 记载重量) 决定，然后在目标函数中增加m i nm 。虽然目标函数 增加了对车辆使用数量的限制，但并没有分析现实生产生活中车 辆呈现动态性的原因，更没有提出针对这些原因应采取的求解策 略和相应的算法。所以，目前的研究成果既没有充分地体现车辆 的动态性，也缺乏实际应用性。 1 4 北京交通大学硕士学位论文 第二，现有研究成果都暗含客户总需求小于等于物流中心所 有车辆服务一次的总运力的假设。现实中的客户需求不是一成不 变，必然呈现波动。在这种假设条件下，客户需求的波动将使物 流中心的车辆数必须满足客户需求的波峰值。对物流中心而言， 车辆的运力只有在波峰点处得到充分运用，而在波峰以下的绝 大多数时间里运力大量浪费。所以现实中物流中心配置的车辆数 必然小于波峰需求值，也就是说现实中存在大量客户总需求超过 物流中心所有车辆一次服务运力总和的情况，车辆需要循环使用。 不难看出，该假设对现有研究成果的实际应用性产生了巨大的束 缚。所以，作者提出一个新的问题：车辆循环使用动态车辆v r p s ， 并将在建立该问题的模型的基础上通过设计相应的算法解决这个 问题。 作者在深入分析现实中车辆路径问题( 主要基于配送车辆路 径问题) 的特点后，认为造成车辆动态性的原因主要有以下几方 面： ( 1 ) 车辆处于修理状态而不能参与作业的信息的动态性。这 部分动态信息主要体现在车辆进入和结束修理状态的时间的动态 性。特别是结束修理状态的时间的动态性可能直接影响到作业计 划的制定以及计划的调整。但这部分问题主要集中在信息的更新 是否及时上，所以其解决策略应是加强车辆信息系统信息的维护 和及时更新，并对车辆的维护修理时间做预测。 ( 2 ) 车辆在运行过程中突发故障，不能按既定计划完成运输 任务。这属于随机信息，没有很强的规律性，必须制定良好的实 时优化策略予以解决。所以，需要考虑以下两种情况：是车辆 动态车辆路径问题的模型和算法研究 经过紧急修复能够重新投入运行。在这种情况下，可以采取如下 策略：评估车辆紧急修复后投入运行( 所耽误时间、费用、顾客 满意度等) 与重新安排车辆两种方案对目标函数影响程度，取对 目标函数更有利的方案。二是车辆短时间内不能修复，这时应采 取重新安排车辆策略。 ( 3 ) 替代车辆信息的动态性。( 3 ) 是( 2 ) 采取重新安排车 辆策略的连锁反应，替代车辆的来源有三：物流中心空闲车辆、 己完成修理车辆和已完成任务车辆。这三种车辆来源其信息都是 动态的。前两类可以归结到一起处理，考虑车辆容量、距离以及 时间窗要求等因素制定相应的寻优和比较方案找出成本最小的替 代车辆。 ( 4 ) 由于其他任务( 部门) 调用车辆造成车辆的动态信息。 为了使已定计划得到充分保证，采取部门保护策略：即只允许未 纳入计划内的车辆被其他部门调用。如果所有车辆均己纳入计划 中，则不接受其他部门的调车命令。 ( 5 ) 车辆循环作业。主要是确定参与循环的车辆的信息的动 态性，这类动态信息是以往的研究没有提及的。本文将采用实时 局部优化调度策略加以解决。 基于以上分析，在对现实的动态车辆v r p s 问题进行一些抽 象和简化后，可以将动态车辆v r p s 描述为： 从物流中心用多台车辆向多个客户送货，物流中心和客户的 位置一定，相互间的最短距离已知且固定，不考虑运输网络中车 辆流量的限制，物流中心与客户、客户与客户问的车辆行驶时间 只与车辆的运行速度有关；客户的需求量一定，且对货物送到时 1 6 北京文通大学硕士学位论文 间的要求为软时间窗，系统跟踪车辆运行全过程，实时更新车辆 信息，要求根据这些信息实时地、合理地安持车辆的行驶路线， 使目标函数得到优化，并满足以下约束条件： ( 1 ) 单一客户的需求量不超过车辆的最大载重量： ( 2 ) 每条路径上客户的需求量之和不超过车辆的最大载重 量； ( 3 ) 每条配送路径的长度不得超过车辆的。次最大经济行驶 距离； ( 4 ) 每个客户的需求必须得到满足，且由一台车辆服务。如 果该台车辆出现故障，可以由其他车辆替代完成： ( 5 ) 货物送达客户的时问应尽量满足软时间窗要求，在时间 窗之外送达将给予一定惩罚； ( 6 ) 车辆可以循环使用，但车辆完成一次作业返回物流中心 后，必须完成整备和装货作业，然后才能参与循环作业。循环使 用的车辆如果作业时间超过其满负荷工作时间( 如l o 小时) ，超 过部分将给予超负荷惩罚。 综上所述，本文研究的动态车辆v r p s 是基于软时间管的、 非满载、纯送货且车辆循环使用的动态车辆v r p s 。 2 2 动态车辆v r p s 的求解策略 动态车辆v r p s 用传统的人工智能算法单步求解，也能得到 一定程度的满意解，但很难体现出动态性，对实际问题的适应性 很差。作者通过分析车辆的动态性原因，发现车辆的动态性几乎 都产生于车辆执行计划过程中，据此本文设计了动态车辆v r p s 都产生于车辆执行计划过程中，据此本文设计了动态车辆v r p s 动态车辆路径问题的模型和算法研究 的两阶段求解策略： 第一阶段：制定整体优化计划。 该阶段将用禁忌搜索算法进行整体寻优，制定车辆路径方案。 确定各台车辆服务的路径和路径中包括的所有客户及其服务顺 序，包括车辆循环使用方案计划，尽可能减少车辆作业小时数、 车辆不能满足客户时间窗要求所受到的惩罚以及车辆超负荷运行 惩罚。 第二阶段：实时局部优化调度。 该阶段将在执行第一阶段制定的计划的过程中，不断更新车 辆信息，根据这些信息，调整车辆循环使用方案以及制定车辆突 发故障的解决方案。 ( 1 ) 车辆循环使用策略：规定循环作业车辆必须返回物流中 心整备3 0 分钟后才能重新投入工作。重新投入作业的车辆从物流 中心出发，要求尽可能满足客户的软时间窗要求，使得循环使用 车辆不满足客户时间窗要求的惩罚小时数和超负荷作业惩罚小时 数最小。 ( 2 ) 车辆突发故障解决策略：根据决策者主观偏好决定是否 使用替代车辆。决定使用替代车辆时，若物流中心有空闲车辆， 选择空闲车辆从物流中心出发作为替代车辆否则，选择完成一 次作业后返回物流中心的车辆作为替代车辆，并将其看作车辆循 环作业处理。 之所以采用上述两阶段求解策略，是基于如下几方面的原因： ( 1 ) 车辆的动态性集中体现在车辆作业过程中，可以将这些 动态信息纳入实时局部优化调度阶段考虑，而在制定整体优化计 北京交通大学硕士学位论文 划阶段不考虑。基于对车辆动态性的原因的深入分析，作者认为 这种策略是切实可行的。 ( 2 ) 制定整体优化计划阶段易得出满意解，甚至最优解。制 定整体优化计划阶段避开了车辆动态性的干扰，可以近似认为是 解决一个静态的v r p s ，而对静态v r p s 的研究相对比较成熟，可 以获得比较满意的解，甚至最优解。 ( 3 ) 禁忌搜索算法具有良好的寻优性能。郎茂祥1 1 8 1 在其博 士论文中通过实验计算证明：在禁忌搜索算法、爬山算法、遗传 算法、模拟退火算法等几种人工智能算法中，禁忌搜索算法收敛 速度最快、获得解的质量也相对较高。 ( 4 ) 车辆循环使用问题在制定整体优化计划阶段通过禁忌搜 索算法也可以很好地解决。具体解决方法将在后文的算法研究和 设计中详述。 ( 5 ) 实时局部优化调度阶段只是局部调整第一阶段计划。局 部调整不是对循环路径以及使用替代车辆的路径做出调整，而是 对这些路径重新调配车辆，寻找最优的调整方案，既不会对第一 阶段的整体方案产生较大影响，保持计划的整体优化性，又可以 通过实时的方式处理车辆的动态性信息，解决车辆的动态性问题。 下文关于动态车辆v r p s 的数学模型、算法研究和设计均基 于上述两阶段求解策略。 2 3 动态车辆v r p s 的数学模型 由于软时间窗的存在，为了尽可能减少因将货物早于时问窗 卸下而遭受的惩罚，本文将采用早到等待原则：尽量安排车辆将 动态车辆路径问题的模型和算法研究 货物在客户规定的时间窗内送到，若车辆到达客户的时刻早于该 客户的时间窗开始时刻，可以考虑让车辆在该客户处等待，一直 等到时