Dynamic Clustering Meeting Points Strategy to Improve Operational Service Capability of Flex-Route Transit
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 149, Issue 6
Abstract
To improve the operational service capability of flex-route transit under the condition of uncertain and inhomogeneous passenger travel demand, a dynamic meeting points optimization solution is proposed. This solution can set dynamic pickup and drop-off meeting points according to real-time travel demand. The flex-route transit operation mode is described in detail and is divided into a two-stage optimization problem. Mixed integer programming is employed to formulate the problem with a twofold objective—(1) serve as many requests as possible; and (2) minimize the time cost of the accepted passengers. An improved memetic solution algorithm is proposed for the model constructed. Computational results based on real-world cases show that the dynamic clustering meeting points solution breaks the space constraints of the original pickup and drop-off points of passengers and can significantly reduce the proportion of passenger reservation requests rejected without increasing operation cost.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
All data, models, and code generated or used during the study appear in the published article.
Acknowledgments
This research was supported by National Key Research and Development Program in China (Grant No. 2018YFB1601001) and the National Natural Science Foundation of China (Grant No. 52272319).
References
Altman, N. S. 1992. “An introduction to kernel and nearest-neighbor nonparametric regression.” Am. Stat. 46 (3): 175–185. https://doi.org/10.1080/00031305.1992.10475879.
Becker, J., R. Teal, and R. Mossige. 2013. “Metropolitan transit agency’s experience operating general-public demand-responsive transit.” Transp. Res. Rec. 2352 (1): 136–145. https://doi.org/10.3141/2352-16.
Crainic, T. G., F. Errico, F. Malucelli, and M. Nonato. 2012. “Designing the master schedule for demand-adaptive transit systems.” Ann. Oper. Res. 194 (1): 151. https://doi.org/10.1007/s10479-010-0710-5.
Ester, M., H. P. Kriegel, J. Sander, and X. Xu. 1996. “A density-based algorithm for discovering clusters in large spatial databases with noise.” In Vol. 96 of Proc., 2nd Int. Conf. on Knowledge Discovery and Data Mining, 226–231. Trier, Germany: The DBLP Computer Science Bibliography.
Farwell, R., and E. Marx. 1996. “Planning, implementation, and evaluation of Omniride demand-driven transit operations: Feeder and flex-route services.” Transp. Res. Rec. 1557 (1): 1–9. https://doi.org/10.1177/0361198196155700101.
Fischetti, M., J. J. Salazar-González, and P. Toth. 1997. “A branch-and-cut algorithm for the symmetric generalized traveling salesman problem.” Oper. Res. 45 (3): 378–394. https://doi.org/10.1287/opre.45.3.378.
Fittante, S. R., and A. Lubin. 2015. “Adapting the Swedish service route model to suburban transit in the United States.” Transp. Res. Rec. 2563 (1): 52. https://doi.org/10.3141/2536-07.
Gutin, G., and D. Karapetyan. 2010. “A memetic algorithm for the generalized traveling salesman problem.” Nat. Comput. 9 (1): 47–60. https://doi.org/10.1007/s11047-009-9111-6.
Jiao, L. 2015. “Urban land density function: A new method to characterize urban expansion.” Landscape Urban Plann. 139 (7): 26–39. https://doi.org/10.1016/j.landurbplan.2015.02.017.
Kaufman, L., and P. J. Rousseeuw. 1990. Partitioning around medoids (Program PAM). Wiley series in probability and statistics. Hoboken, NJ: Wiley.
Koffman, D. 2004. Operational experiences with flexible transit services: A synthesis of transit practice. Washington, DC: Transportation Research Board.
Laporte, G., and Y. Nobert. 1983. “Generalized travelling salesman problem through n sets of nodes: An integer programming approach.” Inf. Syst. Oper. Res. 21 (1): 61–75. https://doi.org/10.1080/03155986.1983.11731885.
Li, X., and L. Quadrifoglio. 2009. “Optimal zone design for feeder transit services.” Transp. Res. Rec. 2111 (1): 100–108. https://doi.org/10.3141/2111-13.
Paulley, N., R. Balcombe, R. Mackett, J. Preston, and P. White. 2004. “The demand for public transport.” In Proc., World Conf. on Transport Research. Lyon, France: World Conference on Transport Research Society.
Potts, J. F., M. A. Marshall, E. C. Crockett, and J. Washington. 2010. A guide for planning and operating flexible public transportation services. Washington, DC: Transportation Research Board.
Qiu, F., W. Li, and A. Haghani. 2015. “A methodology for choosing between fixed-route and flex-route policies for transit services.” J. Adv. Transp. 49 (3): 496–509. https://doi.org/10.1002/atr.1289.
Qiu, F., W. Li, and J. Shen. 2014a. “Two-stage model for flex-route transit scheduling.” J. Southeast Univ. (Natl. Sci. Ed.) 44 (5): 1078–1084. https://doi.org/10.3969/j.issn.1001-0505.2014.05.036.
Qiu, F., W. Li, and J. Zhang. 2014b. “A dynamic station strategy to improve the performance of flex-route transit services.” Transp. Res. Part C: Emerging Technol. 48 (Nov): 229–240. https://doi.org/10.1016/j.trc.2014.09.003.
Quadrifoglio, L., M. M. Dessouky, and F. Ordóñez. 2008. “Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints.” Eur. J. Oper. Res. 185 (2): 481–494. https://doi.org/10.1016/j.ejor.2006.12.030.
Quadrifoglio, L., M. M. Dessouky, and K. Palmer. 2007. “An insertion heuristic for scheduling mobility allowance shuttle transit (MAST) services.” J. Sched. 10 (1): 25–40. https://doi.org/10.1007/s10951-006-0324-6.
Quadrifoglio, L., R. W. Hall, and M. M. Dessouky. 2006. “Performance and design of mobility allowance shuttle transit services: Bounds on the maximum longitudinal velocity.” Transp. Sci. 40 (3): 351. https://doi.org/10.1287/trsc.1050.0137.
Sales, L. P. A., C. S. Melo, T. O. Bonates, and B. A. Prata. 2018. “Memetic algorithm for the heterogeneous fleet school bus routing problem.” J. Urban Plann. Dev. 144 (2): 04018018. https://doi.org/10.1061/(ASCE)UP.1943-5444.0000454.
Song, X., J. O. Sexton, C. Huang, S. Channan, and J. R. Townshend. 2016. “Characterizing the magnitude, timing and duration of urban growth from time series of Landsat-based estimates of impervious cover.” Remote Sens. Environ. 175 (3): 1–13. https://doi.org/10.1016/j.rse.2015.12.027.
Velaga, N. R., J. D. Nelson, S. D. Wright, and J. H. Farrington. 2012. “The potential role of flexible transport services in enhancing rural public transport provision.” J. Public Transp. 15 (1): 111–131. https://doi.org/10.5038/2375-0901.15.1.7.
Yao, R., and S. Bekhor. 2021. “A dynamic tree algorithm for peer-to-peer ridesharing matching.” Networks Spatial Econ. 21 (4): 801–837. https://doi.org/10.1007/s11067-021-09523-y.
Zhao, J., and M. M. Dessouky. 2008. “Service capacity design problems for mobility allowance shuttle transit systems.” Transp. Res. Part B: Methodol. 42 (2): 135. https://doi.org/10.1016/j.trb.2007.07.002.
Zheng, Y., W. Li, and F. Qiu. 2018. “A slack arrival strategy to promote flex-route transit services.” Transp. Res. Part C: Emerging Technol. 92 (Jul): 442–455. https://doi.org/10.1016/j.trc.2018.05.015.
Zheng, Y., W. Li, F. Qiu, and H. Wei. 2019. “The benefits of introducing meeting points into flex-route transit services.” Transp. Res. Part C: Emerging Technol. 106 (Sep): 98–112. https://doi.org/10.1016/j.trc.2019.07.012.
Zhou, X., J. Xi, Z. Guan, and X. Ji. 2021. “Dispatching design for customized bus of hybrid vehicles based on reservation data.” J. Adv. Transp. 2021 (Dec): 8868291. https://doi.org/10.1155/2021/8868291.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 149 • Issue 6 • June 2023
Copyright
© 2023 American Society of Civil Engineers.
History
Received: Sep 8, 2022
Accepted: Dec 28, 2022
Published online: Mar 27, 2023
Published in print: Jun 1, 2023
Discussion open until: Aug 27, 2023
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
Cited by
- Jin Zhang, Rongrong Guo, Wenquan Li, Research on Dynamic Scheduling and Route Optimization Strategy of Flex-Route Transit Considering Travel Choice Preference of Passenger, Systems, 10.3390/systems12040138, 12, 4, (138), (2024).
- Rongrong Guo, Yan Zheng, Jin Zhang, Jingcai Yu, Wenquan Li, Applicability Analysis of a Line-Based Hybrid Transit System in Different Road Structures, Journal of Transportation Engineering, Part A: Systems, 10.1061/JTEPBS.TEENG-8314, 150, 7, (2024).