Transforming Ridesharing: Harnessing Role Flexibility and HOV Integration for Enhanced Mobility Solutions

Urban traffic congestion presents several challenges, including longer travel times, increased fuel consumption, higher emissions, and adverse environmental and health impacts. Expanding infrastructure and investing in public transit can be expensive and sometimes impractical in densely populated areas. While congestion pricing and alternative transportation modes exist, they may fall short in less densely populated areas. High-Occupancy Vehicle (HOV) lanes, dedicated for multi-occupant vehicles [1], effectively reduce congestion by promoting ridesharing and public transit. These lanes enhance traffic flow and serve as key strategies to tackle this issue, especially on busy freeways [1, 2]. HOV lanes in places like Beijing, Hong Kong, and California have shown significant benefits, including reduced travel times and improved traffic flow [3]. Carpoolers also enjoy incentives like reduced toll charges, motivating more people to use high-occupancy transportation modes and thereby reducing overall road congestion [4].

Dynamic ridesharing systems with non-employee or non-contractor drivers also aim to alleviate congestion. They facilitate connections between travelers with compatible itineraries and schedules on short notice. Within ridesharing systems, an array of matching and transfer strategies exist. Some studies focus on one-to-one matching, where each rider is paired with a single driver capable of accommodating one passenger at a time [5]. A more comprehensive ridesharing approach involves a many-to-many scheme, where the system accommodates multiple stops for drivers and potential transfers between drivers and riders [2]. Another aspect of ridesharing systems is the role of participants as being driver or rider, which are typically defined upon trip registration. While some studies consider role flexibility [5, 6], the assumption is that all participants possess personal vehicles and thus have no preference, or that the system adheres to one-to-one frameworks. Similarly, studies on HOV [4] lack flexibility in participants roles, focusing on hired drivers and simplified one-to-one schemes. This study aims to fill these gaps by introducing a Mixed Integer Linear Programming (MILP) model for HOV lanes with a many-to-many approach and considering comprehensive role flexibility among participants. Ridesharing with multiple passengers in a vehicle may offer cost savings, and when combined with HOV lanes, it provides time-saving benefits.

We consider a dynamic ridesharing system that operates on a transportation network \({\mathbb{G}}=\left({\mathbb{N}},{\mathbb{E}}\right)\), where \({\mathbb{N}}\) denotes nodes and \({\mathbb{E}}\) represents edges. Participants \({\mathbb{P}}=\left\{{\mathbb{C}}\cup {\mathbb{N}}{\mathbb{C}}\right\}\) register their trip details and preferences are divided into car owners \({\mathbb{C}}\), and non-car owners \({\mathbb{N}}{\mathbb{C}}\). Given the role-flexibility of the problem, individuals who take on the role of drivers \(d\) form a subset \({\mathbb{D}}\subseteq {\mathbb{C}}\). Meanwhile, those who register as non-car owners or car owners but are assigned passenger roles constitute the set of \(r\) riders \({\mathbb{R}}\supseteq {\mathbb{N}}{\mathbb{C}}\). Each participant’s travel data includes submission time \({s}_{p},\) origin \({o}_{p}\) and end \({e}_{p}\) locations, earliest departure \(E{D}_{p}\), latest arrival times \(L{A}_{p}\), with car owners specifying car capacity \({Q}_{d}\) and a notification deadline \({\Delta }_{p}\) for potential matches. We represent HOV nodes as \({\mathbb{N}}_{H}\subset {\mathbb{N}}\) and define \({\mathbb{E}}_{H}\) as the edges present in the sub-graph of \({\mathbb{G}}\) induced by \({\mathbb{N}}_{H}\).

To adapt to the dynamic nature of the problem and accommodate continuous information arrival we employ a rolling horizon strategy [5]. This involves periodic re-optimization of a static problem formulation at specific times based on incoming trip announcements. Prior to model solution, we perform preprocessing to account for users’ spatiotemporal constraints. This narrows down the available nodes and links for each participant, leading to a reduced search space and facilitating the identification of viable and non-viable pairings of drivers and riders. We define the set of accessible nodes for participant \(p\in {\mathbb{P}}\) as \({\mathbb{A}}{\mathbb{N}}_{p}=\left\{i\in {\mathbb{N}}:{T}_{{s}_{p},i}+{T}_{i,{e}_{p}}\le L{A}_{p}-E{D}_{p}\right\},\) with \({T}_{i,j}\) denoting the shortest trip time between locations \(i\) and \(j\). Also, we establish sets of mutually accessible nodes for each participants-driver pair, denoted as \({\mathbb{A}}{\mathbb{N}}_{pd}\), and their corresponding accessible links \({\mathbb{A}}{\mathbb{E}}_{pd}\). Viable matches \({\mathbb{R}}{\mathbb{D}}\) between riders and drivers, are based on overlapping accessible links and time constraints. It is important to note that due to transfer allowances a complete path or time overlap is not necessary. A match exists if \({\mathbb{A}}{\mathbb{E}}_{pd}\ne \varnothing \) and \(\neg \left(L{A}_{d}\le E{D}_{p} \parallel L{A}_{p}\le E{D}_{d}\right)\). To account for potential wait times, we introduce constraints into the model that synchronize meeting times at pickup and transfer points, all the while maintaining onboard riders’ schedules. To formulate this problem, we define the decision variables as outlined in Table 1.

In the notation provided, we formulate the many-to-many flex-role ridesharing problem within a network that includes HOV as follows.

Objective function (1) maximizes total matches and minimizes travel time, with \({\lambda }_{p}\) as the travel time for the fastest route from origin to destination, and \({t}_{i,j}\) as edge travel time. Constraint (2) ensures the departure of drivers from their origins, while constraint (3) guarantees their arrival at their destinations. Constraint (4) fulfills flow conservation for the driver’s path. Constraint (5) directs riders out of their origin and (6) ensures that they end their trips at their destination. Constraint (7) indicates flow conservation for riders. Moreover, these constraints enable passengers to transfer between drivers, creating a many-to-many scheme. Constraint (8) ensures vehicle capacity and the prerequisite that a driver must travel along a link for a rider on that link. Constraint (9) guarantees single-driver assignments for each step of a rider’s path. Constraint (10) mandates car owners to be assigned as drivers before providing service to others. Constraint (11) states that car owners can either provide a ride service or receive it. Constraint set (12) states that a pick follows and immediate travel to the next node. Constraint (13) checks the feasibility of pickup at node \(i\) by driver \(d\). This requires that incoming edges at \(i\) sum to zero, while outgoing edges sum to one. Constraint (14) monitors the possibility of drop-offs, ensuring that a source node only has outgoing flow while a destination node only receives incoming flow. Constraints (15)-(17) ensure meaningful orders for pickups and drop-offs. Constraint (15) guarantees that each pickup corresponds to a drop-off. Constraint (16) act as the counter on nodes visited by driver \(d\) as they cross edges, tracking progress along the route. For pickup-drop-off order, constraint (17) ensures pick up location \(i\) have a higher counter than drop-off point \(j.\) Constraint sets (18) and (19) limit the number of passengers on board after serving node \(j.\) The coefficient \({M}_{1}\) is set to \({M}_{1}= {Q}^{d}+{\sum }_{p\in {\mathbb{P}}}1.\) Constraints (20) enforces a minimum passenger requirement for HOV lane access. Constraint (21) relates departure times at nodes and its subsequent immediate node, where \({M}_{i,j}^{p}=L{A}_{p}-E{D}_{p}+{t}_{i,j}\). This also prevents subtours. Constraint (22) and (23) ensures adherence to time windows for participants. Constraint sets (24) and (25) describe the type of variables.

To compare the time savings from HOV and Flex roles, we utilize the New York City Taxi Trip dataset [7], which contains coordinates, timestamps, and trip durations. We randomly selected ~ 17k requests, with ~ 8k from non-car owners and ~ 9k from car owners. To address missing departure and arrival time in data, we follow literature [2] practices by adding or subtracting a random time between 0 and 5 min from the pickup and drop-off times. To identify accessible nodes within a user’s time frame, we employ Yen’s shortest path algorithm [8] and analyze the first 10 shortest paths. We obtain map data using the OpenStreetMapX package [9]. The map contains 40490 nodes and 12,242 edges, from which we randomly set 785 edges to have HOV lanes (see Fig. 1). A minimum of 2 occupants is required for HOV lane access. The system operates from 9:00 am to 07:00 pm, and we employ a rolling horizon [5] with a 5-min period for all experiments. All models are implemented in Julia v1.8.3 and solved using ILOG CPLEX v22.1.0 on a laptop with a Core (TM) i7 processor and 16 GB of RAM.

Bild vergrößern

Table 2 summarizes findings, with values averaging over the horizon. The ‘%Match’ represents served participants to non-car owners, while ‘%Shift’ is the ratio of car owners served by others. Combining role flexibility with HOV lanes achieves the lowest objective function. However, role flexibility alone achieves a higher %match, likely due to HOV access requirements that limits combination of users can travel together. Role flexibility enhances total matches compared to inflexible models, but it is influenced by the driver-passenger ratio. We sometimes achieve 112% matches, serving all non-car owners and 12% of car owners through role shifts. However, in other cases, more role shifts can lead to imbalances, affecting service levels to non-car owners.

Role flexibility improves total matches in both HOV and non-HOV scenarios, with its effectiveness tied to the driver-passenger ratio. Further research on the correlations among role flexibility, role shifts, participant ratios, and service levels is an interesting avenue for future research.