Int. J. of Metaheuristics   »   2016 Vol.5, No.1

 

 

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

 

Int. J. of Metaheuristics, 2016 Vol.5, No.1, pp.67 - 90

 

Submission date: 07 Nov 2015
Date of acceptance: 24 May 2016
Available online: 11 Sep 2016

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article