车辆合乘问题的两阶段分布式估计算法

交通运输系统工程与信息 ›› 2016, Vol. 16 ›› Issue (2): 164-169.

车辆合乘问题的两阶段分布式估计算法

杨志家*¹，王子¹，汪扬^{1, 2}，闵明慧¹，李中胜¹

1. 中国科学院沈阳自动化研究所网络化控制系统重点实验室，沈阳110016；2. 辽宁石油化工大学，辽宁抚顺113001

收稿日期:2015-10-30 修回日期:2015-12-12 出版日期:2016-04-25 发布日期:2016-04-25
作者简介:杨志家（1973-），男，吉林通化人，研究员，博士生导师，博士.
基金资助:
国家自然科学基金/ National Natural Science Foundation of China（61233007）; 国家863高技术研究发展计划项目/ National High Technology Research and Development Program of China（2012AA041701）; 中国科学院“面向感知中国的新一代信息技术研究”战略性先导专项/Strategic Priority Research Program of the Chinese Academy of Sciences（XDA06020602）.

Two-stage Estimation of Distribution Algorithm to Solve Multi-vehicle Carpooling Problem

YANG Zhi-jia¹，WANG Zi¹，WANG Yang^{1, 2}，MIN Ming-hui¹，LI Zhong-sheng¹

1. Key Lab of Networked Control Systems, Shenyang Institute of Automation, CAS, Shenyang 110016, China; 2. Liaoning Shihua University, Fushun 113001, Liaoning, China

Received:2015-10-30 Revised:2015-12-12 Online:2016-04-25 Published:2016-04-25

摘要/Abstract

摘要：

针对智慧交通中多车辆合乘问题，提出一种分布式并行计算环境下的合乘模型. 利用合乘概率矩阵的先验知识，实现更高效的运算和求解.当合乘概率矩阵不是单位矩阵时，合乘模型被增广为车主合乘和乘客合乘两个阶段.两阶段分布式估计算法运用可行合乘解的合乘概率矩阵，作为一种随机优化方法求解最优值.根据可搭乘矩阵初始化合乘概率矩阵，并在优化过程中连续更新合乘概率矩阵.车主同乘客分离优化，减少了出行车辆，并实现了互相搭乘的合乘模型.通过合乘模型的优化迭代能够为乘客挖掘出高效可行的搭乘路线.实验结果表明，该合乘模型具有平均等待时间少、平均载客量大、人均行驶距离短的高效出行特点.

关键词: 智能交通, 分布式估计算法, 随机优化, 合乘问题, 时间窗

Abstract:

A multi-carpooling model is proposed for the multi-vehicle carpooling problem in a distributed parallel computing environment. The prior knowledge of the carpooling probabilistic matrix is used for more efficient computing and effective solutions. When the carpooling probabilistic matrix is not the identity matrix, the multi- carpooling model is augmented into two stages of drivers’ridesharing and passengers’ ridesharing. A two-stage estimation of distribution algorithm is proposed as a stochastic optimization method to solve the optimum with a carpooling probabilistic matrix of promising carpooling solutions. A ridable matrix initiates the carpooling probabilistic matrix, and the optimization consists of a series of incremental updates of the carpooling probabilistic matrix. The optimization process of drivers and passengers is separated; hence, the carpooling model implements the mutual ridesharing to decrease vehicles demanded. The carpooling model mines efficient and compromised ridesharing routes for shared riders by the optimization iterations. Experimental results indicate that the carpooling model has the characteristics of effective and efficient traffic including shorter waiting time, more passenger load, and less average riding distance.

Key words: intelligent transportation, estimation of distribution algorithm, stochastic optimization, carpooling problem, time window

中图分类号:

U469.12

杨志家，王子，汪扬，闵明慧，李中胜. 车辆合乘问题的两阶段分布式估计算法[J]. 交通运输系统工程与信息, 2016, 16(2): 164-169.

YANG Zhi-jia，WANG Zi，WANG Yang，MIN Ming-hui，LI Zhong-sheng. Two-stage Estimation of Distribution Algorithm to Solve Multi-vehicle Carpooling Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(2): 164-169.

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

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

http://www.tseit.org.cn/CN/Y2016/V16/I2/164

参考文献

[1] He W, Hwang K, Li D Y. Intelligent carpool routing for urban ridesharing by mining GPS trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(5): 2286-2296.

[2] Yan S Y, Chen C Y, Chang S C. A car pooling model and solution method with stochastic vehicle travel times[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(1): 47-61.

[3] 潘立军, 符卓. 求解带硬时间窗车辆路径问题的时差插入启发式算法[J].计算机应用，2012，32(11): 3402- 3403. [PAN L J, FU Z. Time difference insertion heuristics algorithm for vehicle routing problem with hard time window[J]. Journal of Computer Applications, 2012, 32(11): 3402-3403.]

[4] 张建强, 方卫国. 有时间窗约束车辆路径问题的改进遗传算法[J]. 计算机工程与应用，2010，46(32): 228- 231. [ZHANG J Q, FANG W G. Improved genetic algorithm for vehicle routing problem with time window [J]. Computer Engineering and Applications. 2010, 46 (32): 228-231.]

[5] Zhang D S, He T, Liu Y H, et al. A carpooling recommendation system for taxicab services[J]. IEEE Transactions on Emerging Topics in Computing, 2014, 2 (3): 254-266.

[6] 王子, 周侗, 汪扬, 等. 基于GPS数据可视化的智能拼车软件设计与实现[J]. 计算机工程与设计, 2015, 36 (2): 529-533+545. [WANG Z, ZHOU T, WANG Y, et al. Design and implementation of intelligent carpooling system based on GPS data visualization[J]. Computer Engineering and Design, 2015, 36(2): 529-533+545.]

[7] 邵增珍, 王洪国, 刘弘, 等.车辆合乘匹配问题中服务需求分派算法研究[J]. 清华大学学报(自然科学版), 2013, 53(2): 252-258. [SHAO Z Z, WANG H G, LIU H, et al. Research on service requirement distribution algorithms in carpooling problems[J]. Journal of Tsinghua University, 2013, 53(2): 252-258.

[8] 肖强, 何瑞春, 张薇, 等. 基于模糊聚类和识别的出租车合乘算法研究[J]. 交通运输系统工程与信息, 2014, 14(5): 119-125.[XIAO Q, HE R C, ZHANG W, et al. Algorithm research of taxi carpooling based on fuzzy clustering and fuzzy recognition[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(5): 119-125.]

[9] Huang S C, Jiau M K, Lin C H. A genetic-algorithmbased approach to solve carpool service problems in cloud computing[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(1): 352-364.

[10] 孟春华, 王洪国, 邵增珍. 基于客户分级及换乘的多车辆合乘问题算法研究[J]. 计算机科学, 2013, 40(9): 237-242. [MENG C H, WANG H G, SHAO Z Z. Algorithm research on multi- vehicle ride matching problem based on passengers classification and transfers[J]. Computer Science, 2013, 40(9): 237-242.]

[11] 王圣尧, 王凌, 方晨, 等. 分布估计算法研究进展[J]. 控制与决策, 2012, 27(7): 961-966. [WANG S Y, WANG L, FANG C, et al. Advances in estimation of distribution algorithms[J]. Control and Decision, 2012, 27(7): 961- 966.]

[12] 樊玮, 苏秋波. 基于分布估计算法的多航段座位分配模型[J]. 信息与控制, 2012, 41(6): 774- 778 + 785. [FAN W, SU Q B. Multi-leg capacity allocation model based on estimation of distribution algorithm[J]. Information and Control, 2012, 41(6): 774-778+785.]

[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.