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

郭羽含; 张宇; 沈学利; 于俊宇

doi:10.7544/issn1000-1239.2020.20190484

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

(辽宁工程技术大学软件学院辽宁葫芦岛 125100) (guoyuhan@lntu.edu.cn)

基金项目: 国家自然科学基金项目(61404069)；辽宁省自然科学基金项目(2019-ZD-0048)；辽宁省教育厅基础研究项目(LJ2019JL012)

详细信息

中图分类号: TP301.6
计量
- 文章访问数: 1006
- HTML全文浏览量: 0
- PDF下载量: 298
出版历程
- 发布日期: 2020-05-31

Multi-Strategy Solution Space Graph Search Algorithm of Real-Time Ride-Sharing Problem

(College of Software, Liaoning Technical University, Huludao, Liaoning 125100)

Funds: This work was supported by the National Natural Science Foundation of China (61404069), the Natural Science Foundation of Liaoning Province of China (2019-ZD-0048), and the Basic Research Project of Liaoning Provincial Education Department (LJ2019JL012).

摘要

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

HTML全文

参考文献(0)

施引文献(17)

期刊类型引用(5)

1.	闫彩瑞，马慧芳，李青青. 基于谱图小波的多尺度社区搜索方法. 计算机工程与科学. 2023(06): 1106-1115 . 百度学术
2.	张霄宏，郝浩宇，任杰成，王海涛. 加权模块度增量引导下的层次社区发现算法. 小型微型计算机系统. 2023(07): 1479-1485 . 百度学术
3.	刁雅静，吴嘉辉，卢健，王志英，朱庆康. 基于层次耦合聚类的用户社区划分方法：以主题公园社交平台为例. 江苏科技大学学报(自然科学版). 2023(04): 86-91 . 百度学术
4.	曹旭，殷铭，漆翔宇. 融合属性熵权和拓扑的局部社区发现算法. 西南民族大学学报(自然科学版). 2022(04): 448-453 . 百度学术
5.	李青青，马慧芳，李举，李志欣. 属性网络中相似性增强随机游走的多社区搜索. 电子学报. 2021(11): 2096-2100 . 百度学术