موازي‌سازي الگوريتم كلوني مورچگان در طراحي شبكه گسسته حمل‌‌ونقل

Parallelization of Ant Colony Algorithm in Transportation Discrete Network Design

طراحي شبكه گسسته حمل ونقل عبارت است از انتخاب زيرمجموعه اي امكان پذير از پروژه ها(بزرگراه ها)ي پيشنهادي در يك شبكه حمل ونقل به منظور كمينه سازي زمان سفر كل كاربران شبكه. اين مساله در كلاس پيچيدگي مسايل NP-Hard قرار دارد كه هيچ الگوريتم موثري براي حل دقيق آن‌ها در مقياس بزرگ وجود ندارد. ازاين رو بيشتر مطالعات انجام گرفته، به منظور يافتن جواب خوبي در مدت زمان معقول، ‌از طريق رويكردهاي ابتكاري و فرا ابتكاري به مساله پرداخته اند. اما راه ديگري كه همچنان براي افزايش سرعت رويكردهاي حل مساله وجود دارد، محاسبات موازي است. مقاله پيش رو، در پي بررسي كاربرد محاسبات موازي در يك الگوريتم فراابتكاري در مساله طراحي شبكه گسسته حمل ونقل است. در اين مقاله، يك الگوريتم موازي كلوني مورچگان، بر مبناي مطالعه پورزاهدي و ابوالقاسمي، با الگوي موازي سازي ارباب-كارگر پيشنهاد مي‌شود‌. براي مطالعه موردي، شبكه حمل ونقلي خلاصه شده شيكاگو با 16 پروژه پيشنهادي درنظرگرفته مي شود. نتايج موازي سازي روي خوشه اي از 8 هسته پردازشي نشان دهنده آن است كه الگوريتم هاي موازي مي-توانند ظرف مدت زمان 4 هزار ثانيه به جواب هايي با كيفيت بالا دست پيدا كنند، درحالي كه همين دستيابي براي الگوريتم هاي تك هسته اي در مدت 10 هزار ثانيه اتفاق مي افتد. نتايج نشان مي دهند كه در دو مورد از سه اجرا، الگوريتم موازي كلوني مورچگان به جواب دقيق مساله دست مي يابد، و در مورد ديگر به جوابي با 07/0 درصد خطا نسبت به جواب دقيق همگرا مي شود. عملكرد موازي الگوريتم كلوني مورچگان، همچنين در كنار الگوريتم شاخه وكرانه موازي گزارش خواهدشد. اين گزارش نشان مي دهد كه الگوريتم موازي شاخه-وكرانه، در مثال مورد نظر، به زمان بسيارزيادي، بيش از 32 هزار ثانيه، براي يافتن جواب دقيق مساله احتياج دارد. البته قضاوت و مقايسه كلي، در خصوص رفتار الگوريتم هاي يادشده به اجراهاي بيشتر بر روي شبكه هاي گوناگون نيازمند است.

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 that 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.