Project: #185 Incentivizing Participation in Peer-to-Peer Ride-Sharing Platform Progress Report - Reporting Period Ending: Sept. 30, 2018 Principal Investigator: Fei Fang Status: Active Start Date: July 1, 2018 End Date: June 30, 2019 Research Type: Applied Grant Type: Research Grant Program: FAST Act - Mobility National (2016 - 2022) Grant Cycle: 2018 Mobility21 UTC Progress Report (Last Updated: Sept. 29, 2018, 10:16 p.m.) % Project Completed to Date: 25 % Grant Award Expended: 20 % Match Expended & Document: 20 USDOT Requirements Accomplishments We have developed an algorithm that can run at the backend of a central matching platform of peer-to-peer (P2P) ridesharing. The algorithm matches the riders' requests and drivers' offers to minimize the total travel cost of all the riders and drivers. This algorithm can help the riders and drivers find matches given their intended trips and can also accommodate the riders' and drivers' personal constraints, preferences and elasticity. In addition, we have started to explore fairness into the matching platform. If we only consider system-wise minimum cost, some drivers and riders may experience significant cost compared to others. We aim to provide matchings with a high level of fairness, where no agent experiences significant cost compare to other matched driver or riders. We have provided a definition of fairness in P2P ridesharing and a multi-objective optimization model for the matching task. The model asks the matching system to provide a set of possible matchings with high quality in both minimizing total travel cost and maximizing the fairness of matching. We are working on designing an algorithm to complete this task. Impacts To our knowledge, the matching algorithm we provide is the first algorithm that considers the users' constraints, preferences and elasticity at the same time. Previous work in this area only considered the users' hard constraints in departure and arrival time but did not consider deviation cost depends on the preferred time. The algorithm can serve as a tool for a P2P ridesharing platform implemented through a website or a smartphone application. The tool automatically recommends compatible carpooling options or ride requests to the users. We plan to embed the algorithm into the platform prototype in another project led by co-PI Alexandre Jacquillat and Prof. Vibhanshu Abhishek from CMU’s Heinz College, and supported by Mobility21. We expect that the existence of this matching algorithm can reduce the users' cognitive burden in finding a matching while enhancing the overall efficacy. Fairness is a very important aspect in matching the riders and drivers in P2P ridesharing platform and is understudied in the context of P2P ridesharing without a payment scheme. This additional consideration of fairness in matching can be viewed as part of a service tool and part of non-monetary incentive design as in the original plan since more users will be incentivized to use the system if the system is committed to taking into account fairness in the matching. With the ongoing work of designing the algorithm that provides a set of high-quality matchings, the system manager can choose how to make the tradeoff between fairness and total travel cost. Other Matching algorithm: For each agent, we consider his origin, his destination, his strict time window of departure, his preferred time of departure, and how much he values each unit time of deviation from their preferred time and detour from their shortest path. The algorithm we design for matching drivers and riders consists of two parts. Firstly, we incrementally construct a tripartite graph with three types of nodes: riders, subsets of riders and drivers. The existence of an edge between a driver and a subset of riders indicates the compatibility between the subset of riders and the driver, i.e., whether or not the driver can give a ride to all the riders in the subset while satisfying the personal constraints of everyone (including himself). For each pair of a driver and a subset of riders, we further use tree search and dynamic programming to compute the minimum total cost if the driver is asked to serve all the riders in the subset. The graph is incrementally generated, in the sense that we increase the size of the subset of riders, and will only check the compatibility of a driver and a subset of riders if the driver is compatible with all the subsets of this particular subset. Secondly, we use mixed integer linear programming to match the drivers and the subsets of riders, with the constraints that each rider request only needs to be served by one driver. Currently, our algorithm can scale up to 26 riders within 300 seconds. Fairness model: We measure the system-level fairness using the minimum utility among all drivers and riders. We model the matching task as providing a Pareto frontier of this multi-objective optimization problem. We are working on an algorithm that computes a list of good matchings that approximate the Pareto frontier. Outcomes New Partners No new partners Issues No significant change.