Modelling of Taxi Dispatch Problem Using Heuristic Algorithms

摘要

Taxi routing is a complex task that involves the pickup and delivery by a fleet of vehicles in a specified time, taking into account many parameters and criteria. This paper describes issues related to this problem. It proposes a formal description of the problem and a goal function using a wide variety of criteria. Three heuristic algorithms: Ant Colony Optimization, Artificial Bee Colony and Genetic Algorithm are selected for testing. As a result three variants of these algorithms are implemented: Ant Colony System (ACS), Predict and Select - Artificial Bee Colony (PS-ABC) and Genetic Algorithm (GA) to conduct a survey. Operators used in the algorithms are adapted to a taxi dispatch problem. The analysis is performed in order to find the best parameters for the algorithms according to the data input. Finally, the efficiency of the algorithms are compared in order to determine the best algorithm. In several experiments the Ant Colony System outperforms any other algorithm presented here with respect to taxi working time currently in service.