IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v121y2019icp41-55.html
   My bibliography  Save this article

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

Author

Listed:
  • Lu, Wei
  • Quadrifoglio, Luca

Abstract

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.

Suggested Citation

  • Lu, Wei & Quadrifoglio, Luca, 2019. "Fair cost allocation for ridesharing services – modeling, mathematical programming and an algorithm to find the nucleolus," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 41-55.
    • Handle: RePEc:eee:transb:v:121:y:2019:i:c:p:41-55
    DOI: 10.1016/j.trb.2019.01.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S019126151730944X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2019.01.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. M. L. Balinski & R. E. Quandt, 1964. "On an Integer Program for a Delivery Problem," Operations Research, INFORMS, vol. 12(2), pages 300-304, April.
    2. Hallefjord, Asa & Helming, Reidun & Jornsten, Kurt, 1995. "Computing the Nucleolus When the Characteristic Function Is Given Implicitly: A Constraint Generation Approach," International Journal of Game Theory, Springer;Game Theory Society, vol. 24(4), pages 357-372.
    3. Xing Wang & Niels Agatz & Alan Erera, 2018. "Stable Matching for Dynamic Ride-Sharing Systems," Transportation Science, INFORMS, vol. 52(4), pages 850-867, August.
    4. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    6. Lloyd S. Shapley, 1967. "On balanced sets and cores," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 14(4), pages 453-460.
    7. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    8. M. Maschler & B. Peleg & L. S. Shapley, 1979. "Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 303-338, November.
    9. Stefan Engevall & Maud Göthe-Lundgren & Peter Värbrand, 2004. "The Heterogeneous Vehicle-Routing Game," Transportation Science, INFORMS, vol. 38(1), pages 71-85, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fielbaum, Andres & Kucharski, Rafał & Cats, Oded & Alonso-Mora, Javier, 2022. "How to split the costs and charge the travellers sharing a ride? aligning system’s optimum with users’ equilibrium," European Journal of Operational Research, Elsevier, vol. 301(3), pages 956-973.
    2. Zhou, Chang & Li, Xiang & Chen, Lujie, 2023. "Modelling the effects of metro and bike-sharing cooperation: Cost-sharing mode vs information-sharing mode," International Journal of Production Economics, Elsevier, vol. 261(C).
    3. Rasulkhani, Saeid & Chow, Joseph Y.J., 2019. "Route-cost-assignment with joint user and operator behavior as a many-to-one stable matching assignment game," Transportation Research Part B: Methodological, Elsevier, vol. 124(C), pages 60-81.
    4. Karaenke, Paul & Bichler, Martin & Merting, Soeren & Minner, Stefan, 2020. "Non-monetary coordination mechanisms for time slot allocation in warehouse delivery," European Journal of Operational Research, Elsevier, vol. 286(3), pages 897-907.
    5. Bian, Zheyong & Liu, Xiang & Bai, Yun, 2020. "Mechanism design for on-demand first-mile ridesharing," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 77-117.
    6. Öner, Nihat & Kuyzu, Gültekin, 2021. "Core stable coalition selection in collaborative truckload transportation procurement," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    7. Gao, Evelyn & Sowlati, Taraneh & Akhtari, Shaghaygh, 2019. "Profit allocation in collaborative bioenergy and biofuel supply chains," Energy, Elsevier, vol. 188(C).
    8. Fu-Shiung Hsieh, 2021. "A Comparison of Three Ridesharing Cost Savings Allocation Schemes Based on the Number of Acceptable Shared Rides," Energies, MDPI, vol. 14(21), pages 1-30, October.
    9. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem & Yacine Rekik, 2022. "Environmental and social implications of incorporating carpooling service on a customized bus system," Post-Print hal-03598768, HAL.
    10. Haoran Chen & Xuedong Yan & Xiaobing Liu & Tao Ma, 2023. "Exploring the operational performance discrepancies between online ridesplitting and carpooling transportation modes based on DiDi data," Transportation, Springer, vol. 50(5), pages 1923-1958, October.
    11. Luo, Chunlin & Zhou, Xiaoyang & Lev, Benjamin, 2022. "Core, shapley value, nucleolus and nash bargaining solution: A Survey of recent developments and applications in operations management," Omega, Elsevier, vol. 110(C).
    12. Liu, Xiaobing & Yan, Xuedong & Liu, Feng & Wang, Rui & Leng, Yan, 2019. "A trip-specific model for fuel saving estimation and subsidy policy making of carpooling based on empirical data," Applied Energy, Elsevier, vol. 240(C), pages 295-311.
    13. Liang Yuan & Xia Wu & Weijun He & Yang Kong & Thomas Stephen Ramsey & Dagmawi Mulugeta Degefu, 2022. "A multi-weight fuzzy Methodological Framework for Allocating Coalition Payoffs of Joint Water Environment Governance in Transboundary River Basins," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 36(9), pages 3367-3384, July.
    14. Theodoros P. Pantelidis & Joseph Y. J. Chow & Saeid Rasulkhani, 2019. "A many-to-many assignment game and stable outcome algorithm to evaluate collaborative Mobility-as-a-Service platforms," Papers 1911.04435, arXiv.org, revised Jun 2020.
    15. Pantelidis, Theodoros P. & Chow, Joseph Y.J. & Rasulkhani, Saeid, 2020. "A many-to-many assignment game and stable outcome algorithm to evaluate collaborative mobility-as-a-service platforms," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 79-100.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Stefan Engevall & Maud Göthe-Lundgren & Peter Värbrand, 2004. "The Heterogeneous Vehicle-Routing Game," Transportation Science, INFORMS, vol. 38(1), pages 71-85, February.
    2. Karaca, Orcun & Delikaraoglou, Stefanos & Hug, Gabriela & Kamgarpour, Maryam, 2022. "Enabling inter-area reserve exchange through stable benefit allocation mechanisms," Omega, Elsevier, vol. 113(C).
    3. Yang, Jian & Li, Jianbin, 2020. "Cooperative game with nondeterministic returns," Journal of Mathematical Economics, Elsevier, vol. 88(C), pages 123-140.
    4. Rene van den Brink & Ilya Katsev & Gerard van der Laan, 2023. "Properties of Solutions for Games on Union-Closed Systems," Mathematics, MDPI, vol. 11(4), pages 1-16, February.
    5. Lozano, S., 2012. "Information sharing in DEA: A cooperative game theory approach," European Journal of Operational Research, Elsevier, vol. 222(3), pages 558-565.
    6. Mingming Leng & Chunlin Luo & Liping Liang, 2021. "Multiplayer Allocations in the Presence of Diminishing Marginal Contributions: Cooperative Game Analysis and Applications in Management Science," Management Science, INFORMS, vol. 67(5), pages 2891-2903, May.
    7. Mathijs van Zon & Remy Spliet & Wilco van den Heuvel, 2021. "The Joint Network Vehicle Routing Game," Transportation Science, INFORMS, vol. 55(1), pages 179-195, 1-2.
    8. Behzad Hezarkhani & Marco Slikker & Tom Woensel, 2016. "A competitive solution for cooperative truckload delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 51-80, January.
    9. Yongjun Li & Feng Li & Ali Emrouznejad & Liang Liang & Qiwei Xie, 2019. "Allocating the fixed cost: an approach based on data envelopment analysis and cooperative game," Annals of Operations Research, Springer, vol. 274(1), pages 373-394, March.
    10. Drechsel, J. & Kimms, A., 2010. "Computing core allocations in cooperative games with an application to cooperative procurement," International Journal of Production Economics, Elsevier, vol. 128(1), pages 310-321, November.
    11. Mauricio Varas & Franco Basso & Paul Bosch & Juan Pablo Contreras & Raúl Pezoa, 2022. "A horizontal collaborative approach for planning the wine grape harvesting," Operational Research, Springer, vol. 22(5), pages 4965-4998, November.
    12. Luo, Chunlin & Zhou, Xiaoyang & Lev, Benjamin, 2022. "Core, shapley value, nucleolus and nash bargaining solution: A Survey of recent developments and applications in operations management," Omega, Elsevier, vol. 110(C).
    13. Hezarkhani, Behzad & Slikker, Marco & Van Woensel, Tom, 2019. "Gain-sharing in urban consolidation centers," European Journal of Operational Research, Elsevier, vol. 279(2), pages 380-392.
    14. H. Andrew Michener & Daniel J. Myers, 1998. "Probabilistic Coalition Structure Theories," Journal of Conflict Resolution, Peace Science Society (International), vol. 42(6), pages 830-860, December.
    15. Gonzalez, Stéphane & Rostom, Fatma Zahra, 2022. "Sharing the global outcomes of finite natural resource exploitation: A dynamic coalitional stability perspective," Mathematical Social Sciences, Elsevier, vol. 119(C), pages 1-10.
    16. Zaporozhets, Vera & García-Valiñas, María & Kurz, Sascha, 2016. "Key drivers of EU budget allocation: Does power matter?," European Journal of Political Economy, Elsevier, vol. 43(C), pages 57-70.
    17. Park, Jongyoon & Han, Jinil & Lee, Kyungsik, 2024. "Integer optimization models and algorithms for the multi-period non-shareable resource allocation problem," European Journal of Operational Research, Elsevier, vol. 317(1), pages 43-59.
    18. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    19. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    20. Bouchery, Yann & Hezarkhani, Behzad & Stauffer, Gautier, 2022. "Coalition formation and cost sharing for truck platooning," Transportation Research Part B: Methodological, Elsevier, vol. 165(C), pages 15-34.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:121:y:2019:i:c:p:41-55. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.