检索结果-内蒙古大学图书馆

Towards an Optimal bus frequency scheduling: When the Waiting Time Matters

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第9期34卷 4484-4498页

作者： Mo, Songsong Bao, Zhifeng Zheng, Baihua Peng, Zhiyong Wuhan Univ Sch Comp Sci Wuhan 430000 Hubei Peoples R China RMIT Univ Comp Sci & Informat Technol Melbourne Vic 3000 Australia Singapore Management Univ Singapore 178902 Singapore

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers' average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based (1 - 1/e)(1 - 1/e)-approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a (1 - rho)(1 - 1/e)(1 -rho)(1 - 1/e) approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a (1 - rho)(1 - 1/e - epsilon)(1 - rho)(1 - 1/e - epsilon) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively.

关键词： bus frequency scheduling optimization user waiting time minimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

bus frequency optimization: When Waiting Time Matters in User Satisfaction 25th

Bus Frequency Optimization: When Waiting Time Matters in Use...

引用

25th International Conference on Database Systems for Advanced Applications (DASFAA)

作者： Mo, Songsong Bao, Zhifeng Zheng, Baihua Peng, Zhiyong Wuhan Univ Sch Comp Sci Wuhan Hubei Peoples R China RMIT Univ Melbourne Vic Australia Singapore Management Univ Singapore Singapore

ISBN: (纸本)9783030594152;9783030594169

Reorganizing bus frequency to cater for the actual travel demand can save the cost of the public transport system significantly. Many, if not all, existing studies formulate this as a bus frequency optimization problem which tries to minimize passengers' average waiting time. However, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold is maximized. We prove that this problem is NP-hard, and present an index-based algorithm with (1 - 1/e) approximation ratio. By exploiting the locality property of routes in a bus network, we propose a partition-based greedy method which achieves a (1 - rho)(1 - 1/e) approximation ratio. Then we propose a progressive partition-based greedy method to further improve the efficiency while achieving a (1 - rho)(1 - 1/e - epsilon) approximation ratio. Experiments on a real city-wide bus dataset in Singapore verify the efficiency, effectiveness, and scalability of our methods.

关键词： bus frequency scheduling optimization User waiting time minimization Approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：