مسأله مسیریابی وسایل نقلیه باز با در نظر گرفتن رضایت ‌رانندگان: الگوریتم تکاملی چند هدفه بر مبنای تجزیه

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

نویسندگان

1 دانشگاه آزاد اسلامی، واحد علوم و تحقیقات تهران

2 استاد دانشکده مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران

3 دانشگاه تهران

چکیده

در این مقاله، یک مدل مسیر‌یابی وسایل نقلیه باز جدید با دو هدف متمرکز بر حداکثر کردن رضایت توزیع کنندگان و حداقل کردن اندازه ناوگان به طور همزمان ارایه می‌شود. با توجه به دنیای واقعی، با توجه به خصوصی بودن توزیع‌کنندگان، درآمد توزیع‌کنندگان به دلیل آن که تابعی از تعداد کالاهای حمل شده می‌باشد با ظرفیت وسیله نقلیه ا ارتباط مستقیم دارد و از طرف دیگر کمینه کردن تعداد ناوگان با استفاده از وسایط نقلیه با ظرفیت های متفاوت باعث هزینه‌های غیر‌مستقیم می‌گردد. علاوه بر آن با توجه به خصوصی بودن ناوگان با توجه به دنیای واقعی وسایط نقلیه پس از سرویس‌رسانی به دپو باز نمی گردند. به دلیل کاربرد فراوان این مدل در توزیع محصولات توسط بخش خصوصی، مسیریابی وسایط نقلیه در حالت باز در این مقاله بررسی شده است. مسأله مسیریابی وسایل نقلیه مورد بررسی از نوع مسایل NP-hard است، از همین رو به منظور حل این نوع مدل از روش فوق ابتکاری تکاملی چند هدفه بر مبنای تجزیهMOEA/D) )‌ استفاده و نتایج حاصل با جواب‌های حاصل از الگوریتم بهینه‌سازی انبوه ذرات چند هدفه (MOPSO) مقایسه و مورد تجزیه تحلیل قرار گرفت. به طور میانگین از نظر زمانی الگوریتم (MOPSO)‌ تقریبا 10 درصد کند تر از الگوریتم (MOPSO) عمل می‌کند علاوه بر آن کیفیت جواب‌های الگوریتم MOEA/D) )‌ در میانگین تعداد ناوگان حمل و نقل حدود 16% بهتر از الگوریتم (MOPSO)‌ است که نشان دهنده عملکرد مناسب الگوریتم پیشنهادی است.

کلیدواژه‌ها

موضوعات


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

An open vehicle routing problem with drivers’ satisfaction solved by a multi-objective evolutionary algorithm based on decomposition

نویسندگان [English]

  • Alireza Salamatbakhsh 1
  • Reza Tavakkoli-Moghaddam 2
  • Narges Norouzi 3
1 Islamic Azad University, Science and Research Branch
2 Professor, School of Industrial Engineering, College of Engineering, University of Tehran
3 University of Tehran
چکیده [English]

In this paper, a new mathematical model is presented for an open vehicle routing problem (OVRP) that maximizes drivers’ satisfaction and minimizes a number of vehicles simultaneously. One of the new problems related to the VRP area is the OVRP that is a new variant of the VRP. In the real world, because of decreasing the related cost, the vehicles should return to the depot after serving the last customer’s location, as the OVRPs do. It is proven that the classic models in VRPs belong to the category of NP-hard problems; thus due to its complexity using exact methods in large-scale problems, a meta-heuristic method based on multi-objective evolutionary algorithm based on decomposition (MOEA/D) is proposed and the associated results are compared with the results obtained by a multi-objective particle swarm optimization (MOPSO) algorithm. The results show that the proposed MOEA/D outperforms the MOPSO. Finally, the conclusion and further research are provided.

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

  • Open vehicle routing problem
  • Multi-objective evolutionary algorithm
  • Decomposition
  • Particle swarm optimization
دوره 7، شماره 3
فروردین 1395
صفحه 449-462
  • تاریخ دریافت: 09 شهریور 1393
  • تاریخ بازنگری: 18 اسفند 1393
  • تاریخ پذیرش: 19 اسفند 1393