A Parallel Ant Colony System Based on Region Decomposition for Taxi-Passenger Matching
A Parallel Ant Colony System Based on Region Decomposition for Taxi-Passenger Matching
Situ Xin, Chen Wei-Neng, Gong Yue-Jiao, Lin Ying, Yu Wei-Jie, Yu Zhiwen and Zhang Jun
Situ Xin, Chen Wei-Neng, Gong Yue-Jiao, Lin Ying, Yu Wei-Jie, Yu Zhiwen and Zhang Jun
Sun Yat-sen University, China
South China University of Technology, China
South China University of Technology, China
Sun Yat-sen University, China
Sun Yat-sen University, China
South China University of Technology, China
South Chi
Sun Yat-sen University, China
South China University of Technology, China
South China University of Technology, China
Sun Yat-sen University, China
Sun Yat-sen University, China
South China University of Technology, China
South Chi
Taxi dispatch is a critical issue for taxi company to consider in modern life.
This paper formulates the problem into a taxi-passenger matching model and
proposes a parallel ant colony optimization algorithm to optimize the model. As
the searchspace is large, we develop a region-dependent decomposition strategy to
divide and conquer the problem. To keep the global performance, a critical region
is defined to deal with the communications and interactions between the
subregions. The experimental results verify that the proposed algorithm is
effective, efficient, and extensible, which outperforms the traditional global
perspective greedy algorithm in terms of both accuracy and efficiency.
