  On-demand transport services in the form of dial-a-ride and taxis are crucial
parts of the transport infrastructure in all major cities. However, not all
on-demand transport services are equal. In particular, not-for-profit
dial-a-ride services with coordinated drivers significantly differ from
profit-motivated taxi services with uncoordinated drivers. As such, there are
two key threads of research for efficient scheduling, routing, and pricing for
passengers: dial-a-ride services (first thread); and taxi services (second
thread). Unfortunately, there has been only limited development of algorithms
for joint optimization of scheduling, routing, and pricing; largely due to the
widespread assumption of fixed pricing. In this paper, we introduce another
thread: profit-motivated on-demand transport services with coordinated drivers.
To maximize provider profits and the efficiency of the service, we propose a
new market mechanism for this new thread of on-demand transport services, where
passengers negotiate with the service provider. In contrast to previous work,
our mechanism jointly optimizes scheduling, routing, and pricing. Ultimately,
we demonstrate that our approach can lead to higher profits, compared with
standard fixed price approaches, while maintaining comparable efficiency.
