## 4 Review of Literature
### Ridesharing Problem
#### 4.1.2 Heuristic and Metaheuristic Algorithms  
One-to-One Ridesharing Problem  
Intermediate locations in dynamic ridesharing systems are proposed by [30] to reduce both the driver's detour and the total travel cost. In further studies, ref. [31] included an a priori approach that allows the driver to set the sharing cost rate towards carpoolers in advance. In the a priori approach, the detour factor is fixed while the detour factor in the posteriori approach is not fixed but the system calculates the most favourable value in ensuring a better matching between ride and driver [32]. Instead of a one-way trip ridesharing problem, a round-trip ridesharing problem with relay stations is proposed by [33]. A relay station can be considered as a new pick up location or a new starting location for a rider to park their vehicle and wait to carpool a driver with the common destination. The traditional round-trip ridesharing systems cannot allow a rider's origin to differ from his or her pick-up location. The proposed round-trip ridesharing system with a relay station ensured that the rider's return trip will pass through the relay station where the rider had left their private car. Moreover, ref. [34] considered the best offer selection problem in real-time ridesharing with intermediate locations. Under the best offer selection problem, the geographical information of the drivers in the system is stored in buckets. When a rider enters the system, the best driver with the best pickup and drop-off locations will be assigned to minimise the total travel cost of rider and driver. A dynamic ride-matching problem with the consideration of a few dedicated drivers is proposed in [35]. An Integer Programming (IP) of the system is formulated to minimise the cost and rate of served riders. Dedicated drivers are assumed to be able to serve multiple rides while ad-hoc drivers can only serve one ride. A heuristic solution composed of a construction step and an improvement step is presented to solve the IP. In the construction step, a pool of riders' requests will be served first under the absence of dedicated drivers and then those unmatched riders will be matched with the dedicated drivers. In this way it can be ensured that the number of served riders can be maximised. In the improvement step, a neighbourhood search algorithm is used to improve the computational time in changing the schedule of the type of driver for a driver. A common destination-based ridesharing system, which can involve large organisations such as companies, is the focus of [36]. The proposed ridesharing system mainly uses company-owned vehicles to allow employees to carpool to work to reduce the localised congestion problem. However, there is a need to re-route existing vehicles or even a requirement for some participants to take their vehicles when issues of vehicle unavailability emerge. In order to optimise the distribution of shared vehicles, a stochastic mixed linear programming model for the car placement problem in ridesharing system is presented to the employees. The proposed solution is a savings heuristic algorithm with a clustering approach. Based on the proposed algorithm, the participants are grouped into clusters with limited sizes and then solved independently by the savings heuristic algorithm. A test case based on Rome's city transportation network is utilised to demonstrate the performance. The results showed that the proposed algorithm can produce a high-quality solution with a short computational time. In [37], a real-time ridesharing system is proposed for instances with hundreds of vehicles in the Melbourne Metropolitan Area. This is solved by a cluster-based matching algorithm in a rolling horizon approach. A federated optimisation architecture-based ridesharing system together with a linear assignment problem to reduce the fleet size is proposed by [38]. A reactive re-balancing procedure is proposed to limit the request rejection rate.