基于改进遗传算法的出租车共乘线路规划研究

交通运输系统工程与信息 ›› 2019, Vol. 19 ›› Issue (6): 123-128.

基于改进遗传算法的出租车共乘线路规划研究

张玺君^*，张祺瑞，张丽娟，王晨辉

兰州理工大学计算机与通信学院，兰州 730050

收稿日期:2019-07-05 修回日期:2019-08-13 出版日期:2019-12-25 发布日期:2019-12-25
作者简介:张玺君(1980-)，男，甘肃临洮人，副教授，博士生.
基金资助:
国家自然科学基金/National Natural Science Foundation of China(61461027, 61762059).

Taxi Sharing Route Planning Based on Improved Genetic Algorithm

ZHANG Xi-jun, ZHANG Qi-rui, ZHANG Li-juan,WANG Chen-hui

College of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China

Received:2019-07-05 Revised:2019-08-13 Online:2019-12-25 Published:2019-12-25

摘要/Abstract

摘要：

常规出租车运行模式效率低，增加了城市的拥堵. 针对兰州市出租车搭载率低和行驶路线规划不合理等问题，设计一种以最高搭载率、最短行驶距离为目标的函数，考虑出租车的容量限制、车辆行驶距离限制及上下车人数约束等问题的共乘模式. 建立基于改进遗传算法的出租车共乘线路规划模型. 通过采用锦标赛选择策略、站点片段交叉设计和站点监督式变异等操作对模型进行求解. 最后用兰州市出租车历史轨迹数据进行实验分析，结果表明，运用设计的出租车线路规划模型及改进的遗传算法，能够快速地得到优化路径，实现多辆出租车的规划路径满足最高搭载率及最短距离的要求.

关键词: 智能交通, 站点编码, 共乘线路, 线路优化, 地图映射

Abstract:

Common taxis working mode is inefficiently and increases congestion in the city. Aiming at the current problem of low taxi carrying rate and unreasonable route planning in Lanzhou, this paper designs a taxi sharing route planning model based on improved genetic algorithm, which takes the maximum carrying rate and the shortest driving distance as the objective function and considers the problems of taxi capacity limitation, the driving distance limitation and the number of people getting on and off. The model was solved by means of championship selection strategy, station fragments cross design and station supervised mutation. Finally, the taxi data of Lanzhou were simulated. The research result was shown that the designed taxi sharing route planning model and algorithm could quickly obtain the optimized paths of the multiple taxis, and the planning routes of multiple taxis were meet the requirements of the highest carrying rate and the shortest distance at the same time.

Key words: intelligent transportation, station coding, sharing route, route optimization, map mapping

中图分类号:

U491.1

张玺君，张祺瑞，张丽娟，王晨辉. 基于改进遗传算法的出租车共乘线路规划研究[J]. 交通运输系统工程与信息, 2019, 19(6): 123-128.

ZHANG Xi-jun, ZHANG Qi-rui, ZHANG Li-juan,WANG Chen-hui. Taxi Sharing Route Planning Based on Improved Genetic Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(6): 123-128.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19949.shtml

http://www.tseit.org.cn/CN/Y2019/V19/I6/123

参考文献

[1] HE Y, ZHANG F, LI Y, et al. Multiple routes recommendation system on massive taxi trajectories[J]. Tsinghua Science, 2016, 21(5): 510-520.

[2] LIN J J, HUANG S C, JIAU M K. An evolutionary multiobjective carpool algorithm using set-based operator based on simulated binary crossover[J]. IEEE Transactions on Cybernetics, 2018(99): 1-11.

[3] 郑建国, 李园园. 基于改进差分进化算法的出租车合乘问题研究[J]. 交通运输系统工程与信息, 2018, 18 (1): 121-126. [ZHENG J G, LI Y Y. Research on taxi sharing problem based on improved differential evolution algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(1): 121-126.]

[4] 周芳汀, 张锦, 周国华. 带时间窗的地铁配送网络路径优化问题[J]. 交通运输系统工程与信息, 2018, 18(5): 88- 94. [ZHOU F T, ZHANG J, ZHOU G H. Optimization of metro distribution network path with time windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(5): 88-94.]

[5] 陶浪, 马昌喜, 朱昌锋, 等. 基于遗传算法的定制公交路线多目标优化[J]. 兰州交通大学学报, 2018(2): 31- 37. [TAO L, MA C X, ZHU C F, et al. Multi-objective optimization of customized bus routes based on genetic algorithm[J]. Journal of Lanzhou Jiaotong University, 2018(2): 31-37.]

[6] YUAN N J, ZHENG Y, ZHANG L, et al. T-finder: A recommender system for finding passengers and vacant taxis[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(10): 2390-2403.

[7] MA S, ZHENG Y, WOLFSON O. Real-time city-scale taxi ridesharing[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(7): 1782-1795.

[8] 马通. 基于遗传算法的并行化k -means聚类算法研究[D]. 杭州: 浙江理工大学, 2018. [MA T. Research on parallel k - means clustering algorithm based on genetic algorithm[D]. Hangzhou: Zhejiang Sci- Tech University, 2018.]

[9] 吴树新. 基于双层遗传算法的城市出租车合乘模型的研究[D]. 大连: 大连交通大学, 2015. [WU S X. Research on urban taxi sharing model based on doublelayer genetic algorithm[D]. Dalian: Dalian Jiaotong University, 2015.]

[10] QIAN S, JIAN C, LE F M, et al. SCRAM: A sharing considered route assignment mechanism for fair taxi route recommendations[C]. Acm Sigkdd International Conference on Knowledge Discovery & Data Mining, 2015.

[11] GARG N, RANU S. Route recommendations for idle taxi drivers: Find me the shortest route to a customer![C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018: 1425-1434.

[1]	郭烈, 胥林立, 秦增科, 王旭. 自动驾驶接管影响因素分析与研究进展[J]. 交通运输系统工程与信息, 2022, 22(2): 72-90.
[2]	徐猛, 刘涛, 钟绍鹏, 姜宇. 城市智慧公交研究综述与展望[J]. 交通运输系统工程与信息, 2022, 22(2): 91-108.
[3]	程君, 张立炎, 陈启宏. 一种基于地图辅助的自动驾驶视-惯融合定位方法[J]. 交通运输系统工程与信息, 2022, 22(2): 117-126.
[4]	王国栋, 刘立, 孟宇, 马智萍, 郑淏清, 顾青, 白国星. 一体式车辆避撞轨迹规划与跟踪控制[J]. 交通运输系统工程与信息, 2022, 22(2): 127-136.
[5]	马东方, 陈曦, 吴晓东, 金盛. 基于强化学习的干线信号混合协同优化方法[J]. 交通运输系统工程与信息, 2022, 22(2): 145-153.
[6]	许波桅, 王玲玲, 李军军. 自动化码头多级作业超网络延误传导特性研究[J]. 交通运输系统工程与信息, 2022, 22(2): 280-289.
[7]	田会娟, 刘嘉伟, 翟佳豪, 邓琳琳. 基于多入侵线的视频车速检测方法[J]. 交通运输系统工程与信息, 2022, 22(1): 49-56.
[8]	贾彦峰, 曲大义, 赵梓旭, 王韬, 宋慧. 基于安全势场的网联自主车辆跟驰行为决策及模型[J]. 交通运输系统工程与信息, 2022, 22(1): 85-97.
[9]	刘文, 汪文博. 基于秩最小化矩阵去噪的船舶轨迹重构方法[J]. 交通运输系统工程与信息, 2022, 22(1): 106-114.
[10]	赵建东, 陈溱, 焦彦利, 张凯丽, 韩明敏. 重点营运车辆的异常驾驶行为识别研究[J]. 交通运输系统工程与信息, 2022, 22(1): 282-291.
[11]	徐东伟, 彭航, 商学天, 魏臣臣, 杨艳芳. 基于图自编码-生成对抗网络的路网数据修复[J]. 交通运输系统工程与信息, 2021, 21(6): 33-41.
[12]	游峰, 梁健中, 曹水金, 肖智豪, 吴镇江, 王海玮. 面向多目标跟踪的密集行人群轨迹提取和运动语义感知[J]. 交通运输系统工程与信息, 2021, 21(6): 42-54.
[13]	王福建, 俞佳浩, 赵锦焕, 梅振宇. 基于站点实时关联度的短时公交客流预测方法[J]. 交通运输系统工程与信息, 2021, 21(6): 131-144.
[14]	张毅, 姚丹亚, 李力, 裴华鑫, 晏松, 葛经纬. 智能车路协同系统关键技术与应用[J]. 交通运输系统工程与信息, 2021, 21(5): 40-51.
[15]	龙建成, 郭嘉琪. 动态交通分配问题研究回顾与展望[J]. 交通运输系统工程与信息, 2021, 21(5): 125-138.