Taxi dispatching strategies with compensations. (15th May 2019)

• Record Type: Journal Article
• Authors: Billhardt, Holger; Fernández, Alberto; Ossowski, Sascha; Palanca, Javier; Bajo, Javier
• Is Part Of: Expert systems with applications. Volume 122(2019)
• Page Start: 173
• Page End: 182
• Publication Date: 2019-05-15
• Subjects: Coordination -- Dynamic fleet management -- Dynamic optimization -- Multi-agent systems -- Open systems -- Taxi assignment; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.01.001
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Customer waiting time can be reduced by global dynamic reassignment of taxis. Cost savings can be used to compensate taxi drivers for accepting "worse" services. Surplus can be kept for the coordination service. The proposal outperforms standard strategies. Abstract: 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.