نوع فایل: word
قابل ویرایش 60 صفحه
چکیده:
مسأله موقعیت یابی تسهیلات (FLP) نیازمند تعیین موقعیت تسهیلات به منظور بهینه سازی یک یا چند معیار مشخص می باشد. این مسأله در عمل و در مواردی که تسهیلات ارائه دهنده خدمات می باشند مانند موقعیت یابی واحدهای صنعتی، ایستگاههای اتوبوس، ایستگاه های آتش نشانی و ... به وفور اتفاق می افتد. ما به طور خاص به مسأله موقعیت یابی پیوسته خواهیم پرداخت . که در آن تسهیلات باید در یک صفحه اقلیدسی قرار بگیرند . ما برای این منظور از یک رویکرد نوین مبتنی بر سیستمهای چندعاملی استفاده می کنیم. مدل پیشنهادی بر اساس تعدادی عامل است که در یک محیط مشترک قرار دارند و از طریق تعامل با یکدیگر سعی دارند که به یک هدف بهینه سازی سراسری دست یابند . تعامل میان عامل ها و محیط آنها که مبتنی بر رویکرد حوزه های پتانسیل مصنوعی می باشد اجازه می دهد که موقعیت عامل ها به طور محلی بهینه گردد. بهینه سازی کل سیستم نتیجه یک فرآیند شامل خودسازماندهی عاملها می باشد. سپس نشان می دهیم که چگونه می توان مدل پیشنهادی را برای در برگرفتن نسخه چندسطحی از مسأله موقعیت یابی تعمیم داد. درنهایت به ارزیابی مدل خواهیم پرداخت . این ارزیابی ها هر دو نسخه ارائه شده از مسأله موقعیت یابی را در برمی گیرند.
مقدمه:
مسأله موقعیت یابی تسهیلات در طی چند دهه اخیر شاهد یک رشد انفجاری بوده است. این مسأله به قدری فراگیر است که مطالعات و تحقیقات زیادی در خصوص آن انجام شده اند که شروع آنها به قرن هفدهم بر می گردد . همانطور که Pruzan و Krarupنشان داده اند چنین چیزی هرگز تعجب آور نیست زیرا سیاست موقعیت یابی یکی از سودآورترین زمینه های تحلیل کاربردی سیستمها می باشد . این امر به دلیل اهمیت تصمیمات مربوط به موقعیت تسهیلات می باشد که در تمام سطوح سازمانهای انسانی وجود دارند . بنابراین چنین تصمیم هایی راهبردی هستند زیرا دارای تأثیرات اقتصادی می باشند. در اینجا از واژه تسهیلات به معنای عام آن استفاده شده است و به موجودیت هایی مانند واحدهای صنعتی، ایستگاههای اتوبوس، مدارس، بیمارستانها، ایستگاههای آتش نشانی و ... اشاره دارد . مسأله کلی، قراردادن تسهیلات در مکانهایی به منظور بهینه سازی چندین هدف مانند فاصله، زمان یا هزینه سفر و برآورده سازی نیازها می باشد . هرچند در اغلب موارد حل مسأله موقعیت یابی به منظور یافتن راه حل بهینه به شدت مشکل است. حتی ساده ترین مدلها نیز در مورد نمونه مسأله های بزرگ از نظر محاسباتی غیرقابل ردیابی هستند. تا کنون برای این نوع از مسائل روشهای هیوریستیک بسیار و چندین الگوریتم دقیق پیشنهاد شده است. اما مشکل اصلی این رویکردها این است که به سادگی قابل انطباق با محیط های پویا که در آنها محدودیت ها و داده ها در طول زمان تغییر می کند نیستند . این یک محدودیت جدی است زیرا مسائل واقعی متعددی وجود دارند که پارامترهایشان در طول زمان تغییر می کند. از جمله این مسائل می توان به مسأله تعیین موقعیت آمبولانس اشاره نمود . دربرخورد با این انعطاف ناپذیری ما از یک رویکرد چندعاملی استفاده می کنیم که برای سیستمهای باز و تغییرات برخط بسیار مناسب می باشد . در واقع مهمترین کاربرد سیستم های چندعاملی در مورد سیستم های باز می باشد. می توان از طریق آزمایشات مختلف نشان داد که این رویکرد مبتنی بر سیستم های چندعاملی قادر به مواجه با محیطهای پویا می باشد که در آنها پارامترهای محیط یا محدودیت ها با گذشت زمان تغییر می کنند . جنبه های پویای محیط مرتبط با تغییراتی است که ممکن است بر روی داده های محیط همانند تعداد تقاضاها و یا تعداد عامل های ارائه دهنده تسهیلات تأثیر بگذارد.
ما در این مطالعه یک رویکرد چندعاملی برای تعیین موقعیت مناسب تسهیلات پیشنهاد نموده ایم که مبتنی بر خود سازماندهی تعدادی عامل واکنشی از طریق تعاملات انجام شده با محیط می باشد . استفاده از رویکرد چندعاملی چندین مزیت دارد. اول این که سیستم های چندعاملی برای مسائل توزیع شده بسیار مناسب هستند. در این سیستم ها تعدادی موجودیت برای رسیدن به اهداف جمعی و فردی با یکدیگر همکاری می کنند . دوم این که حتی اگر سیستمهای چندعاملی یافتن راه حل بهینه را به طور خودکار تضمین نکنند ولی می توانند راه حلهای قابل قبولی را بدون صرف هزینه محاسباتی بسیار زیاد پیدا کنند ، در کنار این که چنین سیستمهایی دارای انعطاف پذیری و توانمندی بالایی می باشند . در رویکرد ارائه شده رفتار عاملها دارای یک منبع الهام فیزیکی می باشد یعنی به همان روشی است که ذرات در جهان اطراف ما حرکت می کنند و بر اساس اطلاعات محیطی که با حوزه های پتانسیل بیان می شود به خودسازماندهی سراسری می رسند . به طور خاص تردر رویکرد پیشنهادی اطلاعات محیطی به شکل ترکیبی از نیروهای جذب کننده و دفع کننده بیان می شوند . ایده کلیدی این است که رفتار عامل های واکنشی در سطح ریز (میکروسکوپی) منجر به ظهور راه حل ها در سطح درشت (ماکروسکوپی) می شود. ما قصد داریم که انعطاف پذیری و توانمندی رویکردمان را با حل مثال هایی از مسأله تعیین موقعیت نشان دهیم . این مثالها شامل تعیین موقعیت ایستگاه های اتوبوس در خطوط موجود و مسأله تعیین موقعیت چندسطحی تسهیلات می باشند.
فهرست مطالب:
فصل اول : مساله موقعیت یابی تسهیلات
مقدمه
1-1) مرور
2-1) کارهای مرتبط
فصل دوم : راه حل ها
1-2) بیان مساله موقعیت یابی پیوسته
2-2) یک رویکرد خودسازمانده برای مساله تعیین موقعیت پیوسته
1-2-2) رویکرد واکنشی و تکنیک حوزه های پتانسیل مصنوعی
2-2-2( هیوریستیک های مبتنی بر عامل های واکنشی
3-2) یک رویکرد چند عاملی خودسازمانده
1-3-2) برآورده سازی محلی تقاضا
2-3-2 ) هماهنگی محلی
3-3-2) حل مساله به صورت دسته جمعی
فصل سوم : آزمایشات
1-3) نتایج بدست آمده از آزمایشات متوالی
2-3) نتایج بدست آمده از آزمایش دوم
3-3) کاربرد برای مساله مکان یابی ایستگاه اتوبوس
3-4) نتایج بدست آمده از آزمایشات پروژه خودمان
فصل چهارم : تطبیق با مسائل تعیین موقعیت چند سطحی
1-4) مساله تعیین موقعیت چند سطحی
2-4) کاربرد در یک مساله چندسطحی توزیع شده
فصل پنجم : بحث
فصل ششم : نتیجه گیری
فصل هفتم : منابع ومآخذ
شکل1-2: نیروهای جذب کننده باعث حرکت عامل به سمت مرکز وزن دار تقاضاها می شوند.
شکل2-2: نیروی دفع کننده میان عامل های A وB باعث دور شدن آنه از یکدیگر می شوند.
شکل3-3:The evolution of facilities positioning for the case study with 400 agents 17
شکل4-3: The fitness evolution for the case study with 400 agents 19
شکل5-3: The evolution of facilities positioning for the Belfort Bus_Network 20
شکل6-3: The fitness convergence ; a test with 143 Bus_Stop21
شکل7-4: 3_level problem
منابع و مأخذ:
[1] Z. Drezner, K. Klamroth, A. Schobel and G.O. Wesolowsky, The Weber Problem,
Facility Location: Application and theory, Edited by Z. Drezner and H.W. Hamacher,
[2] J. Krarup and P.M. Pruzan, The Simple Plant Location Problem: Survey and
Synthesis, European Journal of Operations Research, vol. 12, 1983, 36-81.
[3] J. Brimberg, P. Hansen, N. Mladenovic and E.D. Taillard, Improvement and
Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem,
Operations Research, vol. 48, 2000, 444-460.
[4] M. Wooldridge, N. R. Jennings, and D. Kinny, A Methodology for Agent- Oriented
Analysis and Design, Proceedings of the Third Annual Conference on Autonomous
Agents, Seattle, USA, 1999.
[5] H.V.D. Parunak and S.A. Brueckner, Entropy and Self-Organization in Multi-Agent
Systems, 5th International Conference on Autonomous Agents, 2001, 124-130.
[6] A.I. Barros, Discrete and Fractional Programming Techniques for Location Models,
Kluwer Academic Pub, 1998. 14
[7] D. Tcha and B. Lee, A Branch-and-Bound Algorithm for the Multi-Level
Uncapacitated Location Problem, European Journal of Operations Research, vol. 18,
1984, 35-43.
[8] J. Brimberg and N. Mladenovic, Solving the Continuous Location-Allocation
Problem with Tabu Search, Studies in Locational Anal, vol. 8, 1996, 23-32.
[9] J.H. Jaramillo, J. Bhadury and R. Batta, On the use of Genetic Algorithms to Solve
Location Problems, Computers & Operations Research, vol. 29, 2002, 761-779.
[10] H.D. Pour and M. Mostafa, Solving the facility and layout and location problem by
ant-colony optimization-meta heuristic, International Journal of Production Research,
- 44, no. 23, 2006, 5187-5196.
[11] R.M. de A. Silva and G.L. Ramalho, Ant system for the set covering problem, IEEE
International Conference on Systems, Man, and Cybernetics, 2001.
[12] K. Kumweang and R. Kawtummachai, Solving a SSCFLP in a Supply Chain with
ACO, Suranaree Journal of Science and Technology, vol. 12, 2005, 28-38.
[13] S. Bandini and S. Manzoni and C. Simone, Dealing with space in multi–agent
systems: a model for situated MAS, AAMAS, 2002, 1183-1190.
[14] F. Plastria, On the Choice of Aggregation Points for Continuous p-median Problems:
A Case for the Gravity Center, TOP, vol. 9, 2001, 217-242.
[15] M. Minsky, The Society of Mind, New York: Simon and Schuster, 1986.
[16] R.C. Arkin, Behavior-Based Robotics, MIT Press, 1998.
[17] O. Simonin and J. Ferber, Modeling Self Satisfaction and Altruism to handle Action
Selection and Reactive Cooperation, SAB, 2000, 314-323.
[18] K. Lewin, Principles of Topological Psychology, McGraw-Hill, 1936.
[19] K. Zeghal, J. Ferber, CRAASH: A Coordinated Collision Avoidance System. In
European Simulation Conference, Lyon, France, 1993.
[20] J. Ferber and A. Drogoul, Using Reactive Multi-Agent Systems in Simulation and
Problem Solving, Distributed Artificial Intelligence: Theory and Praxis, Kluwer
Academic Publishers, 1992, 53-80.
[21] A. Drogoul and C. Dubreuil, A Distributed Approach To N-Puzzle Solving,
proceedings of the 12th International Workshop on Distributed Artificial Intelligence,
[22] K. Gh´edira and G. Verfaillie, A Multi-Agent Model for the Resource Allocation
Problem: a Reactive Approach, ECAI, 1992, 252-254. 15
[23] H.V.D. Parunak, Go to the Ant: Engineering Principles from Natural Multi-Agent
Systems, Annals of Operations Research, vol. 75, 1997, 69-101.
[24] A. Colorni, M. Dorigo and V. Maniezzo, Distributed Optimization by Ant Colonies,
proceedings of the first European Conference on Artificial Life, 1992, 134-142.
[25] M. Mamei and F. Zambonelli, Field-Based Coordination for Pervasive Multiagent
Systems, Springer Series on Agent Technology, Springer-Verlag New York, Inc., 2005.
[26] D. Weyns, N. Boucke, and T. Holvoet, Gradient Field-Based Task Assignment in an
AGV Transportation System, AAMAS, Hakodate, Japan, May, 2006.
[27] F. Gechter, V. Chevrier and F. Charpillet, A Reactive Agent-Based Problem-Solving
Model: Application to Localization and Tracking, TAAS, vol. 1, no. 2, 2006, 189-222.
[28] A. Likas, N.A. Vlassis and J.J. Verbeek, The global k-means Clustering Algorithm,
Pattern Recognition, vol. 36, no. 2, 2003, 451-461.
[29] S. Eilon, C.D.T. Watson-Gandy and N. Christofides, Distributed Management,
Hafner, New York, 1971.
[30] I. Bongartz, P.H. Calamai and A.R. Conn, A projection Method for lp Norm
Location-Allocation Problems, Mathematical Programming, vol. 66, 1994, 283-312.
[31] J. Dias, M.E. Captivo and J. Climaco, Dynamic Multi-Level Capacitated and
Uncapacitated Location Problems: an Approach Using Primal-Dual Heuristics, INESCCoimbra, 2004.
[32] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory
of NP-Completeness, W.H Freeman and Co, 1979.
[33] S. Moujahed, N. Gaud and D. Meignan, A Self-Organizing and Holonic Model for
Optimization in Multi-Level Location Problems, the 5th IEEE International Conference
on Industrial Informatics (INDIN’07), Austria, July, 2007.
پروژه بهینه سازی مسائل موقعیت یابی توسط رویکرد چندعاملی خودسازمانده. doc