Optimizing the diamond lane: A more tractable carpool problem and algorithms

K. Shankari

Carpooling has been long deemed a promising approach to better utilizing existing transportation infrastructure. However, there are several reasons carpooling is still not the preferred mode of commute in the United States: first, complex human factors, including trust, compatibility, and not having right incentive structures, discourage the sharing of rides; second, algorithmic and technical barriers inhibit the development of online services for matching riders. High-occupancy vehicle (HOV) lanes which permit vehicles that hold three or more people (HOV3+) have been seen to simultaneously decrease trust concerns and dramatically reduce travel times, thereby providing a promising avenue for addressing both types of issues.

The goal of this article is to present algorithms for optimizing the use of HOV3+ lanes. We first formulate the HOV3 Carpool problem, show that it is NP-Complete, and provide a brief survey of related complexity results in ridesharing. We therefore pose the HOV3- Carpool problem, relaxing the strict capacity constraint of size three. Unlike the previous problem, this new problem is amenable to a wide range of common exact and heuristic methods for solving the problem of finding globally optimal carpool groups (in terms of total vehicle distance) that may utilize these HOV lanes. We present local search, integer programming, and dynamic programming methods; our local search methods include sampling-based (hill-climbing and simulated annealing), classical neighborhood search, and a hybrid random neighborhood search. We assess the methods numerically in terms of scalability and convergence to a naive “perfect carpooling” lower bound. We additionally assess the impact of domain-specific warm-starting strategies to the convergence of the iterative methods. Our experiments study synthetic agents set in both Euclidean and San Francisco Bay Area settings and highlight that the hill climbing local search method scales up to 100K agents, thereby improving upon related previous work (which studies up to 1000 agents), and numerically converge to 1.1 of the lower bound. All other attempted methods face scaling or convergence limitations.

Published On:

Presented At/In: 19th IEEE Intelligent Transportation Systems Conference

Download Paper: https://rise.cs.berkeley.edu/wp-content/uploads/2018/01/diamond-lane-ITSC16.pdf

Link: http://ieeexplore.ieee.org/document/7795739/

Authors: K. Shankari, Ece Kamar, Randy Katz, David Culler, Christos Papadimitriou, Eric Horvitz, Alexandre Bayen