面向道路拥塞的拼车服务质量保障算法
Congestion-aware Carpooling Algorithm for Passenger's Quality of Service
王富罗 1陆青松1
作者信息
- 1. 安徽城市管理职业学院 安徽合肥 230011
- 折叠
摘要
拼车可缓解城市道路拥堵,并降低日常出行成本.现有拼车方法往往忽略道路拥堵对于乘客拼车服务质量的影响,从而导致拼车服务成功率降低.为此,以乘客、司机正收益,以及乘客因为道路拥堵导致不耐烦等待时间最小为约束,定义了基于道路拥塞情境的短途拼车优化问题CAC.为解决上述问题,基于Shapley最优值设计贪心策略加以解决.实验结果表明,在满足乘客服务质量约束下,所设计方法相较于已有算法,可显著提升拼车成功率.
Abstract
Carpooling could not only alleviate traffic congestions,but also reduce people's daily traveling costs.Existing works failed to incorporate the influences of traffic congestion to passenger's quality of service,causing the reduction of carpooling success rate.In this work,considering the constraint of positive utilities of both drivers and passen-gers,we investigate and formulate the congestion-aware short-range carpooling problem termed as CAC.To solve the a-bove problem,a greedy algorithm had been developed on the basis of the Shapley value.Simulation results demonstrated that the designed algorithm outperform the existing algorithm while meeting the passenger's quality of service constraint.
关键词
拼车/效用/Shapley最优值/补偿/NP难Key words
carpooling/utility/shapley value/compensation/NP-hard引用本文复制引用
基金项目
安徽省高等学校自然科学研究项目重点项目(KJ2020A1092)
安徽省高等学校自然科学研究项目重大项目(2022AH040307)
出版年
2024
NETL
NSTL
维普
万方数据