（运筹学与控制论专业论文）一种带时间窗口的危险品vrp问题及其算法.pdf

摘要 在危险品运输管理中，除了考虑成本优化外，还要考虑运输风险控制。目前 关于危险品运输路线的研究，大都针对两点之间的成本风险最小路线求解。带 时间窗口的车辆路线问题( v r p t w ) 经常被用于物流配送的车辆调度，危险品 配送同样存在车辆调度问题。本文提出了一种车辆路线风险度量，并提出了一种 综合考虑路线风险和长度最小化的带时间窗口危险品车辆路线问题。 由于该问题的计算复杂性是n l - h a r d 的，其算法采用邻域搜索的启发式算 法。本文将传统v r p 问题的邻域搜索算法进行拓展，给出了一种新的启发式算 法。该算法根据问题的特征，增加了三种新的路线改进方法来定义一个邻域。对 于该问题的一种特例完全风险规避的情况，本文证明了它的最优解可以由n 个带有时间窗口的最短路组成。本文最后用s o l o m o n 的5 6 个b e n c h m a r k i n g 问题 对算法进行了测试，验证了新算法有很好的求解性能。 关键词：危险品，车辆路线问题，时间窗口 中图分类号：0 2 2 9 i v a b s t r a c t 1 f 1 ”t r a n s p o r t a t i o no fh a z a r d o u sm a t e r i a l si sa l li m p o r t a n tp r o b l e mi ni n d u s t r i a l i z e d s o c i e t i e s ，d u e t ot h ep e r v a s i v e n e s so ft h e s em a t e r i a l s a l t h o u g hm o s te x i s t i n g a n a l y t i c a la p p r o a c h e sf o rh a z a r d o u sm a t e r i a l st r a n s p o r ta c c o u n tf o rr i s k ，t h e r ei sn o a g r e e m e n ta m o n gr e s e a r c h e r so nh o wt om o d e lt h ea s s o c i a t e dr i s k s t h eo b j e c t i v eo f t h i sp a p e ri st op r e s e n tan e w c a r g oq u a n t i t yb a s e dd e f i n i t i o no f r i s ka n dan e wm o d e l c a l l e dh a z a r d o u sm a t e r i a l sv e h i c l er o u t i n gp r o b l e m sw i t ht i m ew i n d o w s ( h m v r p t w ) t h i sp a p e ro n l yg i v e sah e u r i s t i ca l g o r i t h ms i n c e t h eh m v r p t wi san p - h a r d p r o b l e m f o r t u n a t e l y ，i nt h ed s ka v o i ds c e n e ，t h eo p t i m a ls o l u t i o nc a nb eg o tb ys o l v e an u m b e ro f s h o r t e s tp a t hp r o b l e m sw i t ht i m ew i n d o w s i nt h el a s to f t h ep a p e r , s o m e c o m p u t a t i o n a lr e s u l t s ( s o l o m o n s 5 6b e n c h m a r k i n gp r o b l e m s ) i n d i c a t et h a to u r h e u r i s t i c 啪s o l v et h ep r o b l e mv e r yw e l l k e y w o r d s ：h a z a r d o u sm a t e r i a l s ，v e h i c l er o u t i n gp r o b l e m ，t i m ew i n d o w c l a s s i f i e a t i o nc o d e ：0 2 2 9 v 论义独创性声明 术论文是我个人存导师指导下进行的研究工作及耿得的研究成果。论文巾除 j 7 特别加以标注和致谢的地方外，不包禽其他人或其它机构已经发表或撰写过的 研究成果。其他同忐对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名琢嗍塑型 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名i 一滋导师签名：日期：圣竺! ：! ：兰 翅 1 引言 危险品主要包括：易燃易爆品、氧化物、有毒或易感染物质、放射性物质、 腐蚀性物质和有害垃圾等。对于工业生产而言，完全不使用危险品是不可能的， 而危险品的制造和使用往往发生在不同的地点，因此，危险品的运输问题一直是 工业界的一个重要闯瑟。 危险品在运输途中可能会发生事故、造成泄漏，对社会、环境和附近的人造 成直接危害。虽然对危险品的运输公司或个人都加倍小心，事故概率相对低于其 他产品，但一旦事故发生。后果非常严重，并且由于大众和媒体对危险品事故比 其他事故更敏感，事故一旦发生将会造成严重的社会影响。比如，1 9 7 9 年一辆 装载有毒化学物品的车在加拿大米西索加市附近脱轨，装载氯气的货罐泄漏，导 致2 0 0 ，0 0 0 人撤离i 1 0 1 。1 9 8 2 年，阿富汗一辆装载汽油的卡车在隧道内爆炸。 造成2 7 0 0 入伤亡u o t ， 目前已有一些对于危险品运输的研究f 1 0 1 4 2 4 1 。e r k u t 等【i o j 应用数值分析的 方法说明，可以应用路径中边的风险之和来表示路径的风险，并对比几种不同目 标函数下的解。j i n 等【“1 认为车辆经过一定数量的事故后将停止运输，给出了有 限时间和无限时间的模型并给出了相应的解法。v e r t e x 等【2 4 】给出了一种基于g i s 的危险品运输框架。但这些研究仅限于两点之间的危险品运输问题，而实际生活 中的运输问题往往相对复杂。对于一些总需求大、客户多、且需求分散的危险品。 运输不再局限于两点之间，而是一个仓库对应多个客户的配送模式，且客户为了 降低风险，可能只在某一时间段接受送货。 在各种车辆路线问题中，一个基本问题是带时间窗口的车辆路线问题( v e h i c l e r o u t i n g p r o b l e m w i t h t t m e w m d o w s ，v l u t w ) 。其主要内容是：以成本最小的目 标安排多辆车有序地前往配量给定的各配送点而构成的配送路线，其中每辆车必 须从同一车站出发并最后返回车站，每个配送点只能安排一个车次在限定的时间 窗内配送，且每一条配送路线不得超过车辆的装载容量和车辆的最后返回时间： 如果车辆提前到达配送点，则需要等待，直到在时间窗内才能配送【2 l 】。由于 v r p t w 问题为一个n p - h a r d 问题，一般采用启发式算法求解，b r 等【3 4 1 综述了 v r p t w 问题的传统启发式算法和现代启发式算法。v r p t w 问题所考虑的目标 通常是；最小化车辆总行驶路线，最小化车辆总行驶时间或最小化所需车辆数。 目前为止，还没有考虑运输风险对运输路线的影响。 本文基于危险品运输问题和v r p t w 问题，在目标函数中综合考虑行驶路线 长度和风险两个因素提出了一种带有时间窗口的危险品的车辆路线问题 ( h a z a r d o u sm a t e r i a l sv e h i c l er o u t i n gp r o b l e mw i t ht n n ew i n d o w s ，h m v r p t v o ， 并给出了相应的规划模型，分析了该问题同传统v r p 问题的区别，给出了一般 情况下的启发式解法。该启发式算法能够良好的兼容传统v r p t w 问题的启发式 算法。由于核邻域搜索算法中判断邻域中一个解是否优于当前解的时间复杂度为 o ( 矿) ，这将影响算法的效率，本文根据h m v r p t w 问题路线的特点，提出三 种具有简单判别式的路线改进方法来构造邻域，提出扩展的邻域搜索算法。对于 h m v r p t w 问题的两种特殊情况完全风险偏好和完全风险规避，本文分析 得出，对于完全风险偏好情况下该问题等价于一个v r p t w 问题，且本文提出的 启发式算法也退化为一个v r p t w 问题的算法；对于完全风险规避情况，最优解 可以通过求解疗个带有时间窗口的最短路问题( t h es h o r t e s tp a t hp r o b l e mw i t h t u n ew m d o w s ，s p p t w ) 求得，并且提出在求解过程中先求褥一般最短路同题 的解并验证是否满足时间窗口的方法来提高算法的效率。最后，本文应用 s o l o m o n 的5 6 个问题 2 h 进行了数据实验。 本文由6 章组成，概述如下： 第1 章；给出问题的背景、本文的主要贡献及安排。 第2 章：综述了s p p t w 问题及其算法。 笫3 章：综述了v r p 问题及其分类和v r p t w 问题的传统启发式算法。 第4 章：基于危险品运输阔题和v r p t w 同题，在目标函数中综合考虑车辆 路线长度和风险两个因素，提出了h m v r p t w 问题。并给出了相应的规划模型 和启发式算法。该启发式算法包括一种新的路线构造算法和三种新的路线改进算 法。在此基础上进一步讨论了完全风险偏好和规避情况下解的情况，给出了完全 风险规避情况下的最优解算法。 第5 章：应用计算机求解基于s o l o m o n 的5 6 个问题生成的新的问题，对计 算机求解结果做了简要分析。 第6 章：总结全文，提出未来的研究方向。 2 2 s p p t w 问题及其算法 s p p t w 问题是指在一个带有时间窗口的网络中寻找从点p 到点q 的最小费用 路径的问题。在有向图g = 彳) 中，存在一个起始点p 和一个目的点g 。每一条边 ( j ，歹) 4 都有一个相应的费用c 口和时间由，其中如包含在弧( 切的运行时闻和点i 的服务时间。每一个点i 都具有一个时间窗口【6 f 】，车辆只能在这个时间窗口内 到达点i ，如果早于嘶到达点i ，则必须等待至4 i 才可开始为点赧务。该问题已经 被证明为一个n p h a r d 问题【l s l 。 1 9 8 8 年，d e s r o e h e r s 等唧给出了带有时间窗口的最短路问题( 蛐s tp a t h p r o b l e mw i t ht i m ew i n d o w ，s p p t w ) 的一种标号算法，并且应用该算法求解了规 模为2 5 0 0 个点2 5 0 ，0 0 0 条边的问题。 2 1 标号处理 用( 对，g k ) 表示第f 个点的第k 个路径的标号，在不产生歧义的情况下，可 以省略i 和k 。且该标号是在路径驴 h o ) ，玎1 ) ，配) ，) ，“0 ) = p ，犯户口中 迭代产生，如下所示： 珏。尸0 c 如) 2 0 z h 2 m a x a k 9 ，z 缸1 ) 喇) 奶， = i ，l 。l 煳 l m t = l ，三 定义1 如果存在从点p 到点_ ，的两条路径一，穿，相应的标号为( 一，c 1 ) 和( 严，c 2 ) 。 则f 占优于r 即( ，c 1 ) 循环执行，露椭= m m ，穆1 ) + f 髓1 ) 硼妒脚 。直到路线尾 端 步骤1 3 6 脚+ 奶 步骤1 4料l 1 反向循环，6 t 尸m a x a l ( 1 h 1 ) - t l ( t o t ( t e , 1 ) 6 椭 ，直到路线 头部 步骤2 如果所有的边都已经优化过，则算法结束。 否则，找出核路线中未优化的边中6 哪k 最大的边( 舻1 ) ，自( 七) ) ，并将该 边标记为已优化。 步骤3 利用加入时间约束的d 日k s t r a 算法【坫1 优化找出符合时间约束且费用函数 最小的路线。 步骤3 1 找到一点，胆，对于所有的f 九有c 加； 如果，= f ( 矿一1 ) ，用求得的i ( 驴1 ) 到趣矿) 最短路替换边( 妒一1 ) ，“f ) ) ， 返回步骤1 。 步骤3 2 对所有的f ，f ( 矿) ，如果勺+ 缸) ) 一口i r o 一砸- i ) ，则令 巳f ) 2i e p + ) ，白十气r ) j 步骤3 3将l 从图中移除，返回步骤3 1 。 对于任意一条路径x 中的一条边，每次计算步骤1 需要对每个点计算两次， 共需计算2 1 x 1 次，因此，步骤1 的复杂度为2 1 x 1 次。步骤2 中第一次找最大值需 要进行闳次比较，第二次需要因1 次，依此类推，故共需进行凶( 闳- 1 心次比较。 步骤3 中，由于d i j k s t r a 算法【培】的时闻复杂度为0 ( 矿) 。两对于一条路径进行优 化时，每条边均需计算步骤l 步骤3 一次，共需对阅1 条边进行优化，又由 于i z i 月，则该算法的时间复杂度为d f 栉4 ) 。 4 6 2 。核邻域搜索算法 核路线扩展算法可以求得任意核路线的近似最有扩展路线，基于该算法，可 以将传统v r p t w 问题的解改进算法扩展到h m v r p t w 问题中。算法步骤如下： 步骤l 利用4 6 1 节的路线构造算法求得初始核解s 和其近似扩展最优解，。 步骤2 利用v r p t w 的路线改进算法对s 进行一次改进得到n 步骤3 利用4 6 1 2 节的核路线扩展算法求得r 的近似最优解，； 如果，优于，s = l = ，： 否则返回步骤2 。 如果所有改进所得的p 均无法优于伊，妒为近似最优解。算法结束 如图表1 5 所示，由于该算法的路线改进算法通过核路线的变换实现，且为 了同后面提出的扩展的邻域搜索算法区分，这里称之为核邻域搜索算法。该算法 很好的兼容了传统的v r p t w 的邻域搜索算法。由于传统v r p t w 的邻域搜索算 法只能交换核路线，而z ，是否比改进不能通过简单的公式判断，只能获得， 后进行比较，而应用核路线扩展算法的时间复杂度为d f 玎4 ) ，这将直接导致求解 时间的增加。在下一节中，我们将介绍三种简单有效的路线改进算法。 图表1 5 核邻域搜索算法 4 6 3 扩展的邻域搜索算法 本节将根据h m v k p t w 问题的特性，给出三种效率较高的路线改进算法。 用；( j ( 七) ) 表示路径謦= o ) ，1 ) ，西j ) 中在点西助之前所有边的集合，用) 表 2 1 示在路径x 中运送1 单位危险品到点奶所承受的风险，即： = o 觚吩 ( 4 1 8 ) 用s ( 玛表示路径x 中接受服务的点的集合，则路径x 的费用( 4 3 ) 可以用另外 一种形式表示： q x ) = ( 1 一匆：硝“m ) + 五叫种移 ( 4 1 9 ) 在不改变路径结构的情况下公式( 4 1 9 ) 的第一部分保持不变。而公式( 4 1 9 ) 的 第二部分取决于受服务点的位置，受服务的点处的、越小，费用c ( 的就越小。 基于这个思想，提出下面三种服务改进算法。 4 6 3 1 服务重定位算法 如果路径x 中某一节点f 多次出现，该点在劬位置接受服务，路径x 在硐 位置再次经过f 点且不在此位置为其服务。如果 倔) ( 4 2 0 ) 且将点i 转至广( ，) 位置服务后路径仍然符合时间窗口，则上述重定位算法可以降 低该路径的费用。由于所有边的单位风险砌都是正的，因此构的位置必在i ( d 之前。从直观上看即：如果一条路线中多次出现同一节点，则该节点应该在第一 次出现时接受服务可降低费用。 jl 图表1 6 服务重定位算法 4 6 3 2 服务转移算法 两条路径局和恐中均存在点i ，点i 在五中的奶位置接受服务，在局中 的托砂位置但不接受服务，且 乍) 勃 ( 4 2 1 ) 珥+ 。剐五) 嘭s 矿 ( 4 2 2 ) 且将点i 从蜀的奶位置转移到局的页的位置后符合时间窗口，则上述服务转移 算法可以降低总费用。 墨豳 图表1 7 服务转移算法 4 6 3 3 m - n - 服务交换算法 两条路径蜀和局中存在两个点，k ，点门生五中的撕) 位置接受服务，点 k 在局中的l ( k 1 ) 位置接受服务，局的i q 2 ) 位置路过点_ ，但不服务，蜀的f ( 鸵) 位置 路过点k 但不服务，且 嘭乙) + 反k ) 乃7 矗) + 畋哦) ( 4 2 3 ) 嘭一以+ ，西( 也) 码v ( 4 2 4 ) 噍一哆+ k 剐置) 匆s v ( 4 2 5 ) 则将点，。则可以将两点交换，让点，在尼的瓦2 ) 位置接受服务，点k 在蜀的i ( k 2 ) 位置接受服务。 j k 舅习 图表1 81 - 1 服务交换算法 上述为一个1 - 1 服务交换算法的例子，如果路径五中的m 个点桶路径为中 的刀个点交换，则该算法称作m - n - 月 务交换算法。 本节提出的三种路线改进算法都具有简单的判别式来判断是否可以改进总 费用，我们将这三种路线改进算法加入到图表1 5 所示的算法中，得出 h m v r p t w 问题的一种新的启发式算法，如图表1 9 所示。 图表1 9 扩展的邻域搜索算法 4 7 完全风险偏好的h t p t w 问题 当九卸时，管理者完全偏好风险，愿意为微小的路线长度改进增加巨大的风 险。此时，弧( 切的费用函数公式( 4 2 ) 变为c 庐幽，问题即为一般的v r p t w 问题。 由于办符合三角不等式，则核路线扩展算法中的步骤3 求得的最短路线还是弧 ( 切本身，即核路线扩展算法无法对核路线进行改进。因此，求得的初始解和改 进解中不含有经过未服务的点，则第4 6 3 节中提出的三种算法无法对路线改进。 将核路线扩展算法和第4 6 3 节中提出的三种算法从图表1 9 中删除后，算法即 退化为图表2 0 的形式。此时，除初始解算法不同外，该算法同v r p t w 算法完 全相同，算法的精确度和计算时间完全取决于核解的改进算法中传统v r p t w 问 题路线改进算法的选取。 图表2 0 完全风险偏好的邻域搜索算法 4 8 完全风险规避的h v r p t w 问题 当扣l 时，管理者完全规避风险，愿意为微小的风险改进增加巨大的行驶路 线长度。弧( 切的费用函数公式( 4 2 ) 变为。o ；厂。一w 。 定理3 如果某一解由路径蜀，恐，0 组成。其中x 中仅有点f 接受服务，从 点0 到点f 的路线为两点之间的带有时间窗口的最短路问题的解( 除点f 外 所有点的时间窗口均为【d ，m ，点f 的时间窗口为h ，蜘，弧( 劬的费用为啊) ， 从点i 返回点0 的路线为弧( f ，0 ) ，则该解为最优解。 证明： 由于炉1 ，代入公式“1 9 ) 得到路径z 的新费用函数为 c ( x ) = ，酬j ) ) 嘭 ( 4 2 6 ) 则对于任意路径l 其中有f 】，1 个点接受服务。构造存在一组路径y l ，兄，垧。 其中k 与王，的路线完全相同，但妖中只有r 中的第i 个接受服务的点接受服务， 其余点只是路过，并不接受服务。由于髟与j 7 的路线完全相同，由公式( 4 2 6 ) 可 知： c ( y ) = 2 c ( r ) 又由于h ，既，垧与y 的路径相同，则k ，圪，】1 ”也必然满足时间窗口约束。即 路径y 与路径y l ，兄，垧的组合具有相同的费用，且为相同的顾客提供了服务。 即可以将路径l ，转化为一系列路径y l ，砼，垧，如图表2 l 所示。即任意解均可 以转化为一系列仅为一个点服务的路线之和且总费用不变。 而对于一条为只为点f 服务的路径，费用为r f 4 ，西为常量，而吒一的最小值 为从0 到i 带有时间窗口的关于风险的最短路( 所有点的时间窗口均为【6 f 】，弧 ( 奶的费用为勺) 。 综上所述，命题所述解为最优解。证毕。 k 勺x 勺k 勺。 ooo 图表2 l 路径转化 则求解该问题的解转化为求解n 个带时间窗口的最短路问题。 由于s p p t w 算法的时间复杂度为d ( 坍加 膨，行 ) ，当可能的标号总数d 和最大时间窗1 ：3 宽度d 较长时计算相对缓慢。而求解最短路的d i j k s 衄算法【”】 求解较快( 0 协3 ) ) ，因此，我们先应用d i j k s t r a 算法求解从点0 到所有点的最短 路，如果点0 到点f 最短路满足时阅窗口约束，则该路线则为所求解，否则，再 应用s p p t w 的标号算法求解。 5 实例分析 对于v r p t w 问题，国际上公认的启发式算法的比较方法是，采用s o l o m o n 提供的5 6 个1 0 0 个点规模的标准测试问题进行计算结果比较。这些测试问题 根据以下特征产生；1 ) 点的坐标分森；2 ) 一条路线中的平均点数；3 ) 有时间 窗约束的配送点比例；4 ) 时间窗宽度；5 ) 时间窗下限。 s o l o m o n 的v r p t w 测试问题分为6 类，分别记为c 1 、c 2 、r l 、r 2 、 r c l 、r c 2 。其中，c 类( 含c i 和c 2 ) 问题将点分为多个组，每组的点坐标 由服从均匀分布的伪随机数产生，如图表2 2 所示；r 类( 含r 1 和i 匕) 问题 的所有点坐标全部由服从均匀分布的伪随机数产生，如图表2 3 所示；r c 类( 含 r c l 和r c 2 ) 问题则将部分点分组，每组的点坐标由服从均匀分布的伪随机数 产生，而其余点坐标则全部由服从均匀分布的伪随机数产生，如图表2 4 所示。 所有这5 6 个问题可在如下网址下载： h t t p ：w e b c b a n e u e d u m s o l o m o n p r o b l e m s h t m 图表2 2c 类问题 图表2 3r 类问题 图表2 4r c 类问题 s o l o m o n 的测试问题中不存在风险的概念，本文用o l o 之间的随机数( 保 留三位小数) 生成每条边的单位风险，即单位风险最大的边和最小的边最多可以 相差1 0 4 倍，并利用第4 6 节提出的启发式算法求解这些问题。 第4 7 节已经分析了完全风险偏好时扩展的邻域搜索算法与传统的v r p t w 的邻域搜索算法相同，计算结果直接取决于核路线算法中所选取的核路线交换算 法，这里不做计算讨论。而对于五( o ，1 1 的情况，只能计算启发解，尚无最优解 可以对照。因此，这里只计算完全风险规避情况下的解。表格l 列出了在 p e n t i u m i v ( 1 8 g ) p c 机上求解完全风险规避情况下这5 6 个问题的计算结果，其中 n v 代表所需车辆数，时间的单位为秒，图表1 9 中核解的改进算法采用2 - o p t ， e x c h a n g e 和2 - o p t * = 种路线改进算法。 表格1 计算实例 雾矛 ? 罗? 谳解。”冀鼍2曩：1 一：动始解瑟焉瓣一一一一。改进觯_ 一一+ 一秀 黪一， ；n 、，时间，蠢费用，n v，费用=。? 麟一、n y i吒费厦。时姆l - 蘩藿蠹 c 1 0 11 0 02 21 2 0 3 3 52 94 5 9 7 0 32 8 2 0 2 8 41 2 1 0 1 52 3 70 5 7 c 1 0 21 0 0l l1 1 8 7 7 12 56 0 4 7 3 24 0 9 1 6 8 71 1 9 0 9 73 7 40 2 7 c 1 0 31 0 c51 1 6 1 4 32 06 8 2 8 6 64 8 7 9 5 7 5 1 1 7 3 0 55 1 71 o o c 1 0 41 0 021 1 4 6 4 11 87 3 8 3 35 4 4 0 4 8 51 1 4 6 4 17 0 9o 洲 c 1 0 51 0 01 2 1 1 6 4 。0 9 2 65 1 5 2 4 83 4 2 6 2 8 2 1 1 6 4 5 52 4 20 0 4 c 1 0 61 0 091 1 7 0 6 22 83 9 1 1 6 2 2 3 4 1 5 8 4 1 1 7 1 0 83 0 60 0 4 c 1 0 71 0 01 41 1 5 8 7 92 44 8 9 9 1 23 2 2 7 8 8 3 1 1 5 8 7 92 7 70 0 0 c 1 0 81 0 041 1 4 4 1 62 23 9 8 3 4 l2 4 8 1 5 8 3 1 1 4 4 1 6 3 6 9 0 0 0 c 1 0 91 0 011 1 4 3 3 81 87 5 6 3 6 75 6 1 5 2 7 8 1 1 4 3 3 8 4 3 0 0 0 0 c 2 0 11 0 041 1 5 0 2 61 58 5 4 4 2 86 4 2 8 1 8 21 1 5 9 8 93 6 30 8 4 c 2 0 21 0 03 1 1 4 9 9 4 1 4 8 9 1 4 2 56 7 5 。1 9 7 8 1 1 5 6 7 24 7 80 5 9 c 2 0 31 伽31 1 4 9 9 41 31 4 8 0 3 51 1 8 7 - 3 3 7 9 1 1 5 6 7 87 4 4o 5 9 c 2 0 41 0 0l1 1 4 3 3 8l l1 4 3 0 0 311 5 0 7 0 7 61 1 4 3 3 81 2 4 90 0 0 c 2 0 5 1 0 0l1 1 4 3 3 81 39 1 6 6 9 47 0 1 7 4 8 21 1 4 3 3 84 5 80 0 0 c 2 0 6 l 伽l1 1 4 3 3 81 01 0 4 1 9 88 1 1 3 2 8 g1 1 4 3 3 84 7 60 0 0 c 2 0 71 0 0 11 1 4 3 3 8l1 1 5 2 7 39 0 8 1 8 7 51 1 4 3 3 84 8 40 o o c 2 0 81 0 a11 1 4 3 3 81 09 9 5 1 8 87 7 0 3 9 8 0 1 1 4 3 3 85 6 5o 0 0 匿一一。 一一一强优解一。一节? 4 。初始解2 谚一节设迸箨甲。习 曼问题 ，n v畦间费用n v 费用 一。强差 一 n v爨用一舅闻。：。堤善豸 r l o l1 0 051 4 5 8 7 34 93 4 8 9 8 71 3 9 2 4 8 51 5 0 2 8 71 7 ( 33 0 3 r 1 0 21 0 05 l1 2 5 7 9 24 26 1 3 9 1 23 8 8 0 4 0 a8 21 2 9 1 5 52 3 32 6 7 r 1 0 3 1 0 0 4 91 1 3 0 8 l 3 77 0 6 0 2 65 2 4 。3 5 8 21 1 7 2 8 5 2 7 2 3 7 2 r 1 0 4 1 0 ( 1 4 41 0 3 2 1 22 5 8 4 5 2 7 8 7 1 8 9 7 7 91 0 7 1 2 34 2 43 7 9 r 1 0 5 1 0 ( 1 6 ( 31 3 5 1 3 54 1 3 9 4 3 6 4 1 9 2 2 0 蹦1 4 4 6 1 5 2 1 4 7 0 2 r 1 0 61 0 05 61 1 7 5 0 63 56 1 1 1 5 2 4 2 0 1 0 7 81 2 5 3 3 6 3 0 8 6 6 6 r 1 0 71 0 05 21 1 0 9 9 9 2 98 6 2 5 6 5 6 7 7 0 9 8 21 1 3 3 4 l 3 5 42 1 1 r 1 0 81 伽4 51 0 2 4 6 9 2 2 1 0 6 5 8 9 4 0 1 2 8 l1 0 4 1 6 94 5 c1 6 6 r 1 0 9l 伽6 11 1 6 6 4 93 26 9 0 1 蹦4 9 l 6 8 8 61 2 1 5 7 93 1 84 2 3 r 1 l o1 0 061 1 0 7 8 93 07 4 4 2 5 25 7 1 7 7 8 21 1 1 6 5 24 0 20 7 8 r l l l 1 0 ( 3 5 91 0 8 6 6 82 86 5 1 5 7 3 4 9 9 6 0 7 9 1 1 1 0 2 5 3 5 4 2 1 7 r 1 1 21 0 a6 09 9 7 6 1 72 55 3 6 8 3 44 3 8 1 2 7 91 0 0 9 0 84 7 01 1 5 r 2 0 11 0 039 2 1 0 4 21 56 2 3 1 0 35 7 6 5 2 7 69 2 1 0 4 23 9 10 0 0 r 2 0 21 0 09 2 0 1 1 71 49 5 0 9 5 89 3 3 5 2 7 99 2 0 1 1 77 0 4o 0 0 r 2 0 3 1 0 09 2 0 1 1 7 1 1 1 1 5 2 1 81 1 5 2 2 1 8 0 9 2 0 1 1 79 4 5 0 o o 1 1 2 0 4 1 0 09 2 0 1 1 791 9 4 1 1 62 0 0 9 6 9 7 89 2 0 1 1 71 2 0 50 0 0 r 2 0 51 0 ( i9 2 0 1 1 798 7 6 9 3 48 5 3 0 7 7 69 2 0 1 1 76 2 6o 0 0 r 2 0 61 0 0l9 2 0 1 1 91 4 0 5 3 21 4 2 7 3 3 7 79 2 0 1 l 8 0 1o o o r 2 0 71 0 09 2 0 1 1 7s1 4 6 1 81 4 8 8 7 1 7 99 2 0 1 1 71 2 0 l0 0 0 f 匕0 81 0 0 9 2 0 1 1 791 9 1 2 1 71 9 7 8 1 8 8 1 9 2 0 1 1 71 0 9 8 0 0 0 r 2 0 91 0 09 2 0 1 1 l l 1 1 9 9 81 2 0 3 9 6 8 ( 19 2 0 1 1 78 1 2o o o f 也1 01 0 019 2 0 1 1 11 01 0 6 9 9 81 0 6 2 8 7 7 99 2 0 1 1 77 4 50 0 0 r 2 l l1 0 0 19 2 0 1 l ，79 1 3 7 8 78 9 3 1 2 7 8 9 2 0 1 1 71 1 2 7 o 0 0 r c l 0 11 0 06 71 6 6 8 7 43 87 1 1 9 9 83 2 6 6 7 8 71 7 0 5 4 91 9 6 2 2 0 t c l 0 21 0 07 31 5 4 8 6 33 67 8 2 7 3 44 0 5 4 4 8 61 5 8 8 8 32 2 22 6 0 i k l 0 31 0 07 31 4 8 1 7 13 29 2 1 8 0 75 2 2 1 2 8 61 5 1 7 2 42 8 92 4 0 r c l 0 41 0 06 71 2 3 1 2 82 51 0 8 9 57 8 4 8 5 8 11 2 6 2 7 33 7 72 5 5 r c l 0 51 0 07 61 5 1 9 0 93 68 4 8 1 3 94 5 8 3 2 9 01 5 3 3 2 12 6 2o 9 3 r c l 0 61 0 06 91 3 3 1 2 63 36 9 8 3 1 84 2 4 5 5 8 61 3 “0 82 7 9o 9 6 i 配1 0 71 0 07 41 2 6 4 7 22 89 5 8 8 1 76 5 8 1 3 8 11 2 7 3 6 22 9 9o 7 0 r c l 0 8l o o 7 71 2 0 6 9 1 8 7 2 1 7 86 2 2 6 5 7 9 1 2 1 3 1 3 4 0 4 0 5 2 r c 2 0 l1 0 01 61 1 1 l1 57 5 7 1 95 8 1 5 4 7 31 1 1 6 6 63 1 7o 5 1 r c 2 0 21 0 071 1 1 0 4 51 41 1 2 6 8 49 1 4 7 6 7 71 1 1 5 1 35 4 80 4 2 r c 2 0 31 0 0 7l l l o 0 1 1 3 1 1 6 6 2 6 9 5 0 6 8 7 81 1 1 4 6 9 7 8 5 0 4 2 r c 2 0 4l o ol1 0 8 3 。5 71 31 2 5 lo 81 0 5 4 5 9 7 71 0 8 3 5 1 0 1 6 o 0 0 r c 2 0 51 0 041 0 8 6 2 41 48 1 0 7 5 76 4 6 3 9 7 21 3 2 5 2 94 1 32 2 0 l r c 2 0 61 0 041 0 8 3 8 71 29 6 4 7 47 9 0 0 9 7 41 0 8 3 8 75 5 60 0 0 r c 2 0 71 0 01 0 8 3 5 71 11 1 1 9 0 19 3 2 7 1 8 l1 0 8 3 5 77 2 9o 0 0 r c 2 0 81 0 01 0 8 3 5 791 5 0 4 1 51 2 8 8 1 4 7 71 0 8 3 5 71 0 9 8o o o 由表格l 和图表2 5 可见，改进解中有2 4 个问题( 4 2 ) 达到最优解，另外 有1 5 个问题( 2 7 ) 误差在l 以内，1 6 个问题( 2 9 ) 误差在1 0 0 4 以内，只有 1 个问题( 2 ) 误差在1 0 0 , 4 以上。平均误差为1 a 1 。最差解为问题r c 2 0 5 的 启发式解，误差为2 2 0 1 。可见，在完全风险规避的情况下，该算法的计算结 果总体上接近最优解。另外，虽然最优解算法的计算时间较短，但该算法只适用 于完全风险规避的情况，对于其他情况，不能应用该算法求解。 3 0 2 5 2 0 絮1 5 l o 5 0 o 1 1 j 6 1 0 9 6大于1 0 误差 图表2 5 结果分析 6 总结与展望 本文将危险品配送问题同传统的v r p t w 问题相结合，提出了一种带有时间 窗口的危险品v r p 问题，并给出了相应的模型和解法。 本文的主要工作有以下内容： 1 提出一种与车载量相关的风险度量。 2 结合危险品运输问题和v r p t w 问题，提出了唧砌r r w p 问题，并给出了该 问题的规划模型。 3 给出了h m v r p t w 问题的一种启发式解法，其中包括三种新的路线改进算 法。 4 对完全风险偏好和完全风险规避情况下的m 压v r p t w 问题做了进一步讨论， 指出完全风险偏好情况下该闯题为v r p t w 闯题；给出了求解完全风险规避 情况下h m v r p t w 问题的精确解法。 5 应用s o l o m o n 的5 6 个b e n c h m a r k i n g i a 日题进行了计算实验，验证了在完全风险 规避的情况下，该算法的计算结果总体上接近最优解。 本文仅仅对卸汛佩p 1 r w 问题做了初步的探讨，还有许多问题需要在今后的工 作中加以解决。 1 虽然本文建立的模型考虑了比较重要的一些约束，但由于实际情况的复杂性 和车辆调度的多样性，与实际情况仍然差距较大，模型相对理想化。对于一 些比较特殊的约束，如：配送需求的实时调整与响应、某些道路对特定车辆 的可通行性以及速度限制、货物体积与重量的装车双重约束等，都将是以后 值得进一步研究的方向。 2 本文仅仅给出了完全风险规避情况下最优解的求解方法，对一般性问题的最 优解求解方法也非常值得研究。如：可以首先寻找规划模型中子模型的快速 求解方法，并通过列生成的方法求解该问题。 致谢： 值此论文即将完成之际，我衷心地感谢我的导师叶耀华副教授对我的论文从 立题、研究以及最后的提炼进行指导，并百忙中对论文的关键部分提出一些建设 性的建议。叶老师学识渊博、眼界开阔、治学严谨、平易近人、诲人不倦，是我 终身学习的榜样。 同时我也探深地感谢这3 年来不辞辛苦为我们授课的各位老师，和与我一起 努力、相互鼓励、相互支持、共同进步的复旦大学运筹学全体同学。 最后，感谢我的家人，他们对我学业上的支持，对生活上的关心，对我无私 的爱，是我永远都报答不尽的。 参考文献 b a k e rel 【，s c h a f f e rjr s o l u t i o ni m p r o v e m e n th e u r i s t i c sf o rt h ev e h i c l e r o u t i n ga n ds c h e d u l i n gp r o b l e mw i t ht i m ew i n d o wc o n s t r a i n t s 叨a m e r i c a n j o u r n a lo f m a t h e m a t i c a la n dm a n a g e m e n ts c i e n c e s 1 9 8 6 6 ：2 6 1 3 0 0 【2 】b a l i n s k iml ，q u a n d tr e o na ni n t e g e rp r o g r a mf o rad e l i v e r yp r o b l e m 阴 o p e r a t i o n sr e s e a r c h 1 9 6 4 ，1 2 ( 2 ) ：3 0 0 3 0 4 【3 】b r0 ，g e n d r e n um 舡c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，p a r ti ：r o u t e c o n s t r u c t i o na n dl o c a ls e a r c ha l g o r i t h m s 阴t r a n s p o r t a t i o ns c i e n c e 2 0 0 5 ，3 9 ( 1 ) ： 1 0 4 11 8 4 1b ro ，g e n d r e a um v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s 。p a r ti i ： m e t a h e u r i s t i e s 阴t r a n s p o r t a t i o ns c i e n c e 2 0 0 5 ，3 9 ( 1 ) ：11 9 一1 3 9 【5 】c l a r k e g ，w r i g h t j w s c h e d u l i n g o f v e h i c l e s f r o ma c e n t r a l d e p o t t o a n u m b e r o f d e l i v e r yp o i n t s o p e r a t i o n sr e s e a r c h 1 9 6 4 ，1 2 ( 4 ) ：5 6 8 - 5 8 1 【6 】v i g od mv e h i c l er o u t i n gp r o b l e m ( m o n o g r a p h so nd i s e r e t cm a t h e m a t i c s a n da p p l i c a t i o n s ) m s i a m 2 0 0 1 ：3 6 7 7 】d a n t z i ggb ，r f l n l s e rjh mt r u c kd i s p a t c h i n gp r o b l e m 叨m a n a g e m e n t s c i e n c e 1 9 5 9 ，6 ( 1