Customized bus route planning based on spatio-temporal trajectory clustering algorithm

ZHANG Yunxi, LIU Kai, GAO Linjie

Journal of Tsinghua University(Science and Technology) ›› 2026, Vol. 66 ›› Issue (11) : 2168-2179.

PDF(4956 KB)
PDF(4956 KB)
Journal of Tsinghua University(Science and Technology) ›› 2026, Vol. 66 ›› Issue (11) : 2168-2179. DOI: 10.16511/j.cnki.qhdxxb.2026.26.059
DEMAND RESPONSE CUSTOMIZED BUS

Customized bus route planning based on spatio-temporal trajectory clustering algorithm

  • {{article.zuoZhe_EN}}
Author information +
History +

Abstract

[Objective] Customized bus (CB) services—an important supplement to conventional public transportation—provide flexible and demand-responsive travel services. Existing CB route planning methods generally follow a traditional two-stage paradigm consisting of origin-destination (OD) clustering followed by shortest-path optimization. Although these methods are effective in identifying high-density travel hotspots, they face certain limitations. First, they are less effective in identifying potential passenger groups beyond these hotspots. Second, even though passengers exhibit substantial spatiotemporal consistency along alternative routes, they cannot be grouped into the same service unit when their OD pairs are assigned to different clusters. In addition, each OD pair follows only a single shortest path, which ignores the diversity and flexibility of actual route choices. As a result, many potential passenger groups remain unidentified. This study addresses these limitations by designing a CB route planning method based on spatiotemporal trajectory clustering. The objective is to identify potential passenger groups with high spatiotemporal consistency from spatially dispersed travel demands and improve service coverage and operational efficiency. [Methods] The proposed method consists of three components: (1) generating a spatiotemporal alternative route (STAR) set for each passenger by combining the shortest path with multiple highly differentiated alternative routes using Yen’s K-shortest-path algorithm and route similarity evaluation, and constructing complete spatiotemporal trajectory chains using travel-time information; (2) developing a spatiotemporal constrained QuickBundles clustering (ST-QB) algorithm that identifies potential passenger groups with high spatiotemporal consistency while considering spatial proximity and temporal synchronization, thereby enabling the identification of passengers with highly similar travel trajectories and schedules; and (3) designing a two-stage vehicle allocation strategy to maximize passenger coverage while minimizing operating costs. Passenger demands are first assigned to candidate clusters and then matched with appropriate vehicle configurations to generate operationally feasible CB routes. [Results] The proposed method was validated using real-world CB operational data collected in Dalian, China, including 2 800 passenger trips, 178 existing CB routes, and 963 OD pairs. Experimental results showed that the STAR generation process substantially expanded the search space by identifying potential passenger groups with acceptable detour levels. The proposed ST-QB algorithm considered 196 effective trajectory clusters, with approximately 23.4% of passengers assigned to multiple candidate clusters, indicating increased flexibility in service organization. Compared with the original QuickBundles algorithm, ST-QB substantially improved temporal consistency within clusters, indicating better CB operations with the identified passenger groups. Among the 105 CB routes generated using the proposed framework, a passenger coverage rate of 90.96% was achieved in the resulting service network, which was 2.39 percentage points higher than that of the traditional method; the total operating time increased by only 1.21%. Compared with the conventional OD-clustering-based method, the proposed method improved passenger coverage by 18.00 percentage points and the proportion of serviceable clusters from 25.12% to 53.57%, demonstrating a substantially stronger capability to identify potential passenger groups embedded within spatially dispersed travel demands. [Conclusions] The proposed method effectively overcomes the limitations of the traditional “OD clustering + shortest-path optimization” framework by explicitly considering alternative route choices, spatiotemporal trajectory consistency, and potential passenger groups that are often overlooked in existing approaches. The method also provides a scalable and computationally efficient solution for CB route planning and offers practical support for improving service coverage, operational efficiency, and resource utilization in demand-responsive public transportation systems.

Key words

customized bus / vehicle route planning / spatio-temporal alternative routes / trajectory clustering algorithm

Cite this article

Download Citations
ZHANG Yunxi, LIU Kai, GAO Linjie. Customized bus route planning based on spatio-temporal trajectory clustering algorithm[J]. Journal of Tsinghua University(Science and Technology). 2026, 66(11): 2168-2179 https://doi.org/10.16511/j.cnki.qhdxxb.2026.26.059

References

[1] 马昌喜, 郝威, 沈金星, 等. 定制公交线路优化综述[J]. 交通运输工程学报, 2021, 21(5): 30-41. MA C X, HAO W, SHEN J X, et al. Review on customized bus route optimization[J]. Journal of Traffic and Transportation Engineering, 2021, 21(5): 30-41. (in Chinese)
[2] 刘锴, 王静, 王江波, 等. 考虑个体偏好异质性的定制公交选择行为[J]. 中国公路学报, 2024, 37(6): 279-287. LIU K, WANG J, WANG J B, et al. Study on customized bus choice behavior considering individual preference heterogeneity [J]. China Journal of Highway and Transport, 2024, 37(6): 279- 287. (in Chinese)
[3] LIU T, CEDER A A. Analysis of a new public-transport-service concept: Customized bus in China[J]. Transport Policy, 2015, 39: 63-76.
[4] 黄迪, 刘子煜, 刘月, 等. 数据驱动的需求响应型定制公交线路规划[J]. 清华大学学报(自然科学版), 2026, 66(3): 638-650. HUANG D, LIU Z Y, LIU Y, et al. Data-driven route planning for demand-responsive customized bus services[J]. Journal of Tsinghua University (Science and Technology), 2026, 66(3): 638-650. (in Chinese)
[5] 姚恩建, 马斯玮, 向镇, 等. 面向铁路夜间乘客疏散的定制公交线路优化[J]. 北京交通大学学报, 2021, 45(1): 78-84. YAO E J, MA S W, XIANG Z, et al. Optimization of customized bus routes for evacuation of railway passengers arriving at night [J]. Journal of Beijing Jiaotong University, 2021, 45(1): 78-84. (in Chinese)
[6] 陈汐, 王印海, 刘剑锋, 等. 多区域通勤定制公交线路规划模型及求解算法[J]. 交通运输系统工程与信息, 2020, 20(4): 166-172. CHEN X, WANG Y H, LIU J F, et al. Multi-region commuting bus route design model and solution method[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(4): 166-172. (in Chinese)
[7] LI W G, ZHENG L J, LIAO L Q, et al. A multiline customized bus planning method based on reinforcement learning and spatiotemporal clustering algorithm[J]. IEEE Transactions on Computational Social Systems, 2024, 11(3): 3691-3705.
[8] ZHAO R, XU X D, CHEN A. Alternative method of counting the number of efficient paths in a transportation network[J]. Transportmetrica A: Transport Science, 2022, 18(3): 1207-1233.
[9] JI W, LIU S L, HAN K, et al. The share-a-ride problem with mixed ride-hailing and logistic vehicles[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 192: 103758.
[10] MA Y, SCHMÖCKER J D, SUN W Z, et al. Unravelling route choices of large trucks using trajectory clustering and conditional Logit models[J]. International Journal of Transportation Science and Technology, 2025, 17: 238-250.
[11] MARUHASHI J, GREWE V, FRÖMMING C, et al. Transport patterns of global aviation NOx and their short-term O3 radiative forcing-a machine learning approach[J]. Atmospheric Chemistry and Physics, 2022, 22(21): 14253-14282.
[12] 胡昕源, 谢磊, 常吉亮, 等. 改进QuickBundles算法在船舶轨迹聚类中的应用[J]. 中国航海, 2023, 46(3): 145-152. HU X Y, XIE L, CHANG J L, et al. Application of improved QuickBundles algorithm in ship trajectory clustering[J]. Navigation of China, 2023, 46(3): 145-152. (in Chinese)
[13] MA D F, FANG B, MA W H, et al. Potential routes extraction for urban customized bus based on vehicle trajectory clustering[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(11): 11878-11888.
[14] ZHANG D Z, LEE K, LEE I. Hierarchical trajectory clustering for spatio-temporal periodic pattern mining[J]. Expert Systems with Applications, 2018, 92: 1-11.
[15] MONNIER L, TRAONOUEZ L M, TIT K. TS-SCAN: A density- based clustering method for trajectory analysis and anomaly detection[C]// 2024 International Radar Conference (RADAR). Rennes, France: IEEE, 2024: 1-5.
[16] CISCAL-TERRY W, DELL’AMICO M, HADJIDIMITRIOU N S, et al. An analysis of drivers route choice behaviour using GPS data and optimal alternatives[J]. Journal of Transport Geography, 2016, 51: 119-129.
[17] YEN J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716.
[18] GARYFALLIDIS E, BRETT M, CORREIA M M, et al. QuickBundles, a method for tractography simplification[J]. Frontiers in Neuroscience, 2012, 6: 175.
[19] CHEN J Y, WANG R D, LIU L X, et al. Clustering of trajectories based on Hausdorff distance[C]// 2011 International Conference on Electronics, Communications and Control (ICECC). Ningbo, China: IEEE, 2011: 1940-1944.
[20] PAN Z Y, LIANG Y X, WANG W F, et al. Urban traffic prediction from spatio-temporal data using deep meta learning[C]// Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Anchorage, USA: ACM, 2019: 1720-1730.
[21] LUAN X J, EIKENBROEK O A L, CORMAN F, et al. Passenger social rerouting strategies in capacitated public transport systems [J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 188: 103598.
[22] ALONSO-MORA J, SAMARANAYAKE S, WALLAR A, et al. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment[J]. Proceedings of the National Academy of Sciences of the United States of America, 2017, 114(3): 462-467.
[23] SANTI P, RESTA G, SZELL M, et al. Quantifying the benefits of vehicle pooling with shareability networks[J]. Proceedings of the National Academy of Sciences of the United Sates of America, 2014, 111(37): 13290-13294.
[24] 李晶. 城市定制公交潜在线路提取和设计方法研究[D]. 北京: 北京交通大学, 2020. LI J. Research on the extraction and designing method of potential routes for urban customized bus[D]. Beijing: Beijing Jiaotong University, 2020. (in Chinese)
[25] 吴祥国, 姜洋, 张汝华, 等. 快速公交站点步行吸引范围研究[J]. 交通信息与安全, 2011, 29(3): 36-39. WU X G, JIANG Y, ZHANG R H, et al. Pedestrian catchment area of bus rapid transit stations[J]. Journal of Transport Information and Safety, 2011, 29(3): 36-39. (in Chinese)
[26] LYU Y, CHOW C Y, LEE V C S, et al. T2CBS: Mining taxi trajectories for customized bus systems[C]// 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). San Francisco, USA: IEEE, 2016: 441-446.
[27] 唐莹. 通勤定制公交站线规划研究[D]. 北京: 北京交通大学, 2022. TANG Y. Study on stops and routes planning of customized commuter bus[D]. Beijing: Beijing Jiaotong University, 2022. (in Chinese)
[28] 吴冰冰, 魏铌邦. 青岛早报数字报:公交“瘦身”将迎6米“最短”车身[EB/OL]. (2024-09-24) [2026-02-26]. https://epaper.qingdaonews.com/qdzb/html/2024-09/24/content_144794_1321401.htm. WU B B, WEI N B. Digital Qingdao Morning Post: Bus "slimming" to feature6-meter "shortest" body length[EB/OL]. (2024-09-24) [2026-02-26]. https://epaper.qingdaonews.com/qdzb/html/2024-09/24/content_144794_1321401.htm. (in Chinese)
[29] LIU T, YOU H L, GKIOTSALITIS K, et al. Human-machine collaborative decision-making approach to scheduling customized buses with flexible departure times[J]. Transportation Research Part A: Policy and Practice, 2024, 187: 104184.
[30] JIN F L, AN K, YAO E J. Mode choice analysis in urban transport with shared battery electric vehicles: A stated-preference case study in Beijing, China[J]. Transportation Research Part A: Policy and Practice, 2020, 133: 95-108.
PDF(4956 KB)

Accesses

Citation

Detail

Sections
Recommended

/

〈 〉