Finding Least Cost Travel Route Using unconstrained CTP Query- A Survey

Abstract

Nowadays, many travelers targeting the same destination, using their own transport that causes traffic and pollution problems to the environment. To avoid those problems they may assemble at meeting points and can collectively use public or private transport to the destination which can also reduce the global travel cost like energy, money etc... This will benefit the society and the environment. Some existing multi-source trip planning queries like group nearest neighbor query, group trip planning query aims to reduce all the travelers global travel cost by assuming that each traveler goes to the destination individually and do not take collective travel into account. Existed Collective travel planning (CTP) query is used to find the minimum cost path that connects multiple sources and a destination via at most k meeting points. The query is designed for ride sharing by a large population of travelers going to the same destination. I propose a CTP query without k constraint. The query then finds the least cost travel route connecting multiple sources and a destination via unconstrained meeting points. This can be possible by designing an algorithm with a suitable approximation ratio to compute the query in interactive time.
Index terms: — CTP, approximation ratio; group trip planning query; group nearest neighbor query; multi-source trip planning queries;