Assignment and pricing of shared rides in ride-sourcing using combinatorial double auctions
File(s)
Accepted version
Author(s)
Karamanis, Renos
Anastasiadis, Eleftherios
Angeloudis, Panagiotis
Stettler, Marc
Type
Journal Article
Abstract
Transportation Network Companies employ dynamic pricing methods at periods of peak travel to incentivise driver participation and balance supply and demand for rides. Surge pricing multipliers are commonly used and are applied following demand and estimates of customer and driver trip valuations. Combinatorial double auctions have been identified as a suitable alternative, as they can achieve maximum social welfare in the allocation by relying on customers and drivers stating their valuations. A shortcoming of current models, however, is that they fail to account for the effects of trip detours that take place in shared trips and their impact on the accuracy of pricing estimates. To resolve this, we formulate a new shared-ride assignment and pricing algorithm using combinatorial double auctions. We demonstrate that this model is reduced to a maximum weighted independent set model, which is known to be APX-hard. A fast local search heuristic is also presented, which is capable of producing results that lie within 10% of the exact approach for practical implementations. Our proposed algorithm could be used as a fast and reliable assignment and pricing mechanism of ride-sharing requests to vehicles during peak travel times.
Date Issued
2020-04-29
Date Acceptance
2020-04-09
Citation
IEEE Transactions on Intelligent Transportation Systems, 2020, 22 (9), pp.5648-5659
ISSN
1524-9050
Publisher
Institute of Electrical and Electronics Engineers
Start Page
5648
End Page
5659
Journal / Book Title
IEEE Transactions on Intelligent Transportation Systems
Volume
22
Issue
9
Copyright Statement
© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://ieeexplore.ieee.org/document/9082117
Subjects
Transportation Network Companies
Ride-Sourcing
Ride-Sharing
Combinatorial Double Auctions
Notes
12 pages, Ride-Sharing, Combinatorial Double Auctions, Assignment, Dynamic Pricing
Publication Status
Published
Date Publish Online
2020-04-29