基于一种特设启发式算法的车辆优化调度问题研究

ｎｅｅｒｉｎｇꎬ２０１９ꎬ４３(４):１－５.

ＨＥＭＪꎬＺＥＮＧＬＳ.Ｒｅｓｅａｒｃｈｏｎｖｅｈｉｃｌｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｂａｓｅｄｏｎａｓｐｅｃｉａｌｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ[Ｊ].Ｖｉｄｅｏｅｎｇｉ￣

中图分类号:ＴＰ３９９　　　　文献标志码:Ａ　　　　ＤＯＩ:１０.１６２８０/ｊ.ｖｉｄｅｏｅ.２０１９.０４.００１

基于一种特设启发式算法的车辆优化调度问题研究

何曼洁ꎬ曾连荪

(上海海事大学ꎬ上海　２０１３０６)

摘要:建立数学模型将最小车辆规模问题转化为车辆共享网络的精确表述ꎬ设计行程共享网络ꎬ通过结合了Ｅｄｍｏｎｄ匹配算法ꎬＤｉｊｋｓｔｒａ算法等经典算法的特设启发式算法解决共享网络的最大匹配和最优路径问题ꎬ进一步揭示车辆共享网络的结构特性ꎬ通过推导计算效率较高的优化车辆部署和调度算法以最优地解决最小车辆规模问题ꎮ用ｍａｔｌａｂ仿真ꎬ得出最佳参数Δꎬｋ的特设启发式算法ꎬ并进一步证明了该算法通过行程组合ꎬ减少了行程数量ꎬ进一步减少了车辆的需求ꎬ进而实现减少交通拥堵和环境污染的目标ꎮ关键词:启发式算法ꎻ共享网络ꎻ车辆调度

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

(ＳｈａｎｇｈａｉＭａｒｉｔｉｍｅＵｎｉｖｅｒｓｉｔｙꎬＳｈａｎｇｈａｉ２０１３０６ꎬＣｈｉｎａ)

ＨＥＭａｎｊｉｅꎬＺＥＮＧＬｉａｎｓｕｎ

Ａｂｓｔｒａｃｔ:Ｅｓｔａｂｌｉｓｈｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｓｔｏｔｒａｎｓｌａｔｅｔｈｅｍｉｎｉｍｕｍｖｅｈｉｃｌｅｓｉｚｅｐｒｏｂｌｅｍｉｎｔｏａｎａｃｃｕｒａｔｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｔｈｅｖｅｈｉ￣ｃｌｅ'ｓｓｈａｒｅｄｎｅｔｗｏｒｋ.ＤｅｓｉｇｎｔｈｅｉｔｉｎｅｒａｒｙｓｈａｒｉｎｇｎｅｔｗｏｒｋꎬａｎｄｃｏｍｂｉｎｅｔｈｅＥｄｍｏｎｄｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍꎬｔｈｅＤｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍａｎｄｏｔｈｅｒｃｌａｓｓｉｃａｌａｌｇｏｒｉｔｈｍｓｔｏｓｏｌｖｅｔｈｅｍａｘｉｍｕｍｍａｔｃｈｉｎｇａｎｄｏｐｔｉｍａｌｐａｔｈｐｒｏｂｌｅｍｏｆｔｈｅｓｈａｒｅｄｎｅｔｗｏｒｋꎬａｎｄｆｕｒｔｈｅｒｒｅｖｅａｌｔｈｅｓｔｒｕｃｔｕｒａｌｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｖｅｈｉｃｌｅｓｈａｒｅｄｎｅｔｗｏｒｋ.ＯｐｔｉｍｉｚｅｖｅｈｉｃｌｅｄｅｐｌｏｙｍｅｎｔａｎｄｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓｗｉｔｈｈｉｇｈｅｒｔｈｅｏｐｔｉｍａｌｐａｒａｍｅｔｅｒｓΔꎬｋｉｓｏｂｔａｉｎｅｄꎬａｎｄｉｔｉｓｆｕｒｔｈｅｒｐｒｏｖｅｄｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｒｅｄｕｃｅｓｔｈｅｎｕｍｂｅｒｏｆｓｔｒｏｋｅｓｔｈｒｏｕｇｈｔｈｅｓｔｒｏｋｅｌｕｔｉｏｎ.

ｃｏｍｂｉｎａｔｉｏｎꎬｆｕｒｔｈｅｒｒｅｄｕｃｅｓｔｈｅｄｅｍａｎｄｏｆｔｈｅｖｅｈｉｃｌｅꎬａｎｄａｃｈｉｅｖｅｓｔｈｅｇｏａｌｏｆｒｅｄｕｃｉｎｇｔｒａｆｆｉｃｃｏｎｇｅｓｔｉｏｎａｎｄｅｎｖｉｒｏｎｍｅｎｔａｌｐｏｌ￣Ｋｅｙｗｏｒｄｓ:ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍꎻｓｈａｒｅｄｎｅｔｗｏｒｋꎻｖｅｈｉｃｌｅｓｃｈｅｄｕｌｉｎｇ

ｃｏｍｐｕｔａｔｉｏｎａｌｅｆｆｉｃｉｅｎｃｙｔｏｏｐｔｉｍａｌｌｙａｄｄｒｅｓｓｍｉｎｉｍｕｍｖｅｈｉｃｌｅｓｉｚｅｉｓｓｕｅｓ.Ｓｉｍｕｌａｔｅｄｗｉｔｈｍａｔｌａｂꎬｔｈｅｓｐｅｃｉａｌｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｏｆ

　　当今社会的经济飞速发展ꎬ车辆数量与日俱增ꎬ由此产生的交通拥堵和环境污染成为城市交通的主要问题ꎬ因而车辆优化调度问题的重要性日益突出ꎮ国内外文献涉及此类问题的研究很多ꎬ如采用禁忌搜索算法[１]ꎬ通过与周围节点值的比较ꎬ不断迭代更新ꎬ替换当前节点值ꎬ进而实现找到局部最优解的目标ꎻ以遗传算法[２ꎬ３]为核心的多种改进及混合算法[４]ꎬ通过将发车时间排序问题转化为多目标优化问题ꎬ进一步实现了最优路径选择和乘客利益等多目标优化ꎻ以及改进节约算法等其他算以及ＬａｐｏｒｔｅＧ[７]提出的车辆路径的近似算法等ꎬ通法[５]ꎮ国外研究中ꎬ如ＢｅｒｂｅｇｌｉａＧ[６]的动态模型ꎬ

过启发式算法或其他数学模型ꎬ设计了以乘车等待时间ꎬ发车频率等为目标函数的优化模型[８ꎬ９]ꎮ纵观以上各种研究方法ꎬ大多适用于小规模或特定区域ꎬ固定路线的车辆ꎬ解决客户少、道路网络相对简单的问题ꎬ且缺乏对实时动态客流的考虑ꎬ难以对大量数据产生实际效果ꎮ

本文通过建立乘车共享系统ꎬ对共享行程次数ꎬ乘客服务质量ꎬ行程时间等多方面因素进行了综合考虑ꎬ通过可共享网络的方法ꎬ将时空共享问题转化为一个提供有效解决方案的图论框架ꎮ研究如何将这种车辆共享网络转化为有向图上的最小路径覆盖问题ꎬ以实现车辆规模的减少ꎬ从而有

投稿网址ｈｔｔｐ:∕∕ｗｗｗ.ｖｉｄｅｏｅ.ｃｎ｜«电视技术»第４３卷第４期(总第５１３期)

　１

效解决交通拥堵问题ꎬ进一步减轻污染排放的问题ꎮ

１　特设启发式算法模型

１.１　模型假设

本文考虑通过组合行程请求而进行车辆调度ꎬ为了构建数学模型ꎬ作如下基本假设ꎮ

(１)数据集包括车辆ＩＤꎬ起点时间ｔｏｉꎬ目的地(２)行程ｉ和行程ｊ的连接时间ｔｉｊ上限为参(３)由于数据集只包括载客车辆的行程ꎬ因此(４)假设每次行程请求为单人乘客ꎻ

(５)数据来自ｏｐｅｎｓｔｒｅｅｔｍａｐ.ｏｒｇꎬ以及Ｕｂｅｒ

图２　行程最大匹配示意图

ｏｄ

时间ｔｄｉꎬ起点位置ｌｉꎬ目的地位置ｌｉꎮ时间精确到

图１　行程路径自由组合示意图

秒ꎬ位置信息由ＧＰＳ点表示ꎻ数δꎻ

模型不处理空行程ꎻ

１.２　模型建立

Ｍｏｖｅｍｅｎｔ的开源数据集ꎮ

为了在满足同样数量的行程请求的情况下所调用的车辆数量最少ꎬ以达到减轻交通拥堵及环境污染的目标ꎬ现将最少车辆问题转化为共享网络上的路径覆盖问题ꎬ从而转化为二部图最大匹配问题ꎮ设有向网络Ｓ＝(ＴꎬＬ)为行程可共享网络ꎬ其中行程Ｔｉ对应图上节点ꎬ连接节点的有向线段对应行程组合ꎬ即:

组合行程ＴｉꎬＴｊ取决于两次行程的空间/时间属性ꎬ１.２.１　计算最小数量行程合ꎬ算法过程见２.１ꎮ

所有组合行程Ｔｉꎬｊ的集合ꎬＴ１∪Ｔ２＝Ｔꎬｉꎬｊ∈{１ꎬ􀆺ꎬｎ}ꎮ

定义２:Ｓ上的匹配是一组链路Ｌ′⊆Ｌꎬ使得定义１:Ｔ１∈Ｔ为所有单次行程的集合ꎬＴ２为并且取决于两次行程连接的最大延迟Δ(时间窗)ꎮ

用最大匹配算法找到最小行程数量的行程集

{

Ｔｉ∈Ｔꎬ行程请求集合Ｔ

(Ｔ

ｉ

下面以少量的节点为例ꎬ演示如何将车辆数量最少问题转化为路径匹配问题ꎮ如图１所示ꎬ节点表示行程请求ꎬ连接节点的有向线段为行程的一次组合ꎬ连接多个节点的有向线段为一条路径ꎬ要求每个节点至少在一条路径中ꎬ且连接时间上限为δꎬ利用Ｅｄｍｏｎｄ[１０]算法ꎬ找出满足以上条件的最少路径(最大匹配)ꎬ得出图２中的四条路径ꎮ即表示多个行程请求可以由一辆车服务ꎬ因此图１、图２中的行程请求(节点)最少可由四辆车服务ꎬ即将车辆数量最少问题转化为路径匹配问题ꎮ

络ꎬ其中Ｔ＝{Ｔ１ꎬ􀆺ꎬＴｎ}为节点集ꎬ对应于所有可能的ｎ次行程请求的集合ꎮＬ＝{Ｌ１ꎬ􀆺ꎬＬｎ}为链路集ꎬ链路(ＴｉꎬＴｊ)∈Ｌ连接节点Ｔｉ和Ｔｊꎬ行程Ｔｉ和Ｔｊ组合后获得的行程在下面表示为Ｔｉꎬｊꎮ是否可以

进一步ꎬ定义有向网络Ｓ＝(ＴꎬＬ)为共享网

ꎬＴｊ

)∈ｄ

Ｌꎬ当且仅当ｔｏｊ－ｔｉ≤δ

(１)

Ｌ′中任意两个链路端点不交叉ꎬ即为Ｓ的最大匹配ＭｍａｘꎮＳ上的最大匹配即指Ｓ的最大基数匹配ꎬ若Ｓ中的链路被加权ꎬ则Ｓ上的最大加权匹配是使得Ｌ′中的链路权重之和最大的匹配ꎮ程集Ｔ的最小基数为ｎ－｜Ｍｍａｘ｜ꎮ

引理１:若Ｍｍａｘ是Ｓ上的最大匹配ꎬ则可组合行证明:所有行程请求的次数为ｎꎬ匹配Ｍ对应

Ｔ２ꎬ所以Ｔ２中的组合行程个数为Ｍ的基数｜Ｍ｜ꎬ∵

Ｔ１∪Ｔ２＝Ｔꎬ∴Ｔ的基数为ｎ－｜Ｍ｜ꎮ当Ｍ为最大匹配Ｍｍａｘ时ꎬ即Ｍ的基数最大ꎬ为Ｍｍａｘꎬ∴此时Ｔ１.２.２　计算行程最小成本合ꎬ算法过程见２.２ꎮ的基数最小ꎬ为ｎ－｜Ｍｍａｘ｜ꎮ

用最大加权匹配算法找到最小成本的行程集

　２

«电视技术»第４３卷第４期(总第５１３期)｜投稿网址ｈｔｔｐ:∕∕ｗｗｗ.ｖｉｄｅｏｅ.ｃｎ

定义３:设加权可共享网络为Ｓ＝(ＴꎬＬ)ꎬ其中每个链路(ＴｉꎬＴｊ)∈Ｌ用Ｃｉｊ＝Ｃ(Ｔｉ)＋Ｃ(Ｔｊ)－Ｃ(Ｔｉꎬｊ)表示组合行程Ｔｉꎬｊ的成本ꎮ

Ｃ(Ｔｉꎬｊ)加权ꎬ其中Ｃ(Ｔｘ)表示行程Ｔｘ的成本ꎬ

引理２:若Ｍｊｍａｘ是Ｓ上的最大匹配ꎬＳ按定义３Ｃ(Ｔｉ)－

要的时间复杂度为Ｏ(１)ꎮ

ｏ

ｔｏｉ≤ｈｔｉ≤ｔｉ＋Δ

ｏｏｏｔｏｊ≤ｈｔｉ＋ｔｔ(ｌｉꎬｌｊ)≤ｔｊ＋Δ

ｏ

(ｏｄ)≤ｔｄｈｔｉ＋ｔｔ(ｌｏｉꎬｌｊ)＋ｔｔｌｊꎬｌｉｉ＋Δ

(１０)(１１)

(９)

中所述加权ꎬ则最小总行程成本为:Ｃｍｉｎ＝

ｉ＝１ꎬ􀆺ꎬｎ

ｏ

(ｏｄ)＋ｔｔ(ｌｄꎬｌｄ)≤ｔｄｈｔｉ＋ｔｔ(ｌｏｉꎬｌｊ)＋ｔｔｌｊꎬｌｉｊ＋Δｉｊ

∑

相对于单次行程ＴｉꎬＴｊꎬ组合行程Ｔｉꎬｊ的成本降低了Ｃ(Ｔ)＋

ｉ

证明:∵匹配Ｍ对应Ｔ２ꎬ对于Ｔ２(ＴｉꎬＴｊ)∈ＭꎬＣ(Ｔ)－

ｉ＝１ꎬ􀆺ꎬｎ

ｊ

(ＴｉꎬＴｊ)∈Ｍｊｍａｘ

∑

Ｃ(Ｔｉ)＋Ｃ(Ｔｊ)－Ｃ(Ｔｉꎬｊ)

可以类似地验证其他路线的可行性条件ꎮ如果存在至少一条路径满足可行性条件ꎬ则行程ＴｉꎬＴｊ是可组合的ꎬ否则不能组合ꎮ∴对于所有可组合的行程对建立共享网络Ｓ＝(ＴꎬＬ)需要Ｏ(ｎ２)的时间复杂度ꎮ

定义５:基于实际地图数据ꎬ定义街道交叉点集合Ｌꎬ起点用地图上交叉点表示为Ｉｉꎬ目的地为Ｉｊꎬ其中ＩｉꎬＩｊ∈Ｌꎬ所有起点为Ｉｉꎬ目的地为Ｉｊ的行程集合表示为Ｔｉꎬｊꎬ连接交叉点的街道段集合表示为Ｈ＝{ｈ１ꎬ􀆺ꎬｈ２}ꎮ

ｏｄｄ

定义６:当且仅当(ｌｏｕ＝ｌｖ)∧(ｌｕ＝ｌｖ)的时

(１２)

的总成本Ｃ(Ｔｉꎬｊ)＝

∑

Ｃ(Ｔ

ｉꎬｊ

)

Ｃ(Ｔｉ)减去

ꎬ因此Ｔ的总成本由单次行程

(ＴｉꎬＴｊ)∈Ｍｊｍａｘ

节省的总和最大化ꎬ∴Ｔ的总成本最小化ꎮ１.２.３　估算行程时间

对任意起点和目的地之间的行程时间的估计

(ＴｉꎬＴｊ)∈Ｍｊｍａｘ

∑

Ｃｉｊꎬ∵是最大匹配Ｍｊｍａｘꎬ则成本

∑

Ｃ(Ｔｉ)＋Ｃ(Ｔｊ)－

是判断行程是否可以共享的先决条件ꎬ算法过程见２.３ꎮ

定义４:ｈｔｘ为组合行程到达起点ｌｏｉ的时间ꎬｄｔｘ

候ꎬ两次行程Ｔｕ和Ｔｖ是等价的ꎮ

为组合行程到达目的地ｌｄｉ的时间ꎬ当且仅当可以找到行程路线以满足以下条件时ꎬ可以组合行程Ｔｉ和Ｔｊ:

ｏ

ｔｏｉ≤ｈｔｉ≤ｔｉ＋Δ

独立地执行行程时间估计过程ꎬ从起点到目的地的最佳路线包括的街道集合对于任何两个行程ＴｕꎬＴｖ∈Ｔｉꎬｊ是相同的ꎬ因此等价类Ｔｉꎬｊ中的所有行程可被视为同一组街道上的行程时间的多个样本ꎮ然后用单次行程Ｔｉꎬｊ替换Ｔｉꎬｊ中的所有具有相同起点和目的地的行程ꎬ行程时间取Ｔｉꎬｊ中所有行程时间的平均值`ｔｔｉꎬｊꎬ对所有等价类执行次操作ꎬ结果定义为集合Ｔａｇｇꎮ

将Ｔ重新划分为为子集Ｔｉꎬ在每个行程子集上

ｔ≤ｈｔｊ≤ｔ＋Δｄｔｉ≤ｔ＋Δｄｔｊ≤ｔｄｊ＋Δ

ｄ

ｉ

ｏｊ

ｏｊ

(２)(３)(４)(５)

条件可以在时间复杂度Ｏ(１)[１１]中验证如下:

ｏｉ

ｏｊ

ｄｉ

ｄｊ

ｏｉ

ｏｊ

ｄｊ

对于每对行程对ＴｉꎬＴｊꎬ组合行程Ｔｉꎬｊ的可行性∵出发位置一定在目的地前ꎬ∴行程Ｔｉꎬｊ可能

ｄｉ

ｏｊ

ｄｉ

ｄｊ

ｏｊ

ｏｉ

ｄｊ

ｄｉ

ｏｉ

ｏｊ

ｄｉ

２　算法实现

的路线为:ｌ→ｌ→ｌ→ｌꎬｌ→ｌ→ｌ→ｌꎬｌ→ｌ→ｌ→ｌꎬｌ→ｌ→ｌ→ｌꎮ以路线ｌ→ｌ→ｌ

ｏｉ

ｄｊ

ｏｉ

ｏｊ

ｏｉ

ｏｊ

２.１　最大匹配算法

Ｉｎｐｕｔ:可共享网络Ｓ＝(ＴꎬＬ)ｏｕｔｐｕｔ:最小行程数量行程集ＴＴ＝Ｔꎻ//初始化

→ｌ为例ꎬ设ｔｔ(ｌꎬｌ)表示ｌ和ｌ之间的行程时间ꎬ则:

ｈｔｊ＝ｈｔｉ＋ｔｔ(ｌꎬｌ)

ｏｉ

ｏｊ

ｄｔｉ＝ｈｔｊ＋ｔｔ(ｌꎬｌ

ｏｊ

ｄ)ｄｔｊ＝ｄｔｉ＋ｔｔ(ｌｄｉꎬｌｊ

ｄｉ

)

(６)(７)(８)

用Ｅｄｍｏｎｄ匹配算法找出最大匹配Ｍｍａｘꎻ

{ＴｉꎬＴｊ}//Ｔ中只保留组合行程ꎬ移除单次行程Ｔｉꎬ２.２　最大加权匹配算法Ｔｊ返回Ｔꎮ

(ＴｉꎬＴｊ)∈Ｍｍａｘꎬ令Ｔ＝Ｔ∪{Ｔｉꎬｊ}ꎬＴ＝Ｔ－

将等式(６)~(８)代入(２)~(５)ꎬ得到条件(９)

ｏｄｄ

是否存在来验证路径ｌｏｉ→ｌｊ→ｌｉ→ｌｊ是否可行ꎬ需

~(１２)ꎬ通过检验同时满足以下四个条件的ｈｔｉ值

Ｉｎｐｕｔ:可共享网络Ｓ＝(ＴꎬＬ)ｏｕｔｐｕｔ:最小行程成本行程集Ｔ

投稿网址ｈｔｔｐ:∕∕ｗｗｗ.ｖｉｄｅｏｅ.ｃｎ｜«电视技术»第４３卷第４期(总第５１３期)

　３

Ｔ＝Ｔꎻ//初始化加权ꎻ

(ＴｉꎬＴｊ)∈Ｌ用Ｃｉｊ＝Ｃ(Ｔｉ)＋Ｃ(Ｔｊ)－Ｃ(Ｔｉꎬｊ)

ＲｅｌＥｒｒ＝

程的平均相对误差之和ꎻ

Ｓ∈Ｓｔꎬ令ＴＳ＝{Ｔｉꎬｊ∈Ｔａｇｇ｜Ｓ∈Ｓｉꎬｊ}ꎻｔｔｉꎬｊ).｜Ｔｉꎬｊ｜ꎻ

Ｋ＝１.２ꎻ

Ｓ∈Ｓｔꎬ计算偏移量ＯＳ＝

∑Ｔ

ｉꎬｊ∈Ｔａｇｇ

｜ｅｔｉꎬｊ－ｔｔｉꎬｊ｜

//计算所有行

ｔｔｉꎬｊ

用Ｅｄｍｏｎｄ算法找出最大匹配Ｍｍａｘꎻ

{ＴｉꎬＴｊ}ꎻ//让Ｔ中只保留组合行程ꎬ移除单次行程２.３　行程时间估计算法

ｄ

对Ｔｉꎬｊ中任意行程Ｔｕꎬ令ｌｏｕ＝Ｉｉꎬｌｕ＝Ｉｊꎻｄ对等价类Ｔｉꎬｊ中的行程用ｌｏｕ＝Ｉｉꎬｌｕ＝Ｉｊ的单

(ＴｉꎬＴｊ)∈Ｍｍａｘꎬ令Ｔ＝Ｔ∪{Ｔｉꎬｊ}ꎬＴ＝Ｔ－

∑Ｔ

ｉꎬｊ∈ＴＳ

(ｅｔｉꎬｊ－

ＴｉꎬＴｊ返回Ｔꎮ

ｗｈｉｌｅｔｒｕｅｄｏ//内部迭代ꎻ

Ｓ∈ＳｔꎬｉｆＯＳ<０ꎬｔＳ＝ｋ􀅰ｔＳꎻｅｌｓｅｔＳ＝Ｔｉꎬｊ∈Ｔａｇｇꎬｅｔ′ｉꎬｊ＝

次行程Ｔｉꎬｊ置换ꎻ

令ｔｔｉꎬｊ＝`ｔｔｉꎬｊ＝

Ｔｕ∈Ｔｉꎬｊ

∑ｔｔｕ

Ｔｉꎬｊ

ꎻ

ＮｅｗＲｅｌＥｒｒ＝均相对误差ꎻｅｔ′ｉꎬｊꎻ

∑Ｔ

∑Ｓ∈Ｓ

ｔＳ

ꎻｋ

ｉꎬｊ

ｉꎬｊ∈Ｔａｇｇ

｜ｅｔ′ｉꎬｊ－ｔｔｉꎬｊ｜

//更新平

ｔｔｉꎬｊ

Ｔｉꎬｊ∈Ｔａｇｇꎬｅｔｉꎬｊ＝

ｔＳꎻ

返回Ｔｉꎬｊ的集合Ｔａｇｇꎻ

Ｔｉꎬｊ∈Ｔａｇｇꎬ若ｉ＝ｊꎬ从Ｔａｇｇ中移除Ｔｉꎬｊꎻ

ＩｆＮｅｗＲｅｌＥｒｒ<ＲｅｌＥｒｒꎬＲｅｌＥｒｒ＝ＮｅｗＲｅｌＥｒｒꎻ

Ｔａｇｇ中移除Ｔｉꎬｊ//过滤掉重复的行程和过长/短的行程ꎻ

Ｓｉ∈Ｓꎬ设相同的初速度ｖｉｎｔꎬ行程时间ｔＳ＝Ｔｉꎬｊ∈Ｔａｇｇꎬ用Ｄｉｊｋｓｔｒａ算法计算Ｉｉ、Ｉｊ之间的

Ｔｉꎬｊ∈Ｔａｇｇꎬ若`ｔｔｉꎬｊ<２ｍｉｎꎬ或`ｔｔｉꎬｊ>１ｈꎬ从

ａｇａｉｎ＝ｔｒｕｅꎬ返回外部迭代ꎻｅｌｓｅｋ＝１＋(ｋ－１)􀅰０.７５ꎻｅｌｓｅ返回内部迭代ＳＳ＝Ｓ－Ｓｔꎻ

ｉｆｋ<１.０００１ꎬ从内部迭代退出ꎻ

设Ｎ(Ｓ)为与街道Ｓ共用交叉点的街道集合ꎬＳｉ∈ＳＳꎬ计算ｎＳｉ＝｜Ｎ(Ｓｉ)∩Ｓｔ｜ꎻ

Ｌ(Ｓ)

ꎻｖＳ

最佳路线ꎻ

佳路线的街道集合ꎻ

ｉꎬｊ

Ｔｉꎬｊ∈Ｔａｇｇꎬ设Ｓｉꎬｊ＝{Ｓ１ꎬ􀆺ꎬＳｉｋꎬｊ}为构成最

按ｎＳｉ降序排列ＳＳ中的街道ꎻＳｉ∈ＳＳꎬｖＳｉ＝

∑ｈＬ(Ｓ

ｔｔｉꎬｊ

Ｔｉꎬｊ∈Ｔａｇｇꎬ计算平均速度ａｓｉꎬｊ

ｉꎬｊｈ

)

＝

３０ｍ/ｓｅｃꎬ从集合Ｔａｇｇ中移除Ｔｉꎬｊ//过滤过快/慢的行程ꎻ

ｓｅｔａｇａｉｎ＝ｔｒｕｅꎻａｇａｉｎ＝ｆａｌｓｅ

Ｔｉꎬｊ∈Ｔａｇｇꎬ若ａｓｉꎬｊ<０.５ｍ/ｓｅｃꎬ或ａｓｉꎬｊ>

ꎻ

Ｓｔ＝Ｓｔ∪{Ｓｉ}ꎻＳＳ＝ＳＳ－{Ｓｉ}ꎻ

重复以上步骤直到ＳＳ＝øꎻＥＴ(ｉꎬｊ)＝ＥＴꎮ

｜Ｎ(Ｓｉ)∩Ｓｔ｜

∑Ｓ∈Ｎ(Ｓ)∩Ｓ

ｊ

ｉ

ｔ

ｖＳｊ

ꎻｔＳｉ＝

Ｌ(Ｓｉ)

ꎻｖＳｉ

∑Ｓ∈Ｓ

ｈ

ｉꎬｊ

Ｌ(Ｓ)

//输出时间估计矩阵ＶＳ

ｗｈｉｌｅａｇａｉｎｄｏ//外部迭代ꎻ

Ｔｉꎬｊ∈Ｔａｇｇꎬ用Ｄｉｊｋｓｔｒａ算法[１２ꎬ１３]计算Ｉｉ、Ｉｊ

３　结论

由图３得出在Δ＝１００ｓ左右时ꎬ最大行程匹配模式和最小行程时间模式节省的行程数出现明显差异ꎬ其中Δ＝３００ｓ左右时ꎬ最小行程时间模式达到理想状态ꎮ图４中红色和蓝色曲线对比ꎬΔ越大ꎬ

ｉꎬｊ

之间的最佳路线ꎻｔＳꎻ

Ｔｉꎬｊ∈Ｔａｇｇꎬ计算行程估计时间ｅｔｉꎬｊ＝令Ｓｔ＝∪

Ｓｉꎬｊ

Ｔｉꎬｊ∈Ｔａｇｇ

∑Ｓ∈Ｓ

曲线收敛越快ꎬ节省的行程百分比越大ꎻ绿色和黄色曲线对比显示Δ越大ꎬ节省的行程时间百分百比也越大ꎮ综上ꎬ在相同的ｋ＝２情况下ꎬΔ越大ꎬ节省

ꎻ

　４

«电视技术»第４３卷第４期(总第５１３期)｜投稿网址ｈｔｔｐ:∕∕ｗｗｗ.ｖｉｄｅｏｅ.ｃｎ

行程的效果越好ꎬ即越多的行程被组合ꎬ需要的车辆及行程时间减少ꎬ进而实现减少交通拥堵和环境污染的目标ꎮ

[４]曹二保ꎬ汤春华.车辆数目未知的带时间窗口的车辆路径混合遗传算法[Ｊ].武汉理工大学学报(交通科学与工程版)ꎬ２０１１ꎬ３５(１):３３－３７.

陈锋.带时间窗约束的多类型车辆路径问题的改进节约算法[Ｊ].科学技术与工程ꎬ２０１２ꎬ１２(２４):６０８２ＢＥＲＢＥＧＬＩＡＧꎬＣＯＲＤＥＡＵＪＦꎬＬＡＰＯＲＴＥＧ.Ｄｙ￣－６０８６.

[５]

[６]

ｎａｍｉｃｐｉｃｋｕｐａｎｄｄｅｌｉｖｅｒｙｐｒｏｂｌｅｍｓ[Ｊ].ＥｕｒｏｐｅａｎＪｏｕｒ￣ｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈꎬ２０１０ꎬ２０２(１):８－１５.ＬＡＰＯＲＴＥＧ.Ｔｈｅｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍ:ＡｎｏｖｅｒｖｉｅｗｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈꎬ１９９２ꎬ５９(３):３４５－３５８.２００９ꎬ３６(１):２９３－２９４.

ｏｆｅｘａｃｔａｎｄａｐｐｒｏｘｉｍａｔｅａｌｇｏｒｉｔｈｍｓ[Ｊ].ＥｕｒｏｐｅａｎＪｏｕｒ￣

[７]

[８][９]

胡金初.网络流算法的分析及研究[Ｊ].计算机科学ꎬＬＩＢꎬＺＨＡＮＧＤꎬＳＵＮＬꎬｅｔａｌ.Ｈｕｎｔｉｎｇｏｒｗａｉｔｉｎｇ?

Ｄｉｓｃｏｖｅｒｉｎｇｐａｓｓｅｎｇｅｒ－ｆｉｎｄｉｎｇｓｔｒａｔｅｇｉｅｓｆｒｏｍａｌａｒｇｅ－

图３　节省行程百分比对比

ｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＰｅｒｖａｓｉｖｅＣｏｍｐｕｔｉｎｇａｎｄＣｏｍｍｕｎｉ￣ｃａｔｉｏｎｓＩＥＥＥꎬ２０１１.

Ｗｏｒｋｓｈｏｐｓ

(ＰＥＲＣＯＭ

Ｗｏｒｋｓｈｏｐｓ).

ｓｃａｌｅｒｅａｌ－ｗｏｒｌｄｔａｘｉｄａｔａｓｅｔ[Ｃ].２０１１ＩＥＥＥＩｎｔｅｒｎａ￣

[１０]法拉.基于Ｅｄｍｏｎｄｓ－Ｋａｒｐ算法的输入排队调度[Ｊ].

计算机工程ꎬ２００５ꎬ３１(１８):１３－１５

[１１]ＹＡＮＧＪꎬＪＡＩＬＬＥＴＰꎬＭＡＨＭＡＳＳＡＮＩＨ.Ｒｅａｌ－ｔｉｍｅ

ｍｕｌｔｉｖｅｈｉｃｌｅｔｒｕｃｋｌｏａｄｐｉｃｋｕｐａｎｄｄｅｌｉｖｅｒｙｐｒｏｂｌｅｍｓ[Ｊ].ＴｒａｎｓｐｏｒｔＳｃｉꎬ２００４ꎬ３８(２):１３５－１４８.

[１２]ＢＥＲＢＥＧＬＩＡＧꎬＣＯＲＤＥＡＵＪＦꎬＬＡＰＯＲＴＥＧ(２０１０)

Ｒｅｓꎬ２０１０ꎬ２０２(１):８–１５.

Ｄｙｎａｍｉｃｐｉｃｋｕｐａｎｄｄｅｌｉｖｅｒｙｐｒｏｂｌｅｍｓ[Ｊ].ＥｕｒＪＯｐｅｒ

图４　节省行程及节省行程时间对比

参考文献:[１]

戴冬ꎬ王江晴.一种基于禁忌搜索算法的车辆路径问题的改进算法[Ｊ].中南民族大学学报(自然科学版)ꎬ２００７ꎬ２６(１):６４－６６.[２]

ｒｉｔｈｍｆｏｒｔｈｅｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍ[Ｊ].Ｃｏｍｐｕｔｅｒｓ＆黄明ꎬ闫淑娟ꎬ梁旭.遗传算法和禁忌搜索算法在车间调度中的研究进展[Ｊ].工业控制计算机ꎬ２００４ꎬ１７(２):４－５.

ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈꎬ２００３ꎬ３０(５):７８７－８００.ＢＡＫＥＲꎬＢＡＲＲＩＥＭꎬＡＹＥＣＨＥＷＭＡ.Ａｇｅｎｅｔｉｃａｌｇｏ￣

[１３]ＴａｃｈｅｔＲꎬＳａｇａｒｒａＯꎬＳａｎｔｉＰꎬｅｔａｌ.Ｓｃａｌｉｎｇｌａｗｏｆｕｒｂａｎ

ｒｉｄｅｓｈａｒｉｎｇ[Ｒ].Ｓｃｉ.Ｒｅｐ.２０１７:４２８６８.

􀲻

作者简介:交通等ꎻ

何曼洁(１９９４—)ꎬ硕士生ꎬ主要研究方向为物联网、智能曾连荪(１９６２—)ꎬ博士ꎬ教授ꎬ硕士生导师ꎬ主要研究方向为物联网、无线接入技术、定位测控技术、安全监控技术、车联网等ꎮ责任编辑:胡鑫

收稿日期:２０１９－０１－１７

[３]

投稿网址ｈｔｔｐ:∕∕ｗｗｗ.ｖｉｄｅｏｅ.ｃｎ｜«电视技术»第４３卷第４期(总第５１３期)

　５