## 4 Review of Literature
### Ridesharing Problem
#### 4.1.2 Heuristic and Metaheuristic Algorithms
In PCSA, the move generation and move control technique can avoid unnecessary perturbation and focus on optimising the existing schedule to better improve the efficiency of the SA. The proposed PCSA utilised an efficient domain decomposition and merging paradigm to reduce the domain into small independent sub-domains to speed up the parallelisation. Afterwards, the mixing of states and a parallel scheme for SA are further applied to increase the parallel efficiency and scalability. Throughout the simulation, the results showed that PCSA is suitable for solving the ridesharing problem with strong spatial constraints within a short amount of computational time. The First Mile (FM) problem refers to the transportation connection between the passengers' homes and transportation hubs such as railway station and bus terminals. Feeder buses and on-demand shared mobility services are the key means of transportation in solving the FM problem. However, the demands of feeder buses remain low due to issues related to reliability and cost. Therefore, autonomous vehicles are employed as an alternative form of transportation to serve the FM problem as they greatly enhance accessibility and connectivity. With this in mind, ref. [60] proposed a MILP model for an Autonomous Vehicle (AV)-based dynamic vehicle dispatch and ridesharing schedule to minimise the operational cost for the FM service. The rolling horizon framework is utilised in the model formulation to ensure the efficiency of the fleet operation. A cluster-based solution method is employed to solve the large scale FM problems. The proposed solution method has great potential in speeding up the computational time as it partitions the requests in groups instead of individually before solving them. In the work by [61], they proposed a fair ridesharing route optimisation model which takes both system optimisation and user-fairness into consideration to enhance the rationality of ridesharing. The user-fairness considered in this study allows the users with a long detour to have better discount rates to save on travel cost. Additionally, the model constraints consider the benefits for both drivers and riders in the optimisation to ensure the high demand for the ridesharing service among them. An improved GA in both crossover and mutation operator is used to solve this problem. Many-to-One Ridesharing Problem  
In [62], an intelligent chromosome agent-driven approach is proposed to enhance the performance of the Evolutionary Algorithm in a solution to the multi-hop ride-matching optimisation problem. It can be defined as Autonomous and Intelligent Agents (E2 AIA) where genetic operators will be driven by chromosome agents through a powerful negotiation protocol. E2 AIA remains stable in processing time while there is an increase in the number of users. Overall, E2 AIA can generate ride-matching solutions while minimising the number of required vehicles. Many-to-Many Ridesharing Problem  
A dynamic multi-hop ride-matching problem is introduced and solved using a meta-heuristic approach based on controlled genetic operators [63]. Apart from the ridesharing system that featured meeting points and multiple hops, in [64] a multi-hop ridesharing system that incorporates meeting points is proposed. The authors also introduce another feature called \"return restrictions together\" with a backup transportation service in allowing a closed corporate community to participate in ridesharing. To overcome the complexity and real-time aspect of the dynamic carpooling optimisation system (DyCOS), in [65] proposed a Tabu Search (TS) i proposed that employs an explicit memory system with several searching strategies to make optimal decisions automatically. To ensure high-quality solutions, DyCOS adopted detour and transfer concepts. In the ridesharing problem, a driver has to pick up multiple riders. Therefore, they have to visit several different locations and end their journey at the final destination.