## 4 Review of Literature
### Carpooling Problem
#### 4.2.2 Heuristic and Metaheuristic Algorithms
In 2015, an ICS based on a service-oriented architecture was proposed and solved using a fuzzy controlled genetic-based carpool algorithm [82]. The fuzzy controlled genetic-based carpool algorithm is a combined approach of the GA and a fuzzy control system. Moreover, in [83] a heuristic multi-objective optimisation algorithm is proposed to solve carpool service problem featured high-occupancy-vehicle itineraries. This approach takes into consideration the enhancement of vehicular space occupancy for each portion of the ridesharing itinerary involving multiple objectives. The proposed approach is a NSGAII which is a combination of the heuristic search operation and the multi-objective individual selection. In carpooling, neither drivers nor riders are willing to wait for one and another, especially in real-world situations. By introducing both appearance time and endurance time into the existing Carpool Service Problem (CSP), the CSP is transformed into a Carpool Service Problem with Time Window (CSPTW) [84]. An Ant Path-oriented Carpooling Allocation approach (APCA) is employed to solve the CSPTW. Furthermore, [PERSON] and [PERSON] [72] proposed a new mathematical model for carpooling with consideration of the cost of travel times, vehicle use, and vehicle delays. Due to the NP-hard characteristic of the problem, an exact algorithm can guarantee an optimal solution in a small-scale problem. The optimal solution cannot be obtained in a reasonable time, especially in solving for a large-scale NP-hard problem. Hence, a heuristic beam search is further introduced to solve large-scale problems. The proposed heuristic beam search algorithm allows a trade-off between optimality and solving time to achieve better results using shorter computational time. In the existing carpooling models, a 2-person carpool team is much more common than the 3+ person carpool team. Due to its complexity, a 3+ person carpooling solution is not generally available. It is undeniable that 3+ person carpooling is more effective in traffic management as compared to a 2-person carpooling model. Thus, in [85] two heuristics based on SA and TS are presented to solve the network-based carpool matching model for a 3+ person home-to-work carpooling problem. Many-to-One Carpooling Problem  
Ref. [86] proposed a particle swarm carpool algorithm (PSCA) based on stochastic set-based PSO to solve the CSP which is formulated as a discrete optimisation problem. The main objective of the CSP is to maximise the matched rides to drivers, while the secondary objectives are the maximisation of evaluation scores to all driver-rider matches, minimisation of average driver travel distance, minimisation of the average rider waiting distance, and the minimisation of the average rider travel distance. In the computational analysis, the performance of the PSCA is compared with Binary PSO and GA based on the benchmarks of a metropolitan area with actual transportation movement. Throughout the nonparametric statistical test, PSCA is proven to be superior in solving the objectives of the CSP. Multiple Origins-One Destination Carpooling Problem  
A new variant of LTCPP which involved multiple origins and one destination is introduced in [87]. The proposed carpooling problem involved a two-stage IP formulation. The first stage is the formulation of the driver selection and passenger assignment problem and the shortest path problem is the second stage of the problem formulation. A stochastic TS algorithm is proposed to solve the problem. In the work of [88], they proposed an Artificial Bee Colony algorithm combining a Variable Neighbour Search and Tabu List (ABC-VNSTL) to solve LTCPP with a time window. One Origin-Multiple Destinations Carpooling Problem  
A Multi-destination Daily Car Pooling Problem (MDCPP) with consideration of transfer point is presented in [89]. The transfer point allows two drivers to meet at an intersection point where the carpoolers can change vehicles to decrease the length of the detour the drivers have to make.