Dynamic Ride-Matching for Large-Scale Transportation Systems

Abstract

Efficient dynamic ride-matching (DRM) in large-scale transportation systems is a key driver in transport simulations to yield answers to challenging problems. Although the DRM problem is simple to solve, it quickly becomes a computationally challenging problem in large-scale transportation system simulations. Therefore, this study thoroughly examines the DRM problem dynamics and proposes an optimization-based solution framework to solve the problem efficiently. To benefit from parallel computing and reduce computational times, the problem’s network is divided into clusters utilizing a commonly used unsupervised machine learning algorithm along with a linear programming model. Then, these sub-problems are solved using another linear program to finalize the ride-matching. At the clustering level, the framework allows users adjusting cluster sizes to balance the trade-off between the computational time savings and the solution quality deviation. A case study in the Chicago Metropolitan Area, U.S., illustrates that the framework can reduce the average computational time by 58% at the cost of increasing the average pick up time by 26% compared with a system optimum, that is, non-clustered, approach. Another case study in a relatively small city, Bloomington, Illinois, U.S., shows that the framework provides quite similar results to the system-optimum approach in approximately 62% less computational time.

Keywords

public transportation innovative public transportation services and technologies mobility as a service (MaaS)rural intercity bus specialized transportation

Dynamic ride-matching (DRM) in large-scale transportation systems has been studied and incorporated in many transportation simulation models ( 1 – 3 ). As stated in Özkan and Ward, the closest driver is a commonly practiced policy that is simple and straightforward to implement ( 4 ). In this policy, the closest driver to each given rider is fetched from a sorted adjacency matrix, and these closest drivers meet the travel demand of the riders. Although this policy is favorable, as it is not computationally complex and requires relatively low memory as well, as it somewhat resembles real life by depicting the greedy approach in decision-making, it is not system optimum. In an optimal environment, a match between a vehicle and a request would occur in a way that either the total pick up time is minimized or the total number of matches is maximized. In the minimization approach, some riders may wait longer to be picked up, compared with the time with the closest driver policy, to conserve less total pick up time.

A DRM framework including an optimization model that provides a system-optimum ride-matching by minimizing the total pick up time was proposed in Sarma et al. ( 3 ). The model proposed is a type of the classic transportation problem and simple to solve. Yet, in large-scale problems, let alone solving the problem, even building the model is computationally time-consuming. In large-scale transportation system simulations, such as Polaris (developed by the Argonne National Laboratory to quantify the mobility and energy impacts of new transport technologies on a regional basis), computational time is a major driver toward conducting quick and reliable analyses for real-life problems ( 1 ). From the perspective of a fleet operator, computational time is a key aspect for real-time operation, since users wish their request to be assigned timely. Therefore, in this study a DRM framework is developed that partitions the transportation network into clusters to efficiently solve the problem in small pieces by utilizing a modified version of the optimization model in Sarma et al. ( 3 ). A linear programming (LP) model and an integer linear programming (ILP) model are created to solve the DRM problem. The framework quickly matches vehicles and requests with minimal interruption in the general computational flow of the aforementioned simulation model.

In this study, a ride-matching framework is constructed that separates the network into clusters of vehicles and requests using an unsupervised machine learning method, and it utilizes an LP to form sub-networks that can be quickly solved using an ILP. With the aid of parallel computing, the framework minimizes the computational time while keeping the solution quality at acceptable levels. This approach is compared with the closest driver policy and the framework in Sarma et al. from computational time and quality perspectives ( 3 ).

The contributions of this study are as follows. A modeling framework is provided that divides a transportation network into smaller pieces and solves the DRM problem. Based on the subject problem, it is possible to determine the size of problem pieces to balance the trade-off between the computational efficiency and the solution quality. A case study is conducted on the Chicago Metropolitan Area, U.S., to illustrate the pick up time savings and the computational efficiency of the presented framework.

Literature Review

Ride-matching has been widely studied under different problem settings. Studies similar to the current study are Sarma et al., Al-Kanj et al., Jin and Hu, and Xu et al. (3, 5–7). A similar work that solved the problem without partitioning the network was presented in Sarma et al. ( 3 ). This study developed a solution framework by considering their optimization model. An approximate dynamic programming to maximize the revenue gained by the matching of vehicles and requests was proposed in Al-Kanj et al. ( 5 ). The study considered a network with 32,874 trip requests and optimized for up to 650 trips by dividing the total requests into 15 min time intervals. Trajectory matching for a ride-sharing problem was used in Jun and Hu ( 6 ). Although they focused on a different problem, their concern was also about large-scale networks. The Markov decision process to solve a similar large-scale DRM problem was used in Xu et al. ( 7 ). Although “thousands” of trips was mentioned a few times, the authors did not provide the exact number of trips considered in their “real-world experiment.” The problem addressed in this study is similar to present day door-to-door services through a smartphone application in which users make requests for immediate pick up, though ride-sharing is not allowed. The literature also broadly focuses on vehicle routing, and pick up and drop off time windows. In the DRM problem, vehicle routing and time windows are not considered, since future demands are unknown. Such features can improve operational efficiency but would considerably increase the complexity and the time-to-solution. Rather, the problem tackled in this study is less complex, but it considers very large instances.

Methodology

This section describes the problem, presents the model structure and formulations, and proposes an alternative solution approach to benchmark the original model.

Problem Description

The DRM problem can be described as follows. In a given transportation network and a pre-determined planning horizon, a set of riders request vehicles. The sets of vehicles and ride requests are denoted by $V$ and $R$ , respectively. At a micro level, the problem is simply to find the closest vehicle to each request such that the total pick up time or vehicle miles traveled (VMT) to pick up the riders is minimized. This study focuses on a user-centric approach that minimizes the pick up time, rather than the VMT, that could be of potential interest to operators. Meanwhile, a network operator can restrict the maximum pick up time, denoted by $M$ . In the DRM problem, carpooling or the impact of current decisions on the following planning horizon are not considered. Instead, the problem of discrete time intervals is solved considering the problem setting at the current time step. In large transportation network problems, computational time and space significantly affect the modeling approach choice. Therefore, the focus is solely on the core of the problem which simply is matching vehicles and requests at a system optimum. The travel time between vehicle $v \in V$ and request $r \in R$ is defined by $T_{vr}$ . Finally, let the binary variable $x_{vr} = 1$ , if vehicle $v \in V$ is matched with request $r \in R$ ; otherwise, $x_{vr} = 0$ . For ease of readability, the notations will be tabulated, where appropriate, as in Table 1 which lists the sets, parameters, and variables defined thus far. Further, note that calligraphic letters are used to represent sets, uppercase Roman letters for parameters (e.g., $M$ ), lowercase Roman letters for variables (e.g., $x_{vr}$ ), and lowercase Greek letters (e.g., $ν$ for vehicles and $γ$ for requests) as superscripts to modify parameters. Based on these definitions, the following ILP model is presented, which will be henceforth referred to the DRM model, and it was built in Sarma et al. to optimally match vehicles and requests ( 3 ).

max_{x} \sum_{\begin{matrix} v \in V, r \in R \end{matrix}} (M - T_{vr}) x_{vr},

(1)

Table 1.

Sets, Parameters, and Variables Used in the Dynamic Ride-Matching (DRM) Model

Set	Definition
$V$	Set of vehicles in the network, indexed by $v \in V$
$R$	Set of ride requests in the network, indexed by $r \in R$
Parameter	Definition
$T_{vr}$	Travel time from vehicle $v \in V$ to request $r \in R$
$M$	Maximum allowed pick up time
Variable	Definition
$x_{vr}$	${\begin{matrix} \begin{matrix} 1, if v \in V is matched with r \in R, \\ 0, otherwise . \end{matrix} \end{matrix}$

subject to,

\sum_{\begin{matrix} r \in R \end{matrix}} x_{vr} \leq 1 \forall v \in V,

(2)

\sum_{\begin{matrix} v \in V \end{matrix}} x_{vr} \leq 1 \forall r \in R,

(3)

x_{vr} \in {0, 1} \forall v \in V, r \in R .

(3)

In the DRM model, Objective function 1 maximizes the total time savings between the maximum allowed pick up time and the vehicle-to-requester travel time. Constraint set 2 ensures that each vehicle is assigned up to one request. Constraint set 3 assures that each request is assigned up to one vehicle. In these two constraint sets, equality signs especially are not used, because they may result in an infeasible solution when $| V | > | R |$ or $| V | < | R |$ .

Although the ILP, which can also be interpreted as an LP because of the total unimodularity property, can be quickly solved for reasonable instance sizes, for example $| V | = | R | = 1, 000$ , the computational time is not satisfactory for a large transportation network like the Chicago Metropolitan Area which is a studied case in this manuscript. For example, the problem size is $| V | \approx 280, 000$ and $| R | \approx 12, 000$ in a peak traffic time period of the studied area. In an agent-based modeling framework for the case area, the DRM model should be solved very frequently (e.g., every minute of the simulation time), and the problem size at each time interval is large enough to interrupt the simulation process. Therefore, the main problem focused here is to efficiently match the vehicles and ride requests. Efficiency in this context comes in the form of low computational time and reasonable solution quality. In the following section, a model structure is constructed to solve the DRM problem.

Model Structure and Formulation

The DRM model can be improved by reducing the number of decision variables while creating subsets for vehicle and request pairs that satisfy $T_{vr} < M$ . Yet, this improvement is still not satisfactory to efficiently solve large-scale instances. Therefore, a framework is developed to partition the problem’s graph into clusters, each of which can be separately solved.

While partitioning, three approaches to follow are reviewed: (1) Create clusters such that the total number of links in between the clusters is minimized, a.k.a., min-cut clustering ( 8 , 9 ); (2) Create clusters with uniform computational difficulties; (3) Create clusters such that contiguity and even distribution are conserved as much as possible.

In (1), since the information loss is minimal, such an objective would minimize the deviation from the globally optimal solution, which can be obtained by solving the DRM model. Yet, this approach is not computationally promising because solving the min-cut clustering ILP can be as difficult as solving the DRM problem.

In (2), the uniformity can be satisfied by ensuring equally distributed vehicles and requests to clusters, which requires solving another LP. The resulting partition could be computationally useful, in the sense that clusters can be distributed to several machines or paralleled, and the computation in each cluster could be completed with similar time requirements. The type of LP models for such partitioning or so called districting is reviewed in Validi et al. ( 10 ). In both of the partitioning approaches, a difficult LP/ILP awaits to be solved and a complete graph needs to be inputted into the models.

Acknowledging the difficulties in the first two approaches, in (3), attention is turned to clustering algorithms requiring low memory and less information that quickly partitions a graph into the desired number of clusters. Surely, most of these algorithms do not comply with the aforementioned objectives in (1) and (2), yet the concern of this study is centered around the computational efficiency. Therefore, a commonly used unsupervised machine learning algorithm is adopted: the k-means clustering algorithm. The algorithm takes coordinates of points in the graph and the number of clusters desired as input, and produces clusters as an output using Euclidean distances as a measure. It starts with selecting k centroids; then, it assigns the points to the closest centroids. The advantage of this algorithm is that, once it is run, the output centroids can be used to estimate the clustering in the following time intervals because the distribution of vehicles and requests in the network does not tremendously vary over time. For example, assume the network is partitioned in the first planning horizon. These centroids can be used to form new clusters in the next few, for example 30 min, planning horizons by assigning closest coordinates to these centroids. This convention was followed in the numerical results, and formed the centroids every 30 min. It should also be noted that such an approach may not be well-suited to networks with a high order of spatial dynamics.

To partition the graph, zonal-level data is considered that provide the zone information of given vehicles and requests. Zones (a.k.a. traffic analysis zones) represent geographical and sociological distinctions and are used commonly in transportation network planning. For instance, Chicago Metropolitan Area is studied in 1,960 zones. In general, zone boundaries are defined by the Metropolitan Area Organization(s). Partitioning the network into zones is common in transportation modeling especially because of the computational burden as the number of zones is usually smaller than the number of links or nodes. The zonal-level variables are employed in this model for these reasons.

Vehicles and requests are differentiated by creating separate clusters for each. The goal in this operation is to create problem instances for the DRM model with a uniformly distributed (as much as possible) number of vehicles and requests. This is a similar goal and approach to balancing riders and drivers in dynamic ridesharing problems ( 11 ). This will increase the likelihood of finding a match between vehicles and riders within each problem instance. Therefore, clusters will be used to form small problem instances, which are referred to as DRM networks, using an LP model named the network formation (NF) model. In Table 2, the notations for the NF model are provided.

Table 2.

Sets, Parameters, and Variables Used in the Network Formation (NF) Model

Set	Definition
$S^{ν}$	Subset of vehicle clusters, indexed by $i \in S^{ν}$
$S^{γ}$	Subset of request clusters, indexed by $j \in S^{γ}$
Parameter	Definition
$T_{ij}^{ξ}$	Travel time from vehicle cluster $i \in S^{ν}$ to request cluster $j \in S^{γ}$
$V_{i}$	Number of vehicles in vehicle cluster $i \in S^{ν}$
$R_{j}$	Number of requests in request cluster $j \in S^{γ}$
Variable	Definition
$y_{ij}$	Number of vehicles in vehicle cluster $i \in S^{ν}$ to match the requests in request cluster $j \in S^{γ}$

The cardinalities of $S^{ν}$ and $S^{γ}$ depend on the number of vehicles and requests in the network. For both vehicles and requests, the k-means algorithm can be used to create the clusters. An alternative to this method was proposed by Ward, which is known as Ward’s clustering method ( 12 ). In this context, k-means is more proper because its computational complexity is lower than Ward’s method. The inputs to the k-means algorithm can be either the exact coordinates of vehicles/requests or the zonal coordinates of vehicles/requests. Since the zonal-level information are easier to retrieve, process, and store, it is preferable to utilize zone centroid coordinates of associated vehicles and requests.

Based on the definitions, the NF model that forms the DRM networks is constructed as follows:

min_{y} \sum_{\begin{matrix} i \in S^{ν}, j \in S^{γ} \end{matrix}} T_{ij}^{ξ} y_{ij},

(4)

subject to,

\sum_{j \in S^{γ}} y_{ij} = V_{i} \forall i \in S^{ν},

(5)

\begin{matrix} \sum_{i \in S^{ν}} y_{ij} \geq ⌊ R_{j} \frac{\sum_{k \in S^{ν}} V_{k}}{\sum_{l \in S^{γ}} R_{l}} ⌋ \forall j \in S^{γ}, if \\ \sum_{i \in S^{ν}} V_{i} \geq \sum_{j \in S^{γ}} R_{j}, \end{matrix}

(6)

\begin{matrix} \sum_{i \in S^{ν}} y_{ij} \leq R_{j} \forall j \in S^{γ}, if \sum_{i \in S^{ν}} V_{i} < \sum_{j \in S^{γ}} R_{j}, \\ y_{ij} \in R^{+} \forall i \in S^{ν}, j \in S^{γ} . \end{matrix}

(7)

Objective function 4 minimizes the total travel time from vehicle clusters to rider clusters of all vehicles matching the requests. Constraint set 5 enforces that all vehicles in the vehicle clusters match requests at some request clusters, that is, all vehicles are utilized in a DRM network. Constraint sets 6 and 7 conditionally become active and are designed to create fair DRM networks with equal (as much as possible) numbered vehicles and requests. In Constraint set 6, all vehicles are assigned to requests proportional to the requests in a given cluster. Constraint set 7 does not allow assigning more vehicles than the number of requests to clusters. The NF model is designed in such a way that constraints will not produce an infeasible solution.

The NF model does not directly output the DRM networks, but using $y$ variable solutions, the networks are formed by assigning the first $y_{ij}$ vehicles from vehicle cluster $i$ to the network formed by the associated rider clusters $j$ . Finally, $| D |$ is obtained, where $D$ denotes the subset of networks—DRM networks—to be solved. Within these networks, some may still possess an unbalanced and large number of vehicles or requests, therefore solving these instances may still require significant computational time for two reasons: (i) the LP size may still be substantially large given all potential combinations, and (ii) retrieving the input data for the LP can itself take a significant time. Specifically, with respect to the latter, it is necessary to compute an estimate of travel time between each combination of vehicle and request. Ideally, the shortest path for each combination would be computed given the prevailing times along each link in the network. Computing the shortest path is rather straightforward, and efficient implementations can find the shortest route in few milliseconds or less. However, considering that each DRM can potentially have thousands of vehicles and requests, it can be prohibitive to compute shortest paths for all potential combinations because it could take minutes to compute only the travel times.

To deal with this issue, the $k$ -nearest vehicles are searched, if the number of vehicles are at least equal to the number of requests; $k$ -nearest requests, otherwise. The $k$ -nearest approach is a common practice to deal with the issue. Sarma et al. used this approach on the graph level, which introduced a high computational difficulty by requiring these vehicles or requests to be fetched from very large heap lists ( 3 ). The networking approach alleviates the computational burden on the heap operation as well as reducing the DRM model’s instance size.

In the DRM model, $T_{vr}$ needs attention because fetching this skim matrix for each pair of $(v, r)$ at a point-to-point level requires solving many shortest-path problems. For the whole DRM problem, calculating shortest paths may be as expensive as solving the problem itself. Therefore, as practiced in Sarma et al., the shortest-path problem is solved for the $(v, r)$ pair when the corresponding vehicle and request are in the same zone ( 3 ). If the vehicle and ride request are in different zones, it is preferable to use the zonal travel time. In this light, the proper notations for the updated DRM model are provided in Table 3 followed by the model.

max_{x} {\begin{matrix} \sum_{\binom{v \in V_{dr},}{\binom{r \in R_{d},}{Z_{v}^{ν} \neq Z_{r}^{γ}}}} (M - T_{dvr}^{ζ}) x_{dvr} \\ + \sum_{\binom{v \in V_{dr},}{\binom{r \in R_{d},}{Z_{v}^{ν} = Z_{r}^{γ}}}} (M - T_{dvr}^{ρ}) x_{dvr}, if | V_{d} | \geq | R_{d} |, \\ \sum_{\binom{v \in V_{d},}{\binom{r \in R_{dv},}{Z_{v}^{ν} \neq Z_{r}^{γ}}}} (M - T_{dvr}^{ζ}) x_{dvr} \\ + \sum_{\binom{v \in V_{d},}{\binom{r \in R_{dv},}{Z_{v}^{ν} = Z_{r}^{γ}}}} (M - T_{dvr}^{ρ}) x_{dvr}, otherwise . \end{matrix}

(8)

Table 3.

Sets, Parameters, and Variables Used in the Updated Dynamic Ride-Matching (DRM) Model

Set	Definition
$V_{d}$	Subset of vehicles in the DRM network $d \in D$ , indexed by $v \in V_{d}$
$R_{d}$	Subset of requests in the DRM network $d \in D$ , indexed by $r \in R_{d}$
$V_{dr}$	Subset of $k$ -nearest vehicles in the DRM network $d \in D$ to a given request $r \in R_{d}$ meeting the maximum travel time requirement, $V_{dr} = \cup_{n = 1}^{k} {v \| v \in V_{d} \land m ({T_{dvr}^{ζ} \| T_{dvr}^{ζ} < M}, n)} \forall d \in D, r \in R_{d}$ , where the function $m ({\cdot}, n)$ outputs $v$ of the $n^{th}$ smallest element of a given set ${\cdot}$ . This subset is created if $\| V_{d} \| \geq \| R_{d} \|$
$R_{dv}$	Subset of $k$ -nearest requests in the DRM network $d \in D$ to a given vehicle $v \in V_{d}$ meeting the maximum travel time requirement, $R_{dv} = \cup_{n = 1}^{k} {r \| r \in R_{d} \land m ({T_{dvr}^{ζ} \| T_{dvr}^{ζ} < M}, n)} \forall d \in D, v \in V_{d}$ , where the function $m ({\cdot}, n)$ outputs $v$ of the $n^{th}$ smallest element of a given set ${\cdot}$ . This subset is created if $\| V_{d} \| < \| R_{d} \|$
Parameter	Definition
$T_{dvr}^{ρ}$	Point-to-point travel time from vehicle $v \in V_{d}$ to request $r \in R_{d}$ . It is defined for $(v, r)$ , if $v$ and $r$ are in the same zone.
$T_{dvr}^{ζ}$	Zonal travel time from vehicle $v \in V_{d}$ to request $r \in R_{d}$ . It is defined for $(v, r)$ , if $v$ and $r$ are in different zones.
$Z_{v}^{ν}$	The zone information of vehicle $v \in V$
$Z_{r}^{γ}$	The zone information of request $r \in R$
Variable	Definition
$x_{dvr}$	${\begin{matrix} \begin{matrix} 1, if vehicle v \in V_{d} is matched with request \\ r \in R_{d} in d \in D, \\ 0, otherwise . \end{matrix} \end{matrix}$

subject to,

\sum_{\begin{matrix} r \in R_{d} \end{matrix}} x_{dvr} \leq 1 \forall v \in V_{d r'}, r' \in R_{d}, if | V_{d} | \geq | R_{d} |,

(9)

\sum_{\begin{matrix} r \in R_{dv} \end{matrix}} x_{dvr} \leq 1 \forall v \in V_{d}, if | V_{d} | < | R_{d} |,

(10)

\sum_{\begin{matrix} v \in V_{dr} \end{matrix}} x_{dvr} \leq 1 \forall r \in R_{d}, if | V_{d} | \geq | R_{d} |,

(11)

\sum_{\begin{matrix} v \in V_{d} \end{matrix}} x_{dvr} \leq 1 \forall r \in R_{d v'}, v' \in V_{d}, if | V_{d} | < | R_{d} |,

(12)

x_{dvr} \in {0, 1} .

(12)

In the updated DRM model, Objective function 8–Constraint set 12, $x$ variables can be treated as $x_{dvr} \in R^{+}$ and an LP instead of an ILP can be solved because of the total unimodularity property. This relaxation may help commercial solvers to utilize faster solution algorithms compared with the branch-and-bound method that is commonly used to solve ILPs. Objective function 8 maximizes the total time savings between $M$ and the travel time based on the conditions. Constraint sets 9 and 10 become active according to the condition and function the same as Constraint set 2. Similarly, Constraint set 11 and Constraint set 12 are conditionally activated and function the same as Constraint set 3.

After solving the updated DRM model, some vehicles or requests may remain unmatched because of the $k$ -nearest approach and a discrepancy between the numbers of vehicles and requests within a DRM network. Finally, these vehicles and requests are matched using the closest vehicle policy that complies with the operator’s maximum pick up time restriction. This matching is carried out on a first-come, first-served basis and does not guarantee to match all vehicles and riders. The overall structure of this approach can be found in Algorithm 1. Note that parallel computing can be utilized for the portions with loops.

Algorithm 1: The network formation-based solution algorithm
Initialize by creating $\| S^{ν} \|$ vehicle clusters and $\| S^{γ} \|$ request clusters using the k-means algorithm.
Using the clusters, solve the NF model Objective function 4–Constraint set 7 and obtain the DRM networks $D$ .
for $d \in D$ in parallel do
Solve the updated DRM model Objective function 8–Constraint set 12.
Store unmatched vehicles and requests in separate lists.
end
Match the unmatched vehicles and requests on a first-come, first-served basis complying with the maximum pick up time restraint.

Numerical Results

This section evaluates the performance of the proposed approach. First, Polaris—the simulation framework in which the simulations were carried out—is briefly introduced, and later two case studies are presented.

Polaris Agent-Based Modeling

Polaris is an agent-based modeling framework that can reproduce both supply and demand aspects of urban mobility in metropolitan areas ( 1 ). To validate the framework and compare its performance with other approaches in the literature, numerical analyses are conducted in this simulation environment.

The demand aspect is captured by modeling each person as an independent agent that makes multiple decisions based on select attributes, available modes, cost of decisions, and travel times. These decisions include strategic decisions, such as determining work location and vehicle ownership ( 13 ). The activity-based model follows the so called “ADAPTS” framework with operational decisions implemented through different choice models, including activity generation, as well as mode and destination choices ( 14 – 16 ).

The supply aspect is captured by traffic, transit, and transportation network company (TNC) simulation models. The traffic simulation models feature an implementation of the Link Transmission Model ( 17 ). Routes are determined based on an information-mixing dynamic traffic assignment strategy ( 18 ). Transit simulations include details, such as boarding, alighting, and transfers considering different public transportation modes. The multi-modal router provides routes specific to each individual containing the specific line, time, and location of boarding and alighting ( 19 ).

Polaris simulates fleet operators providing door-to-door transportation services ( 20 ). The operation is presented by a fleet operator that controls a set of vehicles. Requests are mediated by the operator which assigns requests to available vehicles. Trips for these type of services are generated as an outcome of the traveler mode and destination choice models based on the paradigm of activity-based model. Each of these models are calibrated based on household survey data. The outputs of these models are then validated by comparing with data available from local agencies, such as ridership data from Chicago Transit Authority and Chicago Transportation Network Providers data ( 21 ). More about validation can be found in Auld et al. ( 22 ).

Finally, all computations were carried out on an Intel^® Xeon^® Gold 6138 CPU@2.0 GHz workstation with 128GB of RAM and 40 cores, and problem instances were solved using the Dynamic Linked Library interface to the solver IBM ILOG^® CPLEX^® 12.10 ( 23 ).

Case Study in Chicago Metropolitan Area

Chicago Metropolitan Area has a population of over 10 million people with more than 30 million trips occurring daily. The network contains around 55,000 unidirectional links and almost 20,000 nodes.

The High Technology–Mobility Scenario (B) presented in Serma et al. is simulated, in which households are likely to forfeit their private car ownership and rely on door-to-door mobility services ( 13 ). Each household may relinquish their private vehicles based on demographic characteristics following Menon et al. ( 24 ). (Refer to Gurumurthy et al. for specific details of this scenario [20]). Only 40% of households own a car as opposed to 98% in the baseline model calibrated for the year of 2018. In addition, the fares for door-to-door services were substantially reduced assuming a great portion of vehicles are autonomous. Yet, the framework is also applicable to other scenarios where vehicles are not autonomous. Experiments were conducted in this scenario to objectively compare the framework with other policies.

This scenario was simulated for three different ride-matching strategies: (1) the centralized framework in Sarma et al., (2) the approach proposed here, and (3) a sequential assignment to the closest vehicle (assuming inter-zonal travel times) as in Gurumurthy et al. ( 3 , 20 ). In both of the optimization-based methodologies (i.e., this study and Sarma et al.), it is assumed that $k = 200$ , and point-to-point travel times are computed for each potential match with inter-zonal travel time lower than 4 min ( 3 ). The assignments were performed at 1 min time intervals (i.e., they consider all requests generated in the previous minute as well as any previously unassigned requests). Notice that the time interval is an important component that determines the trade-off between the computational complexity and overall system performance including matching rate and average pick up time. In Yang et al., a thorough analysis was carried out to quantify this trade-off and find the optimal time interval ( 25 ). In the current study, the time interval is not an output of an optimization framework, but it was determined by observing the simulation framework.

Figure 1 shows an example snapshot of the problem layout for 1 min. time interval in the Chicago case. In all three sub-figures, rectangles denote zones. In Figure 1a, the distributions of vehicles and requests can be observed. In Figure 1, b and c , different colors represent clusters of requests and vehicles, respectively. It can also be noticed that the majority of vehicles and requests are centered around the downtown area at this time interval.

Figure 1.

An example Chicago Metropolitan area: (a) requests and vehicle distributions, (b) request clusters, and (c) vehicle clusters for an arbitrary 1 min time interval.

Table 4 summarizes key statistics, such as the total number of requests, average pick up times, and central processing unit (CPU) times, for each strategy. The computational time is reported only for the optimization-based strategies, because the closest vehicle policy yields the solutions in substantially low (in the order of 1 s at the peak traffic) CPU time. Further, the optimization-based strategies require finding $k$ -nearest (with $k = 200$ ) vehicles (or passengers) for all requests, while the closest vehicle approach only requires finding the closest vehicle without any further computation. It is worth noting that the results depend on the fleet size, which is a simulation input. A value was picked that, at the same time, can serve all trips with the least number of vehicles. To that end, a value was picked in which travelers experience increased pick up time at the peaks. For the case of Chicago, that value is 300,000.

Table 4.

Summary of Solution Statistics for the Chicago Metropolitan Area Case

Strategy	Requests (M)	Empty vehicle miles traveled (VMT) (%)	Average pick up (s)	Average central processing unit (CPU) time (s)	Maximum CPU time (s)
Closest vehicle	6.32	13.2	226	NA	NA
Sarma et al. ( 3 )	6.31	9.4	151	18.4	82.5
This study	6.28	12.0	190	7.76	20.8

Note: NA = not available.

Figure 2 shows the key comparison metrics of the simulation results. Figure 2a depicts the number of matched requests for each strategy, and Figure 2b illustrates the average pick up times during the time interval (i.e., 1 min). In both graphs, the closest vehicle strategy, the framework in Sarma et al., and the proposed framework are represented by blue, red, and green lines, respectively ( 3 ). The three strategies are able to serve a similar number of requests throughout the 24 h period although presenting a distinct pattern. The strategy underperforms at the onset of morning peak which happened in conjunction of two events: (i) an imbalance between request pick up locations and drop off locations that led idle vehicles to be located far away from pick up locations, and (ii) a relatively low number of idle vehicles for the prevailing demand, since overall demand peaked in the morning. Specifically, in this scenario, vehicles are initially evenly spread through the network, while the number of requests at the morning peak is distinct from that distribution. Clearly, the framework in Sarma et al. that considers all vehicles in a single problem handled this imbalance better ( 3 ). Possibly, a different initial distribution scheme or enabling repositioning as in de Souza et al. could mitigate this issue ( 26 ). The next case study will show that the impact of such imbalance is lower on a relatively smaller problem size.

Figure 2.

Chicago Metropolitan area simulation results for (a) the number of matched requests and (b) the average pick up time.

Finally, CPU times over the 24 h period are presented in Figure 3. The total CPU time for the presented framework is driven by the clustering settings of requests, the time to solve the NF model, and the time to solve the DRM networks. Since all of the DRM networks are independent, the time to solve the sub-problems is represented by the maximum time across all of them in a multi-threaded implementation. It was observed that the CPU times remained below 20 s throughout all the simulation period, while the baseline implementation yielded higher than 80 s of CPU time in the morning peak. The distribution of the solution time confirms that the clustering approach evenly distributes the vehicles and requests, and it creates sub-problems with comparable difficulties.

Figure 3.

Central processing unit (CPU) time results comparing this study with the literature for the Chicago Metropolitan area case.

Case Study in Bloomington, Illinois, U.S

Similar experiments were performed for the case of Bloomington, IL, which is another study area of the Polaris simulation tool. This network contains 7,000 links, 2,540 nodes, and a significantly low population at around 150,000. In this case, the propensity for TNC trips was increased by altering the alternative specific constant in the mode choice model. Around 20% of 650,000 simulated trips were performed using the TNC mode with nearly 5,000 vehicles. Although Bloomington is a much smaller area than Chicago, its simulation is useful to show another representative case. Therefore, a user of this framework can predict the final performance by positioning the studied network in between these two cases.

The key solution statistics are presented in Table 5 which follows the same pattern as Chicago. However, the proposed strategy achieves a closer performance compared with the method of Sarma et al., while keeping significantly lower computational times throughout the simulation ( 3 ).

Table 5.

Summary of Solution Statistics for the Bloomington, IL, Case

Strategy	Requests (K)	Empty vehicle miles traveled (VMT) (%)	Average pick up (s)	Average central processing unit (CPU) time (s)	Maximum CPU time (s)
Closest vehicle	152.9	25.2	167	NA	NA
Sarma et al. ( 3 )	152.3	21.1	133.0	2.6	34.5
This study	153.0	22.3	140.3	0.99	7.6

Note: NA = not available.

Figure 4a depicts the number of matched requests along a 24 h time period. In this case, the number of matched requests over time is similar for all evaluated strategies. Figure 4b illustrates the average pick up time for all three methodologies. The optimization-based strategies outperform the closest vehicle assignment by a significant margin in relation to the pick up time. The relative performance difference between this study and Sarma et al. is similar to the Chicago case ( 3 ).

Figure 4.

Bloomington, IL, simulation results for (a) the number of matched requests and (b) the average pick up time.

The CPU time comparison is provided in Figure 5. The method of Sarma et al. shows a small average, but reaches almost to 35 s in the morning peak ( 3 ). The proposed approach yields considerably lower computational times around the peak traffic, while the difference is smaller in the off-peak.

Figure 5.

Central processing unit (CPU) time results comparing this study with the literature for Bloomington, IL, case.

Conclusion

This study defined the DRM problem and reviewed its relationship to relevant problems studied in the literature. A framework was developed to solve the DRM problem in small pieces. In this framework, clusters of vehicles and requests were created. DRM networks were formed using a linear program that aims to minimize the travel time between clusters while satisfying an even distribution of vehicles and requests to these networks. Once the problem is partitioned, a multi-threaded approach was used to solve the sub-problems.

The framework made it possible to solve the problem in a large-scale transportation simulation on an average of 7.8 s as opposed to 18.4 s without the partitioning approach. Although the framework provided considerable computational time savings, the solution quality, in relation to the total pick up time, diminished by an average of 26%. In both study cases, the major CPU time improvements occur at times when there are more requests than vehicles, and, therefore, the approach without partitioning yields higher computational time.

Our case study in the Bloomington, IL, area, which possesses a comparatively smaller transportation network, showed that the clustering approach performs quite well in small-scale problems. In this case, the presented framework provided 62% computational time savings at the cost of 5% higher pick up time compared with a system-optimum approach in the literature. Further, this study’s approach provided the highest number of matches between vehicles and requests.

The method is especially suitable for large networks where the computational times can be significantly high. It is acknowledged that the method may underperform at specific situations of operations under high demand with an unbalanced distribution of vehicles, in which the centralized method can handle the situation better at the expense of higher computational time. Therefore, a mix of strategies can be adopted to reduce the average pick up time—for example, using the centralized framework in peak times and the proposed approach in non-peak times. Nevertheless, it should be highlighted that the computational time can also be an operational bottleneck, and this framework is flexible on the number of sub-problems. A better solution quality can be obtained by fine-tuning the computational time requirements while adjusting cluster sizes. In the future, the authors will investigate improvement strategies, such as defining the number of clusters that account for the imbalance of vehicles in the network, and also employing a repositioning algorithm to mitigate this imbalance. Therefore, clusters with better distribution of idle vehicles and drivers can be obtained. It should also be noted that the proposed framework consistently outperforms the closest vehicle assignment.

Another limitation in the study stems from considering only one request for a match. In some simulations, ride-sharing (carpooling) is useful to assess different possible future transportation scenarios. Therefore, future studies will focus on improving the current framework and incorporating the ride-sharing feature.

Footnotes

Acknowledgements

This work was sponsored by the U.S. Department of Energy (DOE) Vehicle Technologies Office (VTO) under the Systems and Modeling for Accelerated Research in Transportation (SMART) Mobility Laboratory Consortium, an initiative of the Energy Efficient Mobility Systems (EEMS) Program. David Anderson, a DOE Office of Energy Efficiency and Renewable Energy (EERE) manager, played important roles in establishing the project concept, advancing implementation, and providing ongoing guidance.

The submitted manuscript has been created by UChicago Argonne, LLC, Operator of Argonne National Laboratory (``Argonne''). Argonne, a U.S. Department of Energy Office of Science laboratory, is operated under Contract No. DE-AC02-06CH11357. The U.S. Government retains for itself, and others acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan. .

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: T. Cokyasar, F. de Souza; data collection: F. de Souza; analysis and interpretation of results: T. Cokyasar, F. de Souza; draft manuscript preparation: T. Cokyasar, F. de Souza, J. Auld, O. Verbas. 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 material is based on work supported by the U.S. Department of Energy, Vehicle Technologies Office, under the Systems and Modeling for Accelerated Research in Transportation Mobility Laboratory Consortium, an initiative of the Energy Efficient Mobility Systems Program.

ORCID iDs

Taner Cokyasar

Felipe de Souza

Joshua Auld

Omer Verbas

References

Auld

Hope

Ley

Sokolov

Zhang

POLARIS: Agent-Based Modeling Framework Development and Implementation for Integrated Travel Demand and Network and Operations Simulations. Transportation Research Part C: Emerging Technologies, Vol. 64, 2016, pp. 101–116. https://doi.org/10.1016/j.trc.2015.07.017.

Boesch

P. M.

Ciari

Agent-Based Simulation of Autonomous Cars. Proc., 2015 American Control Conference (ACC), Chicago, IL, 2015, pp. 2588–2592.

Sarma

J. N.

Nam

Hyland

M. F.

de Souza

Yang

Ghaffar

Verbas

I. O.

Effective and Efficient Fleet Dispatching Strategies for Dynamically Matching AVs to Travelers in Large-Scale Transportation Systems. Proc., IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), IEEE, Rhodes, Greece, 2020, pp. 1–6.

Özkan

Ward

A. R.

Dynamic Matching for Real-Time Ride Sharing. Stochastic Systems, Vol. 10, No. 1, 2020, pp. 29–70. https://doi.org/10.1287/stsy.2019.0037.

Al-Kanj

Nascimento

Powell

W. B.

Approximate Dynamic Programming for Planning a Ride-Hailing System Using Autonomous Fleets of Electric Vehicles. European Journal of Operational Research, Vol. 284, No. 3, 2020, pp. 1088–1106.

Jin

Towards Scalable Processing for a Large-Scale Ride Sharing Service. Proc.,9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing, Fukuoka, Japan, 2012, pp. 940–944.

Guan

Zhang

Nan

Liu

Bian

Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach. Proc., 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Association for Computing Machinery, New York, NY, 2018, pp. 905–913.

Johnson

E. L.

Mehrotra

Nemhauser

G. L.

Min-Cut Clustering. Mathematical Programming, Vol. 62, No. 1, 1993, pp. 133–151.

Feo

T. A.

Khellaf

A Class of Bounded Approximation Algorithms for Graph Partitioning. Networks, Vol. 20, No. 2, 1990, pp. 181–195.

10.

Validi

Buchanan

Lykhovyd

mposing Contiguity Constraints in Political Districting Models. http://www.optimization-online.org/DB_FILE/2020/01/7582.pdf. Accessed July 17, 2020.

11.

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.

12.

Ward

J. H.

Jr.

Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association, Vol. 58, No. 301, 1963, pp. 236–244.

13.

Auld

J. A.

de Souza

Enam

Javanmardi

Stinson

Verbas

Rousseau

Exploring the Mobility and Energy Implications of Shared Versus Private Autonomous Vehicles. Proc., IEEE Intelligent Transportation Systems Conference (ITSC), Auckland, New Zealand, IEEE, 2019, pp. 1691–1696.

14.

Auld

Mohammadian

Framework for the Development of the Agent-based Dynamic Activity Planning and Travel Scheduling (ADAPTS) Model. Transportation Letters, Vol. 1, No. 3, 2009, pp. 245–255.

15.

Auld

Rashidi

T. H.

Javanmardi

Mohammadian

Dynamic Activity Generation Model Using Competing Hazard Formulation. Transportation Research Record: Journal of the Transportation Research Board, 2011. 2254: 28–35.

16.

Auld

Mohammadian

Planning Constrained Destination Choice in the ADAPTS Activity-Based Model. Proc., 90th Annual Conference of the Transportation Research Board, Washington, DC.

17.

de Souza

Verbas

Auld

Mesoscopic Traffic Flow Model for Agent-Based Simulation. Procedia Computer Science, Vol. 151, 2019, pp. 858–863. https://doi.org/0.1016/j.procs.2019.04.118.

18.

Auld

Verbas

Stinson

Agent-Based Dynamic Traffic Assignment with Information Mixing. Procedia Computer Science, Vol. 151, 2019, pp. 864–869.

19.

Verbas

Ö.

Auld

Ley

Weimer

Driscoll

Time-Dependent Intermodal A* Algorithm: Methodology and Implementation on a Large-Scale Network. Transportation Research Record: Journal of the Transportation Research Board, 2018. 2672: 219–230.

20.

Gurumurthy

K. M.

de Souza

Enam

Auld

Integrating Supply and Demand Perspectives for a Large-Scale Simulation of Shared Autonomous Vehicles. Transportation Research Record: Journal of the Transportation Research Board, 2020. 2674: 181–192.

21.

Chicago Data Portal. Transportation Network Providers - Trips, 2020. https://data.cityofchicago.org/Transportation/Transportation-Network-Providers-Trips/m6dm-c72p. Accessed August 1, 2020.

22.

Auld

J. A.

de Souza

Enam

Javanmardi

Stinson

Verbas

Rousseau

Exploring the Mobility and Energy Implications of Shared Versus Private Autonomous Vehicles. Proc., IEEE Intelligent Transportation Systems Conference (ITSC), 2019, pp. 1691–1696.

23.

IBM. IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual, 2017. https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.studio.help/pdf/usrcplex.pdf. Accessed August 1, 2020.

24.

Menon

Barbour

Zhang

Pinjari

A. R.

Mannering

Shared Autonomous Vehicles and their Potential Impacts on Household Vehicle Ownership: An Exploratory Empirical Assessment. International Journal of Sustainable Transportation, Vol. 13, No. 2, 2019, pp. 111–122. https://doi.org/10.1080/15568318.2018.1443178.

25.

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.

26.

de Souza

Gurumurthy

K. M.

Auld

Kockelman

K. M.

An Optimization-based Strategy for Shared Autonomous Vehicle Fleet Repositioning. Proc., 6th International Conference on Vehicle Technology and Intelligent Transport Systems, SciTePress, 2020, pp. 370–376. https://doi.org/10.5220/0009421603700376.