بهینه سازی مسیر تردد سرویسهای حمل و نقل یک شرکت، با استفاده از خوشه بندی و الگوریتم ژنتیک

نوع مقاله : علمی - پژوهشی

چکیده

یکی از راهکارهای استفاده پایدار از منابع، سیستم حمل و نقل ادارات است. امروزه، سامانه های حمل و نقل به صورت دلخواه و با نظر افراد تعیین می شوند، در حالی که این انتخاب بهینه نیست. بنابراین باید روشی اتخاذ شود که بتوان این مسئله را به صورت کارآمد مدل کرد. از سوی دیگر در صورتی که تعداد کارمندان در یک شرکت زیاد باشد، فضای جستجوی مسئله افزایش پیدا کرده و استفاده از الگوریتمهای ریاضی مشکل است. به همین منظور در این مقاله سعی شده است با استفاده از یک روش خوشه بندی ساده، فضای جستجوی مسئله را کاهش داده و سپس با استفاده از الگوریتم جمعیت مبنای ژنتیک، مسیر بهینه در هر خوشه برای کارمندان جستجو شود. اما یکی از مشکلات الگوریتم ژنتیک، بکارگیری عملگرهای مناسب با شرایط مسئله است. در این مقاله سعی شده است که با بکارگیری عملگرهای تقاطع و جهش مناسب و ابتکاری، شرایط حل مسئله بهبود داده شود و زمان رسیدن به جواب بهینه کاهش داده شود. این الگوریتم در یک قسمت از شهر تهران که اطلاعات آن مربوط به سال 1387 است، بکار گرفته شده است. با استفاده از این الگوریتم توسعه داده شده، مسئله ضمن جوابگو بودن، در تعداد تکرار کمتری نسبت به روش ژنتیک با عملگرهای ساده، به جواب بهینه همگرا شده و دارای آزمون تکرار پذیری بالاتری نیز هست. در نهایت پیشنهاداتی برای نزدیک کردن شرایط مسئله به شرایط واقعی و استفاده از الگوریتمهای جمعیت مبنای دیگر ارایه شده است.

کلیدواژه‌ها


عنوان مقاله [English]

Optimization of Office Transportation System by using Clustering and Genetic Algorithms

چکیده [English]

One of the major solutions for sustainable use of resources is official transportation system. Nowadays, the current transportation systems are determined optionally by people opinions, whereas this choice is not optimum. Therefore, a method must be taken due to a model to solve this problem efficiently. On the other hand, if the number of employees is considerable in a company, the problem area will be increased and using the mathematic algorithms will be difficult. Therefore in this paper the authors tried to reduce the problem’s search area by simple clustering method and then searched optimum path for employees in each cluster by population-based Genetic Algorithm. But one of problems about Genetic Algorithm using operations are appropriate for problematic conditions. In this paper the authors tried to develop the problem- solving conditions by using the appropriate cross over and mutation operations and then decrease spend time for finding the optimum solution. This algorithm is used in a part of Tehran city, and the information refers to 2006. By using the developed algorithm, on one hand, problem is responsive and the on the other hand problem is converged to optimum answer with lower repetition number in comparison with genetic method with simple operations and it has high repeatable test. At the end, the authors propose some suggestions to close the problem’s condition to real world condition and using some other population-based algorithms.

کلیدواژه‌ها [English]

  • optimization
  • GIS
  • vehicle routing problem
  • Genetic algorithm
  • Clustering