Research On Ant Colony Optimization Of Vehicle Routing Based On Time-space Transformation And Association Rules

Vehicle routing optimization is one of the most important research areas in Geographic Information System for Transportation (GIS-T). Ant Colony Optimization (ACO), representative of artificial intelligence computing, becomes a research hotspot in the field of route optimization. This paper takes into account several problems that exist in vehicle routing optimization of transportation networks and carries out the following researches.(1) Time geography framework of transportation system and the MDS time-space transformation model are analyzed from the GIS perspective of geograpphy space and time space. In order to solve the TSP constrained by Transportation Networks (TSP-TN), two improved ACO algorithms based on time-space transformation theory are proposed:Ant Colony Optimization extended by Metric Time-Space (ACO-MTS algorithm) and Ant Colony Optimization extended by Heuristic Time-Space (ACO-HTS algorithm). Both algorithms transform the geography-space configuration of demand points within transportation networks into time-space configuration by the MDS time-space transformation model. The ACO-MTS algorithm makes use of the convex-hull property of metric two-dimensional Euclidean time space in order to guide the ants to construct routes in a search space more closed to the best solution. The ACO-HTS algorithm uses time distance as global heuristic information of probability choice rule in ant route construction by the relationships of global dissimilarity measurement of time distance in time space so as to make up the insufficiency of local heuristic information in the original ACO algorithm. Experimental results show that, in large TSP-TN problem, the ACO-MTS algorithm can greatly speed up the convergence of ACO and improve the quality of the best solution; while in large TSP-TN problem of traffic congestions, the ACO-HTS algorithm can effectively enhance the ability of seeking global best solution and improve the best solution found.(2) In order to solve the area segmentation and delivery problem within transportation networks, the time-space transformation model of time geography framework and the Self-organizing Map (SOM) of artificial neural networks are combined to propose a time-space transformation and segmentation model named MDS-SOM model. The MDS-SOM model takes the time-space configuration of MDS as the input of SOM and generates topologically-ordered classification structure of demand points in time space, then area segmentation of time space is mapped into that of geography space according to the corresponding relationships of points. Ant Colony Optimization based on Time-Space Transformation and Segmentation (ACO-TSTS algorithm) is proposed upon the MDS-SOM model. Experimental results indicate that, in the application of area segmentation and route optimization within transportation networks, time-space segmentation is more appropriate than geography-space segmentation since the delivery routes in the time-space segmentation solution cost much less and also keep relative stabilization of the delivery areas.(3) The mathematic model of VRP ant colony optimization and the principles of the MACS-VRPTW algorithm are analyzed. In order to solve the VRP constrained by transportation networks (VRP-TN) with determined number of vehicles, Multiple Ant Colony System based on Time-Space Transformation (MACS-TST algorithm) is proposed with the VRP route simplification model in the MACS-VRPTW algorithm as a prototype. The MACS-TST algorithm introduces two ant colonies sharing best solutions as the cooperation mode. One is the ACS-TIME ant colony in the MACS-VRPTW algorithm; the other is the ACS-TIME-TC ant colony that introduces the metric property of time space upon the definition of the ACS-TIME ant colony. In the metric two-dimensional Euclidean time space, the ACS-TIME-TC ant colony uses the solution components of time convex hull of every sub-TSP to optimize pheromone distribution and thus the whole process of seeking best VRP route takes best sub-TSP route search into account at the same time. Experimental results show that, the MACS-TST algorithm not only finds better solution much faster, but also improves the quality of the best solution.(4) From the perspective of data mining and knowledge discovery, it is found out that a large amout of near best routes generated from the ACO iterations are not effectively used by ants. Therefore, the idea of using association rules mining to study ACO is proposed. The key issue of this idea is to find a fast association rules mining algorithm of high performance to solve the bottleneck of conventional algorithms. On the performance analysis of Apriori algorithm and vertical mining algorithm, two improved accociation rules ming algorithms are proposed. One is the improved Apriori algorithm based on Support Count Matrix (Apriori-SCM algorithm), the other is the Fast Algorithm of Long mode Association rules based on Vertical mining (FALAV algorithm). The Apriori-SCM algorithm is an exact improved algorithm that can compress search space effectively, reduce the cost of Apriori join and prune steps, and increase the efficiency of frequent itemset generation. The FALAV algorithm is a heuristic fast algorithm with less computation cost and high performance. It can discover long mode association rules much faster than the Apriori algorithm.Ant Colony Optimization based on Association Rules Mining (ACO-ARM algorithm) is proposed based on these two improved association rules ming algorithms. The ACO-ARM algorithm includes two methods:one is named ACO-ARM algorithm based on Apriori-SCM, the other is named ACO-ARM algorithm based on FALAV. Experimental results indicate that, both two ACO-ARM algorithms can improve the quality of ACO best solution. However, the ACO-ARM algorithm based on Apriori-SCM has much lower performance than ACO; while the ACO-ARM algorithm based on FALAV not only finds better solution than ACO, but also greatly speeds up the convergence of ACO with less computational time and high performance.