  Recently, with the advancement of the GPS-enabled cellular technologies, the
location-based services (LBS) have gained in popularity. Nowadays, an
increasingly larger number of map-based applications enable users to ask a
wider variety of queries. Researchers have studied the ride-sharing, the
carpooling, the vehicle routing, and the collective travel planning problems
extensively in recent years. Collective traveling has the benefit of being
environment-friendly by reducing the global travel cost, the greenhouse gas
emission, and the energy consumption. In this paper, we introduce several
optimization problems to recommend a suitable route and stops of a vehicle, in
a road network, for a group of users intending to travel collectively. The goal
of each problem is to minimize the aggregate cost of the individual travelers'
paths and the shared route under various constraints. First, we formulate the
problem of determining the optimal pair of end-stops, given a set of queries
that originate and terminate near the two prospective end regions. We outline a
baseline polynomial-time algorithm and propose a new faster solution - both
calculating an exact answer. In our approach, we utilize the path-coherence
property of road networks to develop an efficient algorithm. Second, we define
the problem of calculating the optimal route and intermediate stops of a
vehicle that picks up and drops off passengers en-route, given its start and
end stoppages, and a set of path queries from users. We outline an exact
solution of both time and space complexities exponential in the number of
queries. Then, we propose a novel polynomial-time-and-space heuristic algorithm
that performs reasonably well in practice. We also analyze several variants of
this problem under different constraints. Last, we perform extensive
experiments that demonstrate the efficiency and accuracy of our algorithms.
