Parallelization of Ant Colony Algorithm in Transportation Discrete Network Design

Transportation Discrete Network Design Problem (TDNDP) is the problem of selecting a feasible subset of proposed projects، i. e. highways، so as to minimize the total travel time of the network users. This problem falls into the NP-Hard complexity class of problems for which no efficient algorithm exists for exact solution in practical cases. As a result، to find a rather good solution for the problem in a reasonable amount of time، many studies addressed TDNDP through heuristic and meta-heuristic approaches. However، application of parallel computing is still another way to further speedup TDNDP solution approaches. 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 master-worker parallelization paradigm. The Chicago Sketch transportation network is considered as a case study with 16 bi-directional proposed projects. The results of parallelization over a cluster of 8 processing cores support that parallel algorithms can achieve high quality solutions in 4000 seconds، while this happens for the single-core algorithm 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 compared with that of the branch and bound algorithm. The comparison indicates that the parallel branch and bound algorithm requires more that 32000 seconds running time to find the exact solution of the problem، while the parallel ACA reveals a much faster performance. Transportation Discrete Network Design Problem (TDNDP) is the problem of selecting a feasible subset of proposed projects، i. e. highways، so as to minimize the total travel time of the network users. This problem falls into the NP-Hard complexity class of problems for which no efficient algorithm exists for exact solution in practical cases. As a result، to find a rather good solution for the problem in a reasonable amount of time، many studies addressed TDNDP through heuristic and meta-heuristic approaches. However، application of parallel computing is still another way to further speedup TDNDP solution approaches. 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 master-worker parallelization paradigm. The Chicago Sketch transportation network is considered as a case study with 16 bi-directional proposed projects. The results of parallelization over a cluster of 8 processing cores support that parallel algorithms can achieve high quality solutions in 4000 seconds، while this happens for the single-core algorithm 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.