## 4 Review of Literature
### Ridesharing Problem
#### 4.1.1 Exact Algorithms  
One-to-One Ridesharing Problem  
A maximum-weight bipartite matching algorithm in solving the single driver-single rider ride-matching problem is proposed by [16]. The limitations of the proposed method are long computational time and omitting the individual preferences. A rolling horizon approach in postponing the finalisation of previously found matches until a deadline set by the users is proposed to maximise the number of participants. In the case of a dynamic ridesharing setting, drivers and riders may reject a match (that fulfills individual cost savings and satisfies the participants' time preferences) if they believe they can establish a better match on their own. In the notation of stability in cooperative game theory, such a pair can be considered as blocking pair. If there are one or more blocking pairs in the matching solution, then it can be called an unstable rideshare matching. To deal with the unstable matching, the authors of [17] proposed an optimisation approach with the notion of stability and several mathematical formulations to establish stable or nearly stable matches. There is also a network partition-based match making \begin{table}
\begin{tabular}{l l l l l} \hline \hline \multirow{2}{*}{**Types**} & \multicolumn{4}{c}{**Problem Variants**} & \multirow{2}{*}{**Data Characteristics**} & \multirow{2}{*}{**Solution Approaches**} \\ \cline{2-2} \cline{4-4}  & **Drivers and Riders (D–R)** & & & **Origins and Destinations (O–D)** & \\ \hline Ridesharing & One-to-One & One Origin–One Destination & Static & Exact Algorithms \\ Carpooling & One-to-Many & One Origin–Multiple Destinations & Stochastic & Heuristic and Metaheuristic \\ Taxsharing & Many-to-One & Multiple Origins–One Destination & Dynamic & Other Algorithms \\ Vanpooling & Many-to-Many & Multiple Origins–Multiple Destinations & & \\ Multi-Modal & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Classification of the Shared Mobility Problem. algorithm proposed by [18] to reduce the size of the search space in finding matches for dynamic ridesharing. The participants' flexibility angle was then researched by [19]. They performed a study to quantify the impact of the participants' flexibility on a single-driver, single-rider ridesharing system. Three different types of participant flexibility, which are (i) matching flexibility, (ii) detour flexibility, and (iii) scheduling flexibility, are considered in this study to identify what types of flexibility can bring better efficiency to the ridesharing system. The study showed that flexibility plays an important role in contributing to the high matching rates, especially in ridesharing systems with low participation rates. P2P ridesharing can be considered as a two-sided (drivers and riders) market in SMP. A mathematical formulation of one-to-one matching in ridesharing systems with role flexibility is formulated to investigate the stability of the model. To achieve stable ridesharing matching, ref. [20] proposed a new market game. In the new market game, a Mixed Integer Programming (MIP) that finds the minimum amount of subsidy required is proposed to stabilise the system. For the solution method, a decomposition-based Lagrangian relaxation algorithm is proposed to obtain a stable solution. Among some of the works using exact algorithms, ref. [21] formulated MIP for one-to-many ridesharing problems with flexible roles and solved this using CPLEX. In [22], they introduced a green ridesharing problem with the consideration of two objectives and named it a Bi-objective Green Ridesharing Problem. It is a nonlinear multi-objective problem with CO\({}_{2}\) emission minimisation and average ride profit maximisation. Furthermore, [PERSON] and [PERSON] [23] later proposed three different ridesharing schemes and two different reformulations of ridesharing constraints that are capable of solving real-time real-world ridesharing problems.