Rigorous Systems Research Group (RSRG) Seminar

This "works-in-progress" talk presents an overview of two projects underway at Xerox Research Centre India (XRCI) under the Sustainability theme: (1) First, we present a cost-sharing scheme for passengers who share (perhaps different portions of) a ride, either by carpooling, or using commercial cabs or ride-hailing services. Modeling a passenger's disutilty as a combination of the monetary ride cost and the inconvenience cost due to detours, we provide constraints on the optimal route under which our cost-sharing scheme is Strongly/Sequentially Individually Rational (SIR), in the sense that not only are the passengers better off having chosen ridesharing, their disutility is non-increasing as the ride progresses and additional passengers are picked up. These SIR constraints are desirable for the passengers, because, coupled with a mobile app that can present this decrease in a visually compelling manner, our cost-sharing scheme has the potential to increase the adoption of ridesharing among commuters. (2) Second, we tackle the "chicken-and-egg" problem facing Electric Vehicle (EV) adoption–potential EV users are hesitant to make the switch because there isn't enough charging infrastructure out there, and charging station network operators hesitate to set up charging stations if there is not sufficient demand for charging. Specifically, a charging station service provider is concerned with the demand at the candidate locations and the budget for deployment, whereas the potential EV user is concerned with charging station reachability and short waiting times at the station. We propose a "mixed-packing-and-covering" optimization framework that captures these competing concerns, and extends to an alternate scenario where a government agency seeks to optimize its allocation of grants (e.g., to incentivize setting up charging stations in low-demand areas) to competing network operators. We identify a family of heuristics that seeks to iteratively find the optimal allocation of the available budget towards satisfying the "packing" (e.g., budget) constraints and the "covering" (e.g., reachability) constraints by alternatingly invoking knapsack and set-cover algorithms. A final, non-technical part of the talk will provide a brief overview of XRCI and discuss internship/collaboration/grant opportunities for students and faculty.