动态车辆共乘问题的双模式协作匹配算法

车辆共乘可有效提升运输资源利用率,降低出行成本,缓解交通拥堵并降低环境污染.针对动态车辆共乘问题构建了整数规划模型,并提出了一种基于离线匹配和在线匹配的双模式协作匹配算法.在离线匹配阶段,以共乘比率和绕行距离为标准对匹配价值进行评估,设计了基于带权路径搜索树的通用共乘比率生成算法对共乘参与者进行准确高效的预匹配.在在线匹配阶段,提出了基于首尾距离度的实时订单插入算法,并对离线匹配结果中的行驶路径进行修正.通过双模式协作,可有效兼顾算法的实时性和结果质量.基于真实数据的大量实验结果表明,该算法给出的匹配方案在总匹配价值和求解效率上均优于实验中的对比算法,其平均离线匹配率达93.71%、平均双模式协作匹配率达85.53%,增加运输资源利用率82.86%,减少车辆并发数84.86%.     

动态共乘系统中一种高效的插入操作方法

针对现有插入操作方法因时间复杂度高而降低动态共乘系统的运行效率,设计了一种以最小化车辆绕行距离为优化目标的线性时间插入操作方法,考虑乘客上车、下车时间约束和车辆容量限制等条件的动态共乘路线优化问题.建立共乘路线模型,采用动态规划技术和固定源节点插入位置的策略,以及利用位置向量的计算结果,可在常量时间内找到车辆绕行距离最小的目标节点的插入位置.理论分析表明:方法能够在线性时间内找到源节点和目标节点的最佳插入位置.仿真结果表明,基于线性时间的插入操作方法能够迅速地得到共乘优化路线,显著提高了动态共乘系统的运行效率.     

大数据背景下动态共乘的研究进展

共乘也被称为“合乘”、“拼车”、“顺风车”,通过有效整合运力资源减少路上行驶车辆数量,对缓解交通拥堵、降低出行费用、减轻环境污染都有重要意义.大数据背景下实时更新的车辆位置信息数据、城市交通数据、社交网络数据,为智能出行特别是共乘带来了全新的发展机遇.在车辆行驶中对乘客请求进行实时匹配的动态共乘,是大数据背景下智能出行发展趋势的代表.在统一归纳了解决动态共乘实时性的Filter and Refine框架基础上,介绍了动态共乘的各种类型;针对大数据背景下动态共乘问题遇到的问题,对Filter步骤中预先计算可行解、建立动态空间索引、基于请求分组预处理及并行优化方法,Refine步骤中简化计算模型、采用新型数据结构、利用启发式算法等优化方法进行了详细介绍;然后对大数据背景下保证动态共乘系统的价格机制、信用体系和人机接口等相关技术进行了分析;最后,总结展望了大数据背景下动态共乘中亟待解决的关键问题和未来的研究方向,以期为创造低碳生活、绿色出行,解决环境污染有所启示.     

面向公平保障的共乘定价与匹配算法

在共乘场景中,具有相似行程和时间安排的多名乘客一同出行,可降低出行成本、提高车辆上座率和缓解交通拥堵。现有研究忽略了共乘收费标准不统一和司机恶意竞价对乘客共乘体验的影响。在同时考虑费用约束、车辆容量约束和绕路距离约束的的情况下,提出最大化匹配结果公平性的方案,并将共乘的定价与匹配过程建模为一个两阶段的主从博弈。针对上述方案,提出了一个基于K-means++的请求划分算法,以缩小司乘匹配范围,提高匹配效率;在满足所有参与者约束的前提下,设计了基于两阶段主从博弈的迭代算法DPMA,并从理论上证明了其收敛性。在纽约出租车数据集上进行了仿真实验,通过不同的参数设置验证了DPMA的收敛性。与已有的2个算法相比,DPMA在保障司机收益的同时,在公平指数上分别提高了34.03%和24.42%。实验结果表明所设计机制可以有效避免司机间的恶意竞价,且提高了共乘匹配的公平性。     

基于优化遗传算法的网约车合乘模型

随着城市居民绿色低碳出行思想的提高,网约车合乘出行方式应运而生.但由于合乘模式涉及到的行驶路线问题,乘客与乘客、乘客与驾驶员之间容易产生分歧,并且网约车合乘出行模式的相关成本不明确等诸多问题,网约车合乘模式没有被大范围推广和应用.针对网约车合乘出行模式存在的问题,研究并构建了网约车合乘路径优化模型,模型中考虑了车辆等待时间成本、行驶距离成本、收益、容量约束以及时间窗约束等.针对网约车合乘模型的特点,并基于遗传算法思想,研究设计了满足合乘模型约束条件的求解遗传算法.并使用Matlab软件运行算法程序对算例进行求解,运行44.08 s得到最大利润6 906.297 1元及车辆详细行驶路线,实验表明,通过构建的网约车合乘模型和设计的遗传算法,可以得到合乘路径近似最优解,证明了模型和算法的可行性和有效性.     

考虑匹配可行性的长期合乘问题建模与求解*

车辆合乘对于减少碳排放、停车位需求以及缓解交通压力具有重要意义。针对长期车辆合乘问题(LTCPP),构建了带有车容量和时间窗约束的多目标优化模型。该模型以最小化用户行驶总距离、用户合乘产生的额外驾驶时间、用户实际启程到达时间与用户期望时间的差距以及最大化匹配可行性为目标。LTCPP是聚类和路由问题的组合,基于该特点,提出了一种分布式聚类蚁群算法(DCAC)求解LTCPP。该算法在蚂蚁行进中基于启发式信息与偏好值产生合乘组,继而采用枚举方法确定用户的最佳行驶路径。最后,在Apache Spark分布式计算框架中进行分布式实现。实验结果表明,该算法能为LTCPP提供高质量的解,并且在处理大规模LTCPP问题上具有明显优势。     

即时车辆共乘问题的多策略解空间图搜索算法

车辆共乘旨在通过降低车辆空载率以提升运输效率、缓解交通拥堵、降低环境污染并节省出行资源. 首先针对即时车辆共乘问题构建了数学模型,以共享路程比率和绕行距离约束为手段对车辆合乘中车主资源的利用效率进行评估.然后提出离散排列问题的解空间图理论并对其原理进行了阐述和分析,继而基于此理论构建一种多策略解空间图搜索算法.该算法以并行化结构生成价值矩阵显著提升了传统方法的效率,并以多种控制策略操纵结合离散排列问题特点设计的不同搜索算子,指导搜索过程在解空间图中向更高价值方向移动以高效获取高质量的匹配方案.实验结果表明,该算法的求解质量可达最优解的95%以上,且求解效率明显优于对比实验中的其他算法.     

融合用户相似度与时间期望的长期车辆共乘匹配算法

长期车辆共乘可显著提升出行便利性和稳定性，对缓解城市交通拥堵、减少环境污染具有重要作用，但由于需同步进行分组规划和路径规划，其全局最优匹配方案难以获取且匹配结果的可行性无法保障。针对上述问题，基于行驶距离、行驶时间、出发抵达期望和整合熵权相似度，构建了带有时间窗和车容量约束的多目标混合整数规划模型，采用复合熵权法对独立相似度进行融合，并提出一种质心寻优小簇分割算法对共乘用户进行匹配划分。在用户分割过程中迭代优化共乘组质心，并采用减枝枚举法计算用户的最佳行驶路径，生成符合多元约束的共乘组划分方案。实验结果表明，所提算法与一般K-Means聚类算法相比，平均近似解提高了9.66%。平均时间减少了49.29%，且在处理大规模实例上效果明显，能够高效求解长期车辆共乘匹配问题。     

考虑乘客信任程度的营运车辆合乘线路规划

车辆合乘是解决交通拥堵的有效方法,然而乘客对车辆合乘行为缺乏信任是影响合乘发展的难题。针对这一问题,通过引入信任度权重和用户偏好来衡量合乘的信任水平,以车辆的总行驶距离最短以及总信任度值最高为目标函数,同时考虑了车辆搭载容量约束、车辆行驶距离约束、乘客需求响应约束以及车辆站点服务约束,构建了考虑乘客信任程度的合乘模型,然后针对该模型采用改进的遗传算法进行求解。最后采用北京市新发地周边地区的营运车辆数据进行算法验证。结果表明,该模型能够在有效减少车辆总行驶距离的同时保障较高的乘客合乘信任水平,相较于仅考虑距离优化的模型,距离成本增加了14.8%,信任水平提升了3.3倍。通过对优化结果的对比分析,验证了模型和算法的有效性。     

考虑驾乘人员公平性的网约出租车合乘路径优化模型

为了充分发挥合乘出租车承载率高、运营效益高及交通资源省等优点, 缓解城市打车难问题, 对网约出租 车合乘路径优化问题开展研究. 首先针对路网中网约出租车的供需情况, 以系统路径最短为优化目标建立目标函 数, 其次考虑网约出租车额定载客量、路径合理性、乘客利益及驾驶员收益与时间窗因素, 构建优化模型的约束条 件, 并结合绕行距离与乘客公平性原则进行费用约束, 使得绕行距离长的合乘子路径获得更多的费用补偿, 然后基 于遗传算法思想, 针对合乘路径中乘客需求起终点的次序问题, 设计了改进的交叉与变异算子. 最后依据大连市区 局部路网高峰时段内的出租车供需数据, 利用合乘路径优化模型及算法进行求解. 研究表明, 优化模型及算法可以 短时间寻求到系统近似最优解, 所得合乘方案较非合乘出行模式有效减少了出租车空驶率与乘客的出行成本, 提高 了驾驶员的平均收益.     

基于概率路由的出租车共乘调度算法

针对现有的拼车方案大多服务在线乘客请求,而忽略了离线乘客请求,导致出租车资源无法得到充分利用这一问题,提出了一种基于挖掘历史出行轨迹数据的概率路由拼车优化算法。该算法根据乘客请求的历史时空数据计算出区域概率转移矩阵,并使用该矩阵优化平台为出租车推荐拼车路径,提供了历史数据和拼车问题相融合的一种解决方案,可以有效提高出租车的载客量。在保障离线乘客接载率、在线乘客忍耐度的同时,使用松弛时间的度量指标,可以在O（n）内对整条路径的乘客忍耐时间进行评估预测,并用迪杰斯特拉算法对绕行区域进行路径规划,让出租车的绕行距离最短。使用滴滴GAIA真实数据集对算法有效性进行验证,结果显示,该算法在服务请求数量上高于基准算法12%。     

隐私保护的网约出行的研究综述

为高效利用交通资源,在线网约出行(ORH)服务整合车辆供给和乘客请求信息,派遣符合条件的车辆提供非巡游的出行服务。人们在享受ORH服务带来的便利时,也面临着严重的隐私泄露风险。为此,许多研究利用密码学技术设计隐私保护的ORH服务。首先,本文介绍了隐私保护的ORH服务主要面临的城市动态场景下高效计算密态行程开销、实时动态规划密态行程、安全共享不同ORH服务的运力资源等挑战。然后,回顾了欧式距离、路网距离和行驶时间三类行程开销的安全计算方法,其中,欧式距离计算效率高,但误差大,现有路网距离和行驶时长的安全计算方法多数面向静态路网场景,针对城市动态路网场景的安全计算方法有待进一步研究。分析了面向司机、乘客、ORH平台的行程规划问题的求解方法,现有研究往往仅针对司机、乘客或ORH平台的单一目标进行行程规划,事实上行程规划不但要考虑ORH平台自身收益,更要同时兼顾乘客和司机的用户体验。综述了隐私感知的行程预处理方法,单车单客模式、单车多客模式的行程安全共享方法,并总结了其不足与启示。多车单客、多车多客动态模式的行程安全共享有待进一步研究。最后,从城市动态路网下高效的密态行程开销的安全计算与比较、...     

基于社交信任和标签偏好的景点推荐方法

针对现有的景点推荐算法在处理用户关系时忽视了用户隐性信任和信任传递问题,以及当用户处于新城市时由于缺乏用户历史记录无法做出准确推荐的情况,本文提出一种综合用户信任关系和标签偏好的个性化景点推荐方法.在仅仅考虑用户相似度时推荐质量差的情况下引入信任度,通过挖掘用户隐性信任关系解决了现有研究在直接信任难以获取时无法做出推荐的情况,有效缓解了数据稀疏性和冷启动问题.同时在用户兴趣分析过程中将景点和标签的关系扩展到了用户、景点和标签三者的相互关系,把用户的兴趣偏好分解成对不同景点标签的长期偏好,有效地缓解了缺乏用户历史游览记录时推荐质量不佳的问题.通过在Flickr网站上收集的数据进行实验验证,结果表明本文提出的混合推荐算法有效地提高了推荐精度,在一定程度上缓解了冷启动和新城市问题.     

Agent-based approach to analyzing the effects of dynamic ridesharing in a multimodal network

An agent-based modeling for dynamic ridesharing in a multimodal network is proposed in this paper. The study aims to evaluate the performance of dynamic ridesharing system within a multimodal network and explore the competing mechanism between dynamic ridesharing and public transit, with the presence of managed lane facility. The modeling process simulates the interaction between travelers and the network, and applies a heuristic algorithm to model travelers' decision making process under uncertainty. The model is applicable to networks with varying demographics. Multiple scenarios based on the classic Sioux Falls network have been examined. The modeling results demonstrate that the effects of dynamic ridesharing on a network differ with traffic demand and market penetrations of various travel modes. In networks with high travel demand and low market penetration of public transit, the benefits of dynamic ridesharing system on reducing congestion and providing reliable travel time are quite limited. To enhance the effectiveness of dynamic ridesharing, traffic operators may consider project investments on managed lane facilities. In networks with high market penetration of public transit, dynamic ridesharing may attract large amounts of short distance trips and aggravate congestion, especially at the initial launching phase. Policy makers would want to ensure that the existing infrastructure is sufficient to accommodate the extra traffic induced by ridesharing. Ridesharing service providers might also consider proper strategies to avoid “abuse” of the system by short trips and accelerate the market penetration.     

融合动态社交关系的距离度量推荐算法

目前,用户的好友关系及其自身呈现的动态变化趋势,使得基于静态社交关系的推荐算法难以满足现今瞬息万变的世界。为解决准确度较低等问题,提出利用用户购买物品的时序行为挖掘隐式社交关系的方法。首先将隐式社交与相似度算法相融合,其次针对近邻评分的稀疏性,提出改进的近邻评分填补方法,然后使用填补后的近邻评分对模型预测评分进行修正,最后生成预测评分。实验部分采用MovieLens数据集评估提出的方法,并与现存算法作对比分析。结果表明,该算法与传统算法及改进算法相比更稳定,也更有效地预测了目标用户的真实评分。     

结合用户兴趣度聚类的协同过滤推荐算法

针对传统的协同过滤算法忽略了用户兴趣源于关键词以及数据稀疏的问题,提出了结合用户兴趣度聚类的协同过滤推荐算法。利用用户对项目的评分,并从项目属性中提取关键词,提出了一种新的RF-IIF （rating frequency-inverse item frequency）算法,根据目标用户对某关键词的评分频率和该关键词被所有用户的评分频率,得到用户对关键词的偏好,形成用户—关键词偏好矩阵,并在该矩阵基础上进行聚类。然后利用logistic函数得到用户对项目的兴趣度,明确用户爱好,在类簇中寻找目标用户的相似用户,提取邻居爱好的前◢N◣个物品对用户进行推荐。实验结果表明,算法准确率始终优于传统算法,对用户爱好判断较为准确,缓解了数据稀疏问题,有效提高了推荐的准确率和效率。     

社交网络环境下基于信任的推荐算法

现有的基于信任的推荐算法通常假设用户是单一和同质的,没有充分挖掘信任关系信息,且相似关系和信任关系的融合缺乏高效的模型,极大地影响了推荐的准确性和可靠性。本文提出一种基于信任的推荐算法。首先结合全局信任和局部信任,并利用信任的传播性质对信任关系进行建模,然后设置推荐权重,综合考虑相似度和信任度来构建用户间的偏好关系,筛选出邻居。接着将基于记忆的协同过滤思想和社交网络的信任关系融入概率矩阵分解模型,同时使用自适应权重动态决定各部分的影响程度,形成高效统一的可信推荐模型Trust-PMF。本文的算法在FilmTrust、Epinions这两个数据集上与相关算法做了对比验证,结果证实了此算法的高效性。     

基于用户联合相似度的推荐算法

基于用户的协同过滤推荐算法在进行近邻用户的筛选时以用户之间相似度的计算结果作为依据,数据量的增大加剧了数据的稀疏程度,导致了计算结果的准确性较差,影响了推荐准确度.针对该问题本文提出了一种基于用户联合相似度的推荐算法.用户联合相似度的计算分为用户对项目属性偏好的相似度和用户之间人口统计学信息的相似度两个部分.用户的项目属性偏好引入了LDA模型来计算,计算时评分数据仅作为筛选依据,因而避免了对数据的直接使用,减缓了稀疏数据对相似度计算结果的影响;用户之间人口统计学信息的相似度则在数值化人口统计学信息之后通过海明距离进行度量.实验结果表明,本文提出的算法在推荐准确度上优于传统协同过滤推荐算法.