GPU Based Genetic Algorithms for the Dynamic Sub-area Division Problem of the Transportation System

Abstract At the early stage, the transportation system was controlled in a centralized way. As it grows larger, the system becomes decentralized. Nowadays, most of the commercial transportation systems work in a distributed way. The whole city or town is divided into static or dynamic sub-areas by some rules or heuristics. In every sub-area, the strategy is determined independently. As the cloud computing becomes popular, we propose the idea to control and management the transportation in a new centralized way, that is, all the information is collected together at the cloud side. The effect of the centralized control can be no worse than the decentralized one, as the decentralized control strategy is also one strategy of the centralized control. The division of the sub-areas is determined by computational experiments for different scenarios. We adopt the Multi-Agent System (MAS) model for the traffic flow simulation. And we use the Genetic Algorithms (GA) as the method for the computation to obtain good divisions. To overcome the difficult of the heavy computational burdens, we employ the Graphics Processing Unit (GPU) to accelerate the GA. We test the method on a 5×5 lattice road network and the 18 intersection Zhongguancun road network of Beijing. A speedup factor of around 110 is achieved.