（系统工程专业论文）带有时间窗的单车辆动态路径规划系统研究.pdf

独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：i 丝查翟 日期：2 丛：! 兰：鲨 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名 逊年二月皇芝日 大连理工大学硕士学位论文 摘要 本文针对目前物流配送中客户对配送的时间要求越来越严格以及客户数量不断增 加等因素导致的路径规划复杂这一问题，从第三方物流中心的角度出发，研究带有时间 窗的单车辆动态路径规划问题。旨在通过动态路径规划系统能够规划各个客户点服务的 先后顺序以及各个客户点之间的最短路径。通过深入分析这一类问题的特点，引入了桌 面式g i s 开发平台m a p i n f o ，使用m a p x 组件，并以大连市区电子地图为基础，对 路径规划的算法进行了研究和改进。在此基础上，设计并实现了带有时间窗的单车辆动 态路径规划系统，为物流配送中的路径规划提供决策依据。本文所做的主要研究工作包 括： ( 1 ) 通过道路预处理、自动断链、节点匹配等步骤，对大连市电子地图的道路网络 图层进行拓扑处理，剔除冗余的数据，并建立了道路数据库，为路径规划打下基础。 ( 2 ) 在对动态车辆路径规划问题描述和分析的基础上，着重研究这类问题模型的特 点，并分别为两点问路径规划、原始客户的路径规划以及动态路径规划等问题建立数学 模型。 ( 3 ) 在建立了问题的数学模型的基础上，对路径规划的算法进行研究和分析，重点 研究了经典的最短路径算法d d s k t r a 算法，并对其进行改进。在此基础上分别设计 了求两点间最短路径以及带有时间窗的路径规划的改进的d i j s k t r a 算法。 ( 4 ) 从系统的技术架构、系统总体设计、数据库的设计等方面对系统加以设计，并 根据上述内容设计实现了带有时间窗的单车辆动态路径规划演示系统，取得了良好的效 果。 本文的研究有一定的理论意义和实用价值。电子地图的拓扑可以为以后类似的研究 提供数据支持；改进的d i j s k t r a 算法中估价函数的设定对同类研究具有借鉴作用：同时， 本系统在第三方物流中心应用可以满足其动态处理客户的要求，使其能够在满足客户要 求的前提下尽量降低运营成本，更重要的是，能够迅速地对客户的需求做出回应。因此， 本系统有很大的实用价值。 关键词：时间窗；动态路径规划：地理信息系统；改进d i j s k t r a 算法 张志霞：带有时间窗的单车辆动态路径规划系统研究 a s y s t e m f o rs i n g l ev e h i c l e sd y n a m i cr o u t i n gs c h e d u l i n gw i t ht i m e w i n d o w s a b s t r a c t f o c u s i n go nt h ep r o b l e m t h a tt h ec l i e n t so fl o g i s t i c sa r eh a v i n gt h ec e a s e l e s si n c r e a s i n g d e m a n do ff a s ts e r v i c e ，m o r ea n dm o r ec l i e n t sn e e ds e r v i c e ，w h i c hm a k e st h er o u t i n g ，i sm o r e a n dm o r ec o m p l i c a t e d ；t h es t u d yo nt h es y s t e mf o rd y n a m i cr o u t i n gw i t ht i m ew i n d o w sh a s b e e nd o n e t h ep u r p o s eo ft h es y s t e mi sa r r a n g i n gv e h i c l e st os e r v et h ec l i e n t so nt i m ea n d r o u t i n gt h es h o r t e s tp a t h ，e t e a f t e ra n g l i c i z e dt h ec h a r a c t e r i s t i co f t h ep r o b l e m ，d e s k t o pg i s p l a t f o r m m a p l n f oa n dt h ec o m p o n e n t m a p xa r ea p p l i e dt ot h ec o n s t r u c t i o no ft h es y s t e m a l s o ，t h ea r i t h m e t i ci sr e s e a r c h e da n di m p r o v e d a tl a s t ，t h ed y n a m i cr o u t i n gs y s t e mo fs i n g l e v e h i c l ew i t ht i m ew i n d o w si sd e s i g n e da n dp r o g r a m m e d t h i ss y s t e mc a l ls e r v et h e d i s t r i b u t i o nc e n t e rf o rv e h i c l e sa r r a n g i n gv e r yw e l l ，s oi th a sg r e a tp r a c t i c a lv a l u e s t h em a i n r e s e a r c h e sa r ea sf o l l o w s ： ( 1 ) a f t e rr o a d s p r e t r e a t m e n t ，a u t o m a t i cp a r t i n ga n dn o d em a t c h i n g ，t h er o a dl a y e ri n d a l i a nm a pi st o p o l o g i z e d ；r e d u n d a n td a t aa r ee l i m i n a t e d i tg r o u n d e df o rt h er o u t i n g ( 2 ) o nt h eb a s i so fa n a l y s i sa n dd e s c r i p t i o no ft h ep r o b l e m ，t h ec h a r a c t e r i s t i co ft h e p r o b l e m sm o d e li sr e s e a r c h e da sa ne m p h a s i s a l s o ，t h er o u t i n gb e t w e e nt w op o i n t s ，t h e p r i m a r yr o u t i n ga n d t h ed y n a m i cr o u t i n ga r ea l lm o d e l e d ( 3 ) o nt h eb a s i so ft h em o d e l i n g ，s o m er e s e a r c h e sa n da n a l y s i so ft h ea r i t h m e t i ca r e u n d e r t a k e n t h ec l a s s i c a lr o u t i n ga r i t h m e t i c - d i j s k t r ai ss t u d i e da sa ne m p h a s i s a l s o ，i ti s i m p r o v e dt os o l v et h ep r o b l e m so fr o u t i n gb e t w e e nt w op o i n t s ，t h er o u t i n go ft h ep r i m a r y c l i e n t sa n dt h ed y n a m i cr o u t i n g ( 4 ) t h i sp a p e rd e s i g n st h er o u t i n gs y s t e mf r o ms e v e r a lr e s p e c t s ，s u c ha st e c h n o l o g y b u i l d i n g - u p ，f r a l n e ，d e s i g no fd a t a b a s e ，m o d e l i n ga n da r i t h m e t i ci m p r o v i n g ，e t c t h e na d e m o n s t r a t i o ns y s t e mo fd y n a m i cr o u t i n gs y s t e mo fs i n g l ev e h i c l e 、i t l lt i m ew i n d o w sh a s b e e nd e s i g n e da n dr e a l i z e da c c o r d i n gt ot h ea b o v e m e n t i o n e dc o n t e n t s ，a n di td e m o n s t r a t e s g o o dp e r f o r m a n c e t h er e s e a r c hi ss i g n i f i c a n to nt h e o r ya n du t i l i t y 1 1 1 et o p o l o g yo ft h ed i g i t a lm a pc a n p r o v i d ed a t af o rh o m o l o g o u sr e s e a r c h e s ；t h ev a l u ef u n c t i o n so ft h ei m p r o v e da r i t h m e t i cc a n a l s ob eu s e df o rr e f e r e n c ef o rh o m o l o g o u sr e s e a r c h e s a tt h es a m et i m e ，t h i ss y s t e mc a n s a t i s f yt h ed e m a n do f t h el o g i s t i c s f r e i g h t i n gc e n t e r ，w h i c hi sd e a l i n gw i t ht h ec l i e n t s d e m a n d o nt h et i m et h e yc o m e a l s o ，i tc a ns a t i s f yt h ec l i e n t s d e m a n d sa sp r e c o n d i t i o n ，t h e n ，i tt r i e s t os a v et h ef r e i g h t i n gc o s ta sm o r ea si tc a n i naw o r d ，i ti sp r a c t i c a l i i 大连理工大学硕士学位论文 k e yw o r d s ：t i m ew i n d o w s ；d y n a m i cr o u t i n g ；g i s ；i m p r o v e dd i j s k t r a ，h i 大连理工大学硕士学位论文 1 引言 1 1 问题的提出 随着以互联网为平台的网上交易的发展，商品的交易时间已经可以达到马克思所言 的“等于零或者趋近于零”的境界。网上交易使商品交易发生了巨大的革命，不仅时间 缩短，交易速度加快，而且可以大大降低商业交易的交易成本。电子商务可以分解成商 流、物流、信息流、货币流等4 个主要组成部分。任何一次商品流通过程，都是这“四 流”实现的过程。现在看来，商流、信息流、货币流可以有效地通过互联网络来实现， 在网上可以轻而易举完成商品所有权的转移。但是这毕竟是“虚拟”的经济过程，最终 的资源配置，还需要通过商品实体的转移来实现，也就是说，尽管网上可以解决商品流 通的大部分问题，但是却无法解决“物流”的问题。因此。物流成为电子商务的瓶颈。 在我国现在的主要表现是，在网上实现商流活动之后，没有一个有效的社会物流配送系 统对实物的转移提供低成本的、适时的、适量的转移服务。配送的成本过高、速度过慢 是偶尔涉足电子商务的买方最为不满的问题。 尤其是随着电子商务的不断发展，第三方物流中心的竞争也越来越激烈，客户对物 流配送的要求也越来越高。以前的物流配送所要解决的问题就是要根据客户需要把货物 送到客户手上，客户对时间的要求并不时那么严格。因此，物流中心只要规划出一条遍 历所有客户的路径就能满足需求。但是，随着经济的发展，随着科学技术的不断进步， 需要服务的客户越来越多，客户的时间观念也逐渐增强，大部分客户都会对送货时间有 严格的限制。因此，作为第三方物流中心，为了发展，为了在竞争中取胜，就必须要适 应这种需求的变化。因此，他们不得不在路径规划的时候将时间窗因素考虑进来。 此外，由于客户的不断增多，而且他们不可能是同一时间到来，通常是每时每刻都 有新客户来要求服务。作为第三方物流中心，为了求发展，就必须能够动态地处理新任 务，能够迅速地安排运送途中的车辆去处理该任务。因此，问题就是如何安排车辆，车 辆如何协调原来任务和新任务的关系以及如何规划路径等。 本系统旨在解决当物流中心有新的任务到来，如何安排正在送货途中的配送车辆去 为其服务，以及如何改变原来配送路径等问题。现实中应从多个车辆中选择一辆来完成 新任务，但是由于多个车辆的情况比较复杂，本系统从单个车辆入手，对车辆原有任务 以及新客户一起加以分析，规划出一条最优路径，作为决策人员的依据。 本研究有以下几个问题需要解决： ( 1 ) 新的配送任务是时时刻刻都在发生的，不可能所有的都接受，因此有必要有选 择性的接受新任务，即过滤掉一些完全不可能完成的任务。 张志霞：带有时间窗的单车辆动态路径规划系统研究 ( 2 ) 在地图上规划路径，一个首要问题就是对地图的道路网络进行拓扑，本系统所 使用的m a p l n f o 平台没有这一功能，因此，需要在准备阶段编程实现地图的拓扑功能， 将道路数据存入数据库中供路径规划模块使用。 ( 3 ) 新任务到来之前的路径也要通过本系统实现。该模块解决的是带有时间窗的单 车辆路径规划问题。 ( 4 ) 本文在重新规划路径的过程中，不仅要考虑客户的时间窗因素，还要考虑新加 的客户与其供货点的前后问题以及汽车的容量限制等问题。 ( 5 ) 由于是实时地接受新任务，因此对系统的速度要求非常严格，如果速度慢，车 辆的位置情况，完成任务情况等可能早已发生变化，从而导致运算结果毫无意义，不能 对物流配送起到指导的作用。 为了解决本文提出的动态路径规划问题，本文将在给出其算法的基础上，以大连市 的交通道路为应用背景，通过对系统进行分析设计，利用m a p x + v b n e t 实现带有时间 窗的单车辆动态路径规划系统，从而解决这一实际问题，使得物流配送中心在满足客户 时间窗需求的基础上尽量降低成本，在竞争中处于不败之地。 1 2 国内外同类研究综述 本节内容旨在对国内外同类研究进行回顾与总结。首先分析动态路径规划问题的模 型的研究进展，其次对国内外动态车辆路径规划问题算法进行综述，以作为本文研究的 基础。 1 2 1 动态车辆路径问题模型的研究 ( 1 ) 动态车辆路径问题模型的研究进展 作为最早研究动态v r p 的学者之一，p s a r a f t i s 在比较了v r p 静态与动态模型的主 要区别【”。m i c h a e l 等对单个车辆动态p d p 问题的模型进行了研究和分析【2 l 。在模型中， 作者把任务的到来时间看作服从泊松分布。供货点和客户点都是相互独立的并且均匀分 布在该地区。目标函数是最小化为客户服务的总时间。在文献 3 1 中t e o d o r o v i c 等人提出 的一种解随机需求v r p 问题的初步模型中，服务点的需求量假设满足均匀分布，从而 提出了一个解随机需求v r p 问题的框架。m a r k o v l 4 提出一类求解动态调度问题的 m a r k o v 决策模型。这种模型是把系统作为一个马尔可夫型随机系统来求解。p e t e r 等睁j 提出过求解交通堵塞的排队论模型，此外还有s w i h a r t 2 1 等提出过求解单车辆装卸混合问 题的排队论模型，b e r t s i m a s l 6 1 等提出的求解动态旅行修理员问题和多车辆有容量约束的 动态车辆路径问题的排队论模型等。j a i l l e t 把动态路径规划问题归纳成个整数非线性 规划模型，继而又转化成一个整数线性规划模型，最后用分枝定界法来求解这个熬数规 大连理工大学硕士学位论文 划模型。他还指出，实际上动态规划并不能得到一个精确的结果。因此，他提出了用启 发式算法来求解这类问题。受到j m l l c t 的启发，b e r t s i m a s 等 6 1 定义了概率车辆路径问题。 p v r p 模型的需求不是确定的，而是以一个概率信息给出的。他们提出两种不同的策略， 一种是在实际运行中不管顾客是否需要服务，都要按照原定的路线进行。另外一种是绕 过不需要服务的点。与以上几个模型不同，p a l e t t a l 7 1 还曾经提出过一种求解动态旅行商 问题的网络模型。 国内对动态v r p 的研究开始的比较晚，从9 0 年代中后期开始才陆续有相关学术文 章发表。郭耀煌，谢秉磊【8 j 指出“与静态车辆路径问题相比，动态车辆路径问题的一个 显著特征是不再沿用行驶路程最短、运输费用最省作为目标，而是以一些参数的期望值 作为优化目标。”陈壁蜂，陆吴娟，黄樟灿等结合遗传算法的特点，建立了求解动态 最优路径的模型及算法，并且通过实验证明该方法可以有效地解决动态最优路径问题【9 1 。 作者分别建立了两种模型，一种是局部动态最优路径的数学模型，另外一种是全局动态 最优路径的数学模型。张建勇，李军，郭耀煌等对具有不确定需求的单车场单车辆动态 f v r p 进行了研究，并建立了一种模糊需求量的模型。在建立模型的过程中，作者把 已知的车辆运输能力设为c ，而每个节点事先知道的需求量设为模糊数d ，实际实现的 需求量设为d ，目标是求满足运输需求的行驶距离最短的车辆行驶路线。受到 t e o d o r o v i c 3 1 等人的启发，倪勤等人对模型进行了改进，把服务需求量看作满足二项式 分布【1 阽1 p ( 一) = i ，l q ( 1 一q ) “q ，西= o ，l ，6 h j ( 1 1 ) 根据期望值的大小提出了在一条路线上理想最大服务点数的新概念，并在此基础上 建立了三种v r p 问题的新模型。新模型的目标是使得服务费用最小。这种新模型由于 允许服务失败两次和部分服务使得模型能适应多种实际问题。西南交通大学郭耀煌教授 主持的国家自然科学基金项目“不确定信息条件下动态车辆路径问题研究”是对动态 v r p 进行的一个比较全面深入的研究。在研究的过程中，他们对信息不确定条件下的动 态v r p 模型进行了研究。改变以为研究中车辆在由某车场或服务点驶往下一车场或服 务点的途中，不因出现新的信息而改变目的地的一般假设，建立车辆在途中可以改变目 的地的一对多、多对多的动态v r p 模型体系：在分析各种不确定性因素相互影响和有 限叠加的基础上，综合考虑车辆、顾客、路况和路径制订者等方面出现的不确定性，建 立包含多种不确定因素，满足车辆、路网容量、交通规范约束，考虑运输企业和顾客要 求的实用多目标动态v r p 模型。张建勇，郭耀煌，李军等把模糊预约时间的概念引入 张志霞：带有时间窗的单车辆动态路径规划系统研究 到v r p 的研究中，从顾客满意度的角度分析了模糊不确定信息条件下的多目标车辆优 化路径问题【l ”。 从以上叙述可以看出，历经多年的研究，动态车辆路径问题在模型研究方面有了很 大进展。但是，他们所研究的大多是针对不确定信息或者模糊信息。我们所说的动态的 涵义是时时刻刻都在变化的客户信息、供货点信息以及车辆位置信息等。而此类研究目 前比较少。但是此类问题又恰恰是物流配送中切实存在的问题，是亟待解决的问题。因 此，我们有必要对这一类问题进行研究，找到解决的途径。 ( 2 ) 模型的生成 在动态路径规划中，模型的生成也是一个不能回避的问题。以下是对这方面文献的 综述。 李军，郭耀煌等使用“( 节点结构) + 弧段集合 ”表达网络拓扑图i l 引。在该结构 中，一幅图可抽象为“ 节点集合) + 弧段集合) ”。利用这种节点一弧段联合结构，可 以较好地表达真实图中的实体关系。针对道路网数据的特点，也有人采用“混和数据结 构”( h y b r i d d a t as t r u c t u r e ) 来组织道路网数据，利用关系数据库结构描述属性数据， 及用“拓扑关系”的空间数据库结构描述空间几何数据，空间数据和属性数据通过用户 码相关联。这种混和数据结构兼顾了空间数据和属性数据两种不同性质的数据特点，可 全面描述道路网信息，还可有效地实现两类数据的操作、处理和管理。减少数据冗余量， 大大提高数据处理和检索的速度，从而方便地支持空间数据分析。 多边形区域的自动生成是利用输入的节点和弧段的信息，由弧段文件自动组织多边 形。早在1 9 9 4 年李德仁等就提到了一种算法【l4 1 。这种算法首先建立节点一弧段的拓扑 关系，然后根据弧段的方位角大小来自动生成多边形区域。 在实际的路径规划中，起始点和目标点不一定在道路网节点上或路段上( 称为孤立 点) ，从普遍意义出发，假定起始点和目标点动态确定，为了使孤立点与道路拓扑网建 立联系，这就要求在规划前先依据提供的起始点、目标点的地理位置信息迅速确定它们 各自所在的区域。传统的确定方法如铅垂线算法和l p 算法【l ”，均要求已知道路网中所 有的多边形区域拓扑结构，并对其进行计算，l - p 算法还要求把地图的矢量数据结构转 化为单调的链结构，可关系复杂，计算量大。也有人针对系统中落区道路网稀疏的特点 提出一种叫做左转法的新算法，可以根据目标点的地理位置，只生成包围它的最小多边 形区域，从而大大减少了计算工作量，提高了规划效率f 1 6 l 。 上边提到的只是一个目标点的模型。我们所要研究的带有时问窗的动态路径规划问 题涉及到多个目标点，并且跟时间密切相关。这就需要我们在模型的建立方面再做进一 步的研究。 大连理工大学硕士学位论文 1 2 2 动态车辆路径问题算法研究进展 由于动态v r p 一般需要算法对实时发生的信息迅速地做出反应，所以一般的最优 化方法往往不能适应。人们的研究主要集中计算速度比较快的在启发式算法上。从求解 策略来看，动态v r p 的算法可分为两大类：一类是重新优化策略，另一类是局部优化 策略。 ( i ) 重新优化策略 重新优化策略实际上就是将动态问题需要求解的一瞬间看作静态问题来对待。也就 是说一旦接收到变化的信息，比如，客户有变化，或者客户的需求量有变化等，就从头 开始重新寻找最优车辆路径。成功运用重新优化策略的一个典型例子是b e l l 等用于研究 运送大宗商品的车辆路径问题。该研究的核心是基于l a r a n g i a l l 松弛和乘子调整技术的 静态算法。 在国外，这一方面的问题是众多专家学者研究的热点 2 a 7 。p s a r a 僦s ( 1 9 8 0 ，1 9 8 3 ) 1 8 a 9 首次用精确的动态规划算法解决了动态单车辆的d i a l a - f i d e 问题( d a r p ) ，也是采用 了这种重新规划的策略，当输入发生更新时，采用动态规划对路径重新进行优化。s e x t o n 和b o d i n l 2 0 通过应用b e n d e r s 的分解程序把单车辆问题的违反客户需求最小化，化为混 合的二元非线性公式，用这个公式来分别解决路径规划问题的各个组成部分。s e x t o n 和 c h o i 用两阶段的路径规划程序解决单个车辆的问题来使得车辆运行的总时间和由于超 出时间窗引起的用户的不满意程度的线性组合最小。他们的方法可以解决最多有1 8 个 客户的问题。p s a r a f l i sh 提出了一种基于动态规划的精确算法来解决单车辆的动态 d a r p 问题i l 】。在这种问题中，假设有n 个客户有实时的要求，而他们又分别有不同的 取货点与送货点。这些任务交由一辆原始位置已知的货车来完成。目标函数是完成任务 的时间最短与客户因等待服务而造成的不满意程度的最小的结合。此外，还有车辆的容 量以及每个客户的取货点与送货点的前后顺序问题需要考虑进来。但遗憾的是，这种算 法仅仅能够解决包括十个甚至更少的客户的问题。此外还有b a k d 2 l 】和c h r i s t o f i d e s ， m i n g o z z i 和t o t h 2 2 等也在这方面花费了很多精力。 在现实生活中，时间窗存在于很多问题中。因此，我们有必要再把带有时间窗的动 态v r p 问题提出来单独进行分析脚。2 6 1 。d e s r o s i e r 用一种改进的动态规划算法来解决带 有时间窗的d a r p 问题( d a r p t w ) ，这种算法通过消除车辆容量，在前约束以及时间窗 三者之间的矛盾来提高算法的效率。d u m a s 等人( 1 9 9 1 ) 提出的列成生法可以处理多达5 5 个客户的单个车辆的d a r p t w 问题。v a n d e r b r u g g e n 等( 1 9 9 3 ) 1 2 7 1 用了一种两阶段局 部搜索算法来求单种车辆的p d p t w 问题的近优解。他的主要搜索策略就是进行弧交换。 这种算法的准则是超出时间窗的惩罚最小化，同时，在前约束和车辆容量的约束不得违 张志霞：带有时问窗的单车辆动态路径规划系统研究 反。文献中提到“在第一阶段，我们还没能应用全局变量技术来虑及计算的效率问题”； “在接下来的研究中，可以在第一阶段应用超出时间窗的评估从而来减少计算时间”【2 “。 同年，v a nd e rb r u g g e n 等人还提出带惩罚函数的模拟退火算法来求解p d p t w 问题，这 种算法是通过接受次优解，以及穿过实际不可行的状态矢量空间来求解。p a r f a i t sh 提出 的算法【l8 j 对他以前的算法进行了改进，加入了时间窗的限制，这种算法仍然有很多不足 之处：f 1 ) 目标函数缺乏一般性。这种算法提出的目标函数可能在最小化提供服务的总时 间时是好用的，但是在目标是最小化客户的不满意程度是就不一定好用了。这种问题与 时间窗的存在有直接关系。根据推测。不管采用什么目标函数都应该产生差不多的车辆 路线安排。( 2 ) 算法的计算复杂性问题。这种算法的计算复杂度比较大，为o ( n 2 3 n ) ， 这就使得这种算法解决问题的规模局限在一个比较小的范围内( 大约8 1 0 个客户，或 者1 7 2 1 个节点) ，也正是因为这种计算复杂性方面的缺陷，使得精确算法不能得到推 广，更多的研究者把目光转向了启发式算法来解决这类问题。( 3 ) 这种算法在多个车辆的 情况下应用时会有困难。在多个车辆的情况下，时间窗也确实存在，但是却对其进行间 接的解决，而且对于取货和送货时间不能很精确地满足客户的要求。因为如果要选择硬 时间窗的话，就会导致大部分这种问题无解，这样在现实生活中，这种算法不可行。 在国内，这类研究开始的要比国外相对晚一些。目前对于同类问题的研究主要有郭 耀煌、李军等，采用了网络启发式算法f 1 引，对带有时间窗要求的集货送货一体化满载车 辆路径规划进行了研究，并提出了考虑到每项任务，由其集货点至送货点为重车行驶， 故将一项任务由两个点看成是一个点，称为重载点，从而简化了模型的规模。此外还有 霍佳震和张磊【2 8 1 曾经对对这一类问题进行研究。在研究的过程中，他们为了简化而把问 题分解为两个阶段进行求解。第一步，对任务内部的集货点与送货点进行内部安排路径， 第二阶段再对各项任务之间进行外部安排行车路线。这种算法能够在较短的时间内找到 近优解，但是由于简化模型可能丢掉了比较好的解。此外还有叶耀华等人【2 9 】提出一种基 于列生成的分枝定界方法，来解决一种带有时间窗口和在前约束的车辆路线问题。这也 可以应用到动态路径中用于重新规划路径。 ( 2 ) 局部优化策略 由于v r p 问题本身是n p 难题，计算量已经很大，要是每接受一项实时信息，就要 对路径进行重新规划，那么计算量大得令人难以想象，同时很多时候都需要迅速地对实 时信息做出反应，而重新规划路径可能不能满足这个实时的要求。因此，虽然说重新规 划路径在理论上是可行的，但是在实际应用中却不能满足要求。 所谓的局部优化是指事先根据已知的信息制定初始路径，当接收到新的实时信息之 后，用某种算法对路径的局部进行改进，从而使新的路径合乎实时信息的要求。尽管这 大连理工大学硕士学位论文 样得出的新路径可能没有重新优化路径得到的优，但是由于节约了大量的计算时间，对 于现实中的实时车辆调度系统来说更为适合，因此，专家学者在运用局域优化策略方面 的算法研究中投入了大量的精力。 1 9 7 1 年w i l s o n 提出用一种插入法求解动态d a r p 问题，插入的原则是在所有可行 插入位置最小化需求发生到计划装载的延迟时间、从装载点到卸载点的行驶时间以及 计划装载和承诺装载间的时间差。后来，w i l s o n 又与其合作者在研究的过程中对上边提 到的插入法进行了改进，即一旦接收到新需求，并不马上对其做出反应，而是等待未来 的需求到来，从而降低插入法的短视行为。类似地，r o y 等也提出一种插入法用于运送 残疾人问题。在这种情况下，很多的需求都是事先已知，然后根据这些已知信息构造初 始路径。算法先根据时空近似度构造顾客的子簇( m i n i c l u s t e r ) ；在每个子簇中，用插 入法构造路径；最后，通过使顾客从一条路径转移到另一条路径，从而改进初始解。 m a d s c n 等也研究了运送老年人和残疾人的问题，也提出了一种插入方法。算法先用j a w 等提出的修正插入法静态安排车辆路径，然后以最小化新顾客和初始路径已存在顾客的 不便度作为插入准则，按序列模式处理实时需求。g e n d r e a u 等构造了一种适应存储的禁 忌搜索算法，用于并行求解信使服务问题。算法按主从模式构造，主进程控制适应存储， 即存储搜索过程中最好解的路径；从进程执行以c r o s s 交换作为领域的禁忌搜索。当 接受新服务需求时，禁忌搜索停止，将最好解送至主进程的适应存储，用传统的插入方 法，新需求被插入适应存储的每个解中。在更新后，将存储的新解反馈给禁忌搜索，重 新开始优化。 与上述的优化方法都不同，s h e n 通过b p 神经网络学习有经验调度员的调度过程， 逐渐调整连接权系数，使顾客的实时需求得到较快响应，不仅可以减轻调度员的工作量， 还可以得到较优的行车路径。 1 2 3 国内外同类研究总结 现在国内外对静态的v r p 问题研究的比较多【3 1 4 2 1 ，对于动态的v r p 研究则相对较 少一些。目前，对予动态的v r p 研究总结如下： 在模型方面，目前国内外的研究主要集中在存在不确定信息或者模糊信息的动态路 径规划径问题，而对于本文所说的表示“即时”信息的动态路径规划问题的模型研究比 较少。 在算法方面，重新优化策略和局部优化策略各有优缺点。重新优化策略肯定能够满 足所有情况，但是肯定会浪费很多时间和资源。相对而言，局部优化策略能够节约大量 的时间和资源，但是有时候如果新客户比较多或者比较特殊的话，反而应该直接重新优 化比较好，如果坚持局部优化可能事倍功半，反而浪费时间。 张志霞：带有时间窗的单车辆动态路径规划系统研究 因此，在今后的研究中如果能将其二者结合起来，具体问题具体分析，则能事半功 倍。本文旨在对动态车辆路径规划问题的模型和算法的研究与地理信息系统结合起来， 寻求种动态情况下的最优路径，解决实际的物流配送问题。 1 3 本文的研究思路和工作要点 针对地理信息系统在电子商务物流配送中的实际应用情况，本文以提高电子商务物 流配送的实时性、精确性为目标，对带有时间窗的单车辆动态路径规划系统做了初步的 探讨，并在此基础上由v b n e t 实现算法逻辑控制，由m a p x 组件管理图形的显示与控 制，开发出带有时间窗的单车辆动态路径规划系统。 基予以上所提到的研究工作，本文按照系统分析、系统设计、系统测试的思路作如 下编排： 第一章，为本文的引言部分，侧重解释了为什么要解决这一问题，以及解决此问题 的困难所在；此外还对国内外的此类问题的研究进展进行了总结：最后提出了解决该问 题的具体思路。 第二章，基于对带有时间窗的单车辆动态路径规划问题的需求分析，对本文所要研 究和设计实现的系统做了严格的界定；并且对本系统所涉及到的数据、功能等进行了详 细的分析，为后边的系统设计实现打下坚实的基础。 第三章，在对边界界定和需求分析的基础上，对带有时间窗的单车辆动态路径规划 系统的关键技术进行了一定程度的研究；对本文所研究的系统进行了系统设计，这包括 系统的总体设计、电子地图的设计、数据库的设计以及算法的设计等。 第四章，在前几章准备工作的基础上，运用v b n e t 作为开发环境，实现算法逻辑 控制，用m a p x5 0 组件管理图形的显示与控制，实现带有时间窗的单车辆动态路径规 划系统。 第五章，利用本文所实现的系统，在大连地图上使用一些数据来测试本系统的可靠 性等，从而确认本系统的实用性。 大连理工大学硕士学位论文 2 系统分析 本章在对系统的需求分析的基础上，对本文所要研究和设计实现的系统做了详细的 描述和严格的界定：并且对本系统所要涉及到的所有的数据、功能等都进行了详细的分 析，为系统设计和实现打下了坚实的基础。 2 1 问题的描述与界定 目前，路径规划系统根据使用对象和实现的功能而有所不同，不同的路径规划系统 服务的对象不同，实现功能的侧重点也有所区别。一方面，根据实际情况的需要明确本 文所要研究的是什么样的系统，需要实现什么功能：另一方面，由于实际的电子商务物 流是一个复杂的系统，涉及到的因素非常广泛，本文的研究不可能面面俱到。因此有必 要对所要研究的系统做出准确的描述和严格的界定。 2 1 1 问题的描述 随着电子商务的不断发展，客户对物流配送也提出了越来越高的要求。本文所要解 决的问题是动态路径规划问题，具体问题描述如下： 第三方物流中心的车辆都在配送途中。这时，又有客户打电话或者以其他方式通知 需要货物。物流中心在接到新的任务之后，通过对新客户的时间窗要求是否合理、是否 在上班时间、货物的量是否超出车辆的容量限制等来对新任务进行判别，从而决定是否 接受该任务。在判断的过程中，对于时间窗不合理的要求、时间窗距离现在太远的要求、 距离车辆初始位置太远的要求等都要剔除。因此在任务的输入过程中，对每一个输入 的参数都要进行判断。决定接受该任务之后，第三方物流中心如果另外派一辆车去完成 该任务，将会造成对资源的浪费以及成本的增加。他们的一般做法是通过g p s 设备等 获得各个车辆当前所在位置，并通过其他通信手段获得各个车辆当前任务的完成情况。 根据车辆的位置以及任务情况，从已在配送途中的车辆中选择一辆，通过对其现有任务 的位置和时间窗要求、车辆现在所在位置以及车辆剩余容量、新任务的位置以及它的时 间窗要求、新任务的供货点位置等进行分析，决定是否需要重新规划路径，如果需要， 则要规划出新的路径，然后对规划出的路径进行判断，判断结果符合要求，最后把新的 路径显示在地图上，如果不符合要求，则提示该车辆不能完成该任务。 本文所要解决的是动态路径规划，因为车辆是在不停的运动的，车辆位置是不断地 变化的，任务的完成情况也是时时刻刻都在改变。因此本文的规划路径等都是建立在动 态的基础上，要求规划速度要快，否则车辆位置、完成任务情况等发生变化之后，所规 划的结果就会毫无意义。 张志霞：带有时间窗的单车辆动态路径规划系统研究 换种方式说，即调度中心对任意个新的任务都要先做判别，在判别能够完成或者 有可能完成后再进入系统。车辆在接受新的任务之前，有n 项任务尚未完成，那么在本 系统中首先要以该车辆当前位置为起始点，在尽量满足这n 个客户的时间窗和需求量等 要求的前提下遍历该n 个客户点，并尽量找到最短路径。 在接受新的任务之后，目标点变为n + 2 个，即原来的n 个客户点加上一个新加的 客户点和与之对应的供货点。任何客户点都有时间窗约束，而供货点没有时间窗限制。 因此，系统需要在满足这n + 2 个客户点的时问窗要求的前提下，尽量找到最短路径，并 将路径显示在地图上。此外，由于新任务有其对应的供货点，因此，该新客户必须在其 供货点之后访问；在到供货点取货之前，还要判断车辆的剩余容量是否够用。 2 1 2 问题的界定 本文中对所研究问题作如下界定； ( 1 ) 本文研究的动态路径规划系统是为第三方物流中心服务的，其主要目是为第三 方物流中心提供路径规划服务。 ( 2 ) 该系统的使用者就是第三方物流配送中心的车辆调动中心。 ( 3 ) 所服务的第三方物流中心的业务范围为城市物流配送，其供方和需方均在同一 个城市，不考虑为跨城市、跨地区的供方和需方提供物流配送服务。 ( 4 ) 假设g p s 接收装置可以把车辆的当前情况传递给车辆调动中心。 ( 5 ) 各个客户的时间窗限制为软时间窗。 ( 6 ) 假设每个客户的需求量都在车辆容量的允许范围之内。 ( 7 ) 假设车辆始终保持同一速度行驶。 2 2 系统功能分析 带有时间窗的单车辆动态路径规划系统能够提供充足的地理信息和快速的地图浏 览，并享有高精度地图的支持，因此系统第三物流中心的车辆调度中心的车辆调动工作 的益处是显而易见的。通过此系统，用户可以迅速地对新产生的任务进行车辆指派，并 对该车辆的行驶路径进行合理性建议，从而既满足客户的时间窗、货物数量、货物种类 等条件，又能节约车辆的行驶里程，在享有比较好的声誉的同时尽可能地节约成本：同 时，通过该系统自带的电子地图，用户也可以对地图进行快速浏览，查询相关的供货点， 客户信息等。 大连理工大学硕士学位论文 l 带有时间窗的单车辆动态路径规划系统功能i i l 地图操作功能i 任务可行性判别功能路径规划功能人机曲话功能 li j 一 上 【一 上上 j 一 上上上 地地新可重路 新获显 图图任 行 新径 路取刁i 浏数务性规重径用 结 览据 触 判划新判户果 功 提 发别 判规断需功 _ 盥 供断 划求能 图2 1 系统功能图 f i g 2 1s y s t e mf u n c t i o n 2 2 1 地图操作功能 ( 1 ) 地图浏览功能：需要实现地图的缩小、放大、漫游、选择等浏览地图所需要的 基本功能，从丽满足系统的使用者对地图进行快速浏览的需要，通过快速浏览，对地图 的基本情况有个大致的了解，从而也方便使用者使用其它功能。 ( 2 ) 地图数据提供功能：主要是提供地图中的道路数据、客户数据以及供货点数据 等，从而满足用户对地图数据的要求。 幺2 2 任务可行性判别功能 新的任务时时刻刻都在发生，作为车辆调度中心，不可能对任何一个任务都马上接 受，并为其安排车辆马上去完成。因此，在每一项任务到来的时候，首先要根据一定的 规则对其进行判别，从而过滤出一些根本不可能完成的任务。在这一阶段是非常粗略的 判别，主要是看时间窗要求是否在服务时间范围内，以及现在时间是否属于工作时间等。 如果结果显示不能，则可以直接告知客户，不能完成该任务，要求其改变时间窗，或改 变其它要求等。如果有可能完成该任务，则进入下一个环节，即任务可行性判别。 在任务可行性判别这一阶段，要接着对新任务进行判别，即根据客户的要求，现有 的送货车辆的所在位置，完成任务情况，车辆现有容量剩余等影响因素再对新任务进行 判别，只有仍然符合条件的任务才能进入下一个路径规划阶段。否则通知客户，不能完 成其任务，以及不能完成其任务的理由。 张志霞：带有时间窗的单车辆动态路径规划系统研究 2 2 3 路径规划功能 这一功能涉及因素非常多，包括车辆位置、道路的情况以及客户的时间窗等，要在 满足客户要求的前提下尽量找到最短路径，从而提高效率，节约成本，所以说这是一个 复杂的系统工程。这一功能也是本系统的核心功能。本功能主要有两个组成部分。 一个是对原来的路径进行分析，看是否能在不改变原来路径的基础上“顺便”完成 新的任务如果能，要通知系统使用者任务的完成顺序。或者是否新任务在已经走过的路 上，要判断是否需要回去完成等。这两种情况对原路径都没有太大的改变。 另外一个部分就是，如果不是以上情况，则要按照客户要求以及车辆现状等情况对 路径进行重新规划，在满足客户要求的前提下尽量节约成本，找到较短的路径。重新规 划后要将规划好的路径在地图上显示出来，并以文字的形式对各任务的完成顺序给予说 明，从而使系统