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

Mechanism design for first-mile ridesharing based on personalized requirements part II: Solution algorithm for large-scale problems

Author

Listed:
  • Bian, Zheyong
  • Liu, Xiang

Abstract

Ridesharing provides travelers with a low-cost and convenient first-mile mobility service. Our Part I paper designed a mechanism to incentivize more travelers to participate in the first-mile ridesharing service accounting for passengers’ personalized requirements on inconvenience attributes of ridesharing. In order to address the computational challenge of obtaining the mechanism for large-scale transportation networks, this paper develops a novel heuristic algorithm, called the Solution Pooling Approach (SPA) for efficiently solving large-scale mechanism design problems in the first-mile ridesharing context. This paper also extends the SPA to solve generalized mechanism design problems, analyzes specific circumstances under which the SPA can sustain the game-theoretic properties, including “individual rationality” and “incentive compatibility”, and identifies its limitations. For the particular application in first-mile ridesharing, the SPA maintains the properties of “individual rationality” and “incentive compatibility”. Numerical experimental results show that the SPA can address the complex first-mile ridesharing service mechanism design problem in a computationally viable and efficient manner.

Suggested Citation

  • Bian, Zheyong & Liu, Xiang, 2019. "Mechanism design for first-mile ridesharing based on personalized requirements part II: Solution algorithm for large-scale problems," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 172-192.
    • Handle: RePEc:eee:transb:v:120:y:2019:i:c:p:172-192
    DOI: 10.1016/j.trb.2018.12.014
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517308238
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2018.12.014?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. Michel Gendreau & François Guertin & Jean-Yves Potvin & Éric Taillard, 1999. "Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching," Transportation Science, INFORMS, vol. 33(4), pages 381-390, November.
    2. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    3. Krygsman, Stephan & Dijst, Martin & Arentze, Theo, 2004. "Multimodal public transport: an analysis of travel time elements and the interconnectivity ratio," Transport Policy, Elsevier, vol. 11(3), pages 265-275, July.
    4. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    5. Anupam Gupta & Viswanath Nagarajan & R. Ravi, 2017. "Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 876-896, August.
    6. Shahar Dobzinski & Noam Nisan & Michael Schapira, 2010. "Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 1-13, February.
    7. Mu'alem, Ahuva & Nisan, Noam, 2008. "Truthful approximation mechanisms for restricted combinatorial auctions," Games and Economic Behavior, Elsevier, vol. 64(2), pages 612-631, November.
    8. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    9. Shaheen, Susan PhD & Chan, Nelson, 2016. "Mobility and the Sharing Economy: Potential to Overcome First- and Last-Mile Public Transit Connections," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt8042k3d7, Institute of Transportation Studies, UC Berkeley.
    10. Furuhata, Masabumi & Dessouky, Maged & Ordóñez, Fernando & Brunet, Marc-Etienne & Wang, Xiaoqing & Koenig, Sven, 2013. "Ridesharing: The state-of-the-art and future directions," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 28-46.
    11. Masoud, Neda & Lloret-Batlle, Roger & Jayakrishnan, R., 2017. "Using bilateral trading to increase ridership and user permanence in ridesharing systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 102(C), pages 60-77.
    12. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    13. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    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. Tafreshian, Amirmahdi & Masoud, Neda, 2022. "A truthful subsidy scheme for a peer-to-peer ridesharing market with incomplete information," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 130-161.
    2. 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.
    3. Xi, Haoning & Liu, Wei & Waller, S. Travis & Hensher, David A. & Kilby, Philip & Rey, David, 2023. "Incentive-compatible mechanisms for online resource allocation in Mobility-as-a-Service systems," Transportation Research Part B: Methodological, Elsevier, vol. 170(C), pages 119-147.
    4. Yan, Pengyu & Lee, Chung-Yee & Chu, Chengbin & Chen, Cynthia & Luo, Zhiqin, 2021. "Matching and pricing in ride-sharing: Optimality, stability, and financial sustainability," Omega, Elsevier, vol. 102(C).
    5. Lehua Bi & Shaorui Zhou & Jianjie Ke & Xiaoming Song, 2023. "Knowledge-Mapping Analysis of Urban Sustainable Transportation Using CiteSpace," Sustainability, MDPI, vol. 15(2), pages 1-29, January.
    6. Ding, Xiaoshu & Qi, Qi & Jian, Sisi & Yang, Hai, 2023. "Mechanism design for Mobility-as-a-Service platform considering travelers’ strategic behavior and multidimensional requirements," Transportation Research Part B: Methodological, Elsevier, vol. 173(C), pages 1-30.
    7. He, Ping & Jin, Jian Gang & Schulte, Frederik, 2024. "The flexible airport bus and last-mile ride-sharing problem: Math-heuristic and metaheuristic approaches," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 184(C).
    8. Liu, Yining & Ouyang, Yanfeng, 2021. "Mobility service design via joint optimization of transit networks and demand-responsive services," Transportation Research Part B: Methodological, Elsevier, vol. 151(C), pages 22-41.
    9. Zipeng Zhang & Ning Zhang, 2021. "The Morning Commute Problem with Ridesharing When Meet Stochastic Bottleneck," Sustainability, MDPI, vol. 13(11), pages 1-13, May.

    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. Bian, Zheyong & Liu, Xiang, 2019. "Mechanism design for first-mile ridesharing based on personalized requirements part I: Theoretical analysis in generalized scenarios," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 147-171.
    2. 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.
    3. Mu'alem, Ahuva & Schapira, Michael, 2018. "Setting lower bounds on truthfulness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 174-193.
    4. Tafreshian, Amirmahdi & Masoud, Neda, 2022. "A truthful subsidy scheme for a peer-to-peer ridesharing market with incomplete information," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 130-161.
    5. C.-Philipp Heller & Johannes Johnen & Sebastian Schmitz, 2019. "Congestion Pricing: A Mechanism Design Approach," Journal of Transport Economics and Policy, University of Bath, vol. 53(1), pages 74-7-98.
    6. Babaioff, Moshe & Blumrosen, Liad, 2008. "Computationally-feasible truthful auctions for convex bundles," Games and Economic Behavior, Elsevier, vol. 63(2), pages 588-620, July.
    7. Ruijie Li & Yu (Marco) Nie & Xiaobo Liu, 2020. "Pricing Carpool Rides Based on Schedule Displacement," Transportation Science, INFORMS, vol. 54(4), pages 1134-1152, July.
    8. Dütting, Paul & Talgam-Cohen, Inbal & Roughgarden, Tim, 2017. "Modularity and greed in double auctions," Games and Economic Behavior, Elsevier, vol. 105(C), pages 59-83.
    9. Bin Li & Dong Hao & Dengji Zhao, 2020. "Incentive-Compatible Diffusion Auctions," Papers 2001.06975, arXiv.org, revised Apr 2020.
    10. Daskalakis, Constantinos & Syrgkanis, Vasilis, 2022. "Learning in auctions: Regret is hard, envy is easy," Games and Economic Behavior, Elsevier, vol. 134(C), pages 308-343.
    11. Martin Bichler & Zhen Hao & Richard Littmann & Stefan Waldherr, 2020. "Strategyproof auction mechanisms for network procurement," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(4), pages 965-994, December.
    12. Dütting, Paul & Talgam-Cohen, Inbal & Roughgarden, Tim, 2017. "Modularity and greed in double auctions," LSE Research Online Documents on Economics 83199, London School of Economics and Political Science, LSE Library.
    13. Shrestha, Ratna K., 2017. "Menus of price-quantity contracts for inducing the truth in environmental regulation," Journal of Environmental Economics and Management, Elsevier, vol. 83(C), pages 1-7.
    14. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    15. Mizukami, Hideki & Saijo, Tatsuyoshi & Wakayama, Takuma, 2003. "Strategy-Proof Sharing," Working Papers 1170, California Institute of Technology, Division of the Humanities and Social Sciences.
    16. William H. Sandholm, 2005. "Negative Externalities and Evolutionary Implementation," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 72(3), pages 885-915.
    17. Soumyakanti Chakraborty & Anup K. Sen & Amitava Bagchi, 2015. "Addressing the valuation problem in multi-round combinatorial auctions," Information Systems Frontiers, Springer, vol. 17(5), pages 1145-1160, October.
    18. Toyotaka Sakai, 2017. "Considering Collective Choice: The Route 328 Problem in Kodaira City," The Japanese Economic Review, Japanese Economic Association, vol. 68(3), pages 323-332, September.
    19. , & ,, 2015. "Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule," Theoretical Economics, Econometric Society, vol. 10(2), May.
    20. d'Aspremont, Claude & Cremer, Jacques & Gerard-Varet, Louis-Andre, 2004. "Balanced Bayesian mechanisms," Journal of Economic Theory, Elsevier, vol. 115(2), pages 385-396, April.

    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:120:y:2019:i:c:p:172-192. 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.