Position: Ph.D. Student

Current Institution: University of California, Berkeley

Carpooling: a step towards seamless urban transportation

Traffic touches on the lives of billions of people on this planet, and in the US it costs us 50 million hours annually in commuting and 1.9 billion gallons of gas in congestion. A sizable 30% of the traffic in cities is simply searching for parking. Traffic is all at once a technical problem, a political problem, a deeply personal problem — and these aspects must be studied and addressed together. To this end, we must devise solutions that 1) are technically feasible, 2) are politically implementable in a reasonable time-frame, and 3) people will actually use.

Motivated by the problem of insufficient infrastructure for current and growing traffic demands, we studied carpooling, a long-hailed solution to better network utilization and yet still accounts for less than 10% of trips. We sought to understand the failure modes of carpooling, and found through an analysis of 200 employees of a large corporation that time is by far the most important factor in mobility preferences — perhaps enough so to overcome social, psychological, and cultural barriers to carpooling. We therefore formulated a carpooling problem in which all users, riders and drivers alike, can potentially benefit from carpooling through time savings. Specifically, we focused on the carpooling incentive structure of high-occupancy vehicle lanes (HOV), a politically well-established and easily implemented mechanism for traffic control. When the HOV lanes are restricted to three or more occupants (HOV3), which is necessary to maintain the high throughput of the lanes, we show that the corresponding set partitioning optimization problem of optimally assigning users to carpool groups is NP-Complete. Accordingly, prior work on related problems has not been able to scale beyond 1000 users. We therefore study a relaxed version of the problem which allows up to three passengers, and we demonstrate that a sampling-based local search method, which approximates the solution, enables us to scale to 100K users. By carefully considering the technical, political, and personal aspects of the carpool problem from the start, our results are ready to be field tested.

By overcoming social barriers and optimizing for the use of public infrastructure, this work paves the way for coordinating users for even higher throughput. I conclude with two (still hypothetical) examples: 1) automatically learning and introducing ad-hoc bus routes, which can carry up to 80 passengers instead of three, and 2) coordinating individual cars with existing high-throughput public transit systems (buses, subway, train) for a seamless transportation experience.

Cathy Wu received a Master of Engineering degree in Electrical Engineering and Computer Science (EECS) (2013) and a Bachelor of Science degree in EECS (2012) from the Massachusetts Institute of Technology (MIT). She is currently pursuing her Ph.D in the Department of EECS at the University of California, Berkeley. Cathy is a fellow with the NSF Graduate Research Fellowship Program and a winner of the Chancellor’s Fellowship for Graduate Study at UC Berkeley. She is also an awardee of the NDSEG fellowship and the Dwight David Eisenhower Graduate Fellowship. Her current research interests are at the intersection of optimization, statistics, cyber-physical systems, transportation, and robotics. Cathy particularly enjoys working between fields to identify and solve problems with direct positive societal impact. She also enjoys creating art, synthesizing treasure from trash, automated gardens, and personal data analytics.