论文标题
总线频率优化：等待时间在用户满意度上很重要
Bus Frequency Optimization: When Waiting Time Matters in User Satisfaction
论文作者
论文摘要
重组公交频率以满足实际旅行需求可以大大节省公共交通系统的成本。现有研究（即使不是全部）将其作为总线频率优化问题，该问题试图最大程度地减少乘客的平均等待时间。但是，许多调查已经证实，随着等待时间的增加，用户满意度下降了速度。因此，考虑用户满意度考虑到总线频率优化问题。具体而言，据我们最大的知识，我们首次研究了如何安排公共汽车，以便最大化可以在等待时间阈值之内获得公共汽车服务的乘客总数。我们证明了这个问题是NP-HARD，并以$（1-1/e）$近似值率提供了基于索引的算法。通过利用总线网络中路由的局部性属性，我们提出了一种基于分区的贪婪方法，该方法可实现$（1-ρ）（1-1/e）$近似值。然后，我们提出了一种基于渐进式分区的贪婪方法，以进一步提高效率，同时达到$（1-ρ）（1-1/e- \ varepsilon）$近似值。在新加坡的真实城市范围内的总线数据集进行的实验验证了我们方法的效率，有效性和可扩展性。
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-ρ)(1-1/e)$ approximation ratio. Then we propose a progressive partition-based greedy method to further improve the efficiency while achieving a $(1-ρ)(1-1/e-\varepsilon)$ approximation ratio. Experiments on a real city-wide bus dataset in Singapore verify the efficiency, effectiveness, and scalability of our methods.
