## 4 Review of Literature
### Taxisharing Problem
#### 4.3.2 Heuristic and Metaheuristic Algorithms
The proposed algorithm did not yield the optimal solution with the most cost savings over several iterations. However, it greatly improved the computation speed needed to compute the solution. Due to concerns over the scarcity of energy and air pollution, the usage of shared electric vehicles has received great attention among governments and automobile companies. However, there is a problem of inefficient usage of a shared ridership of these electric vehicles. For example, the case where there are two different user requests that might have overlapping origin and destination. Without the rideshare concept, two vehicles might be needed to meet the requests. However, with the utilisation of the rideshare concept, this waste can be avoided as one vehicle can fulfil both requests at the same time. Thus, there is a need to study the mode of Shared Electric Vehicles with Ridesharing (MSEVRS) [98]. The routing optimisation model of MSEVRS is proposed with the inclusion of operational cost, user time cost, user rental cost, and user ridesharing bonus. Throughout the experiment with GA, it appears that the proposed MSEVRS can efficiently reduce the system-wide vehicle mile travelled as compared to the current shared electric vehicles mode (without a rideshare concept). Furthermore, the authors of [99] established a route optimisation model and sharing expenses model for taxisharing that considered vehicles loading rate, riders cost, and distance traveled. Based on the taxi route optimisation model, the passenger pool station operation mode is employed to allocate the number of taxis according to the number of riders at different locations and directions. An improved MOGA is used in the study to obtain the feasible solution of the taxisharing optimisation models. The Station coding and decoding design before the initialisation process as well as the championship operator design before the crossover and mutation operator are the new elements that were included in the improved MOGA. For the many-to-many taxisharing problem, the work in [100] proposes a dynamic Taxi Sharing with Time Window Problem (TSTWP) to maximise the number of matched rides and minimise the cost of the riders. The proposed TSTWP can be extended to a ridesharing model for car owners, or even both taxis and car owners, to share their vehicles to reduce the cost of the trip. Since TSTWP is a static version of the problem, the Greedy Randomised Adaptive Search Procedure (GRASP) is presented to solve it. Later, ref. [101] introduced the Dial-A-Ride Problem with Money (DARP-M) as an incentive that considered cost restrictions. This is a combinatorial optimisation problem that represents the realistic situations of ridesharing and taxisharing where there are taxis and car owners who want to reduce trip costs by sharing their vehicles. The considered criteria are the maximisation of the number of served requests and the minimisation of the sum of the costs of all served requests. Real data are used to create instances for both the dynamic and static problem. In terms of solution methods, a new GRASP heuristic with path re-linking technique and Contraction Hierarchy (CH) algorithm are proposed to solve both the static and dynamic problem respectively. Throughout the experiments, it is shown that the path re-linking technique can greatly improve the performance of the GRASP heuristic. Moreover, the performance of the CH algorithm is far better than the Dijkstra algorithm in handling the dynamic problem. One Origin-Multi Destinations Taxisharing Problem  
A multiobjective taxisharing problem from the passengers' viewpoint is formulated with consideration of the total cost of the trips and the total delay experienced by each passenger [102]. Two MOEAs are applied to find the solution to the proposed problem. One of the MOEAs possessed a decomposition algorithm. Other MOEAs, known as NSGA-II, had an explicit multi-objective Pareto-based fitness assignment. Execution time, convergence and diversity are considered to evaluate the performance of the algorithms.