求解大规模CVRP问题的快速贪婪算法

为求解大规模具有能力约束的车辆路径问题(Capacitated Vehicle Routing Problem,CVRP),提出了一种快速改进贪婪算法CVRP-IMGR。基于贪婪算法思想设计了求解CVRP问题的贪婪算法CVRP-GR,在此基础上进一步采用K-d tree法和Held Karp模型改进了CVRP-GR的求解速度和求解质量,从而得到CVRP-IMGR。CVRPIMGR的复杂度可以达到O(nlogn),能够快速求解大规模(顾客数量大于500)CVRP问题。为验证CVRP-IMGR的有效性,分别采用CVRP-GR、CVRP-IMGR和经典构建型算法Savings求解了当前24个最大规模的CVRP算例,结果表明:CVRP-IMGR的求解速度远快于复杂度为O(n2logn)的CVRP-GR和Savings;CVRP-IMGR对所有算例的求解质量优于CVRP-GR,并且对18个算例的求解质量优于Savings。

群体计算中的偶图匹配算法

大数据依赖高性能计算和复杂智能推理技术等特点,引发人机协作中群体计算任务的复杂性,使得人群与任务的有效匹配成为亟待解决的问题。针对人群和机群如何协作完成大数据任务,提出群体计算中偶图匹配策略-Hopcroft-Karp算法。该算法增强和扩展了匈牙利算法,考虑自适应分割任务的领域、关联度以及人群的背景和能力评估,解决人群与分割后任务群的合理匹配问题。通过实验验证该匹配能够有效提高任务完成的准确率。

未来城市自动驾驶共享汽车规模研究：以上海为例

随着自动驾驶技术的发展,未来以自动驾驶共享汽车(Shared Autonomous Vehicle,SAV)替代有人驾驶汽车成为可能.使用SAV满足城市居民机动化出行需求的情况下,研究SAV的车辆规模.从上海市300万手机用户信令数据中提取机动化出行需求,考虑上海市实际路况的影响,建立基于车辆可共享网络的图论模型,将最小车队规模问题转化为有向无环图的最小路径覆盖问题,利用Hopcroft-Karp算法求解.求解得到,12.8万辆SAV可以满足300万手机用户的机动化出行需求.研究最大调度时间限制、服务范围限制、交通拥堵对SAV车辆规模的影响,为自动驾驶技术普及后,从城市层面确定SAV的车队规模及相应基础设施规划提供参考.

基于多关键字匹配算法的巡检视频评价系统的研究

针对当前巡检视频评价系统的缺陷,本文提出了基于多关键字匹配算法的巡检视频评价系统。将多关键字匹配算法应用到评论自动摘抄中,实现了对与视频相关评论的自动选择。同时结合本系统中存在多组关键字和视频标签长度无法限定等特点,对算法进行了改善与优化。

WSN中基于SDMA的移动高能效数据采集

利用空分多址(SDMA)技术的低时延特性,提出了一种低时延、高能效的移动Sink数据采集算法.首先利用SDMA技术的兼容节点对,按最小能耗最多配对准则,找出最佳的数据汇聚点;然后以兼容节点对的位置特征作为权值来源,使用加权最大配对算法(Hopcroft-Karp算法),得出各汇聚节点对应的最优配对节点对集合;最后找出具有最多配对数目和最大覆盖集的数据汇聚点集合P′,访问集合P′的近似最短路径即是移动节点的最终路径.仿真结果表明,该算法在保持SDMA技术低时延优势的同时,延长了网络平均生存期,具有更好的能量均衡特点.