Shared Mobility Problems: A Systematic Review on Types, Variants, Characteristics, and Solution Approaches

Abstract

The Shared Mobility Problems (SMP) with the rideshare concept based on sharing a vehicle are fast becoming a trend in many urban cities around the world. Examples of these problems are like ridesharing, carpooling, taxisharing, buspooling, vanpooling, and multi-modal ridesharing. This is the new way to access transportation services by those who are propelling the sharing economy, where access rather than ownership is the new norm. This paper provides a systematic review of SMP using the PRISMA (Preferred Reporting Items for Systematic Reviews and Meta-Analysis) method. A total of 110 papers from the last decade are selected from 12 abstracts and citation databases to be reviewed and classified. This is done based on the problem types, variants, characteristics, and solution approaches. The current trends and analysis of the survey findings are also summarised. From this systematic review, it is observed that both the time window and multi-objective problems are popular among the researchers, while the minimisation of the total cost is the main concern in the literature of the SMP. Both static and dynamic cases of the SMP are the most researched where heuristic and metaheuristic approaches are widely adopted by the researchers in the literature. Finally, challenges and suggestions for future work are discussed and highlighted.

1. Introduction

The global population is rapidly increasing, especially in urban cities. The worsening traffic congestion, rising fuel prices, and environmental concerns are the challenges faced in most developing and developed countries in the world. These challenges affect the economic productivity and the quality of life in each of those countries, thus making it a global concern. One approach in addressing the transportation needs of future urban populations is to improve transportation speed and capacities. Alternatively, we can also turn to shared mobility mechanisms.

The deployment of a public transport system is also another method to reduce the traffic congestion problem. Among the main factors why many commuters would choose to use private vehicles instead of public transportation are the shorter travel time, improved privacy, and the high flexibility for scheduling the travel journey. Therefore, not surprisingly, the deterrents to using public transportation are the usual suspects: the problem of low travel speed, low frequency, high discomfort level, and low reliability (long waiting time). Hence, there is an attractiveness of a hybrid of a public transport system which incorporates the conveniences from private vehicles. Thus, the research related to sustainable and shareable systems, such as ridesharing, has gained popularity over the decades.

Shared mobility describes a wide variety of new technology-enabled services and tools that give instant access to new services and travel information, while complementing traditional public transportation modes like fixed route transit. These services include ridesharing, carsharing, new forms of bikesharing, technology-enabled shared ride services, new private forms of transit, and travel itinerary services that ease the selection of travel options. In addition, these services are widely available to the users via most electronic communication devices such as smartphones.

The ridesharing system is one of the promising ways in elevating the traffic congestion problem and reducing CO${}_2$ emissions. The ridesharing system is a mode of transportation that allows travellers to share a trip with someone who has similar itineraries to split travel costs such as fuel, toll, and parking fees. It allows practical usage of available empty seats and potentially reduces fuel consumption. Ridesharing is not a new idea, but it was first led by the U.S. government as a regulation policy to conserve fuel during World War II [1].

The popularity of the ridesharing system is closely related to the growth of technological advances in recent years. The advent of the internet, smartphone gadgets, mobile application development platforms, online payments system, and Global Positioning System (GPS) have greatly encouraged the conversion of traditional ridesharing into dynamic ridesharing [1]. Traditional ridesharing only allows the rideshare with early booking while dynamic (or on-demand) ridesharing can serve real-time requests without any booking.

The ridesharing system can be categorised into profitable and non-profitable. Taxisharing and ride-splitting are under the categories of profit-based ridesharing. Profit-based ridesharing systems provide rideshare service based on the riders’ destinations, which is usually different from the driver. As it involves financial gain, then the received payment from riders involves profit after covering the cost. The riders share the payment so that the travel cost per passenger coulf be cheaper. Peer-to-peer (P2P) ridesharing, carpooling, and vanpooling are classified as non-profitable ridesharing system. In non-profit-based ridesharing, the destination for both riders and driver are the same. The payment from a shared ride is collected directly to cover the driver’s cost. It is not for financial gain [2].

People tend to misunderstand the concept of ride-sourcing and assume it as P2P ridesharing. However, ride-sourcing did not possess the concept of rideshare but ride-splitting. Ride-sourcing and ride-splitting are under the category of on-demand ride services, in which financial gain is involved. Moreover, ride-splitting and P2P ridesharing are not the same, because they have different intention. P2P ridesharing is non-profitable, and the payment only covers the cost of the driver. Ride-splitting is a form of ride-sourcing where riders are matched with similar origins and destination in real-time, and the cost is shared among riders [3]. The driver in ride-splitting plays a role as a service provider without considering whether the destination for both driver and riders are the same. Whereas, P2P ridesharing (or carpooling) is a form of ridesharing that allows a group of people to reach similar destinations. Flexibility, safety, and cost are the determinants in implementing an efficient ridesharing system.

This paper focuses on the recent papers on Shared Mobility Problem (SMP) published in the last decade from January 2010 till January 2021. The main contribution is the implementation of PRISMA (Preferred Reporting Items for Systematic Reviews and Meta-Analysis) method in the systematic review of the SMP based on the detailed classification of problem types, variants, characteristics, and solution approaches. The existing review papers focus mostly only on ridesharing and carpooling, but in this study we extended the review to taxisharing, buspooling, vanpooling, and multi-modal ridesharing. To the best of our knowledge, no work has considered the PRISMA method in performing the systematic review of the SMP.

This paper is organised as follows. Previous review papers related to SMP are discussed in Section 2. The research methodology based on the systematic review process of PRISMA method is presented in Section 3. In Section 4, various SMP are reviewed based on the proposed classification, while Section 5 summarises the current trends and analysis of the survey findings. Section 6 elaborates the challenges and future works related to the SMP specifically for rideshare within a vehicle. Finally, Section 7 gives the conclusions of this systematic review.

2. Previous Review Paper

A number of review or survey papers discuss ridesharing from different scopes and perspectives. The authors of [4] defined real-time or dynamic ridesharing and discussed the challenges of dynamic ridesharing based on economic, social, institutional, and technological aspects. The possible benefits and drawbacks of dynamic ridesharing are explored in detail in comparison with traditional ridesharing. Then there is [5] which focused on the review of optimisation for dynamic ridesharing. The discussion included the aspect of features, overall objectives, variants, as well as the challenges in developing the ridesharing system.

Additionally, the authors of [2] explored the past, present, and future of ridesharing in North America. First, the history of the ridesharing system is discussed in five different phases from 1942 till 2012. This is followed by a discussion of the existing ridesharing system. The future directions of the ridesharing system are also suggested.

The authors of [1] classified the ridesharing matching agencies that are accessible online based on target markets, primary search criterion, classes, business functions, and service types. They stated the challenges of designing the ridesharing system, including elements of pricing, high-dimensional matching, trust and reputation, and institutional design. A future challenge for desirable services of matching agencies is suggested in the paper. Still focusing on IT advancements, ref. [6] presented a chronology of the transformation of dynamic ridesharing from early operator-based to real-time database-driven ridesharing services through the changes in Information and Communication Technologies (ICTs) over the last two decades. They claimed that the interaction between dynamic ridesharing and ICTs will continue to evolve until a balance is achieved.

More recently, ref. [7] performed a review study that mainly focuses on different problem variants of P2P ridesharing with the solution approaches. Their paper consists of a general literature review with 42 papers discussed. However, the paper does not mention the specific databases and techniques that are used in selecting the papers. In terms of the classification of problem variants, ref. [7] discussed solely the number of riders and drivers. In this study, two different types of problem variant classifications are identified and discussed: (i) the number of riders and drivers, and (ii) the number of origins and destinations.

Similarly, ref. [8] conducted a review of optimisation problems related to ridesharing, carsharing, and carpooling, together with the employed methodologies used to solve these problems. The methodologies include exact, approximate, and simulation methods. The challenges for ridesharing and carpooling in solving large-scale problems are identified, such as the concept of ‘agile’ optimisation. A total of 86 papers are selected, from 2008 to 2019, sourced from the Web of Science (WoS) database. The researchers in [8] make use of the term “carsharing” to represent both “ridesharing” and “carpooling” in conducting the review. However, “carsharing” is one part of the shared mobility that is mentioned in [9], which reduced the number of vehicle ownership by sharing the vehicles among people, such as in neighborhood carsharing. In this study, we only focus on the sharing of rides or the so-called pooling (instead of sharing) of vehicles. As compared to [8], this paper studies more in-depth the shared mobility based on characteristics, problem variants, and solution approaches.

In general, the aforementioned review papers only surveyed a moderate number of papers and did not explicitly present the methodology of their review. Instead, they mainly focused on the findings. These papers are presented in Table 1, highlighting the focus of their research. They are categorised according to the year of publication and number of papers reviewed.

3. Research Methodology

In this study, the technique used to perform a systematic review is the PRISMA method [10]. PRISMA is widely used in several scientific fields, especially in the medical sciences, to develop clinical practice guidelines and protocols [11]. PRISMA is also applied in the transportation domain such as in [12]. This technique is an evidence-based minimum set of items for reporting in systematic reviews and meta-analyses. It is designed to help systematic reviewers transparently report why the review was done, what the authors did, and what they found. The PRISMA statement consists of a 27-item checklist and a four-phase flow diagram. The checklist is deemed essential for transparent reporting of a systematic review. It synthesises the research and provides a high-level view on the evidence, being less subject to bias.

3.1. Material Collection

In this subsection, the research questions, inclusion criteria, exclusion criteria, and the PRISMA four-phase flow diagram are discussed. The study at hand undertakes a systematic review of the literature to address the following research questions:

• What would be the classification of the SMP based on problem types, variants, and characteristics?

• What are the solution approaches that have been employed to solve the SMP?

• What are the current trends of the SMP?

• What are the challenges and future work direction in the routing and matching optimisation of SMP?

The first stage is to plan on developing the research aim and questions, keywords, and a set of inclusion and exclusion criteria. The research aim was framed to identify the related studies of SMP based on the types, variants, characteristics, and solution approaches. Thus, (“ridesharing” OR “ridesplitting” OR “ridepooling” OR “taxisharing” OR “shared taxi” OR “carpooling” OR “buspooling” OR “vanpooling” OR “multi-modal”) AND (“ride” AND “matching”) were chosen to be the search keywords. As mentioned in [3], ridesharing, ridesplitting, ridepooling, taxisharing, shared taxi, carpooling, buspooling, vanpooling, and multi-modal are types of problems under the SMP. The (“ride” AND “matching”) search term was used in the database search to ensure that the search is focused on the subject area of mathematics and computer science-related fields, especially for the model formulation, instead of social sciences-related studies in shared mobility.

Based on the PRISMA guidelines, a total of 12 abstract and citation databases (ACM Digital Library, Emerald Insight, IEEE Xplore, INFORMS, MDPI, PLOS One, SAGE, ScienceDirect, Scopus, Springer Link, Taylor & Francis Online, and Wiley Online Library) were searched for peer-reviewed papers by keywords contained in the title, abstract, and the main body of the papers. The last search was performed in January 2021, and we restricted the search to all literature published from January 2010 till January 2021.

In Figure 1, the search results are presented in a flowchart. The search firstly resulted in 1319 records overall. After removing the books, chapters, editorials, reports, and articles that are not in the English language, the search records were reduced to 1094. Then, the total number of articles was further reduced to 460 articles after evaluating the title and abstracts related to the inclusion and exclusion criteria. For a study to be eligible for inclusion in the review, (i) it has to be published in a peer-reviewed English journal or conference proceedings; (ii) its subjects must include, but do not need to be limited to, at least a ridesharing-related paper on routing and matching optimisation or operational decisions in ridesharing; and (iii) it should have at least one variable or attribute associated with the keywords mentioned earlier. The full texts of the selected articles were narrowed down to 110 articles after another 350 articles were removed due to the irrelevance to the research aim. The irrelevant studies that researched economic-related analysis, software or system development, user equilibrium problem, law enforcement, and policy development with regards to SMP studies, such as in [13,14], were also excluded from this systematic review.

3.2. Descriptive Statistics

The descriptive analysis of the 110 selected articles according to their year of publication revealed a rising interest in rideshare-related topics during the last couple of years. Out of the 110 papers, 7 are review papers and were excluded. Therefore, a total of 103 papers were considered in the literature review. There is a gradual increasing trend based on the year in focus, as presented in Figure 2.

Table 2 shows the distribution of papers based on the type of publication over the years. The published papers in journals showed an increasing trend throughout the years. Note that the number of papers in 2021 does not represents the total papers published in 2021 as the search only covers the period until 31 January 2021.

Table 3 shows the collection of real-world datasets used over the years by papers in the selected literature. Overall, 76 out of 110 articles made use of a real-world dataset of a country to experiment with the algorithms.

3.3. Category Classification

Table 4 presents the classification of the SMP. The classification is categorised into five different categories. The first category is the problem types. Then, it is followed by the problem variants category. There are two different categories in terms of the problem variants. The first problem variant is based on the number of drivers and riders (D–R) while the second problem variant is based on the number of origins and destinations (O–D). It was the authors of [5] who proposed a ridesharing classification based on the number of D–R involved. For this variant, there are four different sub-categories, which are One-to-One (1–1), One-to-Many (1–M), Many-to-One (M–1), and Many-to-Many (M–M). They represent a single driver–single rider, single driver–multiple riders, multiple driver–single rider, and multiple driver–multiple riders, respectively. Ref. [15] concentrated on carpooling problem variant and proposed that the second problem variant which can also be divided into four sub-categories. They are One Origin–One Destination (1O1D), One Origin–Multiple Destinations (1OMD), Multiple Origins–One Destination (MO1D), and Multiple Origins–Multiple Destinations (MOMD). The third category is classified based on data characteristics. The data characteristics are static, stochastic, and dynamic. The fourth and last category is based on solution approaches. The solution approaches consist of exact, heuristic and metaheuristics, and other algorithms.

4. Review of Literature

In this section, a detailed and systematic review of the 103 selected papers within the last decade based on the proposed classification found in Table 4 is presented. In each of the subsections that follow, various works are discussed in terms of variants, methodology used in overcoming the problem, as well as the solution proposed along with the challenges that are tackled. This section addressed the first and second research questions mentioned in Section 3.1.

4.1. Ridesharing Problem

A ridesharing problem is one whereby a service provider works to match travellers with similar itineraries and time schedules with short notice, in a private vehicle, to split the cost with other riders. Research done on the ridesharing problem based on the proposed classification is discussed in the following subsections.

4.1.1. Exact Algorithms

One-to-One Ridesharing Problem

A maximum-weight bipartite matching algorithm in solving the single driver–single rider ride-matching problem is proposed by [16]. The limitations of the proposed method are long computational time and omitting the individual preferences. A rolling horizon approach in postponing the finalisation of previously found matches until a deadline set by the users is proposed to maximise the number of participants.

In the case of a dynamic ridesharing setting, drivers and riders may reject a match (that fulfills individual cost savings and satisfies the participants’ time preferences) if they believe they can establish a better match on their own. In the notation of stability in cooperative game theory, such a pair can be considered as blocking pair. If there are one or more blocking pairs in the matching solution, then it can be called an unstable rideshare matching. To deal with the unstable matching, the authors of [17] proposed an optimisation approach with the notion of stability and several mathematical formulations to establish stable or nearly stable matches. There is also a network partition-based match making algorithm proposed by [18] to reduce the size of the search space in finding matches for dynamic ridesharing.

The participants’ flexibility angle was then researched by [19]. They performed a study to quantify the impact of the participants’ flexibility on a single-driver, single-rider ridesharing system. Three different types of participant flexibility, which are (i) matching flexibility, (ii) detour flexibility, and (iii) scheduling flexibility, are considered in this study to identify what types of flexibility can bring better efficiency to the ridesharing system. The study showed that flexibility plays an important role in contributing to the high matching rates, especially in ridesharing systems with low participation rates.

P2P ridesharing can be considered as a two-sided (drivers and riders) market in SMP. A mathematical formulation of one-to-one matching in ridesharing systems with role flexibility is formulated to investigate the stability of the model. To achieve stable ridesharing matching, ref. [20] proposed a new market game. In the new market game, a Mixed Integer Programming (MIP) that finds the minimum amount of subsidy required is proposed to stabilise the system. For the solution method, a decomposition-based Lagrangian relaxation algorithm is proposed to obtain a stable solution.

One-to-Many Ridesharing Problem

Among some of the works using exact algorithms, ref. [21] formulated MIP for one-to-many ridesharing problems with flexible roles and solved this using CPLEX. In [22], they introduced a green ridesharing problem with the consideration of two objectives and named it a Bi-objective Green Ridesharing Problem. It is a nonlinear multi-objective problem with CO${}_2$ emission minimisation and average ride profit maximisation.

Furthermore, Armant and Brown [23] later proposed three different ridesharing schemes and two different reformulations of ridesharing constraints that are capable of solving real-time real-world ridesharing problems. The proposed ridesharing schemes are to maximise the number of assigned passengers (improving access), to maximise the number of assigned users (sustaining the long-term viability of the system), and to minimise the driving distance (reducing emissions and congestion). In terms of the proposed reformulation, the authors re-encode the spatio-temporal resource-allocation constraints and variables together with path constraints simplification to speed up the solving of real-world applications. Although the authors of this paper do not consider transfers between multiple drivers, they do consider multiple pick-ups and drop-offs with role flexibility in improving the performance of all objectives in all regions.

Capacity limitation is the major challenge of the current ridesharing systems. Ref. [24] presented a general mathematical model for real-time high-capacity ridesharing that can serve requests by using vans and minibuses instead of only taxis. A reactive-anytime-optimal algorithm is proposed. It comes with four steps and is proposed to solve the constrained model. The first step is to compute a pairwise request-vehicle shareability graph. Then, the second step is to compute a graph of feasible trips and the vehicles that can serve the requests. In the third step, the optimisation is formulated as an Integer Linear Programming (ILP) one and it computes the greedy assignment of vehicles to trips. After the assignment is done, fleet imbalances may occur when the idle vehicles are in areas far away from the area with the large number of current requests. Hence, re-balancing the remaining idle vehicles to areas of high demand is the final step. The proposed framework can be applied in many real-time multi-vehicle and multi-task assignment problem.

Many-to-Many Ridesharing Problem

A multi-hop P2P ride-matching problem that allowed rider travel in between multiple drivers where a driver can carry multiple riders is introduced in [25]. Due to the complexity of the problem, a decomposition algorithm is devised to reduce the size of the ride-matching problem into multiple smaller problems. Hence, Masoud and Jayakrishnan [26] formulated many-to-many problems based on a time-expanded network together with the feature of a flexible ridesharing system in real time. The real-time ride-matching, the central component of a flexible P2P ridesharing system, is solved using the Ellipsoid Spatio-Temporal Accessibility Method.

For P2P ridesharing, a first-come, first-serve basis is employed in serving customers. However, this is an inefficient approach in a dynamic real-time system. The implementation of the said principle may lead to high computational time in the ride-matching problem. To improve the problem, ref. [27] introduced a P2P ride exchange mechanism to maximise the total number of matched rides. The ride exchange mechanism allowed unmatched riders to purchase an itinerary from a previously matched rider, allowing for a ride exchange accompanied with an exchange of money through the system. There is also work by [28] who introduced a comprehensive modelling framework for the dynamic shared mobility service which is the integration of ridesharing with transfer points. The proposed model assumes heterogeneous customers’ in terms of their service preferences. A novel solution algorithm, a modified version of Column Generation, is used to account for the ridesharing problem with transfer points. On a different point, ref. [29] introduced a novel deterministic model to address the ridesharing problem with different origins and destination under travel time uncertainty. To optimally solve the problem, a MIP model is solved using the Gurobi solver.

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. The proposed algorithm is fully distributable among multiple companies with a privacy protection, while ensuring the assignment achieves optimality. With the proposed ridesharing system, enterprises with small market shares can produce high quality of service without monopolising the whole ridesharing service market. Meanwhile, ref. [39] proposed a comprehensive ridesharing model which mainly focuses on Quality of Service (QoS)-orientation and is cost-effective to optimise the user experience and the cost of the ridesharing service. Instead of the original Differential Evolution (DE) that is designed for continuous optimisation, Differential Evolution-based Ridesharing Algorithm (DERA), a set-based DE, is proposed to search the global optimum for the formulated problem. DERA is specifically designed with the incorporation of several new operators such as greedy initialisation, inter-vehicle mutation, route sensitive selection, and individual repairing/re-factoring operators, to improve the performance in searching for the optimal solution. The experimentaL results showed that DERA outperformed other algorithms used in the study.

Furthermore, the authors of [40] developed a ride-matching algorithm that splits the drivers’ routes and matches riders and drivers again with an extra consideration of a Joint Socialness Score. The score involves data pertaining to the participants’ gender, age, employment status and social tendencies and is used to increase the matching of riders which are in the same likelihood range. The route-splitting incorporated in the proposed algorithm can maximise the distance savings and the number of matched riders to be served. The two-fold aim of the proposed algorithm is to serve more riders and to maximise the user benefits in ride-matching in encouraging more people to participate in the ridesharing system. Additionally, the authors of [41] proposed a trip-based graph partitioning approach to decompose the original one-to-one ride-matching problem into smaller multiple sub-graphs. A dissimilarity measure based on the shareability of trips is applied to reduce the computational time of sub-graphs when solving them in a parallelised setting.

A study addressing commuters’ preferred travel mode based on a cumulative prospect value was performed by [42]. With the enlightenment of the decision-making problem in city logistics, the ridesharing market can be enlarged at a low cost. Thus, the goals considered in this bi-objective ridesharing model are maximising the participation rate of ridesharing among commuters and minimising the total cost of vehicles. In a small-scale scenario, a heuristic algorithm is developed to solve it. Whereas, for the large-scale problems, a hybrid algorithm named VNS-NSGAII algorithm, a combination of Variable Neighbourhood Search (VNS) and Non-dominated Sorting Genetic Algorithm II (NSGA-II), is employed to produce an optimal Pareto front solution.

One-to-Many Ridesharing Problem

A comparative study in utilising different Multi-Objective Evolutionary Algorithms (MOEAs) to solve the route planning problem in dynamic multi-hop ridesharing was done in [43,44,45]. In [46], the authors extended the dynamic ridesharing problem with extra consideration of time windows and solved it by using Genetic Algorithms (GA). Time-dependent route planning is proposed and solved by a genetic local search algorithm [47]. In the following study, Herbawi and Weber [48] introduced an insertion heuristic into the GA to become a hybrid algorithm to solve the same problem, as proposed in [46]. Instead of the single-hop tide matching problem, they considered a multi-hop together with time windows in a dynamic ridesharing problem [49].

The potential benefits of proposing meeting points in a ridesharing system are investigated in [50] by performing an extensive simulation study. The existing ridesharing does not consider the preferences of riders; therefore, a group of compatible preferences in a participating optimal sharing cannot be generated.

In mitigating the congestion problem, ref. [51] proposed a modified pickup and delivery problem with time windows for ridesharing. An insertion heuristic with Tabu Search (Distance-Tabu) for objective of minimising the distance and an insertion heuristic with Tabu Search (Congestion-Tabu) for objective of minimising the congestion function are developed to solve the studied problem. The Adjust Pickup Time Algorithm is applied in each scenario. It considered HOV (High Occupancy Vehicle) lanes and the policy to reduce the toll rates on HOVs (High Occupancy Vehicles) in minimising the travel time and cost by having vehicles with more passengers.

A mixed-integer model for passenger matching and vehicle routing problem in the first-mile ridesharing service was formulated by [52]. The main objective of the study is to minimise the total transportation cost. To achieve computational efficiency, Simulated Annealing (SA) with four neighbourhood structures, a metaheuristic algorithm, is applied to solve the proposed large-scale problem.

Moreover, the authors of [53] considered the characteristics of pickup and drop-off congestion in developing a flow-dependent version of a ride-matching and routing optimisation model to maximise the average loading ratio of the entire system. To address the complexity of the problem, a large neighbourhood search heuristic is established to improve the solution efficiency. In the work in [54], the authors formulated a mathematical model to design an enhanced ridesharing system which considered both the meet points and time window. A tabu-based metaheuristic algorithm is used to solve the Mixed Integer Linear Programming (MILP) on an enhanced ridesharing system. The CPLEX solution is used as the benchmark to validate the performance of the tabu-based metaheuristic algorithm. The detailed assignment of the passenger to the meet point can reduce the en-route delay and save the travel time for a small-scale ridesharing system.

For the study in [55], a concept of space–time window is introduced by formulating an on-demand ridesharing problem for the pickup and delivery problem with space-time windows. A customised solution approach based on the Lagrangian relaxation algorithm is developed to solve the model. The proposed algorithm incorporates a decomposition approach which decomposes the problem into the shortest path problem and knapsack problem that could be solved easily.

Furthermore, the authors of [56] introduced two-sided matching in building a single-driver multiple-rider ridesharing problem with consideration of a system-wide optimal and stable matching. The recursive algorithm and a delete operator are proposed as the solution method in solving the ridesharing model. The recursive algorithm plays an important role in searching feasible rider sets and transforming them into a series of feasible sets. Next, the delete operator is employed to reduce the size of the feasible decision region to further improve the model computational speed. The results show that the proposed algorithm can provide high stability in the ride-matching solutions, albeit with a small sacrifice in terms of the system-wide performance. A detour-based discounting mechanism for the first-mile ridesharing problem was designed by the authors of [57] to encourage more passengers to use public transit. The first-mile ridesharing problem is a multiple-rider, multiple-driver system. The proposed mechanism allows passengers to have their preference on different inconvenience attributes in determining optimal vehicle–passenger matching, along with a vehicle routing plan and customised pricing scheme. In [58], the authors also proposed a Solution Pooling Approach (SPA) to significantly decrease the computational complexity with minimal sacrifice of the quality of the solution.

A ridesharing problem is formulated into a global optimisation task that schedules the requests for multiple vehicles [59]. An efficient Parallel Scheme with Simulated Annealing (PCSA) is developed to handle the matching and routing of these requests. In PCSA, the move generation and move control technique can avoid unnecessary perturbation and focus on optimising the existing schedule to better improve the efficiency of the SA. The proposed PCSA utilised an efficient domain decomposition and merging paradigm to reduce the domain into small independent sub-domains to speed up the parallelisation. Afterwards, the mixing of states and a parallel scheme for SA are further applied to increase the parallel efficiency and scalability. Throughout the simulation, the results showed that PCSA is suitable for solving the ridesharing problem with strong spatial constraints within a short amount of computational time.

The First Mile (FM) problem refers to the transportation connection between the passengers’ homes and transportation hubs such as railway station and bus terminals. Feeder buses and on-demand shared mobility services are the key means of transportation in solving the FM problem. However, the demands of feeder buses remain low due to issues related to reliability and cost. Therefore, autonomous vehicles are employed as an alternative form of transportation to serve the FM problem as they greatly enhance accessibility and connectivity. With this in mind, ref. [60] proposed a MILP model for an Autonomous Vehicle (AV)-based dynamic vehicle dispatch and ridesharing schedule to minimise the operational cost for the FM service. The rolling horizon framework is utilised in the model formulation to ensure the efficiency of the fleet operation. A cluster-based solution method is employed to solve the large scale FM problems. The proposed solution method has great potential in speeding up the computational time as it partitions the requests in groups instead of individually before solving them.

In the work by [61], they proposed a fair ridesharing route optimisation model which takes both system optimisation and user-fairness into consideration to enhance the rationality of ridesharing. The user-fairness considered in this study allows the users with a long detour to have better discount rates to save on travel cost. Additionally, the model constraints consider the benefits for both drivers and riders in the optimisation to ensure the high demand for the ridesharing service among them. An improved GA in both crossover and mutation operator is used to solve this problem.

Many-to-One Ridesharing Problem

In [62], an intelligent chromosome agent-driven approach is proposed to enhance the performance of the Evolutionary Algorithm in a solution to the multi-hop ride-matching optimisation problem. It can be defined as Autonomous and Intelligent Agents (E2AIA) where genetic operators will be driven by chromosome agents through a powerful negotiation protocol. E2AIA remains stable in processing time while there is an increase in the number of users. Overall, E2AIA can generate ride-matching solutions while minimising the number of required vehicles.

Many-to-Many Ridesharing Problem

A dynamic multi-hop ride-matching problem is introduced and solved using a metaheuristic approach based on controlled genetic operators [63]. Apart from the ridesharing system that featured meeting points and multiple hops, in [64] a multi-hop ridesharing system that incorporates meeting points is proposed. The authors also introduce another feature called “return restrictions together” with a backup transportation service in allowing a closed corporate community to participate in ridesharing.

To overcome the complexity and real-time aspect of the dynamic carpooling optimisation system (DyCOS), in [65] proposed a Tabu Search (TS) i proposed that employs an explicit memory system with several searching strategies to make optimal decisions automatically. To ensure high-quality solutions, DyCOS adopted detour and transfer concepts.

In the ridesharing problem, a driver has to pick up multiple riders. Therefore, they have to visit several different locations and end their journey at the final destination. Hence, the uncertain travel time for the driver can be higher when compared to the case with no rideshare. A ridesharing problem with consideration for travel time uncertainty is then proposed by [29]. Their study focussed on the static single driver and multiple riders ridesharing model. To achieve computational tractability, a robust optimisation approach (a hybrid heuristic algorithm with the cluster-first route-second approach) is proposed to handle the ridesharing problem. Before employing a hybrid heuristic algorithm, the cluster-first route-second approach is utilised to decompose the large scale problem into different sub-groups. The two clustering approaches used in the approach are greedy heuristic and k-means clustering. After clustering, the hybrid heuristic algorithm, an extended insertion algorithm in conjunction with a TS, is employed to solve the solution iteratively. Through numerical experiments, the proposed robust optimisation approach can potentially produce a viable solution for solving the large-scale problem.

The events of a natural disaster or man-made disaster can be considered as extreme events that necessitate the short-notice evacuation from a populated area. The authors of [66] presented a two-phase route optimisation method for ridesharing matching with transfers in short-notice evacuations. In the first phase, a vehicle–space–time hyper-dimensional network is constructed based on the obtained network topology information and personal requests. For the second phase, a new time-discretised multiple-ride multiple-driver network flow model is created based on the created vehicle–space–time network to ease the formulation of the ridesharing with transfers. The Lagrangian relaxation solution approach is designed to solve the model.

Multiple Origins–Multiple Destinations Ridesharing Problem

A large-scale ridesharing problem with flexible participants, time window and transfer points is proposed by [67] in addressing both the assignment and sequencing decision in ridesharing. The flexible participants represent flexible drivers who own a car but are willing to be a passenger in a trip. The proposed model provides participants flexibility in deciding which participants act as drivers and relocating alternative locations for the participants to act as passengers. The chosen benchmarks in the study are urban area instances and commuter instances to evaluate the performance of the late acceptance hill climbing and integer programming. The late acceptance hill climbing has advantage in solving large instances. Through the simulation results, it indicated that the cost can be greatly minimised at the condition where 30% of the drivers are flexible. The increase of flexible drivers can further improved the overall solution but suffered from diminishing returns.

4.1.3. Other Algorithms

One-to-One Ridesharing Problem

In [68], the authors proposed a single-hop ridesharing system with a ride-back guarantee. It is formulated as a minimum cost, maximum flow formulation so that it can be solvable on polynomial time. The absence of travel time uncertainty in the ridesharing model could lead to irrational ridesharing matches and inaccurate estimation of the benefit from ridesharing as stated in [69]. Hence, a stochastic ridesharing problem with time-independent travel time uncertainty is proposed. The problem is further extended to a stochastic ridesharing model with time-dependent travel time uncertainty and solved by the Monte Carlo Simulation method.

One-to-Many Ridesharing Problem

A new real-time dynamic ridesharing system that considered the interaction between drivers or riders and the system manager, as well as the interaction between drivers and riders is proposed by [70]. In the proposed ridesharing problem, a discrete event system and a dynamic pickup and delivery model that represent the dynamic and optimal matching problem are developed to optimise the allocation of empty seat in a vehicle to a rider. The results of the proposed optimisation procedure have shown good results in the mean delay per user and a significant reduction of the match refusals.

4.2. Carpooling Problem

Carpooling is less flexible because only travellers with a common origin to a common destination can be matched and served. It is hard to find consistent travel companions with carpooling [8].

4.2.1. Exact Algorithms

One-to-Many Carpooling Problem

In [71] the 2-synchronisation points shortest path problem is introduced, where two paths with a common subpath are synchronised between two points. The synchronisation points act as the pick-up and drop-off point. The driver and riders shared the same path in between the two synchronised points. It is considered as the first paper with the concept of a meeting point.

In the work in [72], an optimisation model is formulated based on the objective to minimise the cost. The cost can be the travel cost, the fixed cost of a vehicle usage, and penalty costs. The branch & bound algorithm, which is an exact algorithm, is used to solve the carpooling problem and obtain an optimal solution.

Multiple Origins–Multiple Destinations Carpooling Problem

An approach based on a Lagrangian relaxation-based algorithm is developed in [15] to solve the long-term many-to-many car pooling problem. Furthermore, the work in [73] extended the model for a many-to-many carpooling problem with consideration of multiple vehicle types and person types. A solution algorithm based on Lagrangian relaxation, a subgradient method and a heuristic for an upper bound solution were developed to solve the proposed model. In [74], the pre-matching of information is another additional consideration into [73]’s proposed model and they named it a car pooling problem with pre-matching information. The solution algorithm used to solve the problem is the similar algorithm that is proposed in [15]. Most carpooling organisations use an inefficient trial-and-error process. Therefore, a stochastic carpooling model which considered stochastic travel times is proposed [75]. Due to the large problem size, a simulation-based evaluation method is developed to solve the model.

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 CO${}_2$ 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 CO${}_2$ 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 proposed to 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. 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, Tamannaei and Irandoost [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. A hybrid ant colony (HAC) algorithm and CPLEX are implemented to solve the MDCPP and classic daily carpooling problem (DCPP). HAC consists of four components which are pre-sorting procedure, an ant colony optimisation-based metaheuristic, a heuristic process embedded inside the ant colony structure, and a local search. The heuristic process is used to determine the transfer point while the local search is implemented to obtain a better solution. Overall, HAC obtained a good solution with limited exploration to the search space.

4.3. Taxisharing Problem

Taxisharing is a taxi service that employs the rideshare concept to solve the problem of a shortage of taxis. In traditional taxi services, they have to wait at particular places, such as the airport or bus station, to wait for a customer to take a ride from them [90]. In taxisharing, the taxi can match the ride based on the demand uploaded from the rider through an online platform. With GPS technology, a taxi driver can perform ridesharing by allowing other riders to get in the car while on a trip to the destination of the initial riders in the car.

4.3.1. Exact Algorithms

One-to-One Taxisharing Problem

Riders find it hard to request a taxi ride, especially during rush hour, because a taxi without rideshare can only meet one rider’s request per trip. A taxi ride with the rideshare concept can merge requests with a similar origin and destination which can greatly improve the ride-matching, particularly during rush hour. In order to solve the problem of taxi vacancy (during off-peak hours) and handle the massive demand for taxi rides (during rush hour), the authors of [91] formulated a mathematical model for route choice and fare optimisation for taxi sharing during off-peak hours and rush hour. LINGO software is used to solve the model by obtaining the optimal solution that satisfies the benefits for both riders and drivers.

One-to-Many Taxisharing Problem

Lagrangian Decomposition and Incremental Cost Heuristic (ICH) are formulated in [90] in the solution methodology for a one-to-many taxisharing problem. ICH is used for assignment while the Lagrangian approach is used in order to obtain the optimal assignment. Lagrangian Decomposition decomposed the large problem into smaller problems and solved them separately. Whereas, ICH is developed as a novel heuristic in finding good quality feasible solutions within limited computational time. The main idea behind the heuristic method is to evaluate all the possible taxi requests to be assigned, resulting in minimum cost under real time implementation. The algorithm yielded upper and lower bounds that served as a benchmark for the heuristic proposed in the paper.

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 improved Multiple-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 a aPareto 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, Sun and Zhang [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. 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.

Many-to-Many Taxisharing Problem

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. Through the experimental results, NSGA-II is capable of achieving a greater amount of non-dominated solutions than decomposition-based MOEAs on all problem instances studied.

Multiple Origins–Multiple Destinations Taxisharing Problem

The work in [103] developed taxisharing models by using network flow techniques. The developed models are a taxi fleet model and two taxi–passenger matching models. The taxi fleet model is solved by the usage of the Lagrangian relaxation with a sub-gradient method. The two taxi–passenger matching models are directly solved using a mathematical programming solver. Furthermore, the authors of [104] extended the work in [103] by incorporating stochastic vehicle travel time into the model and named the model as a Stochastic Taxi Pooling model. The decomposition technique coupled with the use of CPLEX is used to solve the model. The proposed Stochastic Taxi Pooling model revealed significant results when compared to the deterministic taxi pooling model.

4.4. Buspooling Problem

The existing ridesharing systems have the problems of low capacity and high cost. Thus, buspooling, which satisfies the demands for recurring and long-distance trips with low cost, is suggested to resolve the problem of ridesharing. Buspooling is an online bus ridesharing service system that allows the rider to upload their trip demand, and wait for a public bus to be picked up [105]. The bus driver has to follow the established route determined by the online bus-hailing system based on the rider’s demand.

Heuristic and Metaheuristic Algorithms

One-to-One Buspooling Problem

Novel bus ridesharing models which are based on a hybrid form of ridesharing that combines slugging and hitchhiking with a geographic coordinate system is proposed in [106]. A dynamic grid-based heuristic algorithm is proposed, where passengers in the same direction are matched based on demand similarity. The assignment of passengers is based on two different cases. The passengers with the highest similarity are assigned immediately to a vehicle, especially for popular routes. Conversely, the scattered passengers along the less popular routes can be connected by adding intermediate stops on bus lines. Overall, the dynamic grid-based heuristic algorithm that is used as a solution approach of the bus ridesharing models guaranteed a high success rate of ridesharing matching.

One-to-Many Buspooling Problem

The problem of low capacity and high cost of car ridesharing has prompted the development of on-demand bus ridesharing problem that provides a large-scale bus ridesharing service [105]. The problem allows the rider to upload their trip through an online bus-hailing service and wait to be picked up. All the ride requests are integrated, matched and assigned to the bus drivers by the service provider. Both exact algorithms and approximate algorithms are developed to maximise the ride-matching success rate. The solution approach has three phases. The first phase is to solve the matching agency problem. Before proceeding to the algorithm computation, the clustering procedure is performed to cluster the demand with capacity constraints based on the primary search criteria. The contraction-based method, insertion-based method, and dynamic grid-based method are the algorithms that are used to solve the capacitated clustering problem. The contraction-based method used less computational time, but it leads to a local optimal and misses the global optimum. The insertion-based method is proposed to solve the problem of “unfairness”. However, the obtained exact solutions consume a large amount of memory. Therefore, the dynamic grid-based method is used to solve the problem with performance guarantees. The next phase is the pickup or delivery point. In this phase, the objective is to solve the location-allocation problem. The first method utilised is random search. Then, it is followed by a centre-based search to achieve higher accuracy results. The last phase is the pruning process. The proposed bus ridesharing problem proved to be capable of reducing the number of vehicles on the road and the fuel consumption, as well.

4.5. Vanpooling Problem

Vanpooling is a rideshare service using vans. Instead of a classic carpooling problem which will only allow a maximum of 4 passengers in a private vehicle, the authors of [107] introduced the Minimum Cost Vanpool Assignment Model (MCVAM) which allows a group of 9–15 passengers to share their commute to a common target location which is similar to the meeting point. MCVAM offers a one-way trip with one stop at a park-and-ride location to minimise the total cost for all employees. The Two-Stop MCVAM (TSMCVAM) which allows vanpools to stop at a second park-and-ride location is proposed in the same paper and showed significant cost savings as compared to MCVAM. Over the last decade, there has been only one paper that researches the vanpooling problem.

4.6. Multi-Modal Problem

Multi-modal problem refers to multiple modes of transportation involved in a trip with the rideshare concept. The multiple modes of transportation considered are trains, buses, bicycles, and so forth.

4.6.1. Exact Algorithms in the Multi-Modal Problem

In order to allow users to schedule multi-modal trips in a single task, the authors of [108] proposed a generalised ridesharing system that considers one-way carsharing vehicles and the transit system as the potential drivers for its users. A multi-objective MIP is presented to maximise the rate of ride-matching while minimising the inconvenience factor for passengers. The conventional branch and bound algorithm is used in CPLEX to solve for the multi-objective MIP. Furthermore, the work in [109] presented a fully integrated ridesharing system with an existing transit network to increase the coverage area of the transit system. The new proposed shared mobility system involved commuters with workplace and ride-back guarantee. A pure binary program is formulated and solved by an aggregation-disaggregation algorithm to achieve optimality.

Furthermore, the authors of [110] extended the work in [26] to investigate the potential of ridesharing and designed a P2P ridesharing system for transit transport to further improve the transit ridership. Apart from the integration of ridesharing and public transit, the authors of [111] designed a transit-feeder system using multiple sustainable modes which include P2P ridesharing, bikesharing and walking. The proposed system provided travel alternatives, modes, routes and information across multiple modes. Then, to examine the potential benefit of integration between ridesharing and public transit, in [112] a single or multi-modal rideshare problem is introduced that considers the integration and synchronisation of ridesharing and public transit with a solution approach that can solve the problem in an optimal way.

Ridesharing is implemented to reduce the pressure on the existing transport network. However, there exist no effective ways to further integrate carpooling into public transport due to the fuzziness and flexibility of carpooling. Thus, the authors of [113] proposed multi-modal route planning which allows riders to travel to destinations using different combinations of modes. In the ride-matching scenario, ride requests can be matched or unmatched depending on the number of vehicles on road. To avoid the unassigned requests, the work in [114] proposed a multi-modal car and ridesharing problem which assigned different modes of transportation to ride requests. In the problem, ride requests are covered by car while the uncovered ride requests can be assigned to other modes of transportation. The problem is formulated into a vehicle scheduling problem to further optimise the allocation of requests to multiple modes of transportation. A two-layer decomposition algorithm based on column generation is used to solve the problem.

4.6.2. Heuristic and Metaheuristic Algorithms in Multi-Modal Problems

An Angle-based Clustering (AC) algorithm is proposed in [115] to solve both small and large settings of the integrated ridesharing and public transportation system by considering time constraints. The AC algorithm is developed based on three main stages. The first stage is to split the passengers who have a similar or nearby destination into several clusters to further reduce the size of the optimisation model. In the second stage, the total distances between each cluster that formed in first stage are combined and one shared vehicle is assigned to each cluster. In the last stage, a MILP model is used to solve each cluster simultaneously to find the optimal decision in fixing the vehicle assignment decisions. The AC algorithm is proved in solving a relatively large scale multi-modal transportation system problem with less computational effort.

4.6.3. Other Algorithms in the Multi-Modal Problem

The lack of literature related to the integration of existing mobility-on-demand service with other transportation networks, such as bus and rail, reveals a gap that has brought inefficiency in transporting riders to the destination. Therefore, in [116] is proposed a bi-/multi-modal vehicle dispatching and routing algorithm to address the real-time operating ridesharing services with the presence of the public transportation network. A solution algorithm with a shareability concept is proposed to group the requests with similar origins and destinations together for the optimal assignment of passenger vehicles. This could reduce the cost and create seamless bi-/multi-modal trips.

The work in [117] showed how the authors designed an On-Demand Multi-modal Transit Systems (ODMTS) with ridesharing. This is a combined transportation service of fixed bus/rail routes with on-demand shuttles to serve the first/last mile problem. The proposed ODMTS with ridesharing considered a two-step framework which consists of network design optimisation and fleet sizing optimisation. In the first step, a MIP model for the ODMTS with ridesharing is formulated. This is solved by using the route enumeration algorithm to find pickup or drop-off routes to group riders who travel to/from the same hub in an effort to further minimise the total cost (routing cost and operation cost). In the second step, fleet sizing optimisation is discussed and modelled as a maximum flow problem with a covering constraint to ensure the number of shuttles needed is minimised while meeting all the requests by the ODMTS. Through a set of experiments using real-world data, the results showed that the integration of ridesharing into the ODMTS resulted in great improvement in terms of operating cost, passenger convenience, and the number of operating shuttles, as compared to the existing transit system.

5. Current Trends

5.1. Descriptive Analysis

This subsection addressed the third research question highlighted in Section 3.1. Table S1 in the Supplementary File of this paper tabulates the summary of papers based on the Types of SMP. A chart with the number of papers according to the Types of SMP is presented in Figure 3. Out of 103 selected papers, there are 56 papers categorised under ridesharing which is the greatest number among the literature. This is followed by carpooling (22), taxisharing (13), multi-modal (10), buspooling (2) and vanpooling (1).

Meanwhile, Table S2 (see Supplementary File) presents the summary of papers based on the problem variants of the SMP. There are two different categories in terms of the problem variants. The first category is based on the number of drivers and riders (D–R) which has four different sub-categories. They are One-to-One (1–1), One-to-Many (1–M), Many-to-One (M–1), and Many-to-Many (M–M). They represent a single driver–single rider, single driver–multiple riders, multiple driver–single rider, and multiple driver–multiple riders, respectively. The second category of the problem variants is based on the number of origins and destinations (O–D) which can also be divided into four sub-categories. They are One Origin–One Destination (1O1D), One Origin–Multiple Destinations (1OMD), Multiple Origins–One Destination (MO1D), and Multiple Origins–Multiple Destinations (MOMD).

In Figure 4, from the 56 papers reviewed in ridesharing, 24 of the papers are categorised under the 1–M problem. There are 18 of the 1–1 ridesharing papers which comes in second in rank. The third is the M–M ridesharing problems which covers 10 papers. There are three papers categorised under M–1 problem. There is only one paper under the MOMD ridesharing problem.

From the 13 papers reviewed in taxisharing, 6 of the papers are categorised as the 1–M problem (see Figure 5). The 1–1, M–M, and MOMD problems are covered in two papers, which sees them ranked second. Lastly, there is one study categorised as taxisharing under 1OMD problem.

In Figure 6, from the 21 papers reviewed in carpooling, the 1–M problem is in 9 of the studies, which makes it the highest percentage among all other problem variants for carpooling. The MOMD and 1–1 carpooling problems are covered in 4, which sees them ranked the second highest. The MO1D problem is covered in 2 which sees it come in at the third position. The M–1 and 1OMD carpooling problems rank last, being in one study.

Of the two papers of the buspooling problem, one is categorised under the 1–1 problem and another is the 1–M problem. For the vanpooling problem, only one paper is found in the review and this is categorised under the 1–M problem. Both problems are relatively new in the literature as compared to other problems in SMP.

Table S3 (see Supplementary File) shows the summary of papers based on the problem characteristics of the SMP. The problem characteristics are Decentralised (DC), Multi-Objective (MO), Multi-Hop (MH), Ride-Back (RB), Transfer Point (TP), Time Window (TW), Meeting Point (MP), Role Flexibility (ROF), Route Flexibility (ROUF), Arrival Time Flexibility (ATF), Time Flexibility (TF), Driver Detour Flexibility (DDF), Pickup and Delivery Flexibility (PDF), Stable Matching (SB), Static (STA), Stochastic (STO), and lastly, Dynamic (Dy). The descriptions of the characteristics are stated below. A large-scale optimisation problem with many participants can be hard to solve using a centralised approach. In a DC approach, large-scale optimisation problems can be decomposed or clustered into smaller sub-problems in a short time [41].

In a single-objective optimisation problem, only one optimisation goal or aim is focused on in the study. On the other hand, a MO optimisation problem involves two or more optimisation goals in the study. The RB or so-called return restrictions is a feature which allows a participant with a car to leave their vehicle at the meeting point and join the carpool during the planning horizon. Therefore, they can return to the meeting point, where the car is parked, to drive to the final destination [64]. Meanwhile, a MH ridesharing system allows drivers to carry multiple riders at the same time and riders to transfer between vehicles or different modes of transportation [25].

A TP allows passengers to be transferred between multiple drivers. The driver drops off passengers at the transfer point and another driver will bring those passengers to their final destination [28]. Transfer services play an important role in mitigating the shortage of vehicle supply. It can ensure a high rate of ride-matching with a smaller number of vehicles on road. It is also proven that transfer services reduce the total travel distance. Furthermore, a MP can be an alternative point for riders to be picked up and dropped off instead of at the origin or destination. This meeting point can act as a hub for drivers to pick up and drop off multiple riders without visiting every riders’ origins and destinations. It shortens the travel time, travel distance and cost in providing transportation services [50]. A TW is a time constraint where a customer or a task must be served within a certain time interval or time frame [118].

A ROF indicates that the participants’ roles are flexible and can be changed in-between, either as a rider or a driver [21]. A DDF indicates the vehicles are not free to move everywhere and are limited by the vehicles’ sources and destinations with possible detour flexibility [48]. Meanwhile, a PDF indicates the potential pickup/delivery locations are further selected from within the same areas, with proper adjustment to reduce the system cost and improve the matching rate with less inconvenience cost [55]. The TF indicates how much earlier a participant is willing to leave in exchange for being paired with another participant [35], while ATF indicates how flexible the participants are, in terms of time, to reach their final destination. This influences the matching rate in ridesharing [69]. The ROUF indicates the routes of the drivers involved in the rider’s itinerary are not fixed to first-come, first-served order. This allows the driver’s route to be flexible for the other riders [26].

The SB represents rideshare matches that considered a certain notion of stability to maximize the participation rate in a ridesharing [17]. In STA ridesharing, the matching of ridesharing requests must be made in advance. In STO environment, the simulated data involved random variables that are similar to real-time data. On the other hand, in Dy ridesharing, the ride-matching is matched within an instant and it may change over time. Riders in Dy ridesharing can join the ridesharing anytime and at any location without any booking in advance.

Figure 7 shows the distribution of papers based on the problem characteristics mentioned earlier. The most researched problem characteristic is the TW which appears in 59 papers. The one with second-highest coverage is MO (51). In short, TW and MO are the most common problem characteristics considered in SMP. On the other hand, both ATF and PDF are the least studied (1) among the types of problem characteristics. Those problem characteristics could be the potential areas for future studies to create more precise and detailed results.

Similar patterns can be observed for ridesharing, taxisharing, and carpooling problems on the distribution of the papers where both TW and MO are the most researched problem characteristics. These observations are clearly presented in Figure 8, Figure 9 and Figure 10.

In this review, there are two papers which focus on the buspooling problem. Both of the papers have the DC characteristics. In addition, each of the papers has an extra characteristic which is MO and TW, respectively. For the vanpooling problem, only one paper is found in the review and this is categorised as a TW problem.

Figure 11 shows the distribution of papers based on the problem characteristics for multi-modal ridesharing. About a quarter of the papers on multi-modal ridesharing researched in TP. On the other hand, MO problem characteristics are covered in six papers. TF, DC, and RB is the least-studied problem characteristics in multi-modal ridesharing which only accounted for one paper each.

Table 5 reveals the different types of data characteristics researched in SMP over the years. It is observed that the static and dynamic problems are the most popular topics among the researchers with 49 and 48 papers, respectively. Moreover, four papers considered both the static and dynamic problems in the SMP. The stochastic problem is the least researched in this study, as it only accounted for two papers.

In Table 6, we see that the dynamic ridesharing problem is the most popular problem focused on as compared to other types of data characteristics. The dynamic ridesharing problem is covered in 37 of the papers in the review. Slightly more than half of the papers in the taxisharing problem considered the static problem, making it the most among other papers in the review for taxisharing. Only two papers considered the buspooling problem and both are concerned with the static problem. This single focus is also the case where there is only a single vanpooling paper and it too considered the static problem. In the carpooling problem, 18 papers considered the static cases while the remaining 3 papers focused on the dynamic cases. No research is conducted on the stochastic carpooling problem. In Multi-Modal problem, six of the multi-modal-related papers focused on the dynamic problem while the remaining four of the papers focused on the static problem. No research is conducted on the stochastic multi-modal problem.

Table S4 (see Supplementary File) presents the summary of papers based on the 19 distinctive optimisation objectives of the SMP. The optimisation objectives are: Travel Time (TM), Number of Vehicles on Road (NV), Total Cost (TC), Travel Distance (TD), Waiting Time (WT), Delay Time (DT), CO${}_2$ Emission (CE), Number of Transfer (NT), Passengers’ Inconvenience Cost (PIC), Penalty Cost (PC), Number of Modal Changes (NMC), Waiting Distance Cost (WDC), Subsidy (SD), Number of Matched Rides (NMR), Ride Profit (RP), Evaluation Credit Score (ECS), Seat Usage Rate (SUR), Quality of Service (QoS), and lastly, Social Welfare (SW).

Minimisation of TC stands for the cost minimisation for the driver or rider to travel from one origin to one destination [31]. Meanwhile, minimisation of TM refers to the shortest time taken to travel for the driver or rider from one location to one destination [64]. TD minimisation represents the shortest distance path for either the driver or rider from origin to a destination [23]. Minimisation of CE is one of the objectives that takes the CO${}_2$ emission from the vehicles into consideration [76]. Minimisation of the NV is to reduce the number of drivers on the road by maximising the successful matching of riders and drivers [45].

As for the DT, the smallest difference between the desired arrival time and the actual arrival time for a trip is to be minimised [102]. On the other hand, WT for the driver and rider can be different in terms of waiting as a target. Minimisation of the driver’s WT is to minimise the time used by a driver to wait for the rider at the pickup point while minimisation of the rider’s WT is to minimise the time wasted to wait for the driver at the origin point [62]. Minimisation of the NT is for the smallest number of transfers of the rider between multiple vehicles along a trip [111]. A rideshare concept among nations might be hard to implement in the preliminary stage. However, with the government’s support, ridesharing among nations can be greatly popularised. Having said that, investing a large amount of subsidy towards the rideshare plan can be a high expense. Hence, the minimisation of SD is important while ensuring a high ridesharing rate among nations [20].

A PC represents the cost charged onto the drivers or riders who arrive at the destination early or late. Thus, the PC is to be minimised [69]. The PIC cost is caused by the detours from picking up and dropping off passengers below a certain limit which should be kept minimised to further reduce the cost for both the drivers and riders [18]. The NMC stands for a condition where the travellers might ask to change from one mode of transportation to another mode of transportation throughout the trip. The NMC minimisation represents the changes of transportation mode along the trip is to be minimized. This means the trip is made with fewer transfers between different types of modes [108]. On the other hand, a WDC represents the distance for a rider to wait for a driver. Thus, the minimisation of WDC stands for the distance for a driver to drive from a location to rider pickup point [82].

Maximisation of the NMR represents the matching of the driver and rider with a similar itinerary are maximised in order to optimise the demand (rider) and supply (driver) of the market [83]. Moreover, RP is to maximise the revenue and at the same time, minimise the cost for the driver, so that the profit earnings for the trips are maximised [90]. The ECS is a rating of each user that establishes interpersonal trust and the responsibility of the user in the carpool system. The maximisation of ECS is to reduce the unstable matching between the drivers and riders [81]. Meanwhile, the QoS is the quality of the driver in serving the rider throughout a trip. The QoS is evaluated based on the driver’s utility and the rider’s satisfaction level [39]. The maximisation of SUR is to encourage a more efficient use of existing vehicle seats to meet the demand from the riders [84]. Lastly, the SW maximisation represents the high-quality matches to maintain stable matching among the drivers and riders [20].

Figure 12 shows the distribution of the 19 optimisation objectives of the SMP. The highest coverage is the minimisation of TC with 63 papers, followed by the maximisation of NMR and minimisation of TD with 29 papers each. On the other hand, the maximisation of QoS and SW, as well as the minimisation of SD, and NMC, are the least researched in SMP with only one paper each.

Based on Figure 13, the minimisation of TC covered the largest percentage of papers (33 papers) that considered the ridesharing problem. This is followed by works on the minimisation of TM, the maximisation of the NMR, and the minimisation of TD which cover 16, 16, and 15, respectively.

Referring to Figure 14, the minimisation of TC covers the largest portion of works in the taxisharing problem (nine papers). This is followed by TM minimisation which covers four papers. The maximisation of the NMR and minimisation of TD are ranked third among the other objectives in the selected papers.

In Figure 15, the minimisation of TC covers 14 of the papers, which is the largest portion covered in the optimisation objective of carpooling problem. The minimisation of the TD and maximisation of the NMR are the second (7 papers) and third (5 papers) largest, respectively. The minimisation of NV, PC, and CE have the coverage of one paper each.

For the multi-modal problem, the largest percentage of paper coverage in Figure 16 is the minimisation of TC (six papers). The minimisation of TM and maximisation of the NMR are ranked second highest among the other objectives which is covered in four papers.

There is one vanpooling-related paper among the selected literature. The only objective that is considered is the minimisation of the TC. On the other hand, there are two selected papers that fall under the buspooling problem. The considered objectives in the buspooling problem are the TD minimisation and the NMR maximisation which are covered in two papers and one paper in the review, respectively.

Table S5 (see Supplementary File) gives a list of the detailed approaches used in the selected literature to solve the SMP. On the other hand, Table S6 (see Supplementary File) presents a summary of the types of approaches used in the papers for solving the SMP. The approaches are categorised into three different types, which are exact approach, heuristic and metaheuristic approaches and other approaches. The distribution of the 103 selected papers based on the solution approaches used for the SMP over the last decade are tabulated in Table 7 below.

The solution approaches are grouped into four different categories, which are: (i) exact only; (ii) heuristic and metaheuristic; (iii) exact, heuristic, and metaheuristic; and (iv) other approaches. The research papers under the first category considered only the exact algorithm as the solution approach of the problem. The second category covered the selected papers which used heuristics and/or metaheuristics to solve the problem. The third category are the papers which proposed both new exact algorithm and heuristic/metaheuristic algorithms in solving the problem. For those research papers that make use of CPLEX or other exact approaches to compare the solutions (as the benchmark for small instances) of another newly proposed heuristic/metaheuristic are grouped under the second category instead of the third category. Lastly, the papers which used other methods such as simulation method are categorised under the fourth category.

As shown in Table 8, the heuristic and metaheuristic approaches are the most popular approaches considered in solving the SMP, especially for ridesharing, carpooling, and taxisharing problems. This is followed by the exact algorithm. Note that there no research has been conducted in taxisharing and carpooling problems using other approaches. The only paper on the vanpooling problem used the heuristic approach to solve the problem. Of the two papers related to buspooling, one makes use of both exact, heuristic and metaheuristic approaches while the other paper focuses on heuristic and metaheuristic approaches. Seven of the papers on the multi-modal problem make use of the exact algorithm to solve the problem. Two of the papers used other approaches while the remaining paper employed heuristic and metaheuristic approaches.

5.2. Overall Observations

Under the problem variants, there are two types of classification proposed by [5,15]. The authors of [5] proposed a problem classification based on the number of drivers and riders while [15] proposed another type of problem classification based on number of origins and destinations. The classification from [15] does not receive much attention as they only considered the origin and destination in classifying the variants. On the other hand, the classification in [5] is much more welcoming as it can consider whether the riders can be transferred to another driver in between the trips (such as M–1 and M–M).

In term of the simplicity of the problem, it can be ranked from low complexity to high complexity which are 1–1, M–1, 1–M, and M–M, respectively. Among all problems, 1–1 is the simplest because it involves a single-vehicle transport with a single passenger (or multiple passengers who share the same destination locations). However, it does not fit well in a real life situation where vehicles can be fully utilized. The 1–M problem has the highest coverage in the review due to its practical usage. The 1–M scheme allows drivers to serve multiple passengers which can greatly utilise the vehicle’s seat capacity.

There are four categories according to data characteristics. These are: (i) static, (ii) stochastic, (iii) dynamic, and (iv) static and dynamic. In the static case, the vehicle task allocation can only be planned if the passenger information is known in advance. The stochastic case is a scenario that is similar to a real-life situation where some of the data are uncertain instead of fixed. Meanwhile, a dynamic shared mobility system can bring riders and drivers with similar travel patterns and schedules together on very short notice. The paper that considers a static problem first and further extends it to the dynamic problem is assigned to the fourth category (static and dynamic scenario).

The use of software packages, real-time services, financial incentives, and social networking platforms is involved and impacts the current era of shared mobility [2]. They have resulted in a gradual increase of the dynamic SMP in recent decades [5]. Dynamic shared mobility requires an automated matching system so that passengers’ demand can be scheduled on very short notice. In short, the dynamic shared mobility system is a problem with high complexity that requires a great deal of attention from researchers [26]. It could be the reason for the increasing trend of dynamic shared mobility studies as referred to in Table 5. As mentioned before, the dynamic shared mobility system is a high-complexity problem. Therefore, a number of researchers tend to start off with the static case before coming to the dynamic case.

When considering the optimisation objective, as can be observed in Figure 12, one finds that cost minimisation, travel distance minimisation and travel time minimisation have the highest coverage among all other objectives. These objectives can be considered as the most common and general objectives that are widely utilised in different routing-related problems to achieve a “best” solution. Additionally, the maximisation of number of matched rides is another objective that has received great attention. It is also important to note that this objective is very closely related to the dynamic matching-related problem.

There is an increasing awareness of the extent of damage inflicted to the environment by human activities. This has resulted in the usage of science and technology to be more eco-friendly and beneficial towards the policy of environmental protection. Even though there are fewer studies that are concerned with the minimisation of CO${}_2$ emissions (CE) in shared mobility systems (see Figure 12), soon it will become an inevitable criterion in developing an eco-friendly system or product. This will spur interest in more studies on this topic.

In Table 8, heuristic and metaheuristic algorithms have the highest coverage as compared to others due to their black-box optimisation that can solve large instances in low computational time, even though it cannot guarantee optimality. However, the obtained heuristic or metaheuristic solution solely presented cannot validate the obtained solution is a “best” solution. The proposed new exact algorithm is capable of finding a high-quality solution for medium and large instances within a reasonable time. Hence, there is a need to have exact solutions as a benchmark to compare with the solution obtained by a heuristic and metaheuristic. The reason why there are a certain number of research papers which are categorised under the third category (exact, heuristic, and metaheuristic) as shown in Table 8. There are some researchers that make use of an exact algorithm to test the proposed model before moving on to using a heuristic or metaheuristic.

6. Challenges and Future Works

The last research question is addressed in this section. The advancement of technology has greatly improved the living environment of modern people today. For modern people with high purchasing power, buying a vehicle can be a simple matter. In seeking a high-quality lifestyle, people tend not to take public transport but to use personal vehicles. Hence, the increased number of vehicles on the road has slowed down the traffic flow and caused traffic congestion. The idling of vehicles on the congested road emitted a high level of CO${}_2$ which polluted the air. There is a need to enforce eco-friendly transport fuels in reducing air pollution. At the same time, proposing shared transportation can be feasible to reduce the surging number of vehicles.

6.1. Adoption of Hybrid Algorithms

In term of algorithm implementation, exact, heuristic and metaheuristic algorithms are widely adopted in solving the formulated model of the ridesharing problem. An exact algorithm can guarantee optimality while heuristic and metaheuristic algorithms are able to solve the problem using less computational time. There are several new exact algorithms such as the modern column generation, relaxation, and decomposition approaches which were developed to solve large instances. It can be an interesting field of study to be considered for future work. The widely adopted decomposition algorithm in vehicle-routing-related studies are Dantzig decomposition, Lagrangian Decomposition, Benders decomposition and the other extended variants of the decomposition approaches. Those exact algorithms play an important role in developing the tighter lower bounds in order to be able to benchmark the developed heuristics against the optimal solution for large problem instances. CPLEX is the most common method that is used to obtain the optimal solution but it can only deal with small instances. Therefore, there is a need for a new exact algorithm that can decompose large instance problems into less complex subproblems and achieve optimality within a reasonable time.

In terms of heuristic and metaheuristic, a hybrid algorithm is largely adopted because it can achieve the balance of intensification (optimality) and diversification (shorter computational time). The hybridisation can be a hybrid between metaheuristic, heuristic, mathematical programming, and other algorithms from different fields of study. Since the ridesharing problem is a NP hard problem, then there is a need to have a hybrid algorithm. Referring to [119], the hybridisation of the decomposition approach with a metaheuristic could be considered for future studies as a powerful algorithm to be used in vehicle-routing-related problems. With regards to the performance of the algorithms, in [120] it was proposed that the culture of “individual competition” be switched to one of a “collective knowledge discovery”. Instead of competing among different algorithms to prove which methods perform better, it is better to understand which of the algorithms are more efficient in solving a specific problem.

6.2. Revitalisation of SMP during the Covid-19 Pandemic

The Covid-19 crisis has changed the lifestyle of millions of people worldwide. The gradual increase of Covid-19 cases had forced governments to implement a lockdown strategy to restrict the mobility of the people. The restriction of mobility has reduced the use of public transport and ridesharing. Some forecast that the pandemic will end the development of shared mobility and further adversely affect the practice of sustainable urban mobility which has experienced rapid growth over the years. Most of the transportation network companies and public transportation services providers are affected, as passengers prefer to avoid contact with strangers on shared transportation. They were forced to adapt their business practices by adopting strategies such as providing barriers between driver and passenger, equipping the vehicle with sanitisers, and installing digital thermometers to measure passengers’ body temperature in order to eliminate the virus infection threat [121]. These measures may have an important role in rejuvenating the ridesharing and public transportation market. However, the added precautionary measures may cause a surge in fares. Hence, there is a need to conduct research on the “willingness of use” among passengers based on the suggested strategies.

The authors of [122] performed a study on the effect of the current strategies towards the “willingness to use” among passengers. Based on the results of the research, passengers are more willing to use taxi and ride hailing if intensive sanitising of the vehicles is performed more frequently. It was also found that the action of providing free masks, gloves, or sanitisers brought less effect on the “willingness to use” among taxi and ride hailing users. These results can be useful references for countries in implementing further measures. In terms of future work, this can be considered as one of the optimisation objectives in formulating a new SMP.

Apart from the taxi and ridesharing, an owned car is claimed as the safest mode of transportation, followed by bike sharing, scooter sharing and jump scooter sharing. This is shown in [123], where bike sharing in Budapest showed an increased trend throughout the Covid-19 pandemic. Although this systematic review paper does not discuss bike sharing, it is still an interesting aspect that can be considered in the SMP with the inclusion of health issues and other modes of transportation.

6.3. Implementation of SMP into Mobility as a Service

The conventional approach, such as adding the number of routes, trains, and parking garages, can no longer solve the problem of our congested urban areas. With the advancement of technology, Mobility as a Service (MaaS), as an emerging concept, can be another new direction and challenge to implement in reducing vehicle ownership on-road [124].

This concept integrates the new modes (private transport) and other conventional modes (public transport) in achieving seamless mobility. It is a business service that aims to create a cooperative and interconnected between different modes of transport such as public and private transport in fulfilling customers’ mobility need with a common interface [125]. In the real-life scenario, travellers not only choose a route but also the types of transportation modes to travel. MaaS takes away users’ trouble in making their own transport decision and allows them freedom of movement. There is a study that performed synchronisation of the ridesharing concept and tour planning (in the form of MaaS). Research related to MaaS is still limited. The lack of a transparent market to test the appeal of integrated multi-modal mobility service offerings is a challenge for future research. Without sizeable trials, noticeable outcomes of MaaS aligned with sustainability objectives may be unlikely to be achieved. Furthermore, the authors of [126] introduced a novel rideshare-oriented MaaS model in route planning and activity scheduling with rideshare concepts to enhance the mobility of people. However, its implementation and sizeable trials are still limited. Therefore, the assimilation of shared mobility services into the MaaS can be further extended.

6.4. Adoption of Electric Vehicles in SMP

Green and sustainable issues are widely spread in shared mobility. The adoption of alternative fuel vehicles in commercial and private fleets can be one of the green issues. The authors of [127] adopted autonomous electric vehicles in the ridesharing system, while [22] is another related study that considered the CO${}_2$ in the ridesharing system. There are various types of Alternative Fuel Vehicles (AFVs), such as Battery Electric Vehicles (BEVs), Fuel Cells Electric Vehicles (FCEVs), Flexible Fuel Vehicles (FFVs), Natural Gas Vehicles (NGVs), Hybrid Electric Vehicles (HEVs), and Plug-in Hybrid Electric Vehicles (PHEVs). Each type of alternative fuel vehicle has its own merits in the aspects of operation cost, emissions, lifetime, safety, range, network requirements, refuelling stations, and refuelling time. The electric vehicle is the main focus as it is one of the most popular ones among other alternative fuel vehicles.

The challenges related to the combination of the ridesharing problem with the electric vehicles result in a more complex scenario to deal with. The related research of electric vehicles is limited in terms of strategy and operation. Hence, the challenge is associated with the ability to cope with a real-world situation. The incorporation of electric vehicles in logistics and transportation can be favourable in term of sustainability. In the categories of electric vehicles, it can be PHEVs, HEVs, FCEVs, and BEVs [128]. PHEVs and BEVs have the problem of range anxiety for the users as they can only charge at a charging station or at home. With the advancement of technology, HEVs and FCEVs do not have such problems in travelling as they can be refuelled with gasoline for HEVs or hydrogen fuel (FCEVs). However, HEVs still produce harmful emissions, while FCEVs is a zero-emission vehicle. Thus, FCEVs are highly anticipated and are becoming a trending research topic in sustainability as compared to other alternative fuels vehicles. In FCEVs, the cost of the produced energy is much higher as compared to the conventional vehicles on the road [129]. Due to the limited recharging or refuelling station in the early stage, the number of refuelling and recharging stations and the location for the stations to be installed should be taken into consideration.

The second challenge is related to the adoption of electric vehicles. In terms of economic aspects, the cost of the conversion of conventional vehicles to electric vehicles could be an investment for commercial companies. Companies do not need to pay huge costs to renew their whole fleet to EVs because with a very marginal investment they can retrofit their current fleet to include the new alternative fuel vehicles [130]. The wide adoption of EVs among companies in the preliminary stage can stimulate infrastructure suppliers to invest in an extensive infrastructure roll-out [131]. This potential dilemma is often called the “chicken–egg problem” of alternative fuels or “lock-in”, when neither party acts because it waits for the other. As the number of alternative fuel stations increases, it will urge more nations to participate in the market of alternative fuel vehicles. However, the condition might be different when it comes to private owning due to the high cost. Hence, subsidies from the government play an important role in reducing the cost and provide a great push for the growth of these green energy vehicles [132].

Apart from the price of the vehicles, the adding of the refuelling station for FCEVs or upgrading the existing natural compressed gas station is another cost in enabling the operation of sustainable vehicles. The amount of refuelling or recharging stations and the ideal location for them to be installed should be another concern in implementing electric vehicles.

Regarding the operation aspects, efficient route planning with the inclusion of fuel cell vehicles plays a vital role in popularises it among the public. Due to the limited refuelling station in the early stage, the refuelling stations should be included in the working plan of the route planning. Notable advantages of fuel cell vehicles to be used in smart cities bring the necessity to redesign the transportation system to be used. To greatly maximise the usage of electric vehicles in smart cities, there is a need to redesign the whole transportation system to enjoy its benefits entirely.

6.5. Inclusion of Multi-Tier and Multi-Modal Characteristic into Combined People and Freight Transportation Service with the rideshare Concept

Most of the studies only focus on one mode of transportation in performing logistics and transportation. The logistics and transportation are not synchronised effectively. The capacities of the different modes of transportation on road are not utilised fully and effectively. There exists literature on handling ridesharing with multi-modal mean, such as [111], but there are still a very limited number of studies related to the integration of both logistics and transportation in multiple modes of transportation with ridesharing. People and freight are seldom sharing transportation modes, especially in short-haul transportation, although they largely share the same infrastructure. The demands of passenger and freight transport overlap, especially during peak hours. To have a seamless movement of people and parcels, the integration of people and freight flows with multiple modes of transportation can be another area of future research. The authors of [133] present one of the few studies that consider the share-a-ride problem, an efficient planning model, to facilitate people and freight flows using taxis. The authors focussed on transferring parcels and people without the rideshare concept. Hence, the inclusion of the rideshare concept into the integrated people and parcel delivery system is believed to improve the usage of the available seats. Apart from the taxis network, ref. [134] proposed an integrated freight delivery system with scheduled public transportation that can greatly reduce number of the vehicles needed for freight delivery. Since there exists a multi-modal related study in the ridesharing system, then the formulation of multi-modal methods in transportation service with a rideshare concept for both parcels and people can be another future direction of the work.

To make joint use of transport capacity between passengers and goods, in [135] a two-tier transportation problem is introduced in which buses are the first-tier transport and city freighters are the second-tier transport. In the first tier, buses transport goods from the distribution centre to a set of bus stops which act as transit hubs for the goods. In the second tier, city freights deliver the goods from bus stops to the final destinations. Apart from single-tier and two-tiersystems, multi-tier systems are very scarce in the existing literature. A multi-tier distribution system is a system that can keep the large freight fleets away from entering the urban area to avoid congestion problems. For example, the first tier can feature large vehicles such as big trucks or trailers which deliver goods to an intermediate facility or a transit hub, whereas the second tier with smaller vehicles delivers goods to the final destinations. With multi-echelon, city logistics can be more efficient and sustainable. A multi-tier system with multi-transfer can be another direction of study in creating a much more efficient transportation system with fewer vehicles circulating in the urban cities.

7. Conclusions

From the selected literature, the SMP is showing an upward trend and it is expected to continue growing over the next few decades. In this systematic review, a total of 110 papers are reviewed and classified according to different criteria. The detailed classification of SMP with an optimisation algorithm aims to help with the decision-making process in an uncertain environment. The findings show that the heuristic/metaheuristic algorithm is applied the most in the selected literature. This indicates the advancement of computation power as an important catalyst for the solving of SMP. Furthermore, multi-modal-related studies have received more attention of late as compared to single-mode transportation. Instead of sharing rides among vehicles, multi-modal tranport, such as public buses, rail and bicycles, can be alternate modes to include in a journey for the rider along the itinerary. With the detailed analysis of the problem variants, characteristics and solution approaches, this study has identified the main challenges and research opportunities related to optimisation of the SMP. Hence, this study can serve as an important reference with detailed information to help city planners navigate towards more sustainable city planning.

Supplementary Materials

The following are available online at https://www.mdpi.com/article/10.3390/app11177996/s1, Table S1: Summary of Papers based on the Types of SMP, Table S2: Summary of Papers based on the Problem Variants of SMP, Table S3: Summary of Papers based on the Characteristics of SMP, Table S4: Summary of Papers based on the Optimisation Objectives of SMP, Table S5: List of Algorithms employed in selected Papers for SMP, and Table S6: Summary of Papers based on the Solution Approaches of SMP.

Author Contributions

Conceptualisation, K.H.T., L.S.L. and S.P.; methodology, K.H.T., L.S.L. and S.P.; validation, K.H.T. and L.S.L.; formal analysis, K.H.T., L.S.L. and H.-V.S.; investigation, K.H.T. and L.S.L.; resources, K.H.T.; writing—original draft preparation, K.H.T., L.S.L. and H.-V.S.; writing—review and editing, K.H.T., L.S.L. and H.-V.S.; visualisation, K.H.T., L.S.L. and H.-V.S.; supervision, L.S.L. and S.P. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

This research was supported by ITIS GmbH–Universiti Putra Malaysia through International Grant (ITIS-UPM/2021/W164709/6380076-10065).

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:

P2P	Peer-to-Peer
SMP	Shared Mobility Problem
PRISMA	Preferred Reporting Items for Systematic Reviews and Meta-Analysis
1–1	One-to-One
1–M	One-to-Many
M–1	Many-to-One
M–M	Many-to-Many
1O1D	One Origin–One Destination
1OMD	One Origin–Multiple Destinations
MO1D	Multiple Origins–One Destination
MOMD	Multiple Origins–Multiple Destinations

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures and Tables

Figure 1. Literature selection procedure (PRISMA four-phase flow diagram).

Figure 2. Numbers of Papers based on the Year of Publication.

Figure 3. Number of Papers based on the Types of SMP.

Figure 4. Distribution of Papers based on the Problem Variants: Ridesharing.

Figure 5. Distribution of Papers based on the Problem Variants: Taxisharing.

Figure 6. Distribution of Papers based on the Problem Variants: Carpooling.

Figure 7. Distribution of Papers based on the Problem Characteristics.

Figure 8. Distribution of Papers based on the Problem Characteristics: Ridesharing.

Figure 9. Distribution of Papers based on the Problem Characteristics: Taxisharing.

Figure 10. Distribution of Papers based on the Problem Characteristics: Carpooling.

Figure 11. Distribution of Papers based on the Problem Characteristics: Multi-Modal.

Figure 12. Distribution of Papers based on the Optimisation Objectives.

Figure 13. Distribution of Papers based on the Optimisation Objectives: Ridesharing.

Figure 14. Distribution of Papers based on the Optimisation Objectives: Taxisharing.

Figure 15. Distribution of Papers based on the Optimisation Objectives: Carpooling.

Figure 16. Distribution of Papers based on the Optimisation Objectives: Multi-Modal.

Table 1

Related Review Papers.

Paper	Highlights	Year	Number of Papers
[4]	Challenges in economic, social, institutional, and technological aspects.Benefits and drawbacks of dynamic ridesharing.Future direction of dynamic ridesharing.	1974–2010	12
[5]	Characteristics of dynamic ridesharing, rideshare variants, and multi-modal ridesharing problem.	1977 – 2012	38
[2]	Explored the history of ridesharing in North America for five key phases.	1942–2011	43
[1]	Detailed classification of the ridesharing system and matching agencies.	1961–2013	52
[6]	Discussed the evolution of dynamic ridesharing from the past and present to its future with information and communication changes.	1977–2011	19
[7]	Reviewed P2P ridesharing variants literature with solution algorithms. Future direction is discussed.	2004–2020	42
[8]	Reviewed carsharing, ridesharing and carpooling with solution algorithms. Challenges and opportunities of ridesharing.	2008–2019	86

Table 2

Distribution of papers according to type of publication over the years.

Type of Publication	Year
	2010	2011	2012	2013	2014	2015	2016	2017	2018	2019	2020	2021	Total
Journal	0	4	3	5	6	7	9	10	12	13	15	3	87
Conference Proceedings	0	4	5	2	2	3	2	3	1	1	0	0	23
Total	0	8	8	7	8	10	11	13	13	14	15	3	110

Table 3

Distribution of Papers according to Real-World Dataset over the Years.

Country	Year
	2010	2011	2012	2013	2014	2015	2016	2017	2018	2019	2020	2021	Total
USA	0	1	3	1	4	1	2	5	5	3	5	1	31
Ireland	0	0	0	0	1	0	0	0	0	0	0	0	1
Norway	0	0	0	0	0	0	0	0	0	0	1	0	1
Turkey	0	0	0	0	0	0	0	0	0	0	1	0	1
France	0	0	0	2	0	3	1	1	0	0	1	0	8
Italy	0	0	0	1	0	1	1	1	0	0	0	0	4
Taiwan	0	3	1	0	2	0	1	0	1	1	1	0	10
Singapore	0	0	0	0	0	1	0	0	0	1	0	0	2
Austria	0	0	0	0	0	0	0	0	0	0	1	0	1
China	0	0	0	0	0	2	2	1	0	2	3	0	10
Switzerland	0	0	0	0	0	0	0	0	1	0	0	0	1
Korea	0	0	0	0	0	0	1	0	0	0	0	0	1
Brazil	0	0	0	1	0	1	0	0	0	0	0	0	2
Luxembourg	0	0	0	0	0	0	0	1	0	0	0	0	1
Australia	0	0	0	0	0	0	0	1	0	0	0	0	1
Iran	0	0	0	0	0	0	0	0	0	1	0	0	1
Total	0	4	4	5	7	9	8	10	7	8	13	1	76

Table 4

Classification of the Shared Mobility Problem.

Types	Problem Variants		Data Characteristics	Solution Approaches
	Drivers and Riders (D–R)	Origins and Destinations (O–D)
Ridesharing	One-to-One	One Origin–One Destination	Static	Exact Algorithms
Carpooling	One-to-Many	One Origin–Multiple Destinations	Stochastic	Heuristic and Metaheuristic
Taxisharing	Many-to-One	Multiple Origins–One Destination	Dynamic	Other Algorithms
Vanpooling	Many-to-Many	Multiple Origins–Multiple Destinations
Buspooling
Multi-Modal

Table 5

Distribution of Papers based on the Data Characteristics over the Years.

Data Characteristics	Year
	2010	2011	2012	2013	2014	2015	2016	2017	2018	2019	2020	2021	Total
Static	0	3	3	2	3	2	6	4	10	9	7	0	49
Stochastic	0	0	0	0	0	1	1	0	0	0	0	0	2
Dynamic	0	4	3	2	4	6	4	8	3	5	7	2	48
Static & Dynamic	0	0	0	1	1	1	0	1	0	0	0	0	4
Total	0	7	6	5	8	10	11	13	13	14	14	2	103

Table 6

Distribution of Papers based on the Data Characteristics.

Data Characteristics	Ridesharing	Carpooling	Taxisharing	Vanpooling	Buspooling	Multi-Modal	Total
Static	17	18	7	1	2	4	49
Stochastic	1	0	1	0	0	0	2
Dynamic	37	3	2	0	0	6	48
Static & Dynamic	1	0	3	0	0	0	4
Total	56	21	13	1	2	10	103

Table 7

Distribution of Papers based on the Solution Approaches over the Years.

Solution Approaches	Year
	2010	2011	2012	2013	2014	2015	2016	2017	2018	2019	2020	2021	Total
Exact only	0	1	0	0	2	3	4	4	3	2	3	0	22
Heuristic & Metaheuristic	0	6	6	3	3	5	7	4	9	10	10	1	64
Exact, Heuristic, & Metaheuristic	0	0	0	1	3	2	0	3	0	2	1	0	12
Other Approaches	0	0	0	1	0	0	0	2	1	0	0	1	5
Total	0	7	6	5	8	10	11	13	13	14	14	2	103

Table 8

Distribution of Papers based on the Solution Approaches.

Solution Approaches	Ridesharing	Carpooling	Taxisharing	Vanpooling	Buspooling	Multi-Modal	Total
Exact only	14	0	1	0	0	7	22
Heuristic & Metaheuristic	33	18	10	1	1	1	64
Exact, Heuristic, & Metaheuristic	6	3	2	0	1	0	12
Other Approaches	3	0	0	0	0	2	5
Total	56	21	13	1	2	10	103