Collective Travel Planning in Spatial Networks

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

• https://repository.kaust.edu.sa/bitstream/10754/592626/1/07360162.pdf

• https://repository.kaust.edu.sa/bitstream/10754/624983/1/ID_693_ICDE_TKDE_Poster.pdf

• http://xplorestaging.ieee.org/ielx7/69/7445292/07360162.pdf?arnumber=7360162,

http://dx.doi.org/10.1109/tkde.2015.2509998

• http://xplorestaging.ieee.org/ielx7/7929494/7929895/07929932.pdf?arnumber=7929932,

http://dx.doi.org/10.1109/icde.2017.36

• https://dblp.uni-trier.de/db/conf/icde/icde2017.html#ShangCWJWK17,

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://dblp.uni-trier.de/db/journals/tkde/tkde28.html#ShangCWJWK16,

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://vbn.aau.dk/da/publications/9ccf911f-5432-4675-8b85-3f82f40299d0,

https://doi.org/10.1109/TKDE.2015.2509998

• https://vbn.aau.dk/da/publications/ae33669d-14b4-4f6c-8a2e-5620b8359590,

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