基于遗传算法的时相关动态车辆路径规划模型.docx

基于遗传算法的时相关动态车辆路径规划模型.docx

《基于遗传算法的时相关动态车辆路径规划模型.docx》由会员分享，可在线阅读，更多相关《基于遗传算法的时相关动态车辆路径规划模型.docx（21页珍藏版）》请在冰点文库上搜索。

基于遗传算法的时相关动态车辆路径规划模型

第３３卷第８期２００８年８月

武汉大学学报・信息科学版

Ｇｅｏｍａｔｉｃｓａｎｄ

１ｎｆｏｍａｔｉｏｎ

Ｓｃｉｅｎｃｅｏｆ

ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙ

Ｖ０１．３３Ｎｏ．８

Ａｕｇ．２００８

文章编号：

１６７１—８８６０（２００８）０８一０８７５一０５文献标志码：

Ａ

基于遗传算法的时相关动态车辆路径规划模型

唐

健１’２

史文中２孟令奎１

（１武汉大学遥感信息工程学院，武汉市珞喻路１２９号，４３００７９）（２香港理工大学土地测量与地理资讯学系，香港九龙红确）

摘要：

动态车辆路径规划是智能交通和商业物流领域中的一个重要研究方面，其最大的优点是就是综合考

虑了各种实时信息。

及时优化更新配送车辆的行驶路径，进一步降低物流成本。

提出了一种基于遗传算法的时相关动态车辆路径规划模型。

该模型将时变的交通信息和动态客户订单考虑在内，可以获得比较好的动态更新效率和优化结果，为此类动态车辆路径规划探索出了一条可行的途径。

关键词：

动态车辆路径规划；智能交通系统；物流；遗传算法，时相关中图法分类号：

Ｐ２２８．４２；Ｐｚ３７．９；Ｐ２０８

在新的信息技术的推动下，各种动态信息的获取成为可能，如智能交通系统（ｉｎｔｅｌｌｉｇｅｎｔ

ｔｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍ，ＩＴＳ）、ＧＰＳ和ＧＩＳ。

ＩＴＳ、

ＧＰＳ和ＧＩＳ等技术的广泛使用，使得车辆管理系统中车辆货物运送的全程实时监控得以实现。

已有众多的学者对实时动态车辆的路径规划问题进行了研究［１｛］。

对于动态车辆路径的规划而言，动态性的描述不仅在于客户需求的变化，其一个重要的动态特点就是时间依赖性（ｔｉｍｅ－ｄｅｐｅｎｄｅｎｔＶＲＰ）。

它可描述为如下情况：

一个车队在指派车辆服务的所有节点中，以全部行驶时间最短为最优化条件。

但车辆在节点之间行驶的时间不是常量，而是依赖于每天不同的时间交通状况发生变化，即交通网络中弧段Ｌ（ｉ，』）的代价随时间不同而发生变化。

目前，对时间依赖路径规划（ＴＤＴＳＰ）问题的处理大致可以分为两类：

一类为两节点间的旅行时间依赖于一天中所处的具体时段，即把一天分为几个不同的时段，在不同的时段，任意两节点间的旅行时间不同，这种方式的计算相对简单［６］；另一类将弧（ｉ，歹）的旅行时间依赖于节点ｉ在哈密顿圈中所处的位置。

对这类问题，任意两个节点间的旅行时间为一时段，因此，在旅行过程中，不会涉及跨时段的问题‘７。

１０。

。

本文在文献［１１］的基础上提出了一种基于遗传算法的时相关动态路径

规划模型。

１

问题描述

本文考虑的是一个交通网络Ｇ一（ＮＵ｛Ｏ），

Ａ），Ｎ＝｛１，２，…，咒）是一组客户位置点，Ｏ是所有车辆的出发点，Ａ是网络边的集合；对于所有的边ｉ—ｊ；∈Ａ，％代表从节点ｉ到歹的行驶时间，它是随着时间和实际路况动态变化的。

每一个从节点ｉ到节点歹的客户的运货量为ｄｄ，如果从ｉ到Ｊ没有货物信息，则如一ｏ。

对于所有的Ｎ，客户的货运情况可由矩阵Ｄ＝｛也）表达，矩阵行表示取货节点，列表示收货节点，则∑如就表示所

Ｊ＝ｌ

＾

有从ｉ节点取的货物量，∑也表示所有运送到歹

ｉ＝ｌ

节点的货物量。

为简单起见，这里假设所有的节点都是简单的一个用户的取货节点和收货节点＜户，ｒ＞；。

在实际应用中，如果在同一个节点，既是取货点，又是收货点的复杂节点，则可将节点人为地拆分为两个简单节点。

在上述前提下，本文所提问题的解决目标是：

①任何时候，车辆装载不超过Ｋ的货物量；②取货节点必须在收货节点之前；③所有车辆必须在限定的时间内完成货物的运送。

收稿日期：

２００８一０６—１５．

硬目来源：

国家８６３计划资助项目（２００７ＡＡｌ２２３０９）；香港理工大学研究基金资助项目（ＧＹＥｌ３）．

８７６

武汉大学学报・信息科学版

２００８年８月

２

算法模型

动态路径规划算法可以被划分为初始路径规

划和动态更新两个阶段。

初始路径构造阶段，将预知的客户需求信息通过遗传算法全局寻优和路径内寻优后生成初始路径；动态更新阶段，首先执行初始路径，当有新的客户需求到达时，将新的客户需求动态插入已有路径中，同时通知车辆执行新的路径，循环等待新的客户需求到达，直至所有的客户需求都运送完成。

算法流程如图１所示。

初始路径构造动态路径更新

遗传算法令局寻优．

车辆执行规划路径，１．

直至货物运送完毕ｎ

改进启发式的随机Ｉ

最邻近搜索路径内优化

有新客户需求到达

是

ｌ

输ｍ初始优化结果｝＿一

动态更新路径

卜Ｊ

图１

动态路径规划算法流程

Ｆｉｇ．１

ＦｌｏｗＣｈａｒｔｏｆＤｙｎａｍｉｃＶｅｈｉｃｌｅＲｏｕｔｉｎｇ

２．１初始路径规划

２．１．１

遗传算法全局寻优

已有事实证明，利用遗传算法求解ＶＲＰ问题是比较成功的解决方案。

本文所解决的问题涉及多车辆、车辆载货量以及时变的道路交通信息、路径节点顺序必须满足取货节点在收货节点之前等限制条件，因此，利用遗传算法的全局优化必须要经过特殊的染色体编码处理。

模型的矩阵染色体编码模式为：

Ｄ＝

Ｄ，＝

Ｏ１０

０

０

２

Ｋ

‘．

Ｏ

矩阵Ｄ是货运情况，矩阵的行表示取货节点，列表示收货节点，也为货运量。

Ｄ中每一个ｄ。

！

一。

的位置就是染色体的基因，其值由运送

货物的车辆ＩＤ代替，每个基因用三元组形式表示

为＜Ｎｉ，Ｍ，Ｋ＞，Ｎｉ、Ｍ为取货节点和收货节点

编号，Ｋ为车辆编号。

在Ｄ。

矩阵中，ｄ。

：

由车辆１运送，ｄｊ由车辆Ｋ运送。

每一组Ｄ，就表示了一种可能的解决方案。

然而，这样的编码只能表达车辆经过了哪些节点，并不能表达某一车辆通过节点的次序关系，因此，在路径内采用与一般ＴＳＰ问题一致的编码，从左向右的节点序号表达一种可能的规划路径。

基因的交叉（ｃｒｏｓｓｏｖｅｒ）运算操作采用随机选择的方式。

首先，从选择池Ｌ条染色体中随机地选取一对矩阵染色体，为染色体中每个基因加编

序号（假设有挖个基因）。

然后随机产生一个常数Ｉ｝ｌ＜（竹＋１）／２，以＾和竹一＾位置分别为交换操作点，为了加速迭代的收敛，必须保证所选择的丘对基因有两对以上的值不同。

基因的突变（ｍｕｔａ—ｔｉｏｎ）是为了防止在寻优过程中陷入局部最优而将基因值转变为值域范围内的其他值。

对每一个染色体中的基因ｉ—ｌ，２，…，ｇ，给定一个突变概率值缸ｏ，１］，随机地选取一个矩阵染色体的基因ｉ，计算一个概率，若值在Ｏ～“内，则将其车辆编号变化为其他车辆，即由其他车辆来运送。

也就是说，每个基因突变的概率是“ｇ。

交叉和突变运算后，产生了一对新的染色体，计算新染色体的适应度函数，如果新染色体的适应度函数小于（优于）父染色体，则用新染色体取代旧染色体；反之，保留旧染色体。

矩阵染色体的适应度函数可以表示为每条经过内部寻优后的路径所花费的行驶时间之和，即

Ｉ

，＝∑Ｃ劬。

通过对每一代染色体进行交叉、突变

以及路径内寻优操作后，模型将更新记录每一代中的适应度函数最优的一组解决方案。

迭代过程将在进行一个给定的计算次数后停止。

２．１．２

ＴＤＴＳＰ路径内局部寻优

通过遗传算法的交叉和变异操作，可以确定

路径数和每条路径所包含的节点数。

在单条路径内，确定节点的次序问题就是ＴＳＰ，由于道路交通流量是变化的，因此，路径内局部优化就是ＴＤＴＳＰ问题。

为便于分析计算，Ｍａｌａｎｄｒａｋｉ等提出的时间分段策略一直是现有大多数研究所采用的方法。

该方法通过将一天划分为不同的时间段，而每一条弧段在同一时间段内的代价为一个固定的常数，从而将问题转化为相对静态的问题。

本文在这一分段策略的前提下，将一天划分为三个时段，同时为了便于更新计算，不考虑道路

Ｏ

～耵

ｄ２

磊Ｏ

Ｏ

０

第３３卷第８期唐健等：

基于遗传算法的时相关动态车辆路径规划模型

８７７

交通信息跨时段的变化。

由于本文所解决的问题包含有取货和收货节点区分的问题，因此，采用改进的启发式随机最邻近搜索（ｎｅａｒｅｓｔ—ｎｅｉｇｈｂｏｒｒａｎｄｏｍ）进行寻优。

具体算法描述如下：

①在给定的时间从出发点出发；②将当前最后一个节点到所有未访问节点的边按照权值大小升序排列。

从这一组边列表中，按照给定的概率分布随机选择一条边添加入路径中。

由于节点有取货节点和卸货节点的区分，随机选取节点也需考虑取货节点优先的原则；③重复步骤②，直到所有的节点被访问到或达到时间限制和载货量限制条件，返回出发节点；④重复步骤①～③Ｌ次，选择一条最佳的路径。

２．２动态更新过程

若有新的客户需求到达时，原有路径就需要被有效地重新优化。

假设新数据在￡时刻到达，为了重新优化路径，下面的基本信息是必须获取的：

①每辆车在￡时刻的位置和车辆未完成的节点；②￡时刻车辆的载货量情况。

若在时刻￡有一个新的订单到达，运货量为ｄ，系统首先为这个订单生成一个取货节点和一个卸货节点，用三元组表示为＜ｉ，ｊ，ｄ＞。

由于ＲＦＩＤ和ＧＰＳ技术的使用，模型系统根据实时获取当前车辆的载货量信息和实时位置信息，在初始路径规划结果的基础上，将新节点对插入原始路径。

在动态更新过程中，首先考虑将新的节点插入已存在的路径，检查所有车辆的当前位置，新的节点必须插入车辆位置之后。

检查每一种可能的插人情况，计算插入后对原路径的影响Ｊ—ｃｌ—ＣＤ，Ｇ为插入新节点后的路径行驶时间，Ｃｏ为原始路径行驶时间，取Ｊ最小的路径插入新节点。

若所有的新路径都无法插入，则要创建一条新路径。

３试验及分析

３．１路径初始化实例

为测试上述方法的有效性，本文利用生成的一组随机点数据分别进行了初始路径规划和动态更新的测试。

其中，节点产生的范围是在单位１的方形区域内，节点数设为，ｌ＝５０，车辆载货量为Ｋ＝１０，行驶速度设为单位１，因而车辆行驶时间可由几何距离表示。

取货节点和卸货节点由试验系统随机配对，运货量ｄ在１～１０之间随机生成。

一天的送货总时间限制Ａ设为４。

同时将Ａ分为３个均等的时间段，每个时间段内的车辆行驶时间由Ｏ～１随机产生，以表达变化的道路交通信

息。

在这些参数设置下，测试了多组数据，当遗传迭代终止代数设置为１ｏｏｏ时，进行的路径规划结果如图２所示。

重

督

酃妊增

次

图２

四组试验初始路径规划结果曲线图

Ｆｉｇ．２

Ｆ０ｕｒ

Ｐｈ胁ｕｌｔｓｂｙ“ｔｉａｌ

Ｒｏｕｔｅ

Ｃ０璐ｔｒｕｍｏｎ

图２中，Ａ、Ｂ、Ｃ、Ｄ四条曲线分别表示路径初始化算法在上述相同条件设置下重复４次寻优的过程曲线，横轴为寻优迭代次数，纵轴为寻优结果。

从图中可以看出，４次优化过程在迭代约５００次之前下降迅速，之后则趋于平稳，递减过程的单调性比较一致，表明该算法具有较好的稳定性。

在４次寻优结果中，最优结果为１５．００１６６８个单位，它比最坏的初始结果（２５．０１７１７４个单位）降低了约４０％，均值初始结果约降低了３５％。

在相同条件下，经过多次重复测试，寻优后的最终结果相对标准偏差小于３％，这表明初始路径寻优的解的质量是比较高的。

表１记录了在其他参数设置相同、节点规模变化的情况下，道路交通信息分段与不分段时经多次计算后所找到的均值最优解的对比。

表１

时间分段路径规划对比寰

Ｔａｂ．１

ＲｏｕｔｉｎｇＲｅｓｕｌｔｓｗｉｔｈａｎｄ

Ｗｉｔｈｏｕｔ

ＴｉｍｅＰｅｒｉｏｄ

从表１可知，交通时间分段后，所找到的均值最优解要比不分段时的解有一定程度的优化提高。

特别是当节点规模小于１００时，提高率超过１０％。

显然，已分段形式考虑了交通车流量的变化，在一定程度上可更好地体现真实的动态交通信息对道路优化结果的影响，从而降低物流成本。

３．２动态更新实例

假设Ｊ为一次测试实例，令Ｚ（Ｄ为静态路径的规划结果，Ｚ（Ｊ７）为动态更新后的结果，Ｚ（ｒ）为直接用静态方法规划计算的加入更新节点后的

８７８

武汉大学学报・信息科学版

２００８年８月

结果。

模型采用公式Ｒ＝（Ｚ（，）一Ｚ（ｆ。

））／Ｚ（，。

）＊１００％来表达模型更新的有效性。

Ｒ值越小，则更新的有效性越高。

如当ｎ＝５０、Ｋ＝１０时，初始路径规划的最优结果为Ｚ（Ｊ）＝１４．７８６；动态插入两对节点后，规划结果变为Ｚ（１７）一１６．１７８４５；将插入的两对节点加入原始结果进行初始优化，规划结果为Ｚ（ｒ）＝１５．４６８５，则Ｒ＝４．５８％。

表２是在节点数，ｌ＝５０、１００、２００和Ｋ＝１０、

２０、３０，更新节点Ｎｆ分别为２对、４对、６对时的一

组Ｒ值。

裹２动态更新结果分析衰

Ｔａｂ．２

ＡｎａＩｙｓｉｓＲｅｓｕＩｔｆｏｒＤｙｎａｍｉｃＵｐｄａｔｉｎｇ

Ｒ／％Ｎ，＝４

ＮＪ＝６

４．５８７．０８８．９０５．２５

９．ＯＯ３．９９

１．５５

０．５３

６．４５

７．４０９．２０１０．８０６．１５

９．２０

４．６９１．３６２．６０４．４９

９．５７

１１．２４

１２．１０

８．２８１１．８７

５．６５

３．６０

１．０１

Ｏ．５７

从表２结果可以看出，当节点数小于等于１００时，绝大部分的有效性（Ｒ值）都小于１０％，同时，Ｒ值随节点规模的增大而逐渐减小；当节点数咒和车辆载货量Ｋ相同时，随着动态插入节点数的增加，更新结果的Ｒ值又有所增加，表明模型在更新的节点数相对原始节点较少时，有效性比较高。

上述规律也是与实际情况相符的，动态更新只是局部更新，并非全局优化。

当动态插入的节点数增多时，对原先全局优化的路径冲击就会变大，有效性也会相应降低。

但总体上来说，本文所提出的动态更新机制在小规模的节点插人更新时，是具有较高的更新效率和有效性的。

４

结语

动态车辆路径规划是智能交通和商业物流领域中的一个重要研究方面，其最大的优点就是综合考虑了各种实时信息，及时优化更新配送车辆的行驶路径，从而进一步降低物流成本。

本文提出的遗传算法的初始优化和局部动态更新的方法同时解决了客户需求变化和交通信息变化两种动态因素同时影响下的路径规划问题。

试验结果表明，初始优化的稳定性和解的质量和动态更新的有效性均都有很大的改进。

该方法适合于现代通信技术和ＩＴＳ交通信息支持下的动态车辆管理。

同时，该方法也还有许多不足，特别是当动态插入的节点数比较多时，节点更新的有效性会下降，不适合问题规模比较小的情况。

对该问题的优化将是今后继续关注和研究的重点。

参考

文献

［１］

ＧｅｎｄｒｅａｕＭ，ＰｏｔｖｉｎＪＹ．ＤｙｎａｍｉｃＶｅｈｉｃｌｅＲｏｕｔｉｎｇ

ａｎｄ

Ｄｉｓｐａｔｃｈｉｎｇ［Ｃ］．ＦｌｅｅｔＭａｎａｇｅｍｅｎｔ

ａｎｄＬｏｇｉｓ—

ｔｉｃｓ，Ｋｌｕｗｅｒ，Ｂｏｓｔｏｎ，１９９８

［２］

Ｙａｌｌｇ

Ｊｉ锄，Ｊ枷ｅｔＰ，Ｍａｈｍａ黝面Ｈ．Ｒｅ小ｔｉｍｅ

Ｍｕｌ—

ｔｉｖｅｈｉｃｌｅ

１ｈｃｋｈｄ

ＰｉｃｋｕｐａＩｌｄＤｅｌｉｖｅｒｙ

Ｐｒｏｂｌｅｍｓ［Ｊ］．

１ｈｎｓｐｏｒｔａｔｉｏｎＳｄｅｎｃｅ．２００４（３８）：

１３５—１４８

［３］ＦａｂｒｉＡ，ＲｅｃｈｔＰ．０ｎＤｙｒｌａｍｉｃＰｉｃｋｕｐａｎｄＤｅｌｉＶｅｒｙＶｅｈｉｃｌｅＲｏｕｔｉｎｇｗｉｔｈ

ＳｅｖｅｒａｌＴｉｍｅＷｉｎｄｏｗｓａｎｄ

ｗａｉｔｉｎｇＴｉｍｅｓ［Ｊ］．

Ｔｒａｎｓｐｏｒｔａｔｉｏｎ

Ｒｅｓｅａｒｃｈ

Ｐａｒｔ

Ｂ，２００６（４０）：

３３５—３５０

［４］

ＦｌｅｉｓｃｈｍａｎｎＢ，ＧｎｕｔｚｍａｎｎＳ，ｓａｎｄｖｏｓｓ

Ｅ．

Ｄｙ一

尬ｍｉｃ

ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＢａｓｅｄ

ｏｎ

ＯｎｌｉｎｅＴｒａｆｆｉｃＩｎ—

ｆｏ兀ｎａｔｉｏｎ［Ｊ］．

Ｔｒａｎｓｐｏｒｔａｔｉｏｎ

Ｓｃｉｅｎｃｅ，２００４（３８）：

４２０一４３３

［５］李兵，郑四发，曹剑东，等．求解客户需求动态变

化的车辆路径规划方法［Ｊｌ交通运输工程学报，

２００７，７（１）：

１０６・１１０

［６］Ｍａｌａｎｄｒａｋｉｃ，ＤａｓｋｉｎＭｓ．Ｔｉｍｅ—ＤｅｐｅｎｄｅｎｔＶｅｈｉ—

ｃｌｅ

ＲｏｕｔｉｎｇＰｒｏｂｌｅｍｓ：

Ｆｏｒｍｕｌａｔｉｏｎｓ，

Ｐｒｏｐｅｒｔｉｅｓ，

ａｎｄＨｅｕｒｉｓｔｉｃ

Ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ

ｓｃｉ—

ｅｎｃｅ，１９９２（２６）：

１８５—２００

［７］

Ｐｉｃａｒｄ

ＪＣ，ＱｕｅｒｙｒａｎｎｅＭ．ＴｈｅＴｉｍｅ．Ｄｅｐｅｎｄｅｎｔ

ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍａｎｄＩｔｓＡｐｐｌｉｃａｔｉｏｎｔｏ

ｔｈｅＴａｒｄｉｎｅｓｓＰｒｏｂｌｅｍｉｎ

０ｎｅ—ＭａｃｈｉｎｅＳｃｈｅｄｕｌｉｎｇ

口］．０ｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，１９７８（２６）：

８６—１１０

［８］Ｆｏｘ

ＫＲ，ＧａｖｉｓｈＢ，Ｇｒａｖｅｓｓ

ｃ．Ａ矿ｃｏｎｓｔｒａｉｎｔ

Ｆｏｒｍｕｌａｔｉｏｎｏｆｔｈｅ

（Ｔｉｍｅ＿Ｄｅｐｅｎｄｅｎｔ）

Ｔｒａｖｅｌｉｎｇ

ｓａｌｅｓｍａｎ

Ｐｒｏｂｌｅｍ［Ｊ］．

０ｐｅｒａｔｉｏｎｓ

Ｒｅｓｅａｒｃｈ，１９８０

（２８）：

１０１８・１０２１

［９］

Ｌｕｃｅ∞Ａ．

Ｔｉｍｅ－ＤｅｐｅｎｄｅｎｔＴｍｖｅｌｉｎｇ

ｓａｌｅｓｍａｎ

Ｐｒｏｂｌｅｒｎ．ｔｈｅＤｅｌｉｖｅｒｙｍａｎｃａｓｅ［Ｊ］．Ｎｅｔｗｏｒｋｓ，１９９０

（１２０）：

７５３—７６３

［１０］ｗｉｅｌ

Ｒ

ＪＶ，ｓａｈｉｎｉｄｉｓＮＶ．ＨｅｕｒｉｓｔｉｃＢ０ｕｎｄｓａｎｄ

ＴｅｓｔＰｒｏｂｌｅｍＧｅｎｅｒａｔｉｏｎ

ｆｏｒｔｈｅＴｉｍｅ＿Ｄｅｐｅｎｄｅｎｔ

ＴｍｖｅｌｉｎｇＳａＩｅｓｍａｎＰｒｏｂｌｅｍ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ

Ｓｃｉｅｎｃｅ，１９９５（２９）：

１６７—１８３

［１１］Ｃｈｅｕｎｇ

ＢＫＳ，ＣｈｏｙＫＬ。

ＬｉＣＬ，ｅｔａ１．Ｄｙｎａｍｉｃ

Ｒｏｕｔｉｎｇ

ＭｏｄｅＩａｎｄＳｏｌｕｔｉｏｎ

Ｍｅｔｈｏｄｓ

ｆｏｒ

Ｆｌｅｅｔ

ＭａｎａｇｅｍｅｎｔｗｉｔｈＭｏｂｉＩｅＴｅｃｈｎｏｌｏｇｉｅｓ［Ｊ］．Ｉｎｔｅｌ’舱一

ｔｉｏｎａｌ

ＪｏｕｒｎａｌｏｆＰｒｏｄｕｃｔｉｏｎＥｃｏｎｏｍｉｃｓ，２００８，１１３

（２）：

６９４—７０５

第一作者简介：

唐键。

博士生。

研究方向为车载导航和路径规划。

Ｅ．ｎｕｉＩ：

ｔａｎｇｊｉａｎ—ｗｉｎ＠１６３．ｃｏｍ

趵∞加趵∞ｍ∞∞

∞∞∞瑚ｍ

ｍ枷猢枷

第３３卷第８期唐健等：

基于遗传算法的时相关动态车辆路径规划模型

８７９

Ｔｉｍｅ－ＤｅｐｅｎｄｅｎｔＤｙｎａｍｉｃＶｅｈｉｃｌｅＲｏｕｔｉｎｇＢａｓｅｄ

ｏｎ

ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ

ＴＡＮＧＪｉ口九１，２

ＳＨＩ１９矿Ｐ咒２ｈＤ咒９２

ＭＥ。

ＮＧ

Ｌｉ竹ｇ七甜ｉ１

（１

ＳｃｈｏｏｌｏｆＲｅｍｏｔｅＳｅｎ８ｉｎｇａｎｄ

ＩｎｆｏｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ

Ｕｎｉｖｅｒｓｉｔｙ，１２９Ｌｕｏｙｕ

Ｒｏａｄ，Ｗｕｈａｎ４３００７９．Ｃｈｉｌｌａ）

（２

Ｄｅｐａｒｔｍｅｎｔ

ｏｆ

ＬａｎｄＳｕｒｖｅｙｉｎｇａｎｄ

Ｇｅｏ＿Ｉｎｆｏｍａｔｉｃｓ，Ｔｈｅ

Ｈｏｎｇ

ＫｏＩｌｇＰｏｌｙｔｅｃｈｎｉｃ

ＵｎｉＶｅｒｓｉｔｙ，

ＨｕｎｇＨｏｍ，Ｋｏｗｌｏｏｎ，ＨｏｎｇＫｏＴ瑶）

Ａｂｓｔｒａｃｔ：

Ｄｙｎａｍｉｃｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｌａｙｓ

ａｎ

ｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｔｈｅｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎ

ａｎｄｌｏｇｉｓｔｉｃｓ．

ＡＵｋｉｎｄｓｏｆｒｅａｌ—ｔｉｍｅｉｎｆｏｒｍａｔｉｏｎｉｓｕｓｅｄｔｏｒｅ－ｏｐｔｉｍｉｚｅｔｈｅＶｅｈｉｃｌｅ

ｒｏｕｔｅ．

Ａ

ｄｙｎａｍｉｃｖｅｈｉｃｌｅｒｏｕｔｉｎｇｍｏｄｅｌｂａｓｅｄ

ｏｎ

ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ｔｉｍｅ－ｄｅｐｅｎｄｅｎｔｔｒａＶｅｌｉｎｆｏｒｍａｔｉｏｎ

ａｎｄｄｙｎａｍｉｃｃｕｓｔｏｍｒｅｑｕｅｓｔｓ，ｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅｎｅｗｍｏｄｅｌ

ｃａｎ

ａｃｈｉｅｖｅ

ａ

ｂｅｔｔｅｒｒｅ＿ｏｐｔｉｍｉｚｉｎｇ

ｒｅｓｕｌｔ．

Ｋｅｙｗｏｒｄｓ：

ｄｙｎａｍｉｃｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｌａｎ；ｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍ；ｌｏｇｉｓｔｉｃｓ；ｇｅｎｅｔ—ｉｃａｌｇｏｒｉｔｈｍ；ｔｉｍｅ．ｄｅｐｅｎｄｅｎｔ

Ａｂｏ吡ｔ雠ｎｒ砒加ｔ－ｌ钾：

ＴＡＮＧＪＩ锄，Ｐｈ．Ｄ∞旷一ｉ凼Ｉｔｅ，ｍａｊｏｒｓ虮ＶｅｈｊｃＩｅｎ甜ｉｇａｔｉ∞ａｎｄｒｏｕ忙ｐＩ卸

Ｅ帕¨：

协ｎｇｊｉ绷—ｗｉｎ＠１６３．∞ｍ

－＋—－＋——＋—＿．—－■——●——＋——卜——卜・．．——■—－■—・＿．—呻・■——■—－■・—■－－——・＋—■—・＋・■——■—－．．—－■－—■－・—－・■——●——＋——●—＿．—・■—・—－—■—－●——＋——＋—一．－－■——■——■—・■—・——・■—－＋（上接第８７４页）

Ｍｕｌｔｉｍｅｄｉａ

Ｃｏ儿ｅｃｔｉｏｎａｎｄＭａｎａｇｅｍｅｎｔＴｅｃｈｎｏｌｏｇｙＢａｓｅｄ

ｏｎ

ＧＰＳ

’矿ＵＣ口ｉｆｏ，ｌｇ１

ｙＡＮＧＦｚ巧ｉｎ咒ｇ２

ＷＵＹｈ＾口咒ｇ１

ＧＥ＾，Ｇ．，ｉ口ｚ＾ｏ“１

（１

Ｉｎｓｔｉｔｕｔｅ

ｏｆＲｅｍｏｔｅ

ｓｅｎｓｉｎｇａｎｄＧＩＳ，Ｐｅｋｉｎｇ

Ｕｎｉｖｅｒｓｉｔｙ，５

Ｓｕ胁ｅｒ

ＰａｌａｃｅＲｏａｄ，Ｂｅ幻ｉｎｇ

１００８７１，Ｃｌｌｉ眦）

（２

８５２

ＦａｍｏｆＨｅｉｌｏｎｇｊｉａＩＩｇ

Ｐｒｏｖｉｎｃｅ，．４５Ｃｅｎｔｒａｌｓｔｒ∞ｔ，Ｂａｏｑｉｎｇ１５５６２０，Ｃｈｉ舱）

Ａｂｓｔｍｃｔ：

ＡｋｉｎｄｏｆｃｏＩｌｅｃｔｉｎｇ，ｐｏｓｉｔｉｏｎｉｎｇａｎｄｍａｎａｇｉｎｇｓ０１ｕｔｉｏｎ

ｔｏ

ｍｕｌｔｉｍｅｄｉａｂａｓｅｄ

ｏｎｏｒ—

ｄｉｎａｒｙｄｉｇｉｔａｌｃａｍｅｒａ，ＧＰＳｄａｔａｒｅｃｏｒｄｄｅＶｉｃｅ，ａｎｄＧＩＳｃｏｍｐｏｎｅｎｔａｎｄｉｔｓｄｅｍｏｎｓｔｒａｔｉｏｎ

ｓｏｆｔｗａｒｅｓｙｓｔｅｍｉｓｐｒｏｐｏｓｅｄ．

Ｔｈｅｓｏｌｕｔｉｏｎｍａｋｅｓ

ｕｓｅ

ｏｆｐｏｓｔ—ｐｒｏｃｅｓｓｉｎｇｍｅｔｈｏｄ

ｔｏ

ｃａｌｉｂｒａｔｅ

ａｎｄｍａｔｃｈｔｈｅｄａｔｅａｎｄｔｉｍｅｂｅｔｗ亡ｅｎｄｉｇｉｔａｌｃａｍｅｒａａｎｄＧＰＳｄｅｖｉｃｅｉｎｏｒｄｅｒｔｏｇｅｔｔｈｅｐｏｓｉ—ｔｉｏｎｏｆｔｈｅｍｕｌｔｉｍｅｄｉａｗｈｅｒｅｉｔｉｓｃｏｌｌｅｃｔｅｄ．ＴｈｅｍｕｌｔｉｍｅｄｉａｉｓｄｉｓｐｌａｙｅｄａｎｄｍａｎａｇｅｄｂｙＧＩＳ

ｐｌａｔｆｏｒｍ，ｗｈｉｃｈｉｓ

ｅａｓｙ

ｔｏ

ｍａｋｅｓｐａｔｉａｌ

ａｎａｌｙｓｉｓｆｏｒｔｈｅ

ｕｓｅｒｓ．

Ｔｈｉｓｓｏｌｕｔｉｏｎｉｓｈｅｌｐｆｕｌ

ｔｏ

ｍｏｓｔｏｆｄｉｇｉｔａｌｃａｍｅｒａ

ｕｓｅｒｓ

ｔｏ

ｌｏｃａｔｅｔｈｅｍｕｌｔｉｍｅｄｉａ’ｓｐｏｓｉｔｉｏｎｗｉｔｈｏｕｔｉｎｃｒｅａｓｉｎｇｄｅＶｉｃｅ

ｃｏｓｔ

ｔｏ

ａ

ｌａｒｇｅｅｘｔｅｎｔ．

Ｋｅｙｗｏｒｄｓ：

ＧＰＳ；ｍｕｌｔｉｍｅｄｉａ；ｃｏｌｌｅｃｔｉｏｎ；ｐｏｓｉｔｉｏｎｉｎｇ；ｍａｎａｇｅｍｅｎｔ

Ａｂｏ吡ｔｈｅ

ｎｒ吼蛐恤盯ｌＶ灿Ｃ日ｉ∞叼，Ｉ∞ｔｕ怕ｒ，Ｐｈ．Ｄ．ＨＩｓ

ｉｎｔｅｒｅ啪ｄ

ｆｉｅＩｄ

ｉｓ∞ｒｉ伽¨ｕｒａＩ

ＶＲＳａｎｄＬＢＳ

Ｅ椭ＩＩ：

ｗ∞ｃ＠ｐＩ‘ｕ．ｅｄｕ．伽