Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques

Taxi sharing and closely related problems like ride matching have seen considerable attention in the last decade. We provide a short overview with a focus on transfers. A more detailed summary of work on dynamic taxi sharing in general can be found in [31].

The structure of the cost function remains the same for transfer insertions, and transfer insertions are subject to the same constraints as before. Computing the cost of a transfer insertion requires us to know the distances between existing stops and the transfer point in addition to the distances for orig and dest. Compared to no-transfer insertions, this increases the amount of work that needs to be spent solving shortest-path problems. In the following, we describe some additional intricacies that come with transfers.

Here, we summarize the shortest-path techniques most relevant to this paper.

KaRRi [31] is an algorithm for the dynamic taxi-sharing problem without transfers that acts as the basis of our solution to the problem with transfers. Here, we describe how KaRRi and its predecessor LOUD [7] use engineered routing techniques to dispatch requests efficiently.

The central challenge of computing single-transfer insertions is the fact that the pickup vehicle ${\nu }_p$ and the dropoff vehicle ${\nu }_d$ can move freely in the road network, which makes every location in the road network a potential transfer point. Without further limitations, the number of transfer insertions that need to be checked would be at least linear in the size of the road network. However, we can reduce the number of viable transfer locations for each request by taking into account the constraints on vehicle detours imposed by existing riders.

As mentioned in Section 3.2, the constraints on vehicle routes induce a detour leeway $\lambda (s_i,s_{i+1})$ between any two consecutive stops $s_i$ and $s_{i+1}$. This leeway defines the ellipse $ℰ(s_i)\subseteq V$ containing all locations to which a detour between $s_i$ and $s_{i+1}$ can be made without breaking any constraints. Thus, for any feasible transfer insertion $(r,x,{\nu }_p,{\nu }_d,i_p,j_p,i_d,j_d)$, the transfer point $x$ must lie in $ℰ(s_{j_p}({\nu }_p))$ if and in $ℰ(s_{i_d}({\nu }_d))$ if . If we know the detour ellipses of stop pairs along the routes of relevant vehicles, we can deduce a limited set of viable transfer locations for which transfer insertions need to be constructed.

In the following, we describe how detour ellipses can be used to enumerate transfer insertions of different types. For now, we assume that all necessary detour ellipses are known. We explain how to compute a detour ellipse on-the-fly in Section 5.1. We describe how to compute the necessary shortest-path distances in Sections 5.2 and 5.3.

We distinguish between two types of transfer insertions that differ in how detour ellipses constrain the set of potential transfer points.

Whenever a new request $r=(\text{orig},\text{dest},t_{\text{req}})$ is issued, the dispatching algorithm is started with the current route state. The best insertion returned by the algorithm is used to update the route state before the next request is processed.

Our dispatching algorithm is outlined in Algorithm 1. We always allow a rider to use no-transfer or transfer insertions. Thus, to start with, we use the base KaRRi algorithm to find the best no-transfer insertion. Then, we compute the sets $F_p(r)$ and $F_d(r)$ of potential pickup and dropoff vehicles. We compute the detour ellipse for every stop along the routes of these vehicles where a transfer may be made as described in the previous section. Subsequently, we enumerate all ordinary transfer insertions, all ALS transfer insertions for pickup vehicles, and all ALS transfer insertions for dropoff vehicles.

Finding exact transfer insertions requires us to compute the detour ellipses $ℰ(s_i)$ of many stop pairs $(s_i,s_{i+1})$. To find out whether a vertex $v\in V$ lies within $ℰ(s_i)$ we need to know the distances $\delta (s_i,v)$ and $\delta (v,s_{i+1})$ in order to check if $\delta (s_i,v)+\delta (v,s_{i+1})\le \lambda (s_i,s_{i+1})$. In effect, we need to compute the distances $\delta (s_i,v)$ and $\delta (v,s_{i+1})$ for every $v\in V$.

These two one-to-all shortest path problems can simply be solved by running a forward Dijkstra search rooted at $s_i$ and a reverse Dijkstra search rooted at $s_{i+1}$. The Dijkstra searches can be stopped once a vertex $v\in V$ with $d[v]>\lambda (s_i,s_{i+1})$ is settled. During the searches, we memorize which vertices have been settled. For every vertex settled by both searches, we check whether $\delta (s_i,v)+\delta (v,s_{i+1})\le \lambda (s_i,s_{i+1})$ to determine if $v\in ℰ(s_i)$.

As an alternative, we can use the one-to-all speedup technique PHAST (see Section 3.1). We run a forward PHAST search rooted at $s_i$ as well as a reverse PHAST search rooted at $s_{i+1}$. Then, we check whether $v\in ℰ(s_i)$ for every $v\in V$ using the computed distances. Note that PHAST queries cannot be pruned using $\lambda (s_i,s_{i+1})$ like the Dijkstra searches.

As proposed by the authors of PHAST, the queries can be accelerated using both instruction- and thread-level parallelism (cf. Section 3.1). In contrast to PHAST, it is notoriously difficult to apply multi-threading to speed up Dijkstra queries with good scalability [34]. Similarly, bundling Dijkstra queries for vectorized edge relaxations only works well if the sources are close to each other in the graph and thus have overlapping shortest-path trees. Unfortunately, this is not the case for arbitrary stops.

Note that both approaches provide the shortest-path distances between vehicle stops and transfer points that are later required to compute the cost of an insertion.

To find all ordinary transfers, we need to compute the intersection of the detour ellipses of stops of pickup vehicles in $F_p(r)$ and dropoff vehicles in $F_d(r)$, as described in Section 4.2.

The LOUD no-transfer dispatcher provides a way to compute the sets $F_p(r)$ and $F_d(r)$ of potential pickup and dropoff vehicles. For both orig and dest, we run a forward and reverse BCH search that identifies the vehicles and stops at which a detour can be made to perform the pickup or dropoff. Elliptic pruning speeds up these queries and limits the size of $F_p(r)$ and $F_d(r)$ (cf. Section 3.2). These BCH searches also provide the distances needed to compute the detour made for the pickup and the dropoff.

To facilitate intersecting ellipses, we sort every ellipse by vertex ID. Then, any intersection $ℰ(s_{j_p}({\nu }_p))\cap ℰ(s_{i_d}({\nu }_d))$ can be constructed with a linear sweep over $ℰ(s_{j_p}({\nu }_p))$ and $ℰ(s_{i_d}({\nu }_d))$.

If $i_p\ne j_p$ and $i_d\ne j_d$, the distances between stops and transfer points computed during the ellipse reconstruction suffice to calculate the cost of the insertion. In the case of a paired insertion, i.e., $i_p=j_p$ or $i_d=j_d$, we need to additionally know the distances from orig to the transfer point $x$ or the distance from $x$ to dest, respectively. For paired insertions, we first assume $\delta (\text{orig},x)=0$ or $\delta (x,\text{dest})=0$ and compute a lower bound for the cost of the insertion. If this lower bound is worse than the best known cost, we can safely discard it. Otherwise, we compute the distance $\delta (\text{orig},x)$ or $\delta (x,\text{dest})$ using a point-to-point CH query.

As described in Section 4.2, in an ALS insertion, a transfer point may be any location within the detour ellipse of the non-ALS vehicle. Here, we focus on the case that the pickup vehicle ${\nu }_p$ is the ALS vehicle and brings the rider to a transfer point in an ellipse of a dropoff vehicle ${\nu }_d$. Then, we need to know the distances from the last stop $s_{k({\nu }_p)}$ to every location in this ellipse. Extending this to all possible pickup vehicles in $F_p(r)$ and dropoff vehicles in $F_d(r)$, we get a many-to-many shortest path problem where the set of sources $ℒ$ contains all last stops of pickup vehicles, while the set of targets $𝒯$ is the union of all eligible ellipses, i.e.,

We utilize RPHAST for this problem. We run the selection phase once for $𝒯$ and then run a query from every $l\in ℒ$. We can bundle and vectorize these queries (cf. Section 3.1).

A pickup vehicle may also perform both the pickup and the trip to the transfer after its current last stop in a paired ALS insertion $(r,x,{\nu }_p,{\nu }_d,k({\nu }_p),k({\nu }_p),i_d,j_d)$. In this case, we need to know the distance from orig to every transfer point $x$. Thus, we run a single RPHAST query from orig to $𝒯$. Additionally, we need to identify vehicles ${\nu }_p$ that need to be considered for a pickup after their last stop as $F_p(r)$ is not guaranteed to contain all of them. For this purpose, we utilize BCH searches as proposed by KaRRi (cf. Section 3.2). We construct bucket entries for every last stop. Then, a single reverse BCH query rooted at orig computes the distances from all last stops to orig. We prune the set of viable vehicles by comparing cost lower bounds based on these distances to the best known cost.

Now consider the case that the dropoff vehicle goes to the transfer after its last stop while the pickup vehicle incorporates the transfer somewhere along its existing route. Then, the ALS insertion will always be paired since the dropoff must necessarily be performed after the transfer. Thus, we can use the same techniques outlined for paired ALS insertions above.

Computing the cost for a transfer insertion takes much longer than for a no-transfer insertion. Thus, we describe three ways to speed up the computation of insertions and their cost. We focus on ordinary insertions but all techniques are applicable to ALS insertions, too.

Our source code²²2Available at https://github.com/JohannesBreitling/karri-with-transfers. is written in C++20 and compiled with GCC 11.5 using -O3. We use two machines for separate experiments, both running Rocky Linux 9.5. Machine A has 64 GiB of memory and a single 16-core AMD Ryzen 9 3950X processor at 3.5GHz. Machine B has 512 GiB of memory and a single 32-core Intel Xeon Gold 6314U processor at 2.3 GHz. We use 32-bit distance labels and the AVX2 SIMD instruction set with 256-bit registers to compute up to $8$ operations in one vector instruction.

We evaluate KaRRiT on the Berlin-1pct (B-1%), and Berlin-10pct (B-10%) request sets [7] that, respectively, represent taxi-sharing demand for 1% and 10% of the population of the Berlin metropolitan area on a weekday. The request sets for Berlin were artificially generated using the Open Berlin Scenario [48] for the MATSim transport simulation [22]³³3MATSim generates realistic demand data but considering more than 10% of the population would take processing times in the order of multiple months. For details, see [7].. Both sets cover a time window of $30$ hours and follow a realistic distribution of demand on a weekday regarding both time and space. The Berlin-1pct and Berlin-10pct request sets contain $16569$ and $149185$ requests, respectively. Images on the temporal and spatial distribution can be found in Figure 4 in Appendix B. We use $1000$ vehicles for Berlin-1pct and $10000$ vehicles for Berlin-10pct. Each vehicle has a capacity of four and a service time interval covering the entire $30$ hours. The initial locations of all vehicles are drawn uniformly at random. The underlying road network of Berlin and the surrounding area is obtained from publicly available OpenStreetMap data⁴⁴4https://download.geofabrik.de/.. It contains 94422 vertices and 193212 edges. We use the known speed limit of each road to determine the travel time of the according edge in the vehicle network. We compute a contraction hierarchy of the road network using the open-source library RoutingKit⁵⁵5https://github.com/RoutingKit.. This takes less than a minute for Berlin.

For our cost function (see Section 2), we adopt a basic “time is money” approach. We use $\tau =1$ to weight the time of a driver and a rider equally. In accordance with the MATSim transport simulation, we choose $\alpha =1.7$ and $\beta =2\text{min}$. For the remaining parameters, we choose $t_{\text{wait}}^{\text{max}}=600\mathrm{s}$, ${\gamma }_{\text{wait}}=1$, and ${\gamma }_{\text{trip}}=10$.

We analyze the impact of individual features of our algorithm on the running time. For this, we run experiments on machine A. We use the Berlin-1pct instance as running times for a non-optimized implementation are infeasible on Berlin-10pct. We consider the four main components of our algorithm (lines 4-7 in Algorithm 1) separately.

To start with, utilizing PHAST speeds up the computation of detour ellipses by a factor of about $2.5$ compared to the Dijkstra-based implementation (cf. Section 5.1). Thus, we start from this baseline of using PHAST and RPHAST, and illustrate the speedups achieved with our additional measures in Figure 3.

Applying cost bounds (see Section 5.4) has the greatest effect on ALS insertions for the dropoff vehicle with a speedup of about $7.74$. The enumeration of ALS insertions for the pickup vehicle and ordinary insertions become $1.89$ and $1.56$ times faster, respectively.

Additionally checking transfer points for pareto-dominance speeds up the enumeration of ordinary transfer insertions, ALS transfer insertions for the pickup vehicle, and ALS transfer insertions for the dropoff vehicle by factors of $2.96$, $2.15$, and $1.19$, respectively. This shows that transfer point dominance and cost bounds work well in combination. In fact, the two methods seem to synergize as the speedups for transfer point domination are highest for the components where cost bounds provide the least benefit.

Bundling PHAST queries and employing SIMD vector instructions to run up to eight searches simultaneously speeds up ellipse reconstruction by a factor of $2.72$. However, it has almost no effect on the ALS steps because their runtime is dominated by work not affected by SIMD speedups like enumerating insertions or the RPHAST selection phase.

Using four threads for parallel PHAST queries and enumeration of insertions leads to mediocre speedups, ranging from $1.62$ for ALS transfer insertions for the pickup vehicle, to $2.56$ for the dropoff vehicle. For the PHAST queries used during ellipse reconstruction, this can be attributed to the fact that PHAST can only settle vertices in parallel within individual CH levels. Since our road network is comparatively small, the sizes of CH levels are limited and synchronization overhead may be large. For the enumeration of transfers, speedups are again held back by work that we did not parallelize, e.g., the RPHAST selection phase. These effects contribute to the lack of scalability to larger numbers of threads. With $16$ threads we hardly see any speedups compared to $4$ threads. The only component that benefits from more threads is the enumeration of ALS transfer insertions for the dropoff vehicle, which spends a lot of time on trivially parallelizable cost computation.

We compare the running time of the heuristic variant (H) of KaRRiT (see Section 6) with the exact variant (E). The experiments were run on machine B with $32$ threads, all optimizations, and $k=10\%$ for H. Running times per request for different steps are shown in Table 1.

Restricting transfer points to vertices of high CH rank using H reduces the running time of the ellipse reconstruction by a factor of about four compared to the exact solution. As discussed in Section 6, this is caused by the PHAST queries having to perform only one tenth of the work, settling the top $k=10\%$ of vertices in the CH. Since the upper CH levels are small and only vertices within the same CH level can be settled in parallel, the ellipse reconstruction in H does not benefit from multi-threading. This limits the speedup over E to four instead of being closer to ten. Due to reduced ellipse sizes, H computes the cost of about eight times fewer insertions than E. In the ordinary transfer step, the smaller ellipse sizes also reduce the time needed for intersecting ellipses. Additionally, the set of targets $𝒯$ for RPHAST in the ALS transfer components is around two orders of magnitude smaller for H than for E, which speeds up the selection and query phases of RPHAST.

For E, the set of transfer points $𝒯$ includes almost all locations in the road network⁶⁶6It is possible that $|𝒯|>|V|$ since our implementation of KaRRiT uses edges, not vertices, as transfer locations. We still always have $|𝒯|\le |E|$.. Thus, a PHAST query without an expensive RPHAST selection phase may perform better. For H, the number of transfer points is small enough to warrant using RPHAST.

Note that the number of insertions tried can exceed the number of transfer points because every pickup or dropoff vehicle may be matched with any transfer point. In turn, the transfer point pruning strategies outlined in Section 5.4 reduce the number of insertions tried. Interestingly, these pruning strategies appear to be more successful for E than for H as the ratio between the number of insertions tried and the number of potential transfer points is much larger for H than for E. This may be explained by the fact that H already heuristically selects good transfer points based on CH rank such that they may be harder to prune using cost bounds or especially transfer point domination.

We evaluate the impact of allowing transfers on the solution quality of dynamic taxi sharing by experimentally comparing KaRRiT in the exact (E) and heuristic (H) variants to the no-transfer baseline KaRRi. Results for experiments run on machine B are shown in Table 2. Note that we give only preliminary results on dispatch quality, since the focus of this work is on the algorithmic aspects. In the future, we plan to use our new fast algorithm to consider the effect of transfers in more detail with a larger variety of input instances.

Considering the running time of the algorithms, KaRRi is up to two orders of magnitude faster than the heuristic variant, and three orders faster than the exact variant. The running time of H can still be considered practical while E seems infeasibly slow.

On Berlin-1pct, transfers appear to have almost no effect on the solution quality. This can be attributed to the fact that the density of requests is small with about one request per minute. Thus, it is unlikely that two riders share a vehicle (as evidenced by the low vehicle occupancies). Moreover, a vehicle may always be available to take a passenger to their destination directly, which often outperforms any transfer insertions. In additional experiments with artificially increased request densities, we were able to confirm that request density is in fact a deciding factor for the viability of transfers.

As Berlin-10pct also provides a much denser request set, we focus on this instance here. When comparing the exact solution E to KaRRi, we see decent improvements in occupancy rates and slight improvements in vehicle operation times. Average occupancy rates increase by $5.9\%$, and vehicle operation times decrease by $4.6\%$. This is a significant benefit with respect to the use of space on the roads and the operating costs of the taxi-sharing provider. As a drawback, rider trip times increase by $3.1\%$ compared to KaRRi. This matches the expectation that transfers may be good for efficiency at a cost of rider satisfaction.

While these gains may not justify the large running time of E, the heuristic H retains most of the benefits. The improvement for vehicles are about one third smaller than for E, but rider trip times are also less severely affected. Since H is an order of magnitude faster than E, it may therefore be a more viable candidate for a production system.