Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/TKDE.2015.2509998 | IEEE Trans. Knowl. Data Eng. |
Keywords | DocType | Volume |
Approximation algorithms,Approximation methods,Planning,Roads,Green products,Spatial databases | Conference | 28 |
Issue | ISSN | Citations |
5 | 1041-4347 | 33 |
PageRank | References | Authors |
0.97 | 14 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shang Shuo | 1 | 384 | 25.35 |
| lisi chen | 2 | 452 | 25.06 |
| Zhewei Wei | 3 | 215 | 20.07 |
| Christian S. Jensen | 4 | 10651 | 1129.45 |
| Ji-Rong Wen | 5 | 4431 | 265.98 |
| Panos Kalnis | 6 | 3297 | 141.30 |