From Ride-Sourcing to Ride-Sharing through Hot-Spots

Smartphones have allowed us to make ad-hoc travel arrangements. Ride-sharing is emerging as one of the new types of transportation enabled by smartphone revolution. Ride-sharing aims to alleviate current environmental, social and economical issues many big cities are facing due to low vehicle occupancy rates. Although ridesharing companies have millions of users around the world, some of them do not offer true ride-sharing but a similar service called ride-sourcing where private car owners provide for-hire rides. Ridesharing uptake has not been wide due to lack of convenience and incentives. We propose an enhanced ride-sharing model through the inclusion of proper places to meet that we call hot-spots. Hot-spots are shown to increase the convenience by solving the round-trip ride-sharing problem. As we represent our enhanced model through graphs, we introduce a new graph problem that we call Constrained Variable Steiner Tree, which is NP-hard. An effective and readily deployable heuristic solution to this problem is presented which is up to two orders of magnitude faster than the state-of-the-art solution as combinatorial explosion is avoided by the usage of a novel monotonic nondecreasing function.