## 4 Review of Literature
### Carpooling Problem
#### 4.2.2 Heuristic and Metaheuristic Algorithms  
One-to-One Carpooling Problem  
Ref. [76] focused on the practical case of the daily carpooling problem (DCPP) in reducing transportation cost and CO2 emissions. The two different formulations of DCPP that are considered in the paper are direct-route DCPP and tree-route DCPP. For the direct-route DCPP, there is a set of routes such that each of them begins at the house and ends at the workplace. Meanwhile, the tree-route DCPP allows employees to drive their vehicle and stop at intermediary points then join a single car from there to their workplaces. Two different heuristic algorithms are proposed. The first heuristic procedure is employed to solve the tree-route DCPP and the second heuristic procedure is utilised to solve the direct-route DCPP. The differences between them are based on the employed local search algorithms. According to the framework of the proposed heuristic algorithm, the solution obtained from constructive heuristic is then passed to two different local search algorithms accordingly. The first local search algorithm is based on a standard swap operator attempting to interchange all possible pairs of vertices, both belonging to the same route or two different routes. The second local search algorithm is based on a standard move operator which attempted to move each vertex to any other position in any route. The proposed formulations together with the algorithms showed great potential in reducing CO2 emissions. To minimise the number of carpools, the authors of [77] suggested removing the capacity constraint which limits the carpool size to the vehicle's capacity and allows a vehicle to serve more users. A partition-merging-based greedy approach is proposedto check the mergeability between carpools iteratively and then follow by utilising a maximum matching algorithm to maximise the number of carpools merged. A DE is proposed by [78] to solve a carpooling system that allows both passengers and drivers to place bids according to their needs, requirements and constraints. The aim of the paper is to develop solution algorithms to maximise the matching of drivers and riders for ridesharing. It can further improve the efficiency of the transportation system and reduce overall costs. A DE with neighbourhood search is developed based on the concept of neighbourhood search. It is transformed from a continuous decision variable to a discrete binary decision variable so that it can fit the carpooling problem. The generated test data based on real geographical data in Taiwan is used to run the simulation results in identifying the performance of different DE variants. In general, the HOV lane is a lane that allowed vehicles with at least two passengers to use the lane. To maintain high throughput, the authors of [79] formulated a 3+ High-Occupancy-Vehicle (HOV3) carpool problem that required drivers to have at least three passengers instead of two passengers. Four local search methods--hill-climbing, SA, classical local search, and local search with the random neighbourhood--are utilised in the study. One-to-Many Carpooling Problem  
Many existing carpooling systems are deficient in satisfying the requirement of drivers and riders where matching drivers with riders contribute to allocating cost savings among the ridesharing participants. In order to fill this gap in the problem, in [80] a carpooling model is formulated based on double auctions. This allows drivers and riders to place their bids based on their needs and preferences. A discrete cooperative coevolving particle swarm optimisation algorithm is developed to solve the formulated carpooling problem. A cost savings allocation scheme is proposed to benefit the ridesharing participants. The Intelligent Carpool System (ICS) is an advanced carpool system that provides carpool services to carpoolers via a smart handheld device anywhere and anytime [81]. A genetic-based carpool route and matching algorithm is used to solve the carpool service problem which is a multi-objective optimisation problem.