Collective Travel Planning in Spatial Networks

摘要: Travel planning and recommendation are important aspects of transportation. We propose investigate a novel Collective Planning (CTP) query that finds the lowest-cost route connecting multiple sources destination, via at most $k$ meeting points. When travelers target same destination (e.g., stadium or theater), they may want to assemble points then go together by public transport reduce their global travel cost energy, money, greenhouse-gas emissions). This type functionality holds potential bring significant benefits society environment, such as reducing energy consumption emissions, enabling smarter greener transportation, traffic congestions. The CTP is Max SNP-hard. To compute efficiently, we develop two algorithms, including an exact algorithm approximation algorithm. capable finding optimal result for small values $k = 2$ ) in interactive time, while algorithm, which has $5$ -approximation ratio, suitable other situations. performance studied experimentally with real synthetic spatial data.