Parallelization of Ant Colony Algorithm in Transportation Discrete Network Design

Transportation Discrete Network Design Problem (TDNDP) is defined as the problem of selecting a subset of proposed projects (i.e. new highways) for construction, while holding the budget constraint, so as to minimize the total travel time of the network users. TDNDP has been often known as a problem with the bi-level programming formulation. At the upper level, this formulation allows for finding the optimal selection of the projects, while taking into account the route choice behavior of network users at its lower level. Such a formulation falls into the category of problems in the NP-Hard complexity class. These are resource-intensive problems which have not been exactly solved yet with any efficient algorithms. As a result, the main body of TDNDP related literature has ignored the exact solution of the problem and addressed TDNDP through heuristic and meta-heuristic approaches. These approaches contribute to find a rather high quality solution in a reasonable amount of time.
Using heuristic and meta-heuristic algorithms is one way to overcome the complexity of NP-Hard problems like TDNDP. However, application of parallel computing still remains as another way to speed up the performance of such algorithms. Parallel computation aims at harnessing multiple computing resources, e.g. computer processors, to solve a certain problem. Different parallelization paradigms have been developed so far to parallelize solution algorithms. These paradigms generally address the two fundamental questions of how and when the required information should be exchanged among the processors. A master-slave (MS) parallelization paradigm is one of the basic paradigms in which one processor, namely the master, holds the main information of the problem. The master generates new jobs whenever needed, distributes them among other processors (i.e. slaves), and exploits them to work on the sent jobs. This paper is going to explore the application of parallel computation in a meta-heuristic algorithm in TDNDP. A parallel Ant Colony Algorithm (ACA), based on the study of Poorzahedy and Abulghasemi, is proposed with the MS parallelization paradigm. The Chicago Sketch transportation network is considered as a case study with 16 bi-directional proposed projects. The results are reported in three runs over a cluster of 8 processing cores for both single-core and parallel ACAs. According to the performances observed in this paper, parallel algorithms can achieve high quality solutions in 4000 seconds, while this happens for the single-core algorithms in 10000 seconds. The parallel ACA finds the exact solution of the problem in two instances out of three runs and in the other instance it converges to a solution with 0.07 percent error from the exact solution. The parallel performance of ACA is also reported along with that of the branch and bound algorithm. It is observed that the parallel branch and bound algorithm requires more than 32000 seconds running time to find the exact solution of the problem. More accurate comparisons, however, can only be achieved by running the single-core and parallel ACAs more than the three times used in this paper.