From the Cover: Quantifying the benefits of vehicle pooling with shareability networks

Taxi services are a vital part of urban transportation, and a considerable contributor to traffic congestion and air pollution causing substantial adverse effects on human health. Sharing taxi trips is a possible way of reducing the negative impact of taxi services on cities, but this comes at the expense of passenger discomfort quantifiable in terms of a longer travel time. Due to computational challenges, taxi sharing has traditionally been approached on small scales, such as within airport perimeters, or with dynamical ad hoc heuristics. However, a mathematical framework for the systematic understanding of the tradeoff between collective benefits of sharing and individual passenger discomfort is lacking. Here we introduce the notion of shareability network, which allows us to model the collective benefits of sharing as a function of passenger inconvenience, and to efficiently compute optimal sharing strategies on massive datasets. We apply this framework to a dataset of millions of taxi trips taken in New York City, showing that with increasing but still relatively low passenger discomfort, cumulative trip length can be cut by 40% or more. This benefit comes with reductions in service cost, emissions, and with split fares, hinting toward a wide passenger acceptance of such a shared service. Simulation of a realistic online system demonstrates the feasibility of a shareable taxi service in New York City. Shareability as a function of trip density saturates fast, suggesting effectiveness of the taxi sharing system also in cities with much sparser taxi fleets or when willingness to share is low.Vehicular traffic congestion––and the air pollution that results from it––is one of the greatest challenges facing cities all over the world. It comes at great monetary and human cost: in the 83 largest urban areas of the United States alone, the amount of wasted time and fuel caused by congestion has been placed at US$ 60 billion (1). At the same time, the World Health Organization has estimated that over one million deaths per year worldwide can be attributed to outdoor air pollution (2), which is to a large part caused by vehicular traffic (3). Further adverse effects include fatalities through road accidents and economic losses from missed business activities. For these reasons, great hope is placed today in the rapid deployment of digital information and communication technologies that could help make cities “smarter” (4), and, in particular, that could help manage vehicular traffic more efficiently. The use of real-time information allows the monitoring of the urban mobility infrastructure to an unprecedented extent, and opens up new potential for the exploitation of unused capacity. One major example is the public mobility infrastructure: taking advantage of the widespread use of smart phones and their capabilities for running real-time applications, it is possible to design new, smarter transportation systems based on the sharing of cars or minivans, effectively providing services that could replace public transportation with the on-demand qualities of individual mobility or taxis (5). However, although this option has been proposed in the past, municipal authorities, city residents, and other stakeholders may be reluctant to invest in it until its benefits have been quantified (6). This is the goal of the present paper.At the basis of a shared taxi service is the concept of ride sharing or carpooling, a long-standing proposition for decreasing road traffic, which originated during the oil crisis in the 1970s (6). During that time, economic incentives outbalanced the psychological barriers on which successful carpooling programs depend: giving up personalized transportation and accepting strangers in the same vehicle. Surveys indicate that the two most important deterrents to potential carpoolers are the extra time requirements and the loss of privacy (7, 8). However, the lack of correlations between socio-demographic variables and carpooling propensity (8), the design of appropriate economic incentives (9), and recent practical implementations of taxi-sharing systems in New York City (http://bandwagon.io) give ample hope that many social obstacles might be overcome in newly emerging “sharing economies” (10, 11).Besides psychological considerations, it is fundamental to understand the logistic limitations of realistic taxi-sharing systems, which is our focus here. From a theoretical perspective, trip sharing is traditionally seen as an instance of “dynamic pickup and delivery” problems (12, 13), in which a number of goods or customers must be picked up and delivered efficiently at specific locations within well-defined time windows. Such problems are typically solved by means of linear programming, in which a function of the system variables is optimized subject to a set of equations that describe the constraints. Whereas linear programming tasks can be solved with standard approaches of Operations Research or with constraint programming (14), their computational feasibility heavily depends on the number of variables and equations, e.g., the pickup and delivery time windows of each customer, used to describe the problem at hand. Most previous taxi studies have therefore focused on small-scale routing problems, such as within airport perimeters (15, 16). Large urban taxi systems, in contrast, involve thousands of vehicles performing hundreds of thousands of trips per day. A first step toward practical taxi ride-sharing systems is ref. 17, where the authors present the design of a dynamic ride-sharing system inclusive of a taxi dispatching strategy and fare management. Due to computational reasons trip sharing in ref. 17 is decided based on a heuristic approach tailored to the specific taxi dispatching strategy at hand. Our approach, by contrast, is the development of a framework which enables investigation in general terms the fundamental tradeoff between the benefit and the passenger discomfort induced by taxi-sharing systems at the city level, as an example from a wide class of spatial sharing problems.Here we introduce the notion of shareability network to model trip sharing in a simple static way, and apply classical methods from graph theory to solve the taxi trip-sharing problem in a provably efficient way. The differences between static trip sharing as considered herein, and dynamic sharing as considered, e.g., in ref. 17, are discussed in detail in SI Appendix. The starting point of our analysis is a dataset composed of the records of over 150 million taxi trips originating and ending in Manhattan in the year 2011 by all 13,586 registered taxis. For each trip, the record reports the vehicle ID, the Global Positioning System (GPS) coordinates of the pickup and drop-off locations, and corresponding times. Pickup and drop-off locations have been associated with the closest street intersection in the road map of Manhattan (Materials and Methods). We impose a natural network structure on an otherwise unstructured, gigantic search space of the type explored in traditional linear programming. To this end we define two parameters: the shareability parameter k, standing for the maximum number of trips that can be shared, and the quality of service parameter Δ, which stands for the maximum delay a customer tolerates in a shared taxi service trip, mathematically equivalent to the notion of “time window” used in other approaches (13, 17). To ease the analysis, we use the Δ formalism; however, when presented in a real implementation to passengers, it might be psychologically more effective to use the neutral wording “time window” rather than explicitly mentioning the maybe more negatively connoted word “delay.” The choice of defining the quality of service parameter as an absolute time, instead of as a percentage increase of the travel time, is in line with similar realizations in the literature (17), and is motivated by the fact that absolute delay information is likely more valuable than percent estimation of travel time increase for potential customers of a shared taxi service. Further, let Ti=(oi,di,tio,tid),i=1…k be k trips where o_i denotes the origin of the trip, d_i the destination, and tio,tid the starting and ending times, respectively. We say that multiple trips T_i are shareable if there exists a route connecting all of the o_i and d_i in any order where each o_i precedes the corresponding d_i, except for configurations where single trips are concatenated and not overlapped like o₁ → d₁ → o₂ → d₂, such that each customer is picked up and dropped off at the respective origin and destination locations with delay at most Δ, with the delay computed as the time difference to the respective single, individual trip. Imposing a bound of k on shareability implies that the k trips can be combined using a taxi of corresponding capacity (Fig. 1G). Deciding whether two or more trips can be shared necessitates knowledge of the travel time between arbitrary intersections in Manhattan, which we estimated using an ad hoc heuristic (SI Appendix, Fig. S2 and Table S1).Open in a separate windowFig. 1.Shareability networks translate spatiotemporal sharing problems into a graph-theoretic framework that provides efficient solutions. (A) Example of seven trips, T₁,…, T₇, requested and to be shared in Manhattan, New York City. (B) Construction of shareability network for k = 2. Trips that could potentially be shared are connected, given the necessary time constraints to hold which we assume here to be the case. Trips 1 and 4 cannot be shared because the total length of the best shared route would be longer than the sum of the single routes. Likewise, trip 7 is an isolated node because it cannot possibly be shared with other trips. (C) Maximum matching of the shareability network gives the maximum number of trip pairs, i.e., the maximum number of shared trips. (D) Implementation (routing) of the maximum matching solution. (E) Alternatively, maximum weighted matching of the shareability network gives the solution with the minimal total travel time, which in this case leads to a different solution than unweighted maximum matching. Here only two pairs of trips are shared, but the amount of travel time saved, given by the sum of link weights of the matching, 30 + 16, is optimal. (F) Implementation (routing) of the weighted maximum matching solution. (G) k sharing and taxi capacity. Each of the three cases involves a number of trips T_i to be shared, but ordered differently in time t. (Top) This case corresponds to a feasible sharing according to our model with k = 2, and the trips can be accommodated in a taxi with capacity ≥2. (Middle) This case corresponds to a model with k = 3 because three trips are combined, but the three trips can be combined in a taxi with capacity = 2 because two of the trips are nonoverlapping. (Bottom) This case corresponds to k = 3, but here a taxi capacity ≥3 is needed to accommodate the combined trips. Here we are assuming one passenger per trip, in line with the data reported in ref. 18, according to which the average number of passengers per trip is 1.3.For the case k = 2, the shareability network associated with a set ?? of trips is obtained by assigning a node T for each trip in ??, and by placing a link between two nodes T_i and T_j if the two trips can be shared for the given value of Δ (Fig. 1 A and B). The value of Δ has a profound impact on topological properties of the resulting shareability network. Increasing Δ capitalizes on well-known effects of time-aggregated networks such as densification (19, 20), capturing the intuitive notion that the more patient the customers, the more opportunities for trip sharing arise (Fig. 2 A and B). For values of k > 2, the shareability network has a hypergraph structure in which up to k nodes can be connected by a link simultaneously. Because of computational reasons, the shareability parameter k has a substantial impact on the feasibility of solving the problem. A solution is tractable for k = 2, heuristically feasible for k = 3, whereas it becomes computationally intractable for k ≥ 4 (SI Appendix). This constraint implies that taxi-sharing services, and social-sharing applications in general, will likely be able to combine only a limited number of trips. However, as we show below, even the minimum possible number of trip combinations (k = 2) can provide immense benefits to a dense enough community like the city of New York.Open in a separate windowFig. 2.Shareability networks densify with longer time aggregation, increasing sharing opportunities. This exemplary subset of the shareability network corresponds to 100 consecutive trips for values of (A) Δ = 30 s and (B) Δ = 60 s. Open links point to trips outside the considered set of trips. Isolated nodes are represented as self-loops. Node positions are not preserved across the networks. A similar, although visually not insightful, densification effect is observed in shareability networks obtained when k = 3.With the shareability network, classical algorithms for solving maximum matching on graphs (21, 22) can be used to determine the best trip-sharing strategy according to two optimization criteria: (i) maximizing the number of shared trips, or (ii) minimizing the cumulative time needed to accommodate all trips. To find the best solution according to (i) or (ii), it is sufficient to compute a maximum matching or a weighted maximum matching on the shareability network, respectively (Fig. 1 C and E, Materials and Methods). Because a shared trip can be served by a single taxi instead of two, the number of shared trips can be used as a proxy for the reduction in number of circulating taxis. For instance, an 80% rate of shared trips translates into a 40% reduction of the taxi fleet. Other important objectives such as total system cost and emissions are reasonably approximated by criterion (ii).