Multi-Strategy Solution Space Graph Search Algorithm of Real-Time Ride-Sharing Problem
-
摘要: 车辆共乘旨在通过降低车辆空载率以提升运输效率、缓解交通拥堵、降低环境污染并节省出行资源. 首先针对即时车辆共乘问题构建了数学模型,以共享路程比率和绕行距离约束为手段对车辆合乘中车主资源的利用效率进行评估.然后提出离散排列问题的解空间图理论并对其原理进行了阐述和分析，继而基于此理论构建一种多策略解空间图搜索算法.该算法以并行化结构生成价值矩阵显著提升了传统方法的效率，并以多种控制策略操纵结合离散排列问题特点设计的不同搜索算子，指导搜索过程在解空间图中向更高价值方向移动以高效获取高质量的匹配方案.实验结果表明，该算法的求解质量可达最优解的95%以上，且求解效率明显优于对比实验中的其他算法.Abstract: Ride-sharing can improve transportation efficiency, alleviate traffic congestion, reduce environmental pollution and save travel costs through decreasing the vehicle vacancy rate of all participants. Firstly, in this paper, a mathematical model is constructed for the real-time ride-sharing problem, where the utilization efficiency of the driver resources in the ride-sharing is evaluated by means of the shared route percentage and the detour distance constraint. Then, a solution space graph theory of discrete permutation problem is proposed and its principle is elaborated and analyzed. Based on this theory, a multi-strategy solution space graph search algorithm is constructed. The algorithm utilizes a parallel structure to generate the value matrix of driver-rider pairs, which greatly improves the efficiency of the algorithm compared with traditional approaches. Several different search operators, designed based on the characteristics of the discrete permutation problem, are manipulated by multiple control strategies proposed in this paper, which guide the search process to move to higher value directions of the solution space graph to obtain high quality matching results efficiently. The experimental results show that the quality of the algorithm can exceed 95% of the optimal solution, and the efficiency of the algorithm is significantly superior than the other algorithms compared in the experiment.
-
-
期刊类型引用(98)
1. 吴碧莲，陈昕，殷波. 移动边缘计算下基于斯坦伯格博弈的资源分配策略研究. 计算机应用与软件. 2025(02): 136-143 . 
百度学术
2. 文涛，谭蓓. 5G专网场景下的DPI部署方案研究. 邮电设计技术. 2025(02): 37-41 . 百度学术
3. 刘治国，董效奇，汪林，夏清雨，潘成胜. 面向ET-DQN的卫星网络任务部署算法研究. 小型微型计算机系统. 2024(02): 418-424 . 百度学术
4. 韩跃林，朱琦. 多用户D2D计算卸载与资源分配算法. 信号处理. 2024(02): 373-384 . 百度学术
5. 朱海峰，聂赛，彭绪意，刘泽，章志平，吴中华，李桂林，郑源. 基于边缘图像采集的抽蓄电站重大风险图像实时监测. 水电站机电技术. 2024(04): 44-46 . 百度学术
6. 刘冰艺，王东东，施海勇，王恩澍，吴黎兵，汪建平. C-V2X环境下基于队友模型的多智能体通信切换优化. 计算机研究与发展. 2024(11): 2806-2820 . 本站查看
7. 王宇轩，鲍海洲，喻国荣，聂雷，陈民浩. 基于PER-MATD3的任务卸载和资源优化方法. 计算机技术与发展. 2024(12): 57-65 . 百度学术
8. 张成虎，李鹏旭，王琪. 网络金融犯罪预警系统研究——基于区块链和边缘计算. 情报杂志. 2023(01): 59-65 . 百度学术
9. 景毅，姜春晓，詹亚锋. 面向卫星通信的6G通感算融合架构、技术与挑战. 无线电通信技术. 2023(01): 12-20 . 百度学术
10. 彭昇，赵建保，魏敏捷，秦伦明. 基于移动边缘计算的任务卸载优化. 计算机系统应用. 2023(04): 262-267 . 百度学术
11. 李媛媛，付晓东，刘骊，刘利军，彭玮. 利用Hawkes过程模型的移动边缘计算服务质量预测. 小型微型计算机系统. 2023(07): 1571-1577 . 百度学术
12. 叶海军，王国峰，冯志勇. 有人无人网络化信息系统动态协同技术研究. 通信学报. 2023(07): 185-196 . 百度学术
13. 吉祥，蒋锴，成海东. 全域作战指挥信息系统总体架构及核心支柱. 指挥与控制学报. 2023(02): 225-232 . 百度学术
14. 汪诗经，高玉芹，滕勇健. 基于携能和边缘缓存的5G移动通信系统传输技术研究. 电子设计工程. 2023(18): 174-177+182 . 百度学术
15. 孟涛. 计算机技术在5G通信网络中的有效应用研究. 中国新通信. 2023(16): 90-92 . 百度学术
16. 陈鸿凯. 云边协同部署架构在铁塔高空监控中的应用. 大众标准化. 2023(21): 146-148 . 百度学术
17. 黄天海，褚永华，邹瞿超，王元吉，王志康. 多院区发展背景下基于物联网技术的医疗设备管理实践. 中国医疗设备. 2022(01): 37-42 . 百度学术
18. 童瀛，周宇，姚焕章，梁剑，薛虎. 面向私有云的虚拟化网络密文数据防泄漏模型设计. 西安工程大学学报. 2022(01): 129-135 . 百度学术
19. 李爽，郭忠志，肖羽，王帅. 5G网络针对工业互联网需求的边缘云解决方案. 邮电设计技术. 2022(02): 81-87 . 百度学术
20. 陈端云，苏素燕，林巍，林叶青，林昕仪，曹雄志，林巧玲. 基于5G通信的配网差动保护移动边缘计算方法. 信息技术. 2022(03): 56-60+66 . 百度学术
21. 段向阳，杨立，夏树强，韩志强，谢峰. 通感算智一体化技术发展模式. 电信科学. 2022(03): 37-48 . 百度学术
22. 高鸣. 5G通信与广播电视的技术融合分析. 集成电路应用. 2022(03): 75-77 . 百度学术
23. 朱思峰，孙恩林，柴争义. 移动边缘计算场景下基于免疫优化的任务卸载. 西安电子科技大学学报. 2022(01): 152-160 . 百度学术
24. 尚坤豪，符琦，巴冰. 一种基于路边单元协作的任务卸载策略. 湖南科技大学学报(自然科学版). 2022(01): 100-108 . 百度学术
25. 张彦虎，鄢丽娟，马志愤，张彦军. 一种适用于多任务多资源移动边缘计算环境下的改进粒子群算力卸载算法. 计算机与现代化. 2022(05): 54-60+67 . 百度学术
26. 周杰，杜玲禧，宋晶，戚建淮. 一种适用于高速列车的动态建链通信模型. 通信技术. 2022(05): 554-558 . 百度学术
27. 冯晓丽，刘晨，张丽伟，王晓韵. 基于5G MEC的智慧化园区解决方案. 电信科学. 2022(05): 54-63 . 百度学术
28. 赵丽红，丁晓梅. 基于5G MEC技术的智慧校园网络低时延优化方法. 商丘师范学院学报. 2022(06): 20-24 . 百度学术
29. 刘芳正，马博闻，吕博枫，黄霁崴. 一种面向移动边缘计算的无人机基站部署方法. 计算机科学. 2022(S2): 848-854 . 百度学术
30. 杜璞. 移动边缘计算环境下5G通信网络数据安全与隐私保护技术研究. 长江信息通信. 2022(10): 211-214 . 百度学术
31. 刘春林，秦进. 面向5G网络的移动边缘计算节点部署算法设计. 计算机仿真. 2022(12): 436-439+473 . 百度学术
32. 张永棠. 一种深度强化学习的C-RAN动态资源分配方法. 小型微型计算机系统. 2021(01): 132-136 . 百度学术
33. 韩松岳，杨舒洵，黄伟. 基于5G边缘计算增强技术的思考与分析. 长江信息通信. 2021(01): 223-225 . 百度学术
34. 王同，康桂华，刘祥，黄珂. 基于能量收集的MEC系统的计算卸载策略研究. 信息技术. 2021(02): 85-91 . 百度学术
35. 高寒，李晓辉. 边缘计算中云边任务下发策略研究. 信息技术. 2021(02): 103-108 . 百度学术
36. 刘图楠. 5G工业互联网的边缘计算技术架构与应用分析. 长江信息通信. 2021(04): 44-45+53 . 百度学术
37. 赵伟慧，汪晓臣，孙同庆，黄志威，付思. 基于5G移动通信技术的城市轨道交通车地无线网络协同传输方案. 铁路计算机应用. 2021(05): 10-14 . 百度学术
38. 刘笑凯，王文东，国佃利，王萍. 5G安全风险分析与防护体系建设. 电子技术应用. 2021(05): 69-72 . 百度学术
39. 崔娴. 融合可调节负荷的5G通信网络需求响应系统架构. 通信电源技术. 2021(04): 104-105+108 . 百度学术
40. 熊玮. 跨行业资源共享实现5G网络低成本快速部署. 中国管理信息化. 2021(13): 139-141 . 百度学术
41. 杜羽，张兆云，赵洋. 边缘计算在智能电网中的应用综述. 湖北电力. 2021(03): 72-81 . 百度学术
42. 熊玮. 皮卡通——5G全能应急通信变形箱. 数字通信世界. 2021(08): 38-40 . 百度学术
43. 庄立道. 5G网络支撑下广播电视与移动通信的衔接分析. 电视技术. 2021(05): 1-3 . 百度学术
44. 潘宇婷，汪振宇，盛夏. 融合移动边缘计算的5G网络在配电自动化管理大区主站中的应用. 电力与能源. 2021(03): 269-272+276 . 百度学术
45. 诸茂华，关月芝，温玉波，刘绮姮. 边缘计算在优化远岛观测数据传输中的应用研究. 海洋开发与管理. 2021(06): 87-92 . 百度学术
46. 陈霄，刘巍，夏淋淋，周觐，王潋. 边缘计算军事应用需求及作战运用构想. 火力与指挥控制. 2021(08): 1-4 . 百度学术
47. 刘伟，陈振. 边缘计算中面向多码率视频的缓存、转码和传输联合优化策略. 计算机应用研究. 2021(09): 2628-2634 . 百度学术
48. 冯春盛，王伟，付连宇，卢超，卢志鑫，刘沛林. 面向电力5G网络的边缘计算安全防护体系分析. 电力信息与通信技术. 2021(09): 31-37 . 百度学术
49. 杨术，陈子腾，崔来中，明中行，程路，唐小林，萧伟. 功能分发网络:基于容器的智能边缘计算平台. 软件学报. 2021(12): 3945-3959 . 百度学术
50. 孙严智，刘宇明，罗海林，温泉，蒋丽琼. 基于5G端到端切片的多业务泛在智能电网研究. 云南电力技术. 2021(06): 2-7+12 . 百度学术
51. 汪双兔，汪海旸. 基于MEC的5G虚拟专网在家电企业应用研究. 信息技术与网络安全. 2021(01): 56-61 . 百度学术
52. 孙立杰，葛振宇，伍竹歆，刘昌海. 多接入移动边缘计算技术在移动网络的部署实践与思考. 电信工程技术与标准化. 2020(01): 25-30 . 百度学术
53. 邓红红. 5G移动通信网络关键技术及分. 数字通信世界. 2020(02): 134 . 百度学术
54. 尹高，石远明. 移动边缘网络中深度学习任务卸载方案. 重庆邮电大学学报(自然科学版). 2020(01): 38-46 . 百度学术
55. 张海波，荆昆仑，刘开健，贺晓帆. 车联网中一种基于软件定义网络与移动边缘计算的卸载策略. 电子与信息学报. 2020(03): 645-652 . 百度学术
56. 孙广新. 5G技术在移动通信网络中的应用. 数字技术与应用. 2020(01): 14+16 . 百度学术
57. 白昱阳，黄彦浩，陈思远，张俊，李柏青，王飞跃. 云边智能:电力系统运行控制的边缘计算方法及其应用现状与展望. 自动化学报. 2020(03): 397-410 . 百度学术
58. 周天意，叶剑芯. 5G对自动驾驶的影响. 科学咨询(科技·管理). 2020(04): 130-131 . 百度学术
59. 姜维宁，赵振威. 医护患一体化的5G通信模式研究. 自动化与仪器仪表. 2020(04): 179-182 . 百度学术
60. 朱光灿. 5G移动通信网络关键技术. 电子技术与软件工程. 2020(05): 8-9 . 百度学术
61. 乐光学，戴亚盛，杨晓慧，刘建华，游真旭，朱友康. 边缘计算可信协同服务策略建模. 计算机研究与发展. 2020(05): 1080-1102 . 本站查看
62. 孔令义，武俊芹. MEC在移动网中的部署及应用. 邮电设计技术. 2020(05): 79-82 . 百度学术
63. 黄尘琛，滕国伟，汤毅. 针对城市道路的图像语义分割. 电视技术. 2020(05): 1-3+22 . 百度学术
64. 魏明，李冉. 对广电5G建设和发展的思考. 电视技术. 2020(04): 14-17+32 . 百度学术
65. 韩江洪，卫星，陆阳，魏臻，程运安，程磊. 煤矿井下机车无人驾驶系统关键技术. 煤炭学报. 2020(06): 2104-2115 . 百度学术
66. 高阳东，黄勇，郝晓强. 卫星通信与5G通信融合的网络架构与关键技术. 电子技术与软件工程. 2020(10): 26-27 . 百度学术
67. 樊琦. 5G关键技术及应用的探讨. 甘肃科技纵横. 2020(06): 1-3 . 百度学术
68. 刘炎培，朱淇，赵进超. 边缘环境下计算密集型应用的卸载技术研究. 计算机工程与应用. 2020(15): 1-14 . 百度学术
69. 黄泽龙. 边缘计算在物联网领域的研究与分析. 广东通信技术. 2020(07): 13-15+26 . 百度学术
70. 沈博. 5G网络架构的标准研究进展. 信息通信. 2020(07): 261-262 . 百度学术
71. 徐传通. 5G移动通信网络中缓存与计算关键技术研究. 通信电源技术. 2020(11): 178-180 . 百度学术
72. 靳宏尧，李敬义. 边缘计算背景下的5G增强技术与安全防护技术. 通信电源技术. 2020(11): 172-174 . 百度学术
73. 夏靖康. 面向5G的通信网络全局化状态信息非线性切换系统研究. 计算机测量与控制. 2020(09): 223-228 . 百度学术
74. 封万里，王之伟，池庆国，孙志惠，岑翼刚. CDN日志全链路分析系统的实施. 广东通信技术. 2020(10): 53-56 . 百度学术
75. 李嘉. 融合移动边缘计算的未来5G移动通信网络的相关研究. 中国新通信. 2020(19): 19-20 . 百度学术
76. 李叶强，潘海兵. 共建背景的MEC分流+平台专享型部署模式探索. 科学技术创新. 2020(34): 121-123 . 百度学术
77. 胡亚霖. 5G移动通信关键技术. 电子技术与软件工程. 2019(03): 24 . 百度学术
78. 张守武，王凤丽，袁春经. 基于5G超密集网络用户活跃状态的切换管理策略. 通信技术. 2019(02): 354-360 . 百度学术
79. 夏杰，袁春经，王凤丽. 基于公平性的打孔调度算法. 通信技术. 2019(02): 372-376 . 百度学术
80. 王凌风，罗宁. 基于BIM的LTE室内覆盖解决方案. 电信技术. 2019(04): 60-64 . 百度学术
81. 王芮. 5G网络架构设计与标准化进展. 通讯世界. 2019(04): 91-92 . 百度学术
82. 甘为民. 浅析5G技术对移动通信网络建设方式的影响. 数字通信世界. 2019(05): 157 . 百度学术
83. 王芳. 浅谈计算机网络与通信技术. 科技经济导刊. 2019(18): 18 . 百度学术
84. 王辉. 移动边缘计算技术在未来移动通信网络中的应用. 信息通信. 2019(06): 238-239 . 百度学术
85. 熊杰. 在5G小基站上部署MEC的意义分析. 移动通信. 2019(07): 63-66+71 . 百度学术
86. 毕倬. 5G移动通信网络关键技术及分析. 信息与电脑(理论版). 2019(14): 166-167+175 . 百度学术
87. 任娟莉，王若鸿. 5G布局下图书馆多场景VR服务构建. 出版广角. 2019(18): 70-73 . 百度学术
88. 夏彦东，邓宁静. 卫星导航与5G移动通信融合架构的关键技术与应用前景. 中国新通信. 2019(18): 23 . 百度学术
89. 肖文华，刘必欣，刘巍，程钢，王跃华. 面向恶劣环境的边缘计算综述. 指挥与控制学报. 2019(03): 181-190 . 百度学术
90. 孔令义. “5G+MEC”为智能制造赋能的部署应用. 电信科学. 2019(10): 137-145 . 百度学术
91. 李蕾，闻征涛，任容玮. 基于5G和MEC边缘云的智慧商超. 电信科学. 2019(S2): 143-148 . 百度学术
92. 赵思. 5G移动与广播电视融合网络的探索. 信息与电脑(理论版). 2019(22): 170-171 . 百度学术
93. 谢海涛. 浅析5G移动与广播电视融合网络. 数字技术与应用. 2019(12): 18+20 . 百度学术
94. 周旭，李琢，覃毅芳. 面向5G/B5G的智能云化网络架构. 电信科学. 2019(10): 21-30 . 百度学术
95. 陈新海，祖晖，王博思. 面向车路协同的智慧路侧系统设计. 交通与运输. 2019(06): 62-65 . 百度学术
96. 周一青，孙布勒，齐彦丽，彭燕，刘玲，张志龙，刘奕彤，刘丹谱，李兆歆，田霖. 面向通信与计算融合的5G移动增强/虚拟现实. 电信科学. 2018(08): 19-33 . 百度学术
97. 匡文波，江倩岚. 5G时代的媒体用户变化研究. 新闻与写作. 2018(11): 66-70 . 百度学术
98. 虞湘宾，王光英，许方铖. 未来移动通信网络中移动边缘计算技术. 南京航空航天大学学报. 2018(05): 586-594 . 百度学术
其他类型引用(72)
计量
- 文章访问数: 1006
- HTML全文浏览量: 0
- PDF下载量: 298
- 被引次数: 170
下载:
