عنوان

یک راهکار چندعاملی مبتنی بر نظریه بازی برای مسئله مسیریابی وسیله نقلیه با ظرفیت محدود,‮‭Game Theoretic Multiagent approach for Capacitated Vehicle Routing Problem‬ A

Number

‭۲۰۳۱۷پ‬

.Language of Text, Soundtrack etc

per

Title Proper

یک راهکار چندعاملی مبتنی بر نظریه بازی برای مسئله مسیریابی وسیله نقلیه با ظرفیت محدود

Parallel Title Proper

‮‭Game Theoretic Multiagent approach for Capacitated Vehicle Routing Problem‬ A

First Statement of Responsibility

/میر محمد علیپور

Name of Publisher, Distributor, etc.

: مهندسی برق و کامپیوتر

Date of Publication, Distribution, etc.

، ‮‭۱۳۹۷‬

Name of Manufacturer

، راشدی

Specific Material Designation and Extent of Item

‮‭۱۵۱‬ص‬

Text of Note

چاپی - الکترونیکی

Dissertation or thesis details and type of degree

دکتری

Discipline of degree

مهندسی کامپیوتر - گرایش هوش مصنوعی

Date of degree

‮‭۱۳۹۷/۰۶/۱۴‬

Body granting the degree

تبریز

Text of Note

در این پژوهش، به مسئله مسیریابی وسیله نقلیه با ظرفیت محدود پرداخته می‌شود .مسئله مسیریابی وسیله نقلیه با ظرفیت محدود یکی از رایج‌ترین مسائل بهینه‌سازی ترکیبی است که به‌دلیل اهمیت کاربردی و پیچیدگی حل آن از محبوبیت فراوانی برخوردار است .اغلب راهکارهای ارائه شده برای حل این مسئله، خاص منظوره، غیر منعطف و متمرکز هستند .اگرچه در سال‌های اخیر، تحقیقات اندکی در مورد حل این مسئله به‌صورت توزیع‌شده انجام گرفته است ولی راهکارهای ارائه شده از طراحی توزیع‌شده واقعی و خود-سازمانده برخوردار نبوده و هنوز در کارآیی و استواری با محدودیت برخوردار هستند .همچنین، حجم بالای محاسبات و هزینه زمانی بالا از عمده ایرادهای آن‌ها می‌باشند .برای حل چالش‌های موجود، راهکاری توزیع‌شده برای حل مسئله مسیریابی وسیله نقلیه با ظرفیت محدود بر اساس ترکیب تکنیک‌هایی از نظریه بازی و سیستم‌های چندعاملی ارائه شده است .روش پیشنهادی شامل دو مرحله است ‮‭(۱)‬ :خوشه‌بندی و ‮‭(۲)‬ بازی راهبردی بهینه‌سازی خوشه‌ها .در فاز اول، راهکار توزیع‌شده خوشه‌بندی مبتنی بر نظریه بازی معرفی خواهیم نمود که در آن هر مشتری با هدف انتخاب تعدادی از مشتریان به‌عنوان سرخوشه و ایجاد خوشه‌بندی اولیه به بازی محلی خوشه‌بندی با مشتریان همسایه خود می‌پردازد .برای این منظور هر مشتری، جهت اعلان خود به‌عنوان سرخوشه، احتمال تعادل نشی را براساس تعداد مشتریان همسایه خود محاسبه می‌نماید .هر خوشه شامل یک سرخوشه و تعدادی مشتری عضو است .در فاز دوم، بازی راهبردی بهینه‌سازی خوشه‌ها ارائه می‌شود که در آن وسایط نقلیه با هدف کمینه‌سازی تابع هدف مسئله و با در نظر گرفتن محدودیت‌های آن، به ایجاد خوشه‌هایی با ساختار جدید توسط جابه‌جایی مشتریان بین یکدیگر، به بازی می‌پردازند .در ادامه ثابت خواهیم نمود که بازی فوق نوعی بازی پتانسیل کامل است که به تعادل نش می‌رسد .کارآیی راهکار ارائه شده بر روی ‮‭۱۳۸‬ نمونه مسئله مختلف از ‮‭۱۰‬ مجموعه تابع آزمون استاندارد ارزیابی شده و با نتایج تعدادی از الگوریتم‌های مطرح در این زمینه براساس زمان اجرا و کیفیت نتایج مقایسه می‌شود .نتایج به‌دست آمده از آزمایش‌ها نشان می‌دهد که راهکار ارائه شده توانایی رقابت و حتی پیشی گرفتن از الگوریتم‌های بسیار پیچیده برای انواع نمونه مسئله را داشته و سرعت اجرای بالا یکی از مزایای آن است .از طرفی، مسیریابی مشتریان عضو هر خوشه، در واقع همان مسئله فروشنده دوره‌گرد است که با وجود سادگی ظاهری آن، اما یکی از مسائل مهم بهینه‌سازی ترکیبی است که مطالعات گسترده‌ای بر روی آن انجام گرفته است .در این پژوهش برای حل مسئله فروشنده دوره‌گرد، الگوریتم جدیدی براساس یادگیری تقویتی چندعاملی ارائه خواهیم نمود که در آن، هر عامل یک موجودیت خود مختار با حافظه محلی مستقل بوده و از یادگیری تقویتی برای بهبود رفتار خود استفاده می‌نماید .سپس الگوریتم جستجوی محلی جدیدی ارائه خواهیم نمود که در آن با استفاده از جابه‌جایی نظام‌مند ترتیب گره‌ها در نتایج) تورهای (به‌دست آمده توسط راهکار چندعاملی، به بهبود کیفیت نتایج می‌پردازد .در نهایت راهکار ترکیبی مبتنی بر الگوریتم ژنتیک توسعه خواهیم داد که در نقش راهکار اکتشافی بهبود ثانویه عمل نموده و تعدادی از نتایج با کیفیت به‌دست آمده از مراحل قبل را به‌عنوان جمعیت اولیه مورد نیاز دریافت کرده و با به‌کارگیری نوعی عملگر ترکیب نوآورانه با نام ترکیب چند نقطه‌ای هوشمند، به بهبود بیشتر کیفیت آن‌ها می‌پردازد .برای ارزیابی مستقل راهکار ترکیبی ارائه شده برای حل مسئله فروشنده دوره‌گرد، از ‮‭۳۴‬ نمونه مسئله استاندارد از ‮‭TSPLIB‬ استفاده نموده و نتایج عددی به‌دست آمده نشان دهنده توانایی راهکار ارائه شده جهت دست‌یابی به نتایج بهینه و یا نزدیک به بهینه برای بسیاری از نمونه مسائل بوده و قابلیت رقابت آن با الگوریتم‌های مطرح در این زمینه براساس کیفیت نتایج و زمان محاسباتی را به اثبات می‌رساند

Text of Note

In this research, the Capacitated Vehicle Routing Problem was discussed. The Vehicle Routing Problem is a class of well-known combinatorial optimization problems. The great interest in the VRP is due to its practical importance, as well as the difficulty in solving it. Most of the approaches that have been developed to solve this problem are high specialized and inflexible and tend to solve the problem in a centralized way. There has been very little research done into solving this problem in a distributed manner; however, the proposed approaches do not have a real, distributed and self-organizing design, and are still limited in efficiency and robustness. Also, the high volume of computation and high time complexity are the major drawbacks of theirs. To solve these issues, a distributed approach for solving Capacitated Vehicle Routing Problem was proposed based on Multiagent Systems and using the game theory. Proposed approach includes the two phases: (1) clusters construction and (2) clusters optimization. In the first phase, we will introduce a Distributed Game Theoretic Clustering Algorithm, in which each customer plays a local game with its adjacent customers with the aim of selecting a number of customers as a clusters head and creating a primary clustering. For this reason, each customer agent calculates a Nash Equilibrium based on the number of adjacent customers in order to declare itself as a cluster head. Each cluster consists of a cluster head and several member customers. In the second phase, we present a Strategic Clusters Optimization Game for clusters optimization phase, which is played by vehicle for making new clusters structure by movement of some customers between clusters, when the aim is minimizing the CVRP target function while meeting the problem restrictions. We prove the proposed strategic game is an exact potential game and stops at a pure Nash equilibrium. The performance of the proposed approach is evaluated on 138 instances from 10 standard benchmark sets and compared with some state-of-the-art methods in terms of execution time and quality of solutions. Our experiments illustrated that proposed method is able to compete or even outperform much more complex algorithms for a variety of instances and lower running times are one of its advantages. On the other hand, routing the customers of each cluster is in fact the same as the Travelling Salesman Problem. It looks simple, however it is an important and extensively studied problem in the field of combinatorial problem. In this research, we will propose a new algorithm based on Multiagent Reinforcement Learning for Travelling Salesman Problem. Where in, each agent is an autonomous entity with independent local memory and improves its local behavior using reinforcement learning. Then, we will develop a novel Local Search heuristic, to improve the initial tours, which are taken from multiagent reinforcement learning algorithm, by locally manipulating the order of nodes in the initial tours. Finally, we develop a hybrid genetic algorithm, which acts as a secondary improvement heuristic and takes a number of high quality results from the previous steps as the initial population and improves their quality further, by employing a novel crossover operator, called Smart Multi-point crossover. To independently assess the proposed hybrid approach to solve the Travelling Salesman Problem, 34 standard instances from TSPLIB were used. Our experimental results indicate that proposed approach has a good performance with respect to the quality of the solution and the speed of computation and found optimum solution of many datasets and near optimum of the others and enable to compete with some state-of-the-art methods, in terms of solution quality and CPU time

Parallel Title

‮‭Game Theoretic Multiagent approach for Capacitated Vehicle Routing Problem‬ A

علیپور، میرمحمد

Alipour, Mir Mohammad

رضوی، سیدناصر، استاد راهنما

فیضی درخشی، محمدرضا، استاد راهنما

بالافر، محمدعلی، استاد مشاور

Public note

سیاه و سفید

نمایه‌سازی قبلی