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 <inline-formula><tex-math notation="LaTeX">k</tex-math> <inline-graphic xlink:type="simple" xlink:href="shang-ieq1-2509998.gif"/> </inline-formula> 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 <inline-formula><tex-math notation="LaTeX">k</tex-math> <inline-graphic xlink:type="simple" xlink:href="shang-ieq2-2509998.gif"/> </inline-formula> (e.g., <inline-formula><tex-math notation="LaTeX"> k = 2</tex-math> <inline-graphic xlink:type="simple" xlink:href="shang-ieq3-2509998.gif"/> </inline-formula>) in interactive time, while the approximation algorithm, which has a <inline-formula><tex-math notation="LaTeX"> 5</tex-math> <inline-graphic xlink:type="simple" xlink:href="shang-ieq4-2509998.gif"/> </inline-formula>-approximation ratio, is suitable for other situations. The performance of the CTP query is studied experimentally with real and synthetic spatial data.