## 4 Review of Literature
### Taxisharing Problem
#### 4.3.2 Heuristic and Metaheuristic Algorithms  
One-to-One Taxisharing Problem  
One of the popular cases of taxi ridesharing is Taxi Group Ride (TGR), where group users with trips of similar origin and destination are grouped into a single ride. In [92] two essential problems in the implementation of TGR are investigated. The optimal assignment of a set of riders to vehicles is the first problem to be tackled when trying to minimise total saved travel miles. Through the assignment of requests, different behaviours of passengers and drivers in participating taxi group rides are investigated to find out the best incentives for TGR to maximise efficiency. The optimal assignment problem is formulated as an ILP problem and further converted into an equivalent graph problem. An exact algorithm and a heuristic algorithm are used to solve the problem. One-to-Many Taxisharing Problem  
In general, most of the long-term carpool problems are lacking practicality, veracity and efficiency. A dynamic shared-taxi dispatch system is suggested and solved by a Hybrid-SA (HSA) to improve passenger travel by utilising vehicle resources more efficiently [93]. In [94], a vehicle routing problem of ridesharing taxi is proposed and formulated as a route optimisation model. The minimisation of operation cost and maximisation of customer satisfaction are the main aims in this model and a SA is presented to solve the model. Taxisharing can minimise the instances of vacant seats in cars and thus reduce the costs imposed on taxi drivers. This results in lower taxi fares for passengers. Hence, to promote the sharing of taxisharing concept, ref. [90] formulated the problem of assigning passengers to taxis with the rideshare concept as a MIP. Instead of solving the problem solely on the Lagrangian decomposition approach, two heuristic algorithms are proposed to obtain a better-quality feasible solution. A simple heuristic and Incremental Cost Heuristic (ICH) algorithm are utilised to find the feasible solution which gives a lower bound on the optimal objective. Moreover, in [95] a route optimisation model is formulated for taxisharing with a multi-objective function instead of a common taxi problem. The considered objectives are (1) the minimisation of total ridesharing fare of riders, (2) the total ridesharing travelling time of riders, and (3) the total fuel charge for drivers. Overall, the results can further improve the income of drivers and allow passengers to enjoy low fares in taxi ridesharing. The NSGA-II is designed to solve the taxi ridesharing route multi-objective optimisation problem. Looking at the work in [96], both a single-objective and multi-objective taxi pooling path optimisation problem are presented. In a single-objective optimisation problem, the minimisation of distance is considered as the objective and it is solved by a single objective GA. In a multi-objective optimisation problem, the minimisation of travel distance and time are the considered multiple objectives. This model is solved by an improvedMultiple-Objective Genetic Algorithm (MOGA) to obtain a Pareto optimal solution set. The improved MOGA is designed using a different aspect as compared to the common MOGA. In constructing aaPato optimal solution set, the improved multi-objective algorithm adopted the Banker Principle. Crowding density is used to keep the distributivity of improved groups. In term of genetic manipulation, the proposed MOGA designed a kind of pertheno-exchange operator and pertheno ortho-position exchange operator to replace the traditional crossover and mutation operators. There is little literature that focuses on the analysis of the city-scale. Therefore, [PERSON] and [PERSON] [97] presented a vehicle-arc formulation for taxi pooling to study the impacts of taxi-pooling operations in an urban city with real-world taxi trip data from Washington, D.C. The main objective of this study is to minimise the system-wide vehicle miles travelled. The insertion heuristic algorithm is the proposed fast heuristic algorithm used to solve the problem.