عنوان مقاله
کاربرد الگوریتم ممتیک موازی در مسئله مسیریابی وسیله نقلیه با پنجره های زمانی
فهرست مطالب
مقدمه
فرمولاسیون مسئله
ممتیک موازی
آزمایش محاسباتی
نتیجه گیری
بخشی از مقاله
تحلیل تسریع
تسریع روند اجرای MPI PMA در تستهای RC2_6_3 و C1_10_4 مورد بررسی قرار گرفت.راه حل های هدف 11/9600 برای RC2_6_3 و 90/40000 برای C1_10_4 تعیین شدند که در هر مورد تست باید به آنها دست یافت ( در a/b ، a تعداد مسیرها و b فاصله کل سفر را نشان می دهد). برای این اهداف، زمان های اجرای PMA ثبت گردید. روی هم رفته 60 آزمایش برروی هر تعداداز پردازنده ها اجرا گردید: N = 1, 8, 16, ..., 88, 96. تسریع به صورت نسبت زمان متوسط اجرای PMA برای N=1 به زمان متوسط اجرای PMA برای N>1 معلوم محاسبه گردید (شکل 4). تسریع بدست آمده برای تست RC2_6_3 کمی بدتر از تست C1_10_4 بود.
کلمات کلیدی:
A parallel memetic algorithm for the vehicle routing problem with time windows Mirosław Błocho∗† ∗Silesian University of Technology Gliwice, Poland † ABB ISDC Krakow, Poland email: Miroslaw.Blocho@pl.abb.com Zbigniew J. Czech∗† ∗Silesian University of Technology Gliwice, Poland †Silesia University Sosnowiec, Poland email: Zbigniew.Czech@polsl.pl Abstract—A parallel memetic algorithm for the NP-hard vehicle routing problem with time windows (VRPTW) is proposed. The algorithm consists of components which are executed as parallel processes. A process runs either a heuristic algorithm or a hybrid of a genetic algorithm and some local refinement procedures. In order to improve the results, processes co-operate periodically using a novel randomized scheme. During each phase of co-operation processes exploit their best solutions found so far. The purpose of the work is to devise the parallel memetic algorithm which determines the VRPTW solutions of the highest possible quality. The experiments on Gehring and Homberger’s (GH) benchmarking tests show that the algorithm achieves very good results. By making use of it the best-known solutions to 171 out of 300 GH tests were improved. Keywords-parallel memetic algorithm, parallel processes cooperation schemes, genetic and local search algorithms, vehicle routing problem with time windows I. INTRODUCTION The vehicle routing problem with time windows (VRPTW) is an important NP-hard optimization problem. It consists in determining the minimum cost routing plan to deliver goods from a single depot to a set of customers. The primary objective is to minimize the number of vehicles used, and the secondary one is to minimize the total distance traveled by the vehicles. A number of approximate algorithms were proposed for the VRPTW. The most effective approximate algorithms to solve this problem rely on the construction heuristics, improvement heuristics and meta-heuristics. The construction heuristics create a feasible solution by inserting customers iteratively into the partial routes according to some criteria. The examples of using them can be found in [18], [21]. The improvement heuristics modify a current solution by executing local search moves to find better neighbor solutions. The most successful applications of these heuristics are described in [5], [17], [20]. The meta-heuristics usually embed construction and improvement heuristics and their examples can be found in [8], [9], [11], [19]. The memetic algorithms are built upon a population-based search approach. They combine an evolutionary algorithm for the global exploration of a solution space with a local search algorithm for the local exploitation of solutions already found [11]. The most efficient applications of the memetic algorithms to the VRPTW have been proposed so far in [1], [10], [14]. In this work a parallel memetic algorithm for the VRPTW is proposed. The algorithm consists of components which are executed in parallel as processes. A process runs either a heuristic algorithm or a hybrid of a genetic algorithm (GA) and some local refinement procedures. The edge assembly crossover (EAX) operator for reproduction of solutions in the GA is applied. In order to improve the final results parallel processes co-operate periodically using a novel randomized scheme. During each phase of co-operation processes exploit their best solutions found so far. The exploitation may involve the use of the EAX operator. The purpose of the work is to devise the parallel memetic algorithm which determines the VRPTW solutions of the highest possible quality. In the experimental part of the work the speedup of the parallel algorithm and quality of achieved solutions on the MPI implementation of the algorithm are investigated. The remainder of this paper is arranged as follows. Section II formulates the VRPTW problem. In section III the parallel memetic algorithm is presented. Section IV contains the discussion of the computational experiments. Section V concludes the paper.
