期刊
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
卷 28, 期 5, 页码 1132-1146出版社
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2015.2509998
关键词
Collective travel planning; location based services; spatial networks; spatial databases
类别
资金
- National Natural Science Foundation of China (NSFC) [61402532]
- Science Foundation of China University of Petroleum-Beijing [2462013YJRC031]
- Excellent Talents of Beijing Program [2013D009051000003]
- Beijing Nova Program
- DiCyPS center - Innovation Fund Denmark
Travel planning and recommendation are important aspects of transportation. We propose and investigate a novel Collective Travel Planning (CTP) query that finds the lowest-cost route connecting multiple sources and a destination, via at most k meeting points. When multiple travelers target the same destination (e.g., a stadium or a theater), they may want to assemble at meeting points and then go together to the destination by public transport to reduce their global travel cost (e.g., energy, money, or greenhouse-gas emissions). This type of functionality holds the potential to bring significant benefits to society and the environment, such as reducing energy consumption and greenhouse-gas emissions, enabling smarter and greener transportation, and reducing traffic congestions. The CTP query is Max SNP-hard. To compute the query efficiently, we develop two algorithms, including an exact algorithm and an approximation algorithm. The exact algorithm is capable finding the optimal result for small values of k (e.g., k = 2) in interactive time, while the approximation algorithm, which has a 5-approximation ratio, is suitable for other situations. The performance of the CTP query is studied experimentally with real and synthetic spatial data.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据