Parallel Heuristic Algorithms In Geographical Network Analysis

Geographical network analysis is an integral part of Geographical Information System, and plays an increasingly important role in transportation, logistics, E-business, and so on. With the enlargement of the scope of analysis and the expanding of the amount of data, increasingly complicated computing tasks put forward higher requirements on the basic network analysis algorithms. There are several complex problems in geographical network analysis, such as p-median problem, vehicle routing problem, and so on, which are all NP-hard problems and solved by heuristic algorithms. With the increasing of the scale of problems in practical application, the traditional serial algorithms cannot meet the demand of complex application context on computing efficiency and solving capacity. Aiming at the disadvantages that the traditional serial algorithms have low computing efficiency and limited solving capacity, a combination of parallel technique and heuristic algorithms is proposed to take full advantage of computing resource on parallel hardware to improve traditional algorithms' computational efficiency and processing capacity. The main achievements in this study are as follows:(1) The application scheme of parallel heuristic algorithms in geographical network analysis is summarized and concluded. There are several common problems when applying parallel technique and heuristic algorithms to geographical network problems. Therefore, it is necessary to summarize this kind of problems and corresponding solutions and extract a common application framework to guide the designing and development of parallel algorithm on specific problem. Firstly, the characteristics and potential parallel features of different geographical network problems are analyzed, and the problems are divided into three classes by computing complexity: simple problems, compute-intensive problems and NP-hard problems. The latter two types are main research objects in this study. Secondly, two construction schemes of parallel heuristic algorithm which can be applied to geographical network analysis are concluded. The first one is a universal parallel heuristic algorithm based on algorithm parallelization, which improves the calculation efficiency through the parallelization of the time-consuming parts of serial algorithm. This method can ensure the quality of solution. The second one is based on network partition, which aims on some problems that have locality. This scheme is not universal and will result in a quality penalty, but can gain very high efficiency on some specific problems and solve very large scale problem which cannot be solved by serial algorithm. Furthermore, some general data storage strategies, algorithm testing and optimization methods which are applied to parallel network analysis algorithms are summarized. Through above work, a set of practical application schemes and general procedures are proposed and can be used to guide the designing and development of parallel heuristic algorithm on specific problem.(2) A parallel scatter search algorithm for solving p-median problem is proposed. Classical heuristics and meta-heuristics are the most widely used algorithms for p-median problem. Classical heuristics are very efficient, but the quality of result is usually low; while meta-heuristics can gain high quality results, but its efficiency is much lower than classical heuristics'. To solve these problems, parallel technique is introduced to improve the efficiency of meta-heuristic, and a parallel scatter search algorithm for p-median problem is constructed. This parallel algorithm is based on the framework of scatter search, and two time-consuming procedures in the framework, the improvement of initial solutions and the combination of solutions, are parallelized using master/slave mode. In the improvement procedure, different improvement tasks are allocated to processes and executed synchronously; in the combination procedure, the set of subsets is divided into several parts which then be allocated to processes. Several experiments are conducted on some benchmarks and artificial transportation networks. Firstly, the algorithm's correctness is tested on several larger p-median problem instances in OR-Library. The experimental results show that the algorithm proposed in this study can gain high quality solution, and find the optimal solution in most tests, and the deviation is below 0.3% when the solution is not optimal. Secondly, the parallel efficiency and solving quality of the algorithm are tested on artificial transportation networks. The testing is conducted on three test data sets of different size using 1~6 processes, and the algorithm is compared with Densham-Rushton(DR) algorithm which is an efficient classical heuristic. The experimental results show that the parallel algorithm performs well, and its running time reduces by about 60% than serial scatter search algorithm when the number of processes is 5, very close to DR algorithm's running time; the solution quality is as high as serial scatter search and rises by 0.4%~0.9% than DR algorithm's result. In conclusion, the parallel scatter search algorithm proposed in this study can gain high-quality solution in about the same time as classical heuristic, and balances computing efficiency and solution quality.(3) A parallel algorithm for vehicle routing problem(VRP) in geographical network is proposed. The VRP in geographical network is different from the VRP in graph theory, and before applying graph theory algorithm to geographical network VRP, a conversion from geographical network VRP to graph theory VRP based on OD(Origin-Destination) matrix computing must be executed. In large scale geographical network VRP, the conversion can consume a vast amount of computing time and memory. Therefore, a parallelization of the traditional serial algorithm is proposed to improve the overall efficiency of the algorithm for geographical network VRP by parallelizing both the OD matrix computing and the tabu search procedure. Meanwhile, the algorithm is designed especially for PC cluster considering the characteristics of the hardware platform. First of all, a parallel Johnson algorithm is applied to the OD matrix computing to improve the computing efficiency, and a distributed storage strategy is used to distribute the memory cost to different computing nodes, to solve the out-of-memory problem in single node and increase the processing capacity. Secondly, the tabu search procedure is parallelized by partition the neighborhood and a simplified communicational data structure is designed to improve the communication efficiency. Finally, the algorithm is tested on 6 artificial transportation VRP of different size using 1~8 processes. The experimental results show that the proposed algorithm can solve large scale geographical network VRP efficiently and gains high quality solution(average deviation is between 2.11% and 2.87%) and good extensibility. Meanwhile, the acceleration is sufficient on PC cluster and the speedup is between 4.46~6.32 when the number of processes is 8.(4) A parallel algorithm for p-median problem based on network partition is proposed. The parallelization of serial algorithm can improve the computing efficiency of solving p-median problem, but the memory bottleneck limits the processing capacity as the scale of problem increasing. Based on the locality of p-median problem, a network partition based parallel heuristic algorithm is proposed in this study. Firstly, the network is partitioned into several balanced parts using METIS graph partition tools by setting appropriate vertex weights and parameters. Secondly, the sub-problem in each part is solved by serial heuristic. Finally, a specially designed merging procedure is used to adjust the allocation of medians and improve the quality of the global solution. The proposed algorithm is tested on two different scale artificial networks. The experimental results show that:(a)the computing efficiency is very high and the running time of multi-processes computing is less than serial algorithm by one or two orders of magnitude;(b)the solution's quality of the parallel algorithm is a little worse than the serial one's, but the deviation is under 0.3% when the number of parts is appropriate;(c)this parallel algorithm can use multi-processes to solve very large scale problem which cannot be solved by serial algorithm and has a perfect speedup. In conclusion, the network partition based parallel algorithm proposed in the study can improve the computing efficiency greatly and guarantee certain accuracy, and the processing capacity can expand with the increasing of the number of computing nodes. Thus, this algorithm can be used to solve very large scale p-median problems which serial algorithm cannot solve.