Developing an Optimal Peer-to-Peer Ride-Matching Problem Algorithm with Ride Transfers

Abstract

Thanks to recent developments in ride-hailing transit services throughout the world, the peer-to-peer (P2P) ride-matching problem has been actively considered in academia in recent years. P2P ride-matching not only reduces travel costs for riders but also benefits drivers by saving them money in exchange for their additional travel time. However, assigning riders to drivers in an efficient way is a complex problem that requires focusing on maximizing the benefits for both riders and drivers. This study aims to formulate a multi-driver multi-rider (MDMR) P2P ride-matching problem, based on rational preferences and cost allocation for both driver and rider, which also allows riders to transfer between multiple drivers for their travels if needed. Tabu Search (TS) for system-optimal ride-matching and a Greedy Matching (GM) algorithm for stable ride-matching were developed to solve ride-matching cases. The results show that the developed algorithm can successfully solve the proposed P2P MDMR ride-matching problem. MDMR P2P ride-matching can be used in areas where not much demand for ride-sharing exists, or for long-distance travel. Also it can be applied to designs for a more efficient on-demand transit network which can allow for transfers between routes. Moreover, the comparison of results between two implemented approaches shows that system-optimal centralized ride-matching can bring more cost savings for all participants in the system, although it may not always be stable when riders and drivers can choose their ride-matching for their own maximum benefit.

Keywords

public transportation matching ride-hailing ride-sharing

In recent years, ride-sharing has become an important element of urban transportation. Thanks to emerging smartphones and mobile apps, it has become easy to connect travelers and drivers offering ride-sharing through these on-demand transit services ( 1 ). In the United States, major ride-hailing companies like Uber and Lyft have invested substantial funding in improving shared services to travelers. For example, Uber, a ride-hailing company, has the ride-sharing option called UberPool, which offers cheaper prices than those of ride-hailing services.

Although many studies have shown that shared ride-hailing services provide financial advantages and benefits to transportation networks over regular ride-hailing services, shared ride-hailing mobility services still have some issues that raise questions about their efficiency ( 2 ). Shared ride-hailing mobility may also increase deadheading for the ride provider and consequently increase travel time for ride requesters, which makes the system less efficient, with higher vehicle-miles traveled (VMT) ( 3 ). Recently, scholars have considered peer-to-peer ride-sharing services to solve these issues.

A peer-to-peer ride-matching service (P2P RMS) is similar in many aspects to ride-hailing services; however, some fundamental differences make it more profitable in certain situations. Mainly, shared ride-hailing services are provided by transportation network companies (TNC); both the operator and ride provider should financially benefit from the service, and ride providers make trips just for the money without any other purpose. In P2P RMSs, ride providers have their own trips and need to be compensated for the additional travel to provide a service, so trip costs for the ride requester will be cheaper than the trip costs of the ride-hailing company ( 4 ). Moreover, the stability of matching is an issue that is highlighted in P2P RMSs, where drivers and riders can only be matched when there is a reasonable cost saving for them. The flexibility of the ride-sharing system is a key factor that makes the system profitable for both drivers and riders, and in the current market, this flexibility is more easily achieved than at any time before, thanks to app-based platforms and developed algorithms ( 5 ).

This study proposes a novel stable P2P ride-matching problem (RMP) to optimize the multi-driver, multi-rider matching and routing problem, allowing riders to transfer between drivers (vehicles) and share a ride with other riders. Then, it develops optimal algorithms to solve the proposed problems based on Tabu Search (TS), and Greedy Matching (GM) approaches. This study also compares the performance of the proposed model for stable and non-stable matching cases. The main motivation of this study is to have better insight into practical comparisons of stable and non-stable matching algorithms and also into use of transfer points to optimize matching drivers and riders (whether short-distance travel or long-distance) in the transportation network. Allowing riders to transfer between vehicles may increase the chance of having more possible feasible matches between participants, and will also reduce the cost by decreasing the total traveled distance in the system, which will benefit both the rider and the driver. Furthermore, considering transfer points can be useful in areas with a low ride-sharing demand and less access to public or paratransit systems. The results of this study could be utilized by TNCs and on-demand shared mobility service agencies. The organization of this study is as follows: The next section provides a comprehensive review of background studies. The third section describes the proposed problem and two algorithms to solve the model. Section four discusses the performance of the developed algorithms on a hypothetical example, and, finally, the last section concludes this research.

Literature Review

With the emerging shared transit modes in urban areas, scholars have studied the RMP widely in recent decades. The RMP is basically a combinatorial optimization problem that aims to find matches between drivers who are willing to provide rides and riders who need rides by considering feasibility and profitability constraints. RMPs are mainly associated with transit modes that can deliver and pick up passengers simultaneously by request; therefore, RMPs are often considered as demand-responsive and dial-a-ride problem (DARP) studies.

In the past few decades, DARPs have been widely considered by scholars. Generally, the homogeneity of the variables and the status of passengers’ request orders are the main challenges that motivate scholars to optimize DARPs ( 6 ). The homogeneity of the problem is related to adding variables that make the model more realistic, like multi-hubs ( 7 ), varying vehicle capacity, transfer of passengers ( 8 ), and the degree of circuity (DOC) (9, 10). Alternatively, the system’s flexibility in serving passengers has been increased by transforming the problem from static to dynamic, so the transit system can accept a new request while operating ( 11 ).

In DARPs, ride providers are considered as a separate entity as an operator, while in P2P RMP the ride operator can be considered as a user of the system ( 12 ). Furthermore, with DARPs, the availability of vehicles and ride requests is known in advance, while in a P2P RMP, this availability is not deterministic as riders will be matched to ride providers by considering spatial–temporal availability after readiness of the ride providers and feasibility of matching. This special attribute makes the P2P RMP more complicated than DARP, especially when other constraints need to be considered, such as allocating riders with special needs to specific ride providers ( 13 ) or considering the time window constraint for each rider ( 14 ). Stiglic et al. ( 15 ) introduced the concept of meeting points in the RMP. An optimal algorithm has been developed to maximize the number of matched drivers and riders to save ride providers’ driving distance. The concept of the transfer station, applied by Masoud and Jayakrishnan ( 13 ), can make the ride-matching system more efficient by increasing the chance of matching between more riders and drivers. The transfer stations work as given spots where riders can be switched to another driver to continue their trips. The transfer stations are not necessarily located at drivers’ starting or end points; however, serving riders at transfer stations could be more acceptable to drivers as it makes for less complexity and confusion ( 13 ).

Generally, in past related studies, RMPs have been categorized by complexity, as single-driver single-rider (SDSR), single-driver multiple-rider (SDMR), and multiple-driver multiple-rider (MDMR). Agatz et al. ( 16 ) investigated a single-driver and single-rider P2P RMP to optimize unmatched announcements, aiming to maximize the saved travel distance of the drivers. They believed the performance of driver–rider matching is highly dependent on the spatial–temporal status of the ride requesters. Boyacı et al. ( 17 ) solved a one-way vehicle-sharing problem using a simulation approach aimed at maximizing the net revenue for the operator and net benefits for users.

Considering the ability of riders to transfer between drivers makes the problem more complicated. A few scholars have considered the MDMR RMP. Masoud and Jayakrishnan ( 13 ) developed a multi-hop P2P ride-sharing system as a binary optimization problem in which a rider was able to transfer between multiple drivers. They used a decomposition algorithm to solve the model optimally. In another work by Masoud and Jayakrishnan ( 12 ), they developed a flexible ride-sharing system as a dynamic, real-time, and multi-hop system with the ability to find itineraries for a rider by means of optimally routing drivers. Following this study, Tafreshian and Masoud ( 18 ) proposed a one-to-many RMP based on a graph partitioning algorithm that grouped journeys into several sub-problems.

Recently, some studies focused on rational aspects of ride-sharing participants (both ride provider and ride requester). Preferences considering saving money for riders and drivers are the main focus of these studies. Silva et al. ( 19 ) considered a quota traveling salesman problem with passengers (QTSP) to solve the RMP, to increase the flexibility of the model for serving riders in meeting points (alighting and boarding). Although their model aimed to increase satisfaction for both riders and the driver, the proposed model neglected the stability of matching. Wang et al. ( 20 ) developed a stable ride-matching model to fairly distribute cost allocation between driver and rider; however, they considered an average cost saving between driver and rider, which is unfair in some matches. Furthermore, their proposed model was an SDSR problem that was limited to realistic and substantial service. Ma et al. ( 21 ) modified the algorithm by introducing the theory of two-sided matching to solve the ride-sharing stable matching problem by considering cases in which a driver may receive identical benefits for a match with a rider which turned the problem into a stable matching problem with incomplete preference. Also, their developed model was an SDMR problem which is more useful than SDSR.

Since the P2P RMP was recognized as an NP-hard problem ( 22 ), most of the past studies used heuristics and metaheuristics to solve the problem; however, some other studies were based on the goal and scale of the problem using a simulation-based approach (22 –26). The objective functions of the previous related research included maximizing the number of rider and driver matches (14, 15, 24, 27 –30), maximizing the total number of assignments (31 –33), optimizing system costs and benefits (14, 17, 30 , 34 ), travelers’ mode choice (35 –37), and optimizing total distance savings (16, 22, 24).

Although various types of the P2P RMP have received considerable attention in recent years, little knowledge is available about the stable MDMR problem allowing transferring riders between multiple vehicles. Only one study by Peng et al. ( 33 ) considered a stable MDMR problem to optimize matching assignment and pricing; however, their model was unable to permit riders to transfer between multiple drivers. Therefore, this study has two main contributions beyond the reviewed studies. First, it proposes a novel two-stage integer programming model for the MDMR problem according to the SDMR matching problem’s extension. Second, it develops an optimal algorithm to solve the stable MDMR problem considering rational preferences and cost allocation for drivers and riders while allowing a rider to transfer between multiple drivers. Another contribution of this study is to solve the proposed model for both stable and non-stable forms and compare the total cost savings.

Methodology

As discussed in the literature review section, two main approaches in the ride-matching strategies are stable matching and non-stable matching. The stable matching system is a decentralized system, while a non-stable matching system is a centralized system. Although the stable matching approach provides a stable solution, it may not provide the most efficient peer-to-peer ride-matching for the entire system because of the smaller total number of matches as a result of only including rational matches for both the rider and the driver. Therefore, in general, non-stable matching provides more matches in the system, while this may not be individually optimal for both drivers and riders in some circumstances. Figure 1 shows a simple example network with two drivers (D1 and D2) and two riders (R1 and R2). Assume that the cost of trips is commensurate with the shortest distance traveled to reach the destinations. In Figure 1, the vertices represent the location related to origin (shown with superscript “O”) or destination (shown with superscript “D”) of the rider (R)/driver (D), the arrows show the connection between locations, and the value on the arrows indicates the cost of a ride between the two vertices—which is directly related to distance between the two locations. Without ride-sharing, each rider/driver rides from his/her origin to his/her destination (using routes, D₁^O–D₁^D, D₂^O–D₂^D, R₁^O–R₁^D, R₂^O–R₂^D); consequently, each trip costs $6 (total system cost is $24). However, with ride-matching, if R1 and D1, as well as R2 and D2 are matched, for system optimization, the cost per match is $10 (with route D^O–R^O–R^D–D^D, accordingly cost of $2 + $6 + $2) and total system cost becomes $20 ($10 + $10), which cuts $4 from the individual trips.

Figure 1.

Example of ride-sharing network.

Although the system-optimal ride-sharing solution ensures system cost minimization, those ride-matchings are not stable because D1 and R2 ride-matching lowers their travel costs from $10 to $9.20 (with route D₁^O–R₂^O–R₂^D–D₁^D, and a consequent cost of $1.60 + $6 + $1.60), and they will not accept the system-optimal ride-matching. Considering the ride-matching of D1 and R2, it is optimal for R1 and D2 to ride individually with a total cost of $12 rather than to have ride-matching. Thus, in this case, the total system cost increases to $21.20 ($6 + $6 + $9.20) from the system-optimal solution of $20. This ride-matching that gives individual cost minimization is called stable ride-matching. It is a more realistic ride-matching solution when the individuals choose their own ride-matching.

Problem

In this paper, a many-to-many ride-sharing system is considered for which the centralized system matches groups of riders and drivers and offers itineraries to drivers. The system begins its work when a set of participants requests trips as drivers or riders. Each participant applies for an origin and a destination within an allowable time window. All origins and destinations of drivers and riders are considered as potential transfer stations. A transfer station is a meeting location where a rider can be transferred to another driver so as to complete his/her trip. Furthermore, riders can choose their maximum allowed transfers between vehicles, and drivers can decide the maximum number of passengers on board at the same time during their entire trip. Therefore, each time a rider or a driver applies for a trip in the system, the information about these preferences is requested and registered.

The model should be able to consider a case in which a driver can provide a ride from the rider’s origin to the rider’s destination and also from the rider’s origin to the transfer point. We considered that the participants cooperated with the system for the financial efficiency of the service as well as for personal-interest goals such as the effect on the environment. Therefore, the objective of the problem is considered as being to maximize the total travel distance savings of all participants, which also corresponds to minimizing total travel costs. In this problem, a rider can take all of his/her trip with one driver or can be switched to another driver in the middle of his/her trip at a transfer station. According to whether it would minimize total travel costs, the mathematical model decides whether a rider should be switched to another driver in the middle of his/her trip. In this regard, the model considers all possible cases of matches (a set with n drivers and m riders that has at most 2n×2m possible matches) where the number of participants in the match is less than a predefined value, and calculates the optimal costs of these matches; therefore, the model chooses the best case by comparing the total costs of each matching.

In many-to-many ride-sharing systems, riders may be assigned to multiple drivers, transferring between multiple vehicles. Therefore, the system sets the location where each driver picks up and drops off the rider. When the system matches a set of riders with a set of drivers, it means that the trip timing of all participants becomes coordinated as the itineraries. Matches and trips offered by the system should satisfy the participants, or they may choose not to accept the offer, and they will no longer use the system. Two important aspects of participant satisfaction are the timing and cost of their trip. We assume that matches and itineraries are feasible only if they fulfill the timing requirements of all participants as a constraint. There may be ride-sharing matches that satisfy the participants’ timing constraints but do not generate positive vehicle-mile savings. Indeed, to consider a match as feasible, the involved participants should also benefit with respect to the travel cost when accepting the offer. As just mentioned, when the system matches a set of riders with a set of drivers, the trip timing of all participants becomes coordinated as the itineraries. Therefore, in case of one participant’s delay, the mutual dependence of the time scheduling of participants may result in delay to other participants grouped in a match. To overcome this issue, the maximum number of participants in each match is restricted. When a set of drivers are matched with a set of riders, an optimization problem is solved to determine the itinerary of each of the participants and their start and end time of the trip. We assume that the vehicle-mile savings (cost savings or benefits) of sharing a ride are divided equally between the ride’s participants. Another option is to divide the cost saving of a ride among the participants of the match, according to each participant’s trip distance when driving alone.

A good ride-sharing system should produce matches that are stable; we define stability as the concept notation in cooperative game theory. In fact, we call a solution stable when no groups of riders and drivers prefer to depart from their current partners and match together, the latter including the case in which a subset of riders or drivers prefer to reject some of their current partners. Riders and drivers may not use the system if they believe they can establish a better match with higher cost saving on their own. The following are the known parameters of the problem.

Parameters:

$P$ : The set of participants in the system including riders and drivers

$R$ : The set of riders

$D$ : The set of drivers

$TS$ : The set of meeting points/transfer stations, where participants can start and end their trips, and riders can change vehicles in these points

$O_{p}$ : The transfer station where participant $p \in P$ starts his/her trip

$D_{p} :$ Destination of the participant $p \in P$

$t t_{mn} :$ Travel time between each pair of locations $m, n \in TS$

$di s_{mn}$ : Distance between each pair of locations $m, n \in TS$

$e d_{p}$ : The earliest time participant $p \in P$ can start her/his trip in her origin $O_{p}$

$l a_{p} :$ The latest time when participant $p \in P$ must arrive at his/her destination $D_{p}$

$f_{r}$ : The maximum number of transfers between vehicles acceptable for rider $r \in R$

$C a_{d} :$ Maximum number of passengers driver $d \in D$ can carry in his/her vehicle

Let A and B represent the set of all non-empty subsets of R and D, respectively. We introduce the set $A_{r}$ as the set of members of $A$ which include $r \in R$ and $B_{d}$ as the set of members of $B$ which includes $d \in D$ . In this way, $A = ⋃_{r \in R} A_{r}$ and $= ⋃_{d \in D} B_{d}$ .

To model the problem, the preference lists of all groups of participants should be known. The preference list of a group of riders/drivers consists of the set of feasible matches ranked based on the corresponding best ride-share cost savings. The best ride-share with the maximum cost saving between any two groups of the drivers and riders, along with the associated cost saving, can be determined through the model (formulations 11 to 30) in the next subsection. The solution of the model also determines whether a match is feasible or not.

We denote the preferences with the following notation: a $>_{c}$ b denotes that person c prefers person a to b, and a $\geq_{c}$ b denotes that either a $>_{c}$ b or person c is indifferent whether person a or person b. If the cost saving of two ride-shares for a group of drivers/riders is the same, the riders/drivers are indifferent to the two matches. Thus, preference lists may contain ties. Moreover, some matches may be infeasible; so the preference list may be incomplete as well.

By definition of sets A and B, the problem can be modeled as a generalized matching problem between members of sets A and B. Whenever a match is established between two groups of riders and drivers, the members of the two sets share rides together and the trip timing of all participants becomes correlated with their itineraries. To the best knowledge of the current document authors, unlike SDMR, the MDMR ride-sharing problem is not formulated as a matching problem so far. Let $x_{ab}$ represent a binary decision variable equal to 1 if a ride-share match between riders of the set $a \in A$ and drivers of the set $b \in B$ is established and 0, otherwise; and let $g_{ab}$ represent the corresponding cost saving. Moreover, Let $B (a)$ be the set of all members $b$ of the set $B$ where matching $a$ with $b$ is feasible and let $A (b)$ be the set of all members $a$ of the set $A$ where matching $a$ with $b$ is feasible. As mentioned earlier, the feasible matches and the parameter $g_{ab}$ are determined by solving another model (formulations 11 to 30) which is described later in the document.

Max \sum_{a \in A} \sum_{b \in B (a)} g_{ab} x_{ab}

(1)

subject to

\sum_{a \in A_{r}} \sum_{b \in B (a)} x_{ab} \leq 1 \forall r \in R

(2)

\sum_{b \in B_{d}} \sum_{a \in A (b)} x_{ab} \leq 1 \forall d \in D

(3)

\begin{matrix} x_{ab} + \sum_{a^{'} \neq a \subset a} \sum_{b^{'} \in B : b^{'} ⪰ a^{' b}} x_{a^{'} b^{'}} + \sum_{b^{'} \neq b \subset b} \\ \sum_{a^{'} \in A : a^{'} ⪰ b^{' a}} x_{a^{'} b^{'}} \geq 1; \forall a \in A; \forall b \in B (a) \end{matrix}

(4)

x_{ab} \in {0; 1} \forall a \in A; \forall b \in B

(5)

The objective (1) maximizes the total cost saving of the system, which coincides with minimizing the total travel cost. Constraint sets 2 and 3 force each rider (driver) to be matched with at most one group of drivers (riders). Constraint 4 forces the model to generate a stable solution. These constraints state that each pair of riders (set $a \in A$ ) and drivers (set $b \in B$ ), matched or a subset of the members of the set $a \cup b$ , prefers their current match to this one.

In fact, at least one of the three outcomes below must happen for each pair of riders $a \in A$ and drivers $b \in B$ :

$a$ is matched with $b$ and therefore $x_{ab} = 1$ .

Members of the set $a$ are not united for pairing with set $b$ . Therefore, a proper subset $a^{'} \neq a \subset a$ exists where $a^{'}$ is paired with $b^{'} \in B$ , that is, $x_{a^{'} b^{'}} = 1$ , and the members of set $a^{'}$ prefer their current match to pairing $a$ with $b$ , that is, $b^{'} ⪰ a^{' b}$ and $\frac{g_{a^{'} b^{'}}}{| a^{'} | + | b^{'} |} > \frac{g_{ab}}{| a | + | b |}$ .

Members of the set $b$ are not united for pairing with set $a$ . Therefore, a proper subset $b^{'} \neq b \subset b$ exists where $b^{'}$ is paired with $a^{'} \in A$ , that is, $x_{a^{'} b^{'}} = 1$ , and the members of set $b^{'}$ prefer their current match to pairing $a$ with $b$ , that is, $b^{'} ⪰ a^{' b}$ and $\frac{g_{a^{'} b^{'}}}{| a^{'} | + | b^{'} |} > \frac{g_{ab}}{| a | + | b |}$ .

To be precise, the stability constraints (4) can be replaced with the following constraints, where $z_{p}$ is the cost saving of participant $p \in P$ in the current match and $q_{p}^{ab}$ is a binary variable that is equals to 1 if participant $p$ saves less when $a$ is matched with $b$ than its cost saving in the current match. Furthermore, set $a$ is matched with set $b$ if the binary variable $q_{0}^{ab}$ equals 1.

z_{r} = \sum_{a \in A_{r}} \sum_{b \in B (a)} \frac{g_{ab} x_{ab}}{| a | + | b |} \forall r \in R

(6)

z_{d} = \sum_{b \in B_{d}} \sum_{a \in A (b)} \frac{g_{ab} x_{ab}}{| a | + | b |} \forall d \in D

(7)

x_{ab} \geq q_{0}^{ab} \forall a \in A, \forall b \in B (a)

(8)

z_{p} \geq q_{p}^{ab} \times \frac{g_{ab}}{| a | + | b |} \forall a \in A, \forall b \in B (a); \forall p \in a \cup b

(9)

\begin{matrix} q_{0}^{ab} + \sum_{\forall a^{'} \subset a, b^{'} \subset B (a^{'})} \underset{Π_{\forall p \in a^{'} \cup b^{'}}}{Π} q_{p}^{ab} + \sum_{\forall b^{'} \subset b, a^{'} \subset A (b^{'})} \\ \underset{\forall p \in a^{'} \cup b^{'}}{Π} q_{p}^{ab} \geq 1 \forall a \in A, \forall b \in B (a) \end{matrix}

(10)

Constraints 6 and 7 define $z_{p}$ as the cost saving of participant p in the current match. Constraint set 8 forces the set of drivers $a$ to be matched with the set of riders $b$ , if $q_{0}^{ab}$ equals 1. Constraint set 9 forces the variable $q_{p}^{ab}$ to equal zero if the cost saving of participant $p$ is increased when the set of drivers a is matched to the set of riders b. Constraint 10 forces each set of riders $a$ and set of drivers $b$ to be matched or at least two sets $a^{'}$ and $b^{'}$ exist where $a^{'} \subset a, b^{'} \subset B (a^{'})$ or $b^{'} \subset b, a^{'} \subset A (b^{'})$ , and for all members of the sets $a^{'}$ and $b^{'}$ , the cost saving is decreased if the match between sets a and b happens.

Feasibility and Profitability Conditions of Ride-Matching

When a set of drivers b is matched with a set of riders a, the problem of finding the best itinerary for each driver is modeled through restricting the set of drivers and riders to the members included in the sets a and b denoted by SD and SR and by using four sets of decision variables as defined in the following. Moreover, the set of stations is restricted to the ones included in the largest polyhedral generated by connecting the riders and drivers in the match. In fact, the model (formulations 11 to 30) inputs a subset of stations $S \subseteq TS$ , a subset of riders $SR \subseteq R$ and a subset of drivers $SD \subseteq D$ as a matched group, and finds the best itinerary for each driver in SD such that all riders and drivers start their trips from their corresponding origins and end in their destinations in the allowed timing while the total cost savings of the trips are maximized. Therefore, the model also determines the drivers assigned to each rider and the stations where each rider should be taken on or get out.

In the proposed formulation, an equal number of stops for each driver, denoted by $K_{\max}$ , is considered, and we allow the model to repeat the destination of the driver at the end of his/her itinerary to consider all possible solutions of the problem. It is assumed that a driver, unlike a rider, may visit any transfer station more than once in their itinerary. Besides, although this is not a usual case, it is assumed a rider may change vehicle but return to the same one later.

$v_{mnk}^{d}$ Driver d travels from $m$ to $n$ and m is the kth stop of the driver d, $n \neq m \in S$

$y_{mnk}^{rd}$ Rider r travels with driver d from transfer station m to n when m is the kth stop of the driver d, $n, m \in S$

$z_{k}^{rd}$ Rider r starts a partial path with driver d at the driver’s kth stop

$t_{k}^{d}$ Trip starting time of driver d at the kth stop in the driver’s itinerary, where the service starting time at the first point is just the earliest departure time of driver d.

Then the formulation is as follows:

Min \sum_{d \in SD} \sum_{m \in S} \sum_{n \in S} \sum_{k} v_{mnk}^{d} \times di s_{mn}

(11)

subject to

t_{k + 1}^{d} \geq t_{k}^{d} + \sum_{m, n} t t_{mn} v_{mnk}^{d} \forall d \in SD; K_{\max} \geq k \geq 1

(12)

\begin{matrix} t_{k}^{d} + t t_{m D_{r}} - M (1 - y_{m D_{r} k}^{rd}) \leq l a_{r} \forall d \in SD; \forall r \in SR; \\ \forall m \in S; K_{\max} \geq k \geq 1 \end{matrix}

(13)

t_{k}^{d} \geq e d_{r} - M (1 - \sum_{m} y_{O_{r} mk}^{rd}) \forall d \in SD; \forall r \in SR; K_{\max} \geq k \geq 1

(14)

t_{K_{\max}}^{d} \leq l a_{d} \forall d \in SD

(15)

t_{1}^{d} \geq e d_{d} \forall d \in SD

(16)

\begin{matrix} \sum_{n} v_{mn, k + 1}^{d} = \sum_{n} v_{nm, k}^{d} \forall d \in SD; \forall m \neq O_{d}, \\ m \neq D_{d} \in S; K_{\max} - 2 \geq k \geq 1 \end{matrix}

(17)

\sum_{n} v_{O_{d} n, k + 1}^{d} = \sum_{n} v_{n O_{d}, k}^{d} \forall d \in SD; K_{\max} - 2 \geq k \geq 2

(18)

\sum_{n} v_{D_{d} n, k + 1}^{d} = \sum_{n} v_{n D_{d}, k}^{d} \forall d \in SD; K_{\max} - 3 \geq k \geq 1

(19)

\sum_{n} v_{n D_{d}, K_{\max}}^{d} = 1 \forall d \in SD

(20)

\sum_{n} v_{O_{d} n, 1}^{d} = 1 \forall d \in SD

(21)

\begin{matrix} \sum_{d \in SD} \sum_{n} \sum_{k} y_{mn, k}^{rd} = \sum_{d \in SD} \sum_{n} \sum_{k} y_{nm, k}^{rd} \leq 1 \\ \forall r \in SR; \forall m \neq O_{r}, m \neq D_{r} \in S \end{matrix}

(22)

\sum_{d \in SD} \sum_{k} \sum_{n} y_{O_{r} n, k}^{rd} = 1 \forall r \in SR

(23)

\sum_{d \in SD} \sum_{m} \sum_{k} y_{m, D_{r}, k}^{rd} = 1 \forall r \in SR

(24)

\begin{matrix} \sum_{r \in SR} y_{mn, k}^{rd} \leq C a_{d} \times v_{mn, k}^{d} \forall d \in SD; \\ \forall n, m \in S; K_{\max} - 1 \geq k \geq 1 \end{matrix}

(25)

\begin{matrix} z_{k}^{rd} \geq \sum_{m} \sum_{n} y_{mn, k + 1}^{rd} - \sum_{m} \sum_{n} y_{mn, k}^{rd} \\ \forall r \in SR, \forall d \in SD, K_{\max} - 2 \geq k \geq 1 \end{matrix}

(26)

\sum_{d \in SD} \sum_{k} z_{k}^{rd} - 1 \leq f_{r} \forall r \in SR

(27)

\begin{matrix} \sum_{d \in SD} \sum_{k} \sum_{m} t_{k}^{d} \times y_{smk}^{rd} \geq \sum_{d \in SD} \\ \sum_{k} \sum_{m} (t_{k}^{d} + t t_{ms}) \times y_{msk}^{rd} \forall r \in SR, \forall s \neq O_{r}, s \neq D_{r} \in S \end{matrix}

(28)

\begin{matrix} v_{mnk}^{d}, y_{mnk}^{rd}, z_{k}^{rd} \in {0, 1} \forall r \in SR; \forall d \in SD; \\ \forall n, m \in S; K_{\max} - 1 \geq k \geq 1 \end{matrix}

(29)

t_{k}^{d} \geq 0 \forall d \in SD; K_{\max} \geq k \geq 1

(30)

Equation 11 presents the objective function of the problem, minimizing the total distance traveled by all drivers. Constraints 12 to 16 force the model to satisfy the rider’s and driver’s latest arrival and earliest departure times. Constraint sets 17 to 19 enforce that the number of times a driver enters a transfer station equals the number of times he or she leaves the transfer station. Constraint set 20 directs the drivers out of their original transfer stations and constraint 21 ensures that drivers end their trips at their destination transfer stations. Constraint sets 22 to 24 route riders in the network. Constraint set 25 ensures that vehicle capacities are not exceeded and ensures that riders are accompanied by drivers throughout their trips. Constraints 26 and 27 limit the total number of transfers between vehicles for each rider. Constraint 28 ensures that riders leave a transfer station after they have arrived at it.

Then, $g_{ab}$ can be determined simply, using Equation 31 and the solution of the model formulations 11 to 30 for the feasible match between sets $a$ and $b$ . Note that

g_{a . b} = g_{SD . SR} = (\sum_{d \in SD} di s_{O_{d} D_{d}} + \sum_{r} di s_{O_{r} D_{r}} - \sum_{d \in SD} \sum_{m \in S} \sum_{n \in S} \sum_{k} v_{mnk}^{d} \times di s_{mn}) .

(31)

The designed problem may have unmatched riders and drivers if the timing constraint is not satisfied. In this case, the match between the set of riders and the set of drivers is considered as infeasible. Moreover, as mentioned earlier, there may be ride-share matches that satisfy the participants’ timing constraints but do not generate positive vehicle-mile savings, which are also considered infeasible matches. Thus, preference lists can be incomplete. Furthermore, when a set of riders are matched with a set of drivers, one does not expect the solution to generate disjoint itineraries for a subset of riders. However, in the optimal solution of presented formulations 11 to 31, disjointed itineraries can be generated and the output of these formulations is used as an input for formulations 1 to 4. For example, let D = {d1,d2,d3}t and R = {r1,r2,r3}. The solution may result in drivers d1 and d2 routing riders r1 and r2 to their destinations and driver 3 accompanying rider 3 throughout his/her trip. In this circumstance, the drivers’ routes are alike, r3 is matched with d3 and the set {r1,r2} is matched with the set {d1,d2}. Indeed, the disjointed itinerary is infeasible for formulations 1 to 4; thus, this solution is unstable and will not be chosen in the matching problem. This is because the trip cost associated with one of the disjointed sets can be increased when matching r3 with d3 and the set {r1,r2} with the set {d1,d2}. Therefore, the match will be considered infeasible in the second phase of the solution process. In fact, the solution process consists of two stages. In the first stage, parameter $g_{ab}$ should be determined by applying formulations 11 to 30 for any set of riders a and drivers b, and the preference lists of all groups of participants are also obtained. In the second phase, the output formulations 1 to 5 define the optimal solution of the stable RMP.

The model (formulations 11 to 30) is an NP-hard problem and solving the model within a reasonable time for even medium sizes is difficult. However, as mentioned before in the document, the model inputs a subset of riders SR and a subset of drivers SD as a matched group, and finds the best itinerary for each driver in SD such that all riders and drivers start their trips from their corresponding origins and end at their destinations in the allowed timing while the total cost savings of the trips are maximized. To overcome the issue caused by the dependence of the time scheduling of participants of a match to each other, the maximum number of participants in each match is restricted. Thus, one expects the sets SD and SR which are the inputs of the model to be small sets with cardinality mostly <3.

Optimization Methods

Two algorithms, TS and GM, were selected to solve the proposed problem. The GM algorithm is useful when matched samples with similar balanced characteristics are generated. The GM considers one-to-one and one-to-many matched pairs, while it does not allow for sampling with replacement ( 38 ). This GM algorithm has been widely used in ride-sharing studies to compute maximum matches (39 –42). The TS metaheuristic is known for its speed and ability to escape from local minima; however, the main advantage of TS which makes this algorithm suitable for ride-matching rests in its ability to set moving distance to search the optimal solution, while the algorithm can automatically adjust its parameters and change the direction of search. The TS metaheuristics have been implemented for solving ride-sharing/ride-matching problems thanks to the algorithm’s ability to set searching moving distance as an integer (35, 43). In the following, a GM heuristic is presented to solve Equations 1 to 5.

Greedy Matching (GM) Algorithm

Select the match (a,b) with the largest cost saving per participant. Note that the cost saving per participant of a match between set a and set b is determined by $\frac{g_{ab}}{| a | + | b |}$ .

Remove the members of sets a and b from the set of riders and drivers, respectively. Moreover, for each $r \in a$ and $d \in b$ , remove the members of the sets $A_{r}$ and $B_{d}$ from A and B, respectively.

Repeat step 1 and 2 until no feasible matches remain.

Theorem 1. The GM algorithm generates a stable matching solution.

Proof:

Let the algorithm solution be a Greedy Matching solution that is not stable. By definition, there must then exist a pair (a,b) for which $\frac{g_{ab}}{| a | + | b |} > z_{p}; p \in a \cup b$ . This is a contradiction because were this true the match (a,b) would have been selected before the other matches were considered for matching.

Corollary 1 of Theorem 1. If riders and drivers are never indifferent between any two possible matches, the GM algorithm generates the best stable solution with the maximum cost saving for the system.

Proof (by contradiction):

Let (a,b) be the first match selected in the GM solving procedure for which the set of riders a or drivers b are not united to match in the maximum cost-saving solution. For example, the set $a$ is not matched with set $b$ because an $a^{'} \subset a$ (or $b^{'} \subset b)$ exists that is already matched with other participants and members of $a^{'}$ (or $b^{'} \subset b)$ prefer their current match to matching $a$ with $b$ . Without loss of generality, consider that the set of riders a are not united. Let $(a_{1}^{'}, b_{1}^{″}), (a_{2}^{'}, b_{2}^{″}), \dots, (a_{k}^{'}, b_{k}^{″})$ , $k \geq 1$ be the match of members of $a^{'} .$ In this way, $\frac{g (a_{n}^{'}, b_{n}^{″})}{| a_{n}^{'} | + | b_{n}^{″} |} > \frac{g (a, b)}{| a | + | b |}$ ; for $1 \leq n \leq K$ and each $a_{n}^{'}$ prefers $b_{n}^{″}$ to match (a,b).

Note that the set of riders $a$ are the first which are not united. Therefore, participants who are matched with set $a^{'}$ that are matched already, for example, $b_{n}^{″}$ , prefer their current match, $a_{n}^{'}$ , to their match in the maximum cost-saving solution. Thus, both sides of the match ( $a_{n}^{'}, b_{n}^{″}$ ), prefer the match to match (a,b) and (a,b) is unstable in the maximum cost-saving solution. ▪

If riders and drivers, though, are never indifferent between any two possible matches, the GM algorithm generates the best stable solution with the maximum cost saving for the system. However, in the presence of indifference, randomly selecting the pair with the maximum cost saving per participant may lead to the loss of optimality. In this circumstance, all possible outcomes of the GM algorithm should be checked and the one with the maximum objective value is the best solution. Although for most cases the total number of this outcome is not large, finding the best stable matching using the GM algorithm is possible.

Tabu Search (TS) Algorithm

To calculate the effect of the selfish behaviors of the participants, Equations 1 to 3 and 5 are solved by employing a TS algorithm. The TS algorithm starts with a potential solution to the problem generated by using two random permutations of riders and drivers, where a rider and a driver with the same index in the two permutations are matched. This solution is considered as the bestMatch so far. Next, in each iteration of the algorithm, neighbors of the bestMatch are created in the hope of finding an improved solution. The algorithm considers solutions as neighbors if one driver and one rider, at most, are separated from their previous fellow travelers. The disjointed rider and driver may be matched or may join independent itineraries. Furthermore, there is a possibility for both to not match with anyone in the neighbor solution and continue their trips individually. The disjointed rider and driver and their new positions should be selected so that the neighbor solution satisfies feasibility. For each new solution, the objective function is calculated, and the algorithm moves to the next iteration by selecting the neighbor with the most improvement in the objective value as the new bestMatch solution. The iteration continues until it reaches MaxIteration. To determine the new objective value, there is no need to calculate the cost savings for all matches as the algorithm investigates the differences of the previous solution and its neighbor. Moreover, a match score is determined between any two pairs of the participants initialized to zero. In each iteration of the algorithm this score is updated as neighbors are created. The difference of the objective value of the neighbor solution and the current bestMatch is calculated. Then, if this value is greater (smaller) than zero, 1 is added (reduced) to (from) the match score of the new fellow travelers of the disjointed rider and driver and 1 is reduced (added) from (to) their previous co-travelers. The match score of any two participants falls under a specific value called MinimumMatchScore; the two are added to the tabu list and cannot be co-travelers for the next candidate solutions, in a particular number of iterations. Then the match score of the pair is set to zero again. Furthermore, the algorithm allows the tabu list to include at most a constant number of tabu pairs represented by TabuTenure. Each time a new tabu pair is added to the tabu list and makes the list’s length greater than TabuTenure, the oldest pair in the tabu list gets removed. Finally, the whole TS algorithm, from generating a random initial solution to reaching the MaxIteration iterations, is repeated a specific number of times denoted by MaxAlgorithmRepeat and the best match among these runs of the algorithm is selected as the best solution. Figure 2 shows the developed TS algorithm to solve the proposed P2P RMP. The platform of programming algorithms is MATLAB 2019a.

Figure 2.

Developed Tabu Search algorithm to solve the problem.

Example

The proposed model was applied to a numerical experiment in a hypothetical network to demonstrate its performance in solving the problem. The experiment considered 10 riders and 10 drivers in the problem instance; transfer station locations and participant origins and destinations (selected from the transfer stations) were generated randomly. The algorithms were coded in MATLAB 2019a and all the models were performed on a computer with CPU Intel^® Core(TM) i5-7400 3 GHz and 16 GB of RAM. The calculation times required to perform the GM and the TS algorithms for the hypothetical example were 34.2 and 45.1 s, respectively.

In Figure 3, origins and destinations of the participants are shown. To differentiate the drivers as well as the riders, each has a unique number, shown in Figure 3. For example, D2 represents the driver number 2.

Figure 3.

Destinations and origins of the participants in the generated problem instance.

Next, preference lists were created for all groups of riders and drivers. To create the preference lists, the cost savings of the matches were determined. Moreover, to make the computations faster, for each rider and a pair of two drivers, the algorithm determines the best interface transfer station for the rider to move between the two drivers. In this problem, the total number of transfers between vehicles for each rider is limited to two transfers.

The TS and the GM heuristic algorithms explained earlier in the document were used to solve the generated instance. The parameters were set as following. $f_{r} = 2, K_{\max} = 5,$ MaxIteration = 5000, MaxAlgorithmRepeat = 10, MinimumMatchScore = −10, TabuTenure = 30.

As mentioned before, the optimal stable solution can be obtained using the GM algorithm; however the TS algorithm produces an unstable solution. The difference between the objective values of the solutions generated using the two methods represents the “price of anarchy,” which shows the outcome of the selfish behavior of the participants in a practical ride-sharing setting.

The conclusions of the GM and the TS algorithms for the total cost saving of the ride-sharing system is determined as 7969.3 (meters) and 7604.8 (meters), respectively. In this sense, the price of anarchy is 364.5 (meters) which is a significant value in contrast to the cost savings. In fact, the total ride-sharing system cost saving can be increased by 4.8% if based on satisfaction level of the riders. Table 1 represents the results of algorithms for the proposed example. The total cost per kilometer has been considered as 35 cents, in accordance with the last travel reimbursement fees issued by the IRS ( 44 ), and the monetary saving calculation has been considered based on dollars per kilometer.

Table 1.

Results of Algorithms for the Proposed Example

Approach	Routes	Travel distance (m)	Travel distance if not matched (m)	Saving ($)	Total saving ($)
Greedy Matching algorithm	D3, D10, R2, R8	6870.6	11925.8	17.7	26.6
	D2, D4, D5, R9, R4, R3	9771.4	12321	8.9
	D1	500	500	0.0
	D6	2573.9	2573.9	0.0
	D7	250	250	0.0
	D8	2610.1	2610.1	0.0
	D9	2015.6	2015.6	0.0
	R1	2761.3	2761.3	0.0
	R5	2015.6	2015.6	0.0
	R6	1250	1250	0.0
	R7	707.1	707.1	0.0
	R10	1802.8	1802.8	0.0
Tabu Search algorithm	D8, D2, D4, R9, R10, R8	10582.4	14090.7	12.3	27.9
	D3, D10, R2, R4	6369.3	10830.3	15.6
	D1	500	500	0.0
	D5	2061.6	2061.6	0.0
	D6	2573.9	2573.9	0.0
	D7	250	250	0.0
	D9	2015.6	2015.6	0.0
	R1	2761.3	2761.3	0.0
	R3	1677.1	1677.1	0.0
	R5	2015.6	2015.6	0.0
	R6	1250	1250	0.0
	R7	707.1	707.1	0.0

As shown in Table 1, the total saving of the TS algorithm is higher than the GM algorithm because the GM algorithm provides an exact solution through a stable model while the TS algorithm is a metaheuristic approach and finds a near to system-optimal solution. Therefore, the TS model cannot be considered stable, but it opens doors to compromise between riders and drivers most likely to maximize the number of matches or the shared travel distances, which will bring more cost savings in the system.

In Figures 4 and 5, the participants who are grouped together as a match are connected with lines of the same color as their destinations and the transfer stations are shown in a red circle in these figures. As shown in Figure 4, itineraries as in the solution generated by TS algorithm, the matched groups are drivers 2, 4, and 8 with riders 8, 9, and 10 and drivers 3 and 10 with riders 2 and 4. As intended, some drivers (e.g., D2) carried a single rider (e.g., R8), while other drivers (e.g., D10) carried multiple riders (e.g., R2 and R4). Some riders (e.g., R9) were carried by a single driver (e.g., D4), while other riders (e.g., R4) were carried by multiple drivers (e.g., D10 and D3). Other drivers and riders not in the figure were unmatched for one of two reasons: either there was no match with cost saving for these riders and any of the respective drivers, or available matches were not possible because of the presence of at least one of the drivers in more cost-effective groups.

Figure 4.

Itineraries of the matched drivers and riders in the solution generated running the Tabu Search algorithm.

Figure 5.

Itineraries of the drivers and single riders’ paths in the solution generated running the Greedy Matching algorithm.

As shown in Figure 5, the GM algorithm consists of three groups of matched drivers and riders. In one group, drivers 2, 4, and 5 are matched with riders 3, 4, and 9. In the second group, drivers 3 and 10 are matched with riders 2 and 8. In the third group, drivers 9 and 7 are matched with riders 2 and 7. Like the results from the TS algorithm in Figure 5, some drivers (e.g., D10) carried a single rider (e.g., R2), while other drivers (e.g., D2) carried multiple riders (e.g., R9 and R4). Some riders (e.g., R4) were carried by a single driver (e.g., D2), while other riders (e.g., R2) were carried by multiple drivers (e.g., D3 and D10).

Conclusion

In recent years, shared mobility has become more available and attractive because of its economic efficiency, environmental advantages, and social equity aspects, especially where traditional transit service is not available. Among the shared mobility modes, P2P ride-sharing is considered the most economical and desirable because each individual involved in the ride-sharing has a purpose for their travel, and drivers only need to be compensated for the additional travel distance and costs, which makes the ride-sharing more affordable for riders compared with ride-hailing or shared ride-hailing services. P2P ride-sharing not only requires trust between drivers and riders, but it also requires technological advancement to match drivers and riders efficiently. Recent studies have improved ride-matching algorithms; however, this problem still has room for improvement because of its complexity in respect of consideration of spatial and temporal constraints with financial feasibility—to achieve minimization of total travel distance while maximizing the benefits for both drivers and riders.

In this research, a MDMR P2P RMP based on rational preferences and cost allocation for both driver and rider was developed, and TS and GM algorithms were formulated. With the MDMR algorithm, not only can drivers transport multiple riders in their trips but also riders can transfer between multiple drivers for their journeys if needed. A hypothetical example was developed to evaluate the performance and the computational efficiency of the proposed algorithms, and the developed algorithms could successfully solve the proposed P2P MDMR RMP.

One important result of this study comes when we compare the results of the models in two forms of stable matches and non-stable matches. The TS algorithm provides a near-optimal solution for system cost savings in which a better matching performance between riders and drivers is expected rather than the stable form of the model generated by the GM algorithm. Obviously, the metaheuristic approach using TS is seeking to minimize the total costs by relaxing stability constraints in the model; therefore, more cost savings and matches are expected in this approach than would be expected with a stable model. The maximization of the total cost saving of the system depends on how the rider and driver(s) can compromise on costs and trade-off. Therefore, ride-sharing should consider incentive policies and reduce some constraints to boost the flexibility of the non-stable approach to maximize the number of matches.

In most short-distance travel, ride transfer may not look practical. However, for long-distance travel, finding a feasible ride-match may be very difficult, and with a ride-transfer option it is possible to increase ride-matching and reduce total costs. Also, this ride-matching with ride-transfer algorithm can be used for multiple on-demand flexible transit routings. Since the proposed algorithm has a main focus on long-distance trips, this makes the algorithm more applicable in rural areas where fewer transportation options are available and travel distances are relatively longer. The results show that a centralized ride-matching system may convince the driver of the potential for a profitable service in rural areas; it may also eventually make the whole system more profitable (or less costly) in rural areas.

Future research could add more specific matching constraints between drivers and riders, such as same-gender matching, and also use other metaheuristics and solving approaches. In addition, other heuristic methods could be tested so that the efficiency of the algorithm can be improved. Moreover, the proposed P2P RMP introduces a set of transfer stations randomly before matching the drivers and riders and then finds the optimal transfer station among the existing stations. Future studies should find the optimal locations of transfer stations before the matching and also consider more factors such as the waiting times for vehicles and transfers in the model.

Footnotes

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: YL and AN; data collection: AN, MM, YL; analysis and interpretation of results: AN, YL, MM; draft manuscript preparation: AN, YL, MM. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the Urban Mobility & Equity Center at Morgan State University and the University Transportation Center(s) Program of the US Department of Transportation.

ORCID iDs

Amirreza Nickkar

Young-Jae Lee

Mana Meskar

References

Dailey

D. J.

Loseff

Meyers

Seattle Smart Traveler: Dynamic Ridematching on the World Wide Web. Transportation Research Part C: Emerging Technologies, Vol. 7, No. 1, 1999, pp. 17-32. https://doi.org/10.1016/S0968-090X(99)00007-8.

Ordóñez

Dessouky

M. M.

Dynamic Ridesharing. In Leading Developments from INFORMS Communities ( Batta

Peng

, eds.), the Institute for Operations Research and the Management Sciences, Catonsville, MD, 2017, pp. 212–236.

Mohamed

M. J.

Rye

Fonzone

Operational and Policy Implications of Ridesourcing Services: A Case of Uber in London, UK. Case Studies on Transport Policy, Vol. 7, No. 4, 2019, pp. 823–836. https://doi.org/10.1016/j.cstp.2019.07.013.

Liu

Titheridge

Yan

Wang

Tan

Chen

Zhang

A Passenger-to-Driver Matching Model for Commuter Carpooling: Case Study and Sensitivity Analysis. Transportation Research Part C: Emerging Technologies, Vol. 117, 2020, p. 102702. https://doi.org/10.1016/j.trc.2020.102702.

Ashkrof

de Almeida Correia

G. H.

Cats

van Arem

Understanding Ride-Sourcing Drivers’ Behaviour and Preferences: Insights from Focus Groups Analysis. Research in Transportation Business & Management, Vol. 37, 2020, p. 100516. https://doi.org/10.1016/j.rtbm.2020.100516.

Cordeau

J.-F.

Laporte

The Dial-a-Ride Problem: Models and Algorithms. Annals of Operations Research, Vol. 153, No. 1, 2007, pp. 29–46. https://doi.org/10.1007/s10479-007-0170-8.

Braekers

Caris

Janssens

G. K.

Exact and Meta-Heuristic Approach for a General Heterogeneous Dial-a-Ride Problem with Multiple Depots. Transportation Research Part B: Methodological, Vol. 67, 2014, pp. 166–186. https://doi.org/10.1016/j.trb.2014.05.007.

Masson

Lehuédé

Péton

The Dial-a-Ride Problem with Transfers. Computers & Operations Research, Vol. 41, 2014, pp. 12–23. https://doi.org/10.1016/j.cor.2013.07.020.

Nickkar

Lee

Y.-J.

Optimal Automated Demand Responsive Feeder Transit Operation and Its Impact. Final Report. Urban Mobility & Equity Center, Morgan State University, Baltimore, MD, 2018.

10.

Lee

Y.-J.

Meskar

Nickkar

Sahebi

Development of an Algorithm for Optimal Demand Responsive Relocatable Feeder Transit Networks Serving Multiple Trains and Stations. Urban Rail Transit, Vol. 5, No. 3, 2019, pp. 186–201. https://doi.org/10.1007/s40864-019-00109-z.

11.

Berbeglia

Cordeau

J.-F.

Laporte

Dynamic Pickup and Delivery Problems. European Journal of Operational Research, Vol. 202, No. 1, 2010, pp. 8–15. https://doi.org/10.1016/j.ejor.2009.04.024.

12.

Masoud

Jayakrishnan

A Real-Time Algorithm to Solve the Peer-to-Peer Ride-Matching Problem in a Flexible Ridesharing System. Transportation Research Part B: Methodological, Vol. 106, 2017, pp. 218–236. https://doi.org/10.1016/j.trb.2017.10.006.

13.

Masoud

Jayakrishnan

A Decomposition Algorithm to Solve the Multi-Hop Peer-to-Peer Ride-Matching Problem. Transportation Research Part B: Methodological, Vol. 99, 2017, pp. 1–29. https://doi.org/10.1016/j.trb.2017.01.004.

14.

Herbawi

Weber

The Ridematching Problem with Time Windows in Dynamic Ridesharing: A Model and a Genetic Algorithm. Presented at IEEE Congress on Evolutionary Computation, Brisbane, QLD, 2012.

15.

Stiglic

Agatz

Savelsbergh

Gradisar

The Benefits of Meeting Points in Ride-Sharing Systems. Transportation Research Part B: Methodological, Vol. 82, 2015, pp. 36–53. https://doi.org/10.1016/j.trb.2015.07.025.

16.

Agatz

N. A. H.

Erera

A. L.

Savelsbergh

M. W. P.

Wang

Dynamic Ride-Sharing: A Simulation Study in Metro Atlanta. Transportation Research Part B: Methodological, Vol. 45, No. 9, 2011, pp. 1450–1464. https://doi.org/10.1016/j.trb.2011.05.017.

17.

Boyacı

Zografos

K. G.

Geroliminis

An Optimization Framework for the Development of Efficient One-Way Car-Sharing Systems. European Journal of Operational Research, Vol. 240, No. 3, 2015, pp. 718–733. https://doi.org/10.1016/j.ejor.2014.07.020.

18.

Tafreshian

Masoud

Trip-Based Graph Partitioning in Dynamic Ridesharing. Transportation Research Part C: Emerging Technologies, Vol. 114, 2020, pp. 532–553. https://doi.org/10.1016/j.trc.2020.02.008.

19.

Silva

B. C. H.

Fernandes

I. F. C.

Goldbarg

M. C.

Goldbarg

E. F. G.

Quota Travelling Salesman Problem with Passengers, Incomplete Ride and Collection Time Optimization by Ant-Based Algorithms. Computers & Operations Research, Vol. 120, 2020, p. 104950. https://doi.org/10.1016/j.cor.2020.104950.

20.

Wang

Agatz

Erera

Stable Matching for Dynamic Ride-Sharing Systems. Transportation Science, Vol. 52, No. 4, 2018, pp. 850–867. https://doi.org/10.1287/trsc.2017.0768.

21.

Yao

Song

Jin

A Novel Algorithm for Peer-to-Peer Ridesharing Match Problem. Neural Computing and Applications, Vol. 31, No. 1, 2019, pp. 247–258. https://doi.org/10.1007/s00521-018-3733-5.

22.

Aydin

O. F.

Gokasar

Kalan

Matching Algorithm for Improving Ride-Sharing by Incorporating Route Splits and Social Factors. Plos One, Vol. 15, No. 3, 2020, p. e0229674. https://doi.org/10.1371/journal.pone.0229674.

23.

Di Febbraro

Gattorna

Sacco

Optimization of Dynamic Ridesharing Systems. Transportation Research Record: Journal of the Transportation Research Board, 2013. 2359: 44–50.

24.

Nourinejad

Roorda

M. J.

Agent Based Model for Dynamic Ridesharing. Transportation Research Part C: Emerging Technologies, Vol. 64, 2016, pp. 117–132. https://doi.org/10.1016/j.trc.2015.07.016.

25.

Kucharski

Cats

Exact Matching of Attractive Shared Rides (ExMAS) for System-Wide Strategic Evaluations. Transportation Research Part B: Methodological, Vol. 139, 2020, pp. 285-310. https://doi.org/10.1016/j.trb.2020.06.006.

26.

Nourinejad

Ramezani

Ride-Sourcing Modeling and Pricing in Non-Equilibrium Two-Sided Markets. Transportation Research Part B: Methodological, Vol. 132, 2020, pp. 340-357. https://doi.org/10.1016/j.trb.2019.05.019.

27.

Balardino

A. F.

Santos

A. G.

Heuristic and Exact Approach for the Close Enough Ridematching Problem. Springer International Publishing, Cham, 2016.

28.

Najmi

Rey

Rashidi

T. H.

Novel Dynamic Formulations for Real-Time Ride-Sharing Systems. Transportation Research Part E: Logistics and Transportation Review, Vol. 108, 2017, pp. 122–140. https://doi.org/10.1016/j.tre.2017.10.009.

29.

Yang

Qin

Optimizing Matching Time Interval and Matching Radius in On-Demand Ride-Sourcing Markets. Transportation Research Part B: Methodological, Vol. 131, 2020, pp. 84–105. https://doi.org/10.1016/j.trb.2019.11.005.

30.

Kumar

Khani

An Algorithm for Integrating Peer-to-Peer Ridesharing and Schedule-Based Transit System for First Mile/Last Mile Access. Transportation Research Part C: Emerging Technologies, Vol. 122, 2021, p. 102891. https://doi.org/https://doi.org/10.1016/j.trc.2020.102891.

31.

Ghoseiri

Haghani

Hamed

Real-Time Rideshare Matching Problem. Mid-Atlantic Universities Transportation Center, College Park, MD, 2010.

32.

Qian

Zhang

Ukkusuri

S. V.

Yang

Optimal Assignment and Incentive Design in the Taxi Group Ride Problem. Transportation Research Part B: Methodological, Vol. 103, 2017, pp. 208–226. https://doi.org/10.1016/j.trb.2017.03.001.

33.

Peng

Shan

Jia

Jiang

Yao

Stable Ride-Sharing Matching for the Commuters with Payment Design. Transportation, Vol. 47, No. 1, 2020, pp. 1–21. https://doi.org/10.1007/s11116-018-9960-x.

34.

Özkan

Joint Pricing and Matching in Ride-Sharing Systems. European Journal of Operational Research, Vol. 287, No. 3, 2020, pp. 1149–1160. https://doi.org/10.1016/j.ejor.2020.05.028.

35.

Xia

Curtin

K. M.

Zhao

A New Model for a Carpool Matching Service. PloS One, Vol. 10, No. 6, 2015, p. e0129257. https://doi.org/10.1371/journal.pone.0129257.

36.

Ordóñez

Dessouky

A Traffic Assignment Model for a Ridesharing Transportation Market. Journal of Advanced Transportation, Vol. 49, No. 7, 2015, pp. 793–816. https://doi.org/10.1002/atr.1300.

37.

Pang

J.-S.

Ordóñez

Dessouky

Complementarity Models for Traffic Equilibrium with Ridesharing. Transportation Research Part B: Methodological, Vol. 81, 2015, pp. 161–182. https://doi.org/10.1016/j.trb.2015.08.013.

38.

Schuetz

Caflisch

Multistep Greedy Algorithm Identifies Community Structure in Real-World and Computer-Generated Networks. Physical Review E, Vol. 78, No. 2, 2008, p. 026112. https://doi.org/10.1103/PhysRevE.78.026112.

39.

Calvo

R. W.

de Luigi

Haastrup

Maniezzo

A Distributed Geographic Information System for the Daily Car Pooling Problem. Computers & Operations Research, Vol. 31, No. 13, 2004, pp. 2263–2278. https://doi.org/10.1016/S0305-0548(03)00186-2.

40.

Duan

Pettie

Linear-Time Approximation for Maximum Weight Matching. Journal of the ACM (JACM), Vol. 61, No. 1, 2014, pp. 1–23. https://doi.org/10.1145/2529989.

41.

Bei

Zhang

Algorithms for Trip-Vehicle Assignment in Ride-Sharing. Proc., 32nd AAAI Conference on Artificial Intelligence, New Orleans, LA, 2018.

42.

Chen

Mes

Schutten

Quint

A Ride-Sharing Problem with Meeting Points and Return Restrictions. Transportation Science, Vol. 53, No. 2, 2019, pp. 401–426. https://doi.org/10.1287/trsc.2018.0832.

43.

Wang

Dessouky

Ordonez

A Pickup and Delivery Problem for Ridesharing Considering Congestion. Transportation Letters, Vol. 8, No. 5, 2016, pp. 259–269. https://doi.org/10.1179/1942787515Y.0000000023.

44.

IRS. 2021 Standard Mileage Rates. International Foundation of Employee Benefit Plans, Brookfield, WI, 2020.