## 4 Review of Literature
### Ridesharing Problem
#### 4.1.2 Heuristic and Metaheuristic Algorithms
[51] proposed a modified pickup and delivery problem with time windows for ridesharing. An insertion heuristic with Tabu Search (Distance-Tabu) for objective of minimising the distance and an insertion heuristic with Tabu Search (Congestion-Tabu) for objective of minimising the congestion function are developed to solve the studied problem. The Adjust Pickup Time Algorithm is applied in each scenario. It considered HOV (High Occupancy Vehicle) lanes and the policy to reduce the toll rates on HOVs (High Occupancy Vehicles) in minimising the travel time and cost by having vehicles with more passengers. A mixed-integer model for passenger matching and vehicle routing problem in the first-mile ridesharing service was formulated by [52]. The main objective of the study is to minimise the total transportation cost. To achieve computational efficiency, Simulated Annealing (SA) with four neighbourhood structures, a metaheuristic algorithm, is applied to solve the proposed large-scale problem. Moreover, the authors of [53] considered the characteristics of pickup and drop-off congestion in developing a flow-dependent version of a ride-matching and routing optimisation model to maximise the average loading ratio of the entire system. To address the complexity of the problem, a large neighbourhood search heuristic is established to improve the solution efficiency. In the work in [54], the authors formulated a mathematical model to design an enhanced ridesharing system which considered both the meet points and time window. A tabu-based metaheuristic algorithm is used to solve the Mixed Integer Linear Programming (MILP) on an enhanced ridesharing system. The CPLEX solution is used as the benchmark to validate the performance of the tabu-based metaheuristic algorithm. The detailed assignment of the passenger to the meet point can reduce the en-route delay and save the travel time for a small-scale ridesharing system. For the study in [55], a concept of space-time window is introduced by formulating an on-demand ridesharing problem for the pickup and delivery problem with space-time windows. A customised solution approach based on the Lagrangian relaxation algorithm is developed to solve the model. The proposed algorithm incorporates a decomposition approach which decomposes the problem into the shortest path problem and knapsack problem that could be solved easily. Furthermore, the authors of [56] introduced two-sided matching in building a single-driver multiple-rider ridesharing problem with consideration of a system-wide optimal and stable matching. The recursive algorithm and a delete operator are proposed as the solution method in solving the ridesharing model. The recursive algorithm plays an important role in searching feasible rider sets and transforming them into a series of feasible sets. Next, the delete operator is employed to reduce the size of the feasible decision region to further improve the model computational speed. The results show that the proposed algorithm can provide high stability in the ride-matching solutions, albeit with a small sacrifice in terms of the system-wide performance. A detour-based discounting mechanism for the first-mile ridesharing problem was designed by the authors of [57] to encourage more passengers to use public transit. The first-mile ridesharing problem is a multiple-rider, multiple-driver system. The proposed mechanism allows passengers to have their preference on different inconvenience attributes in determining optimal vehicle-passenger matching, along with a vehicle routing plan and customised pricing scheme. In [58], the authors also proposed a Solution Pooling Approach (SPA) to significantly decrease the computational complexity with minimal sacrifice of the quality of the solution. A ridesharing problem is formulated into a global optimisation task that schedules the requests for multiple vehicles [59]. An efficient Parallel Scheme with Simulated Annealing(PCSA) is developed to handle the matching and routing of these requests.