دانلود مقاله ISI انگلیسی شماره 7644 + ترجمه فارسی
عنوان فارسی مقاله

الگوریتم ترکیبی بهینه‌سازی کلونی مورچه برای مسئله مسیریابی دوسطحی وسایل نقلیه

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی
7644 2011 5 صفحه PDF 9 صفحه WORD
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Hybrid Ant Colony Optimization Algorithm for Two Echelon Vehicle Routing Problem
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Procedia Engineering, Volume 15, 2011, Pages 3361–3365

فهرست مطالب ترجمه فارسی
چکیده 
۱- مقدمه 
۲- تعريف مسئله
۳- الگوریتم ترکیبی بهینه‌سازی کلونی مورچه (ACO)
۴- آزمایش و تحلیل
۵- تنظیمات آزمایش
۶-مقایسه با مطالعات دیگر
جدول (1) روش ما را در مقایسه با تحقیقات قبلی نشان می‌دهد [5]
جدول (2) روش ما را در مقایسه با تحقیقات قبلی نشان می‌دهد [3]
۷- جمع بندی
کلمات کلیدی
- بهینه سازی - کلونی مورچه - ترکیبی
ترجمه چکیده
در این مقاله، برای حل مسئله مسیریابی دوسطحی وسایل نقلیه (ترکیب سه الگوریتم ابتکاری یا فراابتکاری) یک الگوریتم کلونی مورچه ابتکاری ترکیبی پیشنهاد و پیاده‌سازی می‌گردد. مسئله ابتدا از طریق استراتژی جداسازی (خوشه مبتنی بر فاصله) به m+1 CVRP تقسیم می‌شود. سپس راه‌حل‌های امکان‌پذیرتر بوسیله بهینه‌سازی کلونی مورچه همراه با تبار همسایگی چندگانه (IACO_MND) ساخته می‌شود. این به عنوان راه‌حل اولیه در روش جستجوی محلی مبتنی بر آستانه برداشت می‌شود. همچنین دو ساختار همسایگی مختلف، یعنی درج مبتنی بر آستانه و مبادله مبتنی بر آستانه به طور متوالی استفاده می‌شوند. نتایج محاسباتی برروی 22 مسئله محک با اندازه‌های مختلف از 20 تا 50 نشان می‌دهد که الگوریتم ترکیبی پیشنهادی می‌تواند بهترین راه‌حل شناخته‌شده را برای برخی از مسائل در زمانی کوتاه پیدا کند. همین نشان می‌دهد که روش پیشنهادی از الگوریتم‌های دیگر در مطالعات گذشته بهتر عمل می‌کند. © 2011 انتشار در الزویر. گزینش یا بازخوانی زیر نظر [CEIS 2011]
ترجمه مقدمه
مسئله مسیریابی وسایل نقلیه (VRP) در سال 1959 توسط دنتزینگ از و رامسر [1] پیشنهاد شد و تاکنون دستاوردهای پژوهشی فراوانی در چند دهه اخیر به ارمغان آورده است. اما تحقیقات در مورد این مسئله اغلب برروی سیستم برنامه‌ریزی تک‌سطحی متمرکز بوده، و تحقیقات در مورد سیستم چندسطحی مانند ME-VRP بسیار اندک بوده است. کراینیک و همکاران [2] سیستم چند‌سطحی را برای نخستین بار برروی نمونه ای از «تدارکات شهری» در سال 2004 اعمال کردند. فلیو و همکاران [3،4] سیستم چند‌سطحی را برای نخستین بار در VRP یکپارچه کردند و مدل ریاضی برای آن ساختند که مسئله مسیریابی چندسطحی وسیله‌نقلیه (ME-VRP) نام گرفت. همانطور که مدل و پیچیدگی تدارکات ترابری افزایش یافت، پژوهشگران بیشتر و بیشتری شروع به مطالعه و بحث در مورد این مسئله کردند. از آنجا که VRP نوعی مسئله سخت بصورت چندجمله‌ای غیرقطعی (NP) به شمار می‌رود، بنابراین مسئله مسیریابی چندسطحی وسیله‌نقلیه ME-VRP NP به‌مراتب پیچیده‌تر از نسخه پایه VRP است. بدین ترتیب، روش حل چنین مسئله‌ای به طور عمده برروی حوزه ابتکاری و فراابتکاری متمرکز می‌شود که می‌تواند راه‌حل بهتری در زمان نسبتاً کوتاه فراهم کند. این روش حل تاکنون نتایج خوبی به دست آورده است. برای مثال، فلیو و همکاران [3،4] از الگوریتم ابتکاری ریاضی‌پایه برای حل تعدادی از نمونه‌های عمومی در مورد 2E-VRP بهره بردند. کراینیک و همکاران [5] یک خوشه‌بندی مبتنی بر الگوریتم ابتکاری پیشنهاد کردند. آنها سپس الگوریتم خود را به‌سادگی بهبود و الگوریتم ابتکاری چندآغازی [6] را پیشنهاد دادند. در این حالت، جستجوی محلی تا زمانی ادامه خواهد یافت که مقدار شیء بهبود نیابد. کرانیک و همکاران [7] رابطه توزیع مشتریان، چیدمان سیستم و هزینه را تحلیل و سپس از لحاظ عملکرد و بهره‌وری با سیستم چند‌سطحی همراه با VRP تک‌سطح سنتی مقایسه کردند. بدین صورت میزان امکان‌پذیری و اثربخشی چند‌سطحی VRP نمایان شد. پربولی و همکاران [8،9] خانواده‌های جدیدی از نابرابری معتبر برای مسئله مسیریابی دوسطحی وسایل نقلیه استخراج کردند تا بطور موثرتری یک راه‌حل امکان‌پذیر بهتر و قوی‌تر بدست بیاورند. بنابراین، در این مقاله یک الگوریتم بهینه‌سازی کلونی مورچه ترکیبی برای 2E-VRP ارائه شده است.
پیش نمایش مقاله
پیش نمایش مقاله الگوریتم ترکیبی بهینه‌سازی کلونی مورچه برای مسئله مسیریابی دوسطحی وسایل نقلیه

چکیده انگلیسی

A hybrid heuristic ant colony algorithm is proposed and applied to solving the two echelon vehicle routing problem, which combines three heuristic or meta-heuristics. The problem is divided into m+1 CVRP by a separation strategy (distance-based cluster). Then better feasible solutions are built by an improve ant colony optimization with multiple neighborhood descent (IACO_MND), which is taken as the initial solution of the threshold-based local search procedure, two different neighborhood structures, i.e., threshold-based insert and threshold-based swap are successively used. Computational results on the 22 benchmark problems with the size ranging from 20 to 50 show that the proposed hybrid algorithm can find the best known solution for some problems in short time, which indicates that the proposed method outperforms other algorithm in literature.

مقدمه انگلیسی

Proposed by Dantzig and Ramser [1] in 1959, VRP has made a lot of research achievement in decades. But the researches about the problem more concentrated in single-level scheduling system, and the researches about the multi-level system, such as ME-VRP, are very small. Crainic et al. [2] apply the multi-level system to the practice first time for a City Logistics instance in 2004. Feliu et al. [3,4] integrated the multi-level system into the VRP first time and build the mathematical model for it, they call it Multi-Echelon Vehicle Routing Problem (ME-VRP). With the model and complexity of logistics increase, more and more researchers began to study and discuss the issue. Since VRP is a NP hard problem, so ME-VRP is NP hard, and more complex than the basic VRP. Therefore, the method for solving such problem mainly focused in heuristic and meta-heuristic which can fine the better solution in a relatively short time. And it has achieved some results. Such as Feliu et al. [3,4] use Base-Math heuristic algorithm for solving a number of public instance about 2E-VRP. Crainic et al. [5] proposed aClustering-based Heuristic algorithm. Then they simple improved their algorithm, and proposed Multi-Start Heuristic Algorithm [6], it asked that the local search will continue until the object value is not be improved. Crainic et al. [7] analyzed the relationship of the distribution of customers, the system layout and the cost, and compared the multi-level system with the traditional single-level VRP in performance and efficiency, which can shows the feasibility and effectiveness of the Multi-Echelon VRP. Perboli et al. [8,9] derived new families of valid inequalities for the two-echelon vehicle routing problem, in order to more efficiently obtain better strength feasible solution. Therefore, this paper proposed a hybrid ant colony optimization algorithm for 2E-VRP.

نتیجه گیری انگلیسی

It is a hot research field that combination of the advantages of different heuristic and meta-heuristic to design more effective hybrid heuristic algorithm for combinatorial optimization problems. Combination of greedy algorithm, ant colony optimization and local search algorithm, this paperproposed a hybrid ant colony optimization algorithm to solve the 2E-VRP. Make use of the rapid of the traditional heuristic, the search diversity of ant colony optimization and the strong local search ability of local search to improve the quality of the solution and speed up the convergence of the algorithm. In the experiment, we run our method in 22 different scale benchmark data. The result illustrates that our algorithm can obtain optimal or better feasible solution in a short time. Furthermore, we compared our algorithm with other 2 literatures, and our method increased 1.59%, 5.56% than they are. It shows that our algorithm is superior to existing algorithm.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.