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.


Original document

The different versions of the original document can be found in:

http://dx.doi.org/10.1109/tkde.2015.2509998
http://dx.doi.org/10.1109/icde.2017.36
https://ieeexplore.ieee.org/document/7929932,
http://ieeexplore.ieee.org/document/7929932,
https://doi.org/10.1109/ICDE.2017.36,
https://academic.microsoft.com/#/detail/2616071153
https://ieeexplore.ieee.org/document/7360162,
https://dl.acm.org/citation.cfm?id=2925263.2925381,
https://doi.org/10.1109/TKDE.2015.2509998,
http://ieeexplore.ieee.org/document/7360162,
https://vbn.aau.dk/da/publications/collective-travel-planning-in-spatial-networks-2,
https://vbn.aau.dk/da/publications/collective-travel-planning-in-spatial-networks(9ccf911f-5432-4675-8b85-3f82f40299d0).html,
https://www.computer.org/csdl/trans/tk/2016/05/07360162.html,
https://academic.microsoft.com/#/detail/2313076811
https://doi.org/10.1109/TKDE.2015.2509998
https://doi.org/10.1109/ICDE.2017.36,
http://www.scopus.com/inward/record.url?scp=85021196794&partnerID=8YFLogxK


DOIS: 10.1109/icde.2017.36 10.1109/tkde.2015.2509998

Back to Top

Document information

Published on 01/01/2016

Volume 2016, 2016
DOI: 10.1109/icde.2017.36
Licence: CC BY-NC-SA license

Document Score

0

Views 0
Recommendations 0

Share this document

claim authorship

Are you one of the authors of this document?