Fair cost allocation for ridesharing services - modeling, mathematical programming and an algorithm to find the nucleolus

作     者：Lu, Wei Quadrifoglio, Luca 

作者机构：Amazon Com Inc Seattle WA USA Texas A&M Univ Zachry Dept Civil Engn College Stn TX 77843 USA 

出 版 物：《TRANSPORTATION RESEARCH PART B-METHODOLOGICAL》 (运输研究B部分：方法)

年 卷 期：2019年第121卷

页      面：41-55页

核心收录：

学科分类：0201[经济学-理论经济学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0814[工学-土木工程] 0823[工学-交通运输工程] 

基　　金：Dissertation Fellowship of Texas AM University 

主　　题：Mathematical programming 

摘      要：This paper addresses one of the most challenging issues in designing an efficient and sustainable ridesharing service: ridesharing market design. We formulate it as a fair cost allocation problem through the lens of the cooperative game theory. A special property of the cooperative ridesharing game is that its characteristic function values are calculated by solving an optimization problem. Several concepts of fairness are investigated and special attention is paid to a solution concept named nucleolus, which aims to minimize the maximum dissatisfaction in the system. Due to its computational intractability, we break the problem into a master-subproblem structure and two subproblems are developed to generate constraints for the master problem. We propose a coalition generation procedure to find the nucleolus and approximate nucleolus of the game. Experimental results showed that when the game has a non-empty core, in the approximate nucleolus scheme the coalitions are computed only when it is necessary and the approximate procedure produces the actual nucleolus. And when the game has an empty core, the approximate nucleolus is close to the actual one. Regardless of the emptiness of the game, our algorithm needs to generate only a small fraction (1.6%) of the total coalition constraints to compute the approximate nucleolus. The proposed model and results nicely fit systems operated by autonomous vehicles. (C) 2019 Elsevier Ltd. All rights reserved.