Urban mobility efficiency is of utmost importance in big cities. Taxi
vehicles are key elements in daily traffic activity. The advance of ICT and
geo-positioning systems has given rise to new opportunities for improving the
efficiency of taxi fleets in terms of waiting times of passengers, cost and
time for drivers, traffic density, CO2 emissions, etc., by using more informed,
intelligent dispatching. Still, the explicit spatial and temporal components,
as well as the scale and, in particular, the dynamicity of the problem of
pairing passengers and taxis in big towns, render traditional approaches for
solving standard assignment problem useless for this purpose, and call for
intelligent approximation strategies based on domain-specific heuristics.
Furthermore, taxi drivers are often autonomous actors and may not agree to
participate in assignments that, though globally efficient, may not be
sufficently beneficial for them individually. This paper presents a new
heuristic algorithm for taxi assignment to customers that considers taxi
reassignments if this may lead to globally better solutions. In addition, as
such new assignments may reduce the expected revenues of individual drivers, we
propose an economic compensation scheme to make individually rational drivers
agree to proposed modifications in their assigned clients. We carried out a set
of experiments, where several commonly used assignment strategies are compared
to three different instantiations of our heuristic algorithm. The results
indicate that our proposal has the potential to reduce customer waiting times
in fleets of autonomous taxis, while being also beneficial from an economic
point of view.

通过使用启发式算法和经济补偿方案，该研究提出了一种用于出租车和客户配对的新算法，该算法提高了城市移动效率，并减少了客户等待时间。