基于三维时空轨迹的拼车改进算法研究
|
摘要
由于私家车数量剧增导致道路拥堵日益严重,拼车作为一种更加环保的出行方式成为人们出行的重要选择。为了提高拼车服务质量,轨迹匹配正成为一个新的研究热点。传统的基于Hausdorff距离的轨迹匹配存在两个问题:只考虑了路径上点的坐标信息,忽略了用户等待时间;直接计算整段路径的Hausdorff距离,无法体现特殊路段对匹配度量的影响。针对上述问题提出两点改进:提出带有时间约束的Hausdorff距离计算方法;提出了一种优化的轨迹匹配方法:用转向点分割原路径,将匹配度量细化到每个子路段。为了评估所提出框架的性能,从Google地图获取到大量中国湖北省武汉市的路线图,实证研究表明,相较于传统的最小完成时间在线模式调度(MCT)算法,所提出的方法能够帮助乘客找到更匹配的轨迹,减少等待时间,从而减少大气污染。
As the increasing number of private cars has caused serious traffic jams, carpooling as an environmentallyfriendly way has become an important choice for people. In order to improve the quality of carpooling service, trajectory matching becomes a new research hotspot. Generally, there are two problems with the traditional trajectory matching based on Hausdorff distance:only the coordinate information of the point on the path is considered, and the user's waiting time is ignored; calculating the Hausdorff distance of the entire path directly, which can't reflect the influence of the special road segment on the matching metrics. This paper proposes two improvements for the above issues:a Hausdorff distance calculation method with time constraints is proposed; an optimized trajectory matching method is proposed:dividing the original path with turning points and refining the matching metrics to each segment. In order to evaluate the performance of the proposed framework, a large number of roadmaps in Wuhan City of the Hubei Province are downloaded from Google map. Empirical studies have shown that compared with the traditional Minimum Completion Time(MCT)online mode scheduling algorithm, the proposed method can help passengers find better matches and reduce waiting time, and thus reducing air pollution.
As the increasing number of private cars has caused serious traffic jams, carpooling as an environmentallyfriendly way has become an important choice for people. In order to improve the quality of carpooling service, trajectory matching becomes a new research hotspot. Generally, there are two problems with the traditional trajectory matching based on Hausdorff distance:only the coordinate information of the point on the path is considered, and the user's waiting time is ignored; calculating the Hausdorff distance of the entire path directly, which can't reflect the influence of the special road segment on the matching metrics. This paper proposes two improvements for the above issues:a Hausdorff distance calculation method with time constraints is proposed; an optimized trajectory matching method is proposed:dividing the original path with turning points and refining the matching metrics to each segment. In order to evaluate the performance of the proposed framework, a large number of roadmaps in Wuhan City of the Hubei Province are downloaded from Google map. Empirical studies have shown that compared with the traditional Minimum Completion Time(MCT)online mode scheduling algorithm, the proposed method can help passengers find better matches and reduce waiting time, and thus reducing air pollution.
引文
[1] Wang X T,Leckie C,Xie H R,et al.Discovering the impact of urban traffic interventions using contrast mining on vehicle trajectory data[C]//Proceedings of Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining,2015:486-497.
[2] Ribeiroá,Silva D C,Abreu P H.Mocas:Mobile carpooling system[J].Advances in Intelligent Systems and Computing,2015,353:913-922.
[3] Huang Y,Powel J W.Detecting regions of disequilibrium in taxi services under uncertainty[C]//Proceedings of the20th International Conference on Advances in Geographic Information Systems,2012:139-148..
[4] Yao J,Chen A,Ryu S,et al.A general unconstrained optimization formulation for the combined distribution and assignment problem[J].Transportation Research Part B(Methodological),2014,59:137-160.
[5] Yang Y,Cui Z,Wu J,et al.Trajectory analysis using spectral clustering and sequene pattern mining[J].Journal of Computational Information Systems,2012,8(6):2637-2645.
[6]刘春,谭梦茜,邵雄凯.基于行车位置数据挖掘的拼车方法研究[J].计算机工程与应用,2017,53(8):76-80.
[7] Zhang X,Ouyang M,Zhang X.Small scale crowd behavior classification by euclidean distance variation-weighted network[J].Multimedia Tools and Applications,2016,75(19):11945-11960.
[8] Bulent C.A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications,2010,37(10):6809-6817.
[9]王君.带时间窗车辆路径问题的差分进化混合算法[J].计算机工程与应用,2013,49(2):24-28.
[10] Zhang C D,Liu D T,Wu X.Near-duplicate segments based news Web video event mining[J].Signal Processing,2016,120:26-35.
[11] Tang L L,Zheng W B,Wang Z Q,et al.Space time analysis on the pick-up and drop off of taxi passengers based on gps big data[J].Journal of Geo-Information Science,2015,17(10):1179-1186.
[12] Feng T.Dynamic taxipooling scheduling algorithm based on sufferage[J].Computer Knowledge and Technology,2011,28(7):7019-7023.
[13] Zafar K,Baig A R.Optimization of route planning and exploration using multi agent system[J].Multimedia Tools and Applications,2012,56(2):245-265.
[14] H?me L.An adaptive insertion algorithm for the singlevehicle dial-a-ride problem with narrow time windows[J].European Journal of Operational Research,2011,209(1):11-22.
[15] Xiao Q,He R C,Zang W,et al.Algorithm research of taxi carpooling based on fuzzy clustering and fuzzy recognition[J].Joural of Transportation Systems Engineering and Information Technology,2014,14(5):119-125.
[16]曹闻,刘浩,李润生.一种改进的Hausdorff距离地图匹配方法[J].计算机工程与应用,2013,49(6):159-162.
[17] Atev S,Miller G,Papanikolopoulos N P.Clustering of vehicle trajectories[J].IEEE Transactions on Intelligent Transportation Systems,2010,11(3):647-657.
[18] Zhang X L,Chen G,Han Y.Modeling and analysis of bus weighted complex network in qingdao city based on dynamic travel time[J].Multimedia Tools and Applications,2016,75(24):17553-17572.
[2] Ribeiroá,Silva D C,Abreu P H.Mocas:Mobile carpooling system[J].Advances in Intelligent Systems and Computing,2015,353:913-922.
[3] Huang Y,Powel J W.Detecting regions of disequilibrium in taxi services under uncertainty[C]//Proceedings of the20th International Conference on Advances in Geographic Information Systems,2012:139-148..
[4] Yao J,Chen A,Ryu S,et al.A general unconstrained optimization formulation for the combined distribution and assignment problem[J].Transportation Research Part B(Methodological),2014,59:137-160.
[5] Yang Y,Cui Z,Wu J,et al.Trajectory analysis using spectral clustering and sequene pattern mining[J].Journal of Computational Information Systems,2012,8(6):2637-2645.
[6]刘春,谭梦茜,邵雄凯.基于行车位置数据挖掘的拼车方法研究[J].计算机工程与应用,2017,53(8):76-80.
[7] Zhang X,Ouyang M,Zhang X.Small scale crowd behavior classification by euclidean distance variation-weighted network[J].Multimedia Tools and Applications,2016,75(19):11945-11960.
[8] Bulent C.A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications,2010,37(10):6809-6817.
[9]王君.带时间窗车辆路径问题的差分进化混合算法[J].计算机工程与应用,2013,49(2):24-28.
[10] Zhang C D,Liu D T,Wu X.Near-duplicate segments based news Web video event mining[J].Signal Processing,2016,120:26-35.
[11] Tang L L,Zheng W B,Wang Z Q,et al.Space time analysis on the pick-up and drop off of taxi passengers based on gps big data[J].Journal of Geo-Information Science,2015,17(10):1179-1186.
[12] Feng T.Dynamic taxipooling scheduling algorithm based on sufferage[J].Computer Knowledge and Technology,2011,28(7):7019-7023.
[13] Zafar K,Baig A R.Optimization of route planning and exploration using multi agent system[J].Multimedia Tools and Applications,2012,56(2):245-265.
[14] H?me L.An adaptive insertion algorithm for the singlevehicle dial-a-ride problem with narrow time windows[J].European Journal of Operational Research,2011,209(1):11-22.
[15] Xiao Q,He R C,Zang W,et al.Algorithm research of taxi carpooling based on fuzzy clustering and fuzzy recognition[J].Joural of Transportation Systems Engineering and Information Technology,2014,14(5):119-125.
[16]曹闻,刘浩,李润生.一种改进的Hausdorff距离地图匹配方法[J].计算机工程与应用,2013,49(6):159-162.
[17] Atev S,Miller G,Papanikolopoulos N P.Clustering of vehicle trajectories[J].IEEE Transactions on Intelligent Transportation Systems,2010,11(3):647-657.
[18] Zhang X L,Chen G,Han Y.Modeling and analysis of bus weighted complex network in qingdao city based on dynamic travel time[J].Multimedia Tools and Applications,2016,75(24):17553-17572.