  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.
