Taxi Pooling Method of Urban Integrated Passenger Transport Hub with Trajectory Similarity

Abstract

Abstract:

For the problem of passenger queue stranded in integrated passenger transport hubs, a taxi pooling model considering trajectory similarity is proposed in this paper. The objectives are to minimize the number of taxis and the total mileage. A trajectory similarity indicator based on boundary area is introduced to morphologically restrict the driving trajectory after taxi pooling. A two-phase algorithm is designed to solve this NP-hard problem. In the first phase, the k-medoids is used to clustering the demands; and in the second phase, the ant colony algorithm is designed to obtain the passenger matching schemes and driving routes. Finally, the results based on survey data prove that the method can decrease the number of taxis and mileage and reduce the waiting time of passengers. Besides, the JAC value of route after taxi pooling is improved because of the trajectory similarity constraint, which satisfies the passengers' expectations of the least difference between the taxi pooling route and the original route.

Key words: traffic engineering, hub taxi pooling, trajectory similarity measuring, bi-objective optimization, ant colony algorithm, clustering

摘要：

针对综合客运枢纽出租车停靠点乘客滞留问题，提出一种考虑轨迹相似度的枢纽出租车合乘模型. 以车辆数最小与总里程最短为目标，基于包围面积的轨迹相似度指标在形态上约束合乘后车辆的行驶轨迹. 设计两阶段算法求解此NP-hard 问题，第1 阶段利用kmedoids 方法对乘客需求聚类，第2 阶段设计蚁群算法求解得到乘客匹配方案及合乘行驶路径. 实测数据实验证明：该方法能较好优化车辆数和总里程，减少乘客等待时间；轨迹相似性度量约束能有效提高合乘后路径的JAC值，满足乘客希望合乘路径与原始路径差异最小化的心理.

关键词: 交通工程, 枢纽出租车合乘, 轨迹相似性度量, 双目标优化, 蚁群算法, 聚类

CLC Number:

U469.12

WU Yue-lin, YUAN Zhen-zhou, CHEN Qiu-fang, XIAO Qing-yu,WANGWen-cheng,WEI Lai. Taxi Pooling Method of Urban Integrated Passenger Transport Hub with Trajectory Similarity[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(2): 188-195.

吴玥琳，袁振洲，陈秋芳，肖清榆，王文成，魏来. 考虑轨迹相似度的综合客运枢纽出租车合乘方法研究[J]. 交通运输系统工程与信息, 2020, 20(2): 188-195.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/abstract/abstract20029.shtml

http://www.tseit.org.cn/EN/Y2020/V20/I2/188

References

[1] MARTINEZ L M, CORREIA G H A, VIEGAS J M. An agent-based simulation model to assess the impacts of introducing a shared-taxi system: An application to Lisbon[J]. Journal of Advanced Transportation, 2015, 49 (3): 475-495.

[2] 程杰, 唐智慧, 刘杰, 等. 基于遗传算法的动态出租车合乘模型研究[J]. 武汉理工大学学报(交通科学与工程版), 2013, 37(1): 187-191. [CHENG J, TANG Z H, LIU J, et al. Research on dynamic taxipooling model based on genetic algorithm[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2013, 37(1): 187-191.]

[3] 丁冉. 出租车动态合乘匹配问题研究[D]. 南京: 东南大学, 2015. [DING R. Research on the dynamic taxipool matching problem[D]. Nanjing: Southeast University, 2015.]

[4] COSLOVICH L, PESENTI R, UKOVICH W. A twophase insertion technique of unexpected customers for a dynamic dial- a- ride problem[J]. European Journal of Operational Research, 2005, 175(3): 1605-1615.

[5] 肖强, 何瑞春, 张薇, 等. 基于模糊聚类和识别的出租车合乘算法研究[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.]

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

[7] 王海起, 翟文龙, 闫滨, 等. 以运动方向为主导的轨迹相似性度量方法[J]. 计算机工程, 2019, 45(11): 37- 46. [WANG H Q, ZHAI W L, YAN B, et al. Trajectory similarity measure based on motion direction[J]. Computer Engineering, 2019, 45(11): 37-46.]

[8] 辛柯俊, 秦中元. 基于聚类算法和蚁群算法的物流配送路径优化研究[J]. 物流工程与管理, 2014, 36(6): 86- 90. [XIN K J, QIN Z Y. Study on logistics distribution route optimization based on clustering algorithm and ant colony algorithm[J]. Logistics Engineering and Management, 2014, 36(6): 86-90.]

[9] BEZDEK J C, PAL N R. Some new indexes of cluster validity[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1998, 28(3): 301-315.

[10] VISVALINGAM M, WHYATT J D. Line generalization by repeated elimination of points[J]. Cartographic Journal, 1993, 30(1): 46-51.

[11] 易先锋. 基于车辆轨迹的个性化路径导航与行程时间预测[D]. 广州: 华南理工大学, 2018. [YI X F. Personalized route navigation and travel time prediction based on vehicle trajectories[D]. Guangzhou: South China University of Technology, 2018.]

[1]	LIN Jian-xin, LIU Bo , ZHAO Xia , ZHANG Lei. Intelligent Construction Method of Vehicle Condition Based on Hybrid Constrained Autoencoder [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 109-116.
[2]	JI Xiao-feng , GENG Zhao-shi. Bivariate Traffic Conflict Extreme Value Model of Truck Collision Prediction on Two-lane Mountain Highway [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 230-238.
[3]	ZHANG Jian-bo , SUN Jian-ping , XU Chun-ling , GUO Jing-xia, WEN Hui-min , SONG Guo-hua. Driver Characteristics Clustering Under Impact of Varying Traffic Operation Conditions [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 330-336.
[4]	MA Jing-feng, REN Gang , LI Hao-jie, CAO Qi, DU Jian-wei. Analysis on Contributing Factors Influencing Severity of E-Bicycle and Motor Vehicle Crashes [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 337-348.
[5]	ZONG Fang , WANG Meng, HE Zheng-bing. A Molecular Dynamics-based Car-following Model for Connected and Automated Vehicles Considering Impact of Multiple Vehicles [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 37-48.
[6]	MA Xiao-long , YU Qiang , LIU Jian-bei . A Calculation Method of Vehicle Collision Probability Based on Roadside Millimeter Wave Radar [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 57-66.
[7]	LIAO Peng, TANG Tie-qiao. Optimization Strategy of Lane-changing Trajectory Based on Vehicle Powertrain and Steering System [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 98-105.
[8]	LIU Yong-hong, LUO Xia , HU Jian-peng. Dynamic Allocation Method for Shared Berth Considering Immediate and Reservation Demands [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 171-181.
[9]	YUAN Zhen-zhou, GUO Man-ze, PENG Yong-xin, YANG Yang. Risk Recognition of Older Pedestrian Traffic Crashes Based on XGB-Apriori Algorithm [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 195-208.
[10]	ZHANG Yu-ting , CHEN Bo-you , ZHANG Shuang-yan, YAN Xue-dong , LI Xiao-meng. Recognition Model of Distracted Drivers When Approaching Signalized Intersections [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 217-224.
[11]	SONG Lang , WANG Jian , YANG Bin-yu , AN Shi. Innovative Design of Transportation Organization for Left-turn Non-motor Vehicles at Continuous Flow Intersection [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 225-233.
[12]	BAI Jing-rong , TANG Bo-ming, SUN Zong-yuan , BI Hui-yun , XIANG Tian-jun. On Driving Load of Super-long Tunnel Adjacent to Interchanges [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 301-310.
[13]	GUO Yan-ru , LUO Zhi-xiong , WANG Jia-chuan , HE Fang. Data-driven Planning and Design for Bike Sharing Parking Spots [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 9-16.
[14]	YOU Feng , LIANG Jian-zhong , CAO Shui-jin, XIAO Zhi-hao, WU Zhen-jiang , WANG Hai-wei. Dense Pedestrian Crowd Trajectory Extraction and Motion Semantic Information Perception Based on Multi-object Tracking [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 42-54.
[15]	LI Jun-xian , SHEN Zhou-biao , TONG Wen-cong , WU Zhi-zhou. Impact of Large Vehicles on Urban Roads with Varying Headway Distributions [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 55-62.