  We introduce an improved algorithm for the dynamic taxi sharing problem, i.e.
a dispatcher that schedules a fleet of shared taxis as it is used by services
like UberXShare and Lyft Shared. We speed up the basic online algorithm that
looks for all possible insertions of a new customer into a set of existing
routes, we generalize the objective function, and we efficiently support a
large number of possible pick-up and drop-off locations. This lays an
algorithmic foundation for taxi sharing systems with higher vehicle occupancy -
enabling greatly reduced cost and ecological impact at comparable service
quality. We find that our algorithm computes assignments between vehicles and
riders several times faster than a previous state-of-the-art approach. Further,
we observe that allowing meeting points for vehicles and riders can reduce the
operating cost of vehicle fleets by up to 15% while also reducing rider wait
and trip times.
