Title: Multiobjective evolutionary algorithms for the taxi sharing problem

Authors: Renzo Massobrio; Gabriel Fagúndez; Sergio Nesmachnow

Addresses: Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay ' Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay ' Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay

Abstract: Transportation planning plays a central role in the design and development of smart cities. In particular, the concept of sharing economy applied to urban transportation is gaining massive public attention in recent years. This article presents the application of two multiobjective evolutionary algorithms to the problem of distributing passengers travelling from the same origin to different destinations in several taxis. A new problem formulation is presented, accounting for two quality of service metrics from the point of view of taxi users: the total cost of the trips and the delay experienced by each passenger. Two multiobjective evolutionary algorithms are proposed: a parallel microevolutionary algorithm (following a linear aggregation approach to combine the problem objectives) and one well-known algorithm from the literature (following a full multiobjective approach based on Pareto dominance). Both algorithms are compared against each other and against two greedy heuristics based on the ideas presented in the related literature. The experimental evaluation is performed over a set of 88 problem instances generated using real GPS taxi data. Results show that the proposed algorithms are able to efficiently reach significant improvements in both problem objectives over the greedy heuristics in short execution times.

Keywords: evolutionary algorithms; multiobjective optimisation; taxi sharing; smart cities; transport planning; urban transport; trip costs; delays.

DOI: 10.1504/IJMHEUR.2016.079103

International Journal of Metaheuristics, 2016 Vol.5 No.1, pp.67 - 90

Received: 27 Nov 2015
Accepted: 24 May 2016
Published online: 12 Sep 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article