Abstract:
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 thesis, 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.
