| عنوان فارسی مقاله: | کاربرد الگوریتم ممتیک موازی در مسیریابی وسیله نقلیه با پنجره زمانی |
| عنوان انگلیسی مقاله: | A parallel memetic algorithm for the vehicle routing problem with time windows |
| دانلود مقاله انگلیسی: | برای دانلود رایگان مقاله انگلیسی با فرمت pdf اینجا کلیک نمائید |
| سال انتشار | 2013 |
| تعداد صفحات مقاله انگلیسی | 8 صفحه با فرمت pdf |
| تعداد صفحات ترجمه مقاله | 13 صفحه با فرمت ورد، به صورت تایپ شده و با فونت 14 – B Nazanin |
| رشته های مرتبط | مهندسی کامپیوتر و برق، مهندسی نرم افزار، هوش مصنوعی، مهندسی کنترل و برق مخابرات |
| مجله | کنفرانس بین المللی P2P، موازی، شبکه، محاسبات ابری و اینترنتی (International Conference on P2P, Parallel, Grid, Cloud and Internet Computing) |
| دانشگاه | دانشگاه فناوری سیلسیا کراکوف، لهستان |
| کلمات کلیدی | الگوریتم ممتیک موازی، طرح های همکاری فرایندهای موازی، الگوریتم های جستجوی محلی و ژنتیکی، مسئله مسیریابی وسایل نقلیه با پنجره های زمانی |
| شناسه شاپا یا ISSN | ISSN |
| لینک مقاله در سایت مرجع | لینک این مقاله در سایت IEEE |
| نشریه | IEEE |
فهرست مطالب:
چکیده
1 مقدمه
2 فرمولاسیون مسئله
3 الگوریتم ممتیک موازی
A به حداقل رساندن تعداد مسیر
B همکاری فرایندهای موازی
C به حداقل رساندن فاصله
4 آزمایشات محاسباتی
A تنظیمات
B تحلیل تسریع
C تحلیل کیفیت راه حل ها
5 نتایج
بخشی از ترجمه:
5. نتایج
در این مقاله الگوریتم ممتیک موازی با مسئله مسیریابی وسایل نقلیه NP-hard مطرح شده است. آزمایش روی تست های GH نشان می دهد که الگوریتم به نتایج بسیار خوبی نائل می گردد. به عقیده ما علت این امر طرح جدید همکاری فرایند است که عامل تاثیرگذار اصلی این کار به شمار می رود. در این طرح ، فرایندها یا پروسه ها در حلقه ای آرایش می یابند، اما ترتیب آنها در حلقه در فازهای متوالی همکاری ، تصادفاً تغییر می کند. در طول هر فاز، فرایندها از طریق حلقه انتقال و از بهترین راه حل های یافت شده تا کنون استفاده می کنند. از میان این راه حل ها، اپراتور EAX اجرا می شود که مفید می باشد، زیرا راه حل های فرزند ساخته شده احتمالاً کیفیت بهتری نسبت به پدرانشان دارند. هزینه همکاری نسبتاًاندک است، زیرا در یک فاز، فرایندها تنها به صورت جفتی ارتباط برقرار می کنند که این مسئله برخلاف زمانی است که فرایندها با استفاده از ارتباط همه با همه، در گروههای بزرگتری همکاری می کنند. به خاطر تصادفی سازی، این جفت فرایندهای جمعی از فازی به فاز دیگر تغییر می کنند که این مسئله به متنوع سازی بهتر راه حل های فرزند می انجامد. روشن است، کارآیی اپراتور EAX و الگوی محاسبه ممتیک، نیز به کیفیت بالای راه حل های VRPTW کمک می کنند.
بخشی از مقاله انگلیسی:
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.
| عنوان فارسی مقاله: | حل مسئله مسیریابی وسایل نقلیه با الگوریتم ممتیک و تایم ویندوز |
| عنوان انگلیسی مقاله: | A parallel memetic algorithm for the vehicle routing problem with time windows |
خرید ترجمه فارسی مقاله با فرمت ورد