On-Demand Mobility Systems Can Ease Commuters’ Burdens
ISE Magazine October 2019 Volume: 51 Number: 10
By Pascal Van Hentenryck
https://www.iise.org/iemagazine/2019-10/html/hentenryck/hentenryck.html
In the United States, car ownership is still the best predictor of upward social mobility. Indeed, the relationship between transportation and social mobility is stronger than that between mobility and several other factors, like crime, elementary school test scores or the percentage of two-parent families in a community (“Transportation Emerges as Crucial to Escaping Poverty,” Mikayla Bouchard, The New York Times, May 7, 2015).
Those without a car are grievously disadvantaged in accessing jobs, healthcare and decent groceries. Millions of people with health insurance cannot get to the doctor due to a lack of mobility options. Tens of millions do not live within a mile of a supermarket and often shop in convenience stores, with sig-nificant consequences in the quality of their nutrition (“The Grocery Gap: Who Has Access to Healthy Food and Why It Matters,” Sarah Treuhaft and Allison Karpyn, Policy Link). Some children need to transfer buses twice before getting to the school of their choice, limiting access to after-school pro-grams and impacting their sleep patterns.
Advanced technologies have much to offer but improving vehicles is only part of the solution. For instance, efficient electric vehicles cannot reduce congestion, which may cost $184 billion in 2030 for the United States alone (“Beyond Traffic 2045,” U.S. Department of Transportation). Public transportation has the potential to mitigate congestion and provide environmentally friendly and cost-effective mobility. Existing systems, however, are of-ten plagued with the infamous “first/last mile” problem – the inability to take travelers all the way from their origin to their destination.
Indeed, in transit systems, fewer than 10% of riders typically walk more than a quarter of a mile. As a result, the vast majority of travelers prefer private vehicles if they can afford them, often creating congestion and emitting significant greenhouse gasses.
New mobility services such as Lyft and Uber have improved transportation for various population segments by using information technology to connect riders and potential drivers. Unfortunately, they increase congestion and greenhouse gas emissions; some cities, including New York, have started to limit their numbers. More importantly perhaps, they often serve the needs of an affluent population and have widened inequalities in accessibility by further draining the revenues of transit authorities (“Just a Better Taxi? A Survey-Based Comparison of Taxis, Transit, and Ridesourcing Services in San Francisco,” Lisa Rayle, Daniel Dai, Nelson Chan, Robert Cervero and Susan Shaheen, Transport Policy, 2016).
Fortunately, ubiquitous connectivity and advances in artificial intelligence and operations research offer significant opportunities to design socially aware, on-demand mobility systems. These novel systems are capable of addressing the first/last mile problem, reduce congestion and parking pressure and decrease greenhouse gas emissions. They may transform mobility for entire population segments and will benefit from autonomous vehicles whenever they become available.
To illustrate the opportunities and the underlying technological challenges, we will review three such systems: on-demand multimodal transit systems, community-based car sharing and large-scale car sharing. It describes the motivation behind these novel mobility systems, provides some pointers to the technology powering them and describes case-studies highlighting their potential benefits in cost and convenience.
On-demand multimodal transit systems
On-demand multimodal transit systems (ODMTS) (Arthur Maheo, Philip Kilby, and Pascal Van Hentenryck, “Benders Decomposition For The Design Of A Hub And Shuttle Public Transit System,” Transportation Science, January-February 2019) aim at transforming public transit by simultaneously addressing accessibility and congestion issues. Being multimodal, ODMTS combine on-demand mobility services to serve low-density regions with high-occupancy vehicles (buses or trains) traveling along high-density corridors. They differ from microtransit solutions by planning, operating and optimizing transit systems holistically, using state-of-the-art optimization technology and machine learning. As a result, they may trans-form accessibility for entire population segments, decreasing widening inequalities in transportation and providing a sustainable transportation model for American cities and beyond.
Informally speaking, ODMTS are for transit systems what Lyft and Uber are for taxi services: Their goal is to use artificial intelligence and operations research, as well as information and communication technologies, to transform public transit and improve accessibility and convenience. In its simplest form, an ODMTS combines small, on-demand, ride-sharing shuttles to address the ubiquitous first/last mile problem with high-occupancy vehicles (e.g., buses) operating a network of high-density corridors to mitigate congestion. The on-demand shuttles are best viewed as feeders to and from the high-occupancy network, although they also serve the local demand.
Large ODMTS may feature multiple types of high-occupancy vehicles (e.g., trains and buses), as well as various forms of small vehicles, which may be shuttles, e-scooters or bicycles in appropriate settings.
An ODMTS forms a unique, integrated network that is de-signed, planned and operated holistically. The network design chooses the routes for the high-occupancy vehicles, sizes the various fleets and produces the driver timetables. The OD-MTS real-time operations decompose a trip in a series of legs and solve generalized dial-a-ride problems over a rolling horizon to dispatch and route vehicles and perform ride-sharing. The dial-a-ride optimization minimizes the average waiting time, while ensuring that any ride does not exceed the time of the shortest path too much (e.g., 15%). The overall pipeline is depicted
Given that there is no range anxiety in ODMTS, they could be operated entirely by electrical vehicles. More-over, ODMTS are also a natural path-way to integrate autonomous vehicles as they become available.
Simulation and pilot results on small and medium transit systems (e.g., 7.5 million riders a year) have shown that an ODMTS can be priced like a traditional transit system while reducing wait times and/or improving accessibility. This is often possible due to a significant reduction in capital expenditures that compensate for additional driver costs for the on-demand shuttles. These simulations were performed in a variety of set-tings including the city of Canberra, Australia, and the transit system of the University of Michigan in Ann Arbor that represent extremes in terms of population densities.
Community-based car sharing
Parking occupies a significant portion of our cities. There are at least 800 million parking spaces in the United States alone and 14% of Los Angeles County is devoted to parking (“The Elephant In The Planning Scheme: How Cities Still Work Around The Dominance Of Parking Space,” Elizabeth Taylor, The Conversation, 2018). Parking also contributes to congestion, as the average share of cruising to find a parking spot is 30% in the United States (“Cruising For Parking,” Donald Shoup, Transport Policy, 2006; “The High Cost of Free Parking,” Shoup, American Planning Association, 2005).
Parking pressure is steadily increasing in corporate and uni-versity campuses and cities. This second case study was motivated by parking pressure at the University of Michigan in Ann Arbor, where the 15 most-used downtown parking lots show typical parking usage: Cars arrive in the morning, park in a lot for six to 10 hours and leave the lot in the evening.
Carpooling has long been proposed as a potential solution for reducing peak-hour congestion and parking pressure. Its adoption, however, is poor in general as 76.4% of American commuters choose to drive alone (“Who Drives to Work? Commuting by Automobile in the United States,” Brian McKenzie, American Community Survey Reports, U.S. Census Bureau, 2015). Jianling Li and co-authors (“Who Chooses to Carpool and Why? Examination of Texas Carpoolers,” Li, Patrick Embry, Stephen P. Mattingly, Kaveh Farokhi Sadabadi, Isaradatta Rasmidatta, Mark W. Burris, Transportation Research Record: Journal of the Transportation Research Board, 2007) identified the difficulty in finding people with similar location and schedule as the main reason for not carpooling. There is thus a unique opportunity to build a matching platform based on artificial intelligence and operations research for boosting adoption of carpooling.
Community-based carpooling (“Community-Based Trip Sharing For Urban Commuting,” M. Hafiz Hasan, Pascal Van Hentenryck, Ceren Budak, Jiayu Chen, Chhavi Chaudhry, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018) is an embodiment of such a platform. Its key idea is to organize pooling around commuting communities, exploiting spatial and temporal locality, i.e., the knowledge of when employees arrive on a (corporate or university) campus in the morning and leave in the evening. It also guarantees a “ride back” in the evening, probably the most critical factor for adoption. This contrasts with the carpooling platform Scoop, which only provides weak guarantees for a ride back, with monthly limits on how much auxiliary services can be used when a ride back is not available.
To satisfy these three properties – spatial and temporal locality and a guaranteed ride back – com-munity-based carpooling proceeds in two steps. First, it clusters commuters in communities, thus ensuring spatial locality. In the second step, an optimization algorithm selects drivers and matches riders to minimize the number of cars and the total travel distance. Each driver is assigned a route for the morning and evening commutes so that every rider is guaranteed a ride back. The routes also guarantee that each commuter will be served within requested time windows, exploiting temporal locality in the matching of drivers and riders.
The resulting optimization problem can be seen as two synchronized dial-a-ride problems. In the model in Figure 4, Ω+ and Ω- respectively represent a set of inbound and outbound routes. A decision variable Xr denotes whether a route r is included in the solution. The objective (1) minimizes the cost of the routes, while constraints (2) and (3) ensure that a rider is present in an inbound and outbound route (ᾳr,i is 1 if rider i is serviced by route r). Constraints (4) express the “ride back” constraints (βr,i is 1 if rider i is the driver on route r). This ensures that a driver in the morning is also a driver in the after-noon and vice-versa. The routes can be generated on-demand using a column-generation approach.
It would be ideal to have the same riders commute together in the morning and the evening as well as every day of the week. Unfortunately, one result of this study is the recognition that riders and drivers must be matched dynamically every day and every morning and afternoon: It is only when riders are matched dynamically that significant car-pooling occurs. This important realization, which explains the poor adoption in existing car-pooling programs, is illustrated in Figure 5. The “no sharing” column represents the number of cars with no car-pooling. Columns WD-WIO, WD-DIO, DD-DIO and DD impose progressively fewer constraints on the matching. In particular, WD-WIO requires that the same routes and drivers are used every day and that the same riders commute together every morning and evening.
As can be seen, these constraints are too stringent. Carpooling under these conditions reduces the number of cars on the road only by 2%. In contrast, DD only requires that the drivers are the same in the morning and in the evening in order to satisfy the “ride back” constraint. It saves the number of cars by 45% for the entire region and by more than 60% within the city limit. The platform thus needs to match drivers and riders every morning and every afternoon in real-time.
Moreover, it is desirable to adjust the afternoon dynamically as riders update their schedules. Optimization algorithms based on route generation are capable to meet these requirements, primarily because they exploit spatial and temporal locality. The car-pooling platform must be dynamic; while the morning and evening shared routes are dense, their intersection is rather sparse.
Large-scale ride sharing
The final on-demand mobility sys-tem presented is a large-scale ride-sharing platform. Ride-hailing systems such as Lyft and Uber have increased congestion in many cities. For instance, recent studies (“Do Transportation Network Companies Decrease Or Increase Congestion?” Gregory Erhardt, Sneha Roy, Drew Cooper, Bhargava Sana, Mei Chen, Joe Castiglione, Science Advances, May 2019) have shown that between 2010 and 2016, weekday vehicle hours of delay increased by 62% compared to 22% in a counterfactual 2016 scenario without ride hailing. Large-scale ride-sharing can change the equation. Authors Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus (“On-Demand High-Capacity Ride-Sharing Via Dynamic Trip-Vehicle Assignment,” Proceedings of the National Academy of Sciences, 2017) have shown that 98% of the riders using taxi and limousine services in New York city can be served with 3,000 vehicles and an average wait of 3.8 minutes (the city has about 12,000 taxis). Recent results using a bespoke column-generation approach have shown that all riders can be served with 2,000 vehicles, an average wait time of 2.2 minutes and an average deviation of 0.62 minute compared to a direct trip (“Column Generation for Real-Time Ride-Sharing Operations,” Connor Riley, Antoine Legrain and Van Hentenryck, Inter-national Conference on the Integration of Constraint Programming,
Technology opens new opportunities
Mobility is a critical aspect of modern societies: It provides access to jobs, healthcare, education, groceries and many other social services. The current transportation infrastruture and systems, however, face significant challenges in pro-viding equitable access, as well as in decreasing congestion and greenhouse gas emission.
Fortunately, the convergence of a number of technologies opens new opportunities that may fundamentally change the mobility landscape. In particular, information and communication technologies and progress in analytics driven by ma-chine learning and optimization make it possible to imagine entirely new mobility systems to meet these pressing challenges.
This article has presented three novel mobility systems addressing different needs: on-demand multimodal transit services, community-based car sharing and large-scale ride sharing. It has shown that these mobility systems have the potential to transform mobility by leveraging technology enablers in communication and predictive/prescriptive analytics.
The mobility systems can be deployed immediately and are sustainable from an economic and business standpoint. Moreover, fleet electrification and autonomous vehicles would amplify their benefits. Electrification, combined with renewable energy, would eliminate a substantial portion of greenhouse gas emission due to transportation, since the pro-posed mobility systems induce no range anxiety. Autonomy, if properly priced, will further decrease costs, enabling to further boost accessibility for entire population segments.