نشریه تخصصی مهندسی صنایع، دوره 47، شماره 1، فروردین ماه 1392، از صفحه 105 تا 112 105 مساله مسیریابی وسائط نقلیه با هدف کاهش سوخت مصرفی و تعداد وسائط نقلیه توسط الگوریتم بهبود یافته بهینه سازي انبوه ذرات

نرگس نوروزي*1، جعفر رزمی2 و محسن صادق عمل نیک3
1دانشجوي دکتري- دانشکده مهندسی صنایع -پردیس دانشکده هاي فنی-دانشگاه تهران
2 استاد دانشکده مهندسی صنایع -پردیس دانشکده هاي فنی-دانشگاه تهران
3دانشیار دانشکده مهندسی صنایع -پردیس دانشکده هاي فنی-دانشگاه تهران
(تاریخ دریافت 10/4/91، تاریخ دریافت روایت اصلاح شده 7/5/91، تاریخ تصویب 12/12/91 )

چکیده
این مقاله به ارائه مدل جدیدي از مساله مسیریابی وسائط نقلیه به منظور کاهش سوخت مصرفی و اندازه ناوگان می پردازد. مدیران شرکت هاي توزیع و صاحبان وسائط نقلیه به دو دلیل مهم علاقه مند به حداقل رساندن سوخت مصرفی در توزیع کالاها می باشند؛ 1) کاهش در سوخت مصرفی به کاهش هزینه هاي سرویس دهی و در نتیجه رضایت مشتریان می انجامد و 2) کاهش در مصرف سوخت به کاهش اثرات مخرب گازهاي گلخانه اي و آلودگی هوا منجر می شود. همچنین استفاده از حداقل ناوگان براي سرویس دهی به مشتریان به منظور کاهش هزینه هاي ثابت و دیگر هزینه هاي مرتبط با وسائط نقلیه در این مقاله مدنظر قرار گرفته است. به دلیل NP-Hard بودن مساله مورد بررسی و به منظور حل مسایل در ابعاد بزرگ از روش فراابتکاري بهبود یافته ي بهینه سازي انبوه ذرات (IPSO) استفاده می شود. سپس براي نشان دادن کارایی الگوریتم طراحی شده جواب هاي به دست آمده با نرم افزار لینگو مقایسه خواهند شد.

واژه هاي کلیدي: مسیریابی وسائط نقلیه سبز، نرخ سوخت مصرفی، الگوریتم بهبود یافته ي بهینه سازي انبوه ذرات

مقدمه
حمل و نقل، اثرات جبران ناپذیري بر محیط زیست می گذارد؛ مصرف منابع، استفاده از اراضی ،تأثیرات سمی بر اکوسیستم و انسان ها، سر و صدا و انتشار گازهاي گلخانه اي و آلایندهها، فقط نمونه اي از این خطرات هستند. جداي از اثرات منفی ذکر شده، انتشار گازهاي گلخانه اي و کربن دي اکسید، به طور مستقیم با سلامتی افراد جامعه و غیر مستقیم با تخریب لایه اوزون ارتباط دارد. لزوم توجه به این موضوع از آنجا ناشی می شود که گازهاي گلخانه اي متصاعد توسط بخش حمل و نقل، باعث ایجاد بخش قابل توجهی از آلودگی هوا در کشورهاي مختلف جهان هستند. از این رو افزایش نگرانی ها درباره کاهش چنین تأثیرات خطرناکی، ضرورت پیاده سازي یک برنامه مدون در حمل و نقل جاده اي را نشان می دهد که مدل هاي مسیریابی وسائط نقلیه سبز مبتنی بر کاهش سوخت مصرفی و آلودگی هوا، می توانند راهگشا باشند.
Email: [email protected] ،88013102 نویسنده مسئول: تلفن 82081067، فکس *

مسئله مسیریابی وسیله نقلیه، یکی از مفاهیم آشنا در زمینه تحقیق در عملیات است که در سه دهه اخیر تلاشها و پیشرفت هاي زیادي در این زمینه انجام شده است. این مسئله اولین بار توسط دنتزیگ و رامسر [1] فرموله و بر اساس روشهاي ریاضی به حل آن پرداخته شد. مسئله مسیریابی وسیله نقلیه ((VRP به مجموعه اي از مسایل اطلاق می شود که در آن ناوگانی متشکل از چندین وسیله نقلیه از یک یا چند قرارگاه، به ارایه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی می پردازند و این کار را به نحوي انجام می دهند که هزینه هاي انجام این کار به حداقل برسد. وسیله نقلیه با شروع از قرارگاه مرکزي، پس از ارایه
خدمت به مشتریان به قرارگاه باز می گردد. هر وسیله، ظرفیت معینی دارد و همه مسیرهاي مربوطه از مبدأ (قرارگاه مرکزي) شروع و به آن ختم می شوند.
بیشتر تحقیقات انجام گرفته، توجه به اهداف اقتصادي را از راه به حداقل رساندن مسافت طی شده، زمان مورد نیاز یا تعداد وسائط نقلیه مورد نیاز و … سرلوحه کار خود قرار دادهاند و از توجه به اهداف زیست محیطی و کاهش آلایندهها غافل ماندهاند. رزمی و رحمان نیا [2] به طراحی یک شبکه زنجیره تأمین به منظور تحویل کالا به مشتریان توسط برنامه ریزي عدد صحیح مختلط با هدف کاهش هزینه حمل و نقل و افزایش رضایت مشتریان پرداختند.
پالمر [3]، مدلی یکپارچه در مسیریابی و انتشار آلاینده ها براي وسائط نقلیه ارائه کرد و نقش سرعت را در کاهش کربن دي اکسید تولیدشده با سناریوهاي مختلف ترافیکی و پنجره زمانی در نظر گرفت که به صرفه جویی 5% در میزان کربن دي اکسید تولید شده دست یافت. گرچه تأثیر میزان بار حمل شده در مسئله او در نظر گرفته نشده بود.
میدن و همکارانش [4] مسئله VRP با محدودیت پنجره زمانی را که در آن، سرعت به زمان سفر وابسته بود، در نظر گرفتند. همچنین یک الگوریتم ابتکاري براي حل مسئله پیشنهاد کردند و در نتایج خود به صرفه جویی 7% در کربن دي اکسید تولید شده در یک مطالعه موردي در کشور انگلستان دست یافتند. جبلی و همکارانش [5] مسئله اي مشابه کار میدن در نظر گرفتند، با این تفاوت که میزان تولید آلاینده ها بر اساس یک تابع خطی از سرعت وسیله نقلیه تخمین زده می شود و تحلیلی براي یافتن سرعت بهینه با توجه به میزان آلاینده ها ارائه کردند. همچنین از یک الگوریتم جستجوي ممنوع (TS) تکرار شونده براي حل نمونه مسائل استاندارد VRP استفاده کردند.
در همین راستا، تاوارس و همکارانش [6] به بررسی تأثیر شیب جاده و بار وسیله نقلیه بر میزان سوخت مصرفی در مسئله جمع آوري ضایعات و فقط براي سه سطح بار پرداختند. بار نیمه، هنگام جمع آوري ضایعات، بار کامل، در راه رفتن به محل تخلیه و بدون بار، در مسیر بازگشت. ارتباط میان نرخ مصرف سوخت و میزان بار در تحقیق آن ها مورد بررسی قرار نگرفت. ولی بدیهی است هنگامی که وسیله نقلیه به گره اي سرویس دهی می کند، میزان بار آن کاهش می یابد که منجر به کاهش نرخ سوخت مصرفی در طول مسیر می شود. بنابراین در نظر گرفتن نرخ سوخت وابسته به بار، در محاسبه دقیق تر هزینه ها ضروري است. همچنین سوزوکی [7] علاوه بر در نظر گرفتن تأثیر میزان بار بر مصرف سوخت وسیله نقلیه، به بررسی تأثیر زمان انتظار وسیله نقلیه در شروع سرویس دهی به مشتریان بر سوخت مصرفی پرداخت. با پیشرفت هاي اخیر در حل اینگونه مسایل و با در نظر گرفتن فرضیات و قیود پیچیده تر، روش هاي فراابتکاري همانند روش الگوریتم ژنتیک [8]، بهینه سازي انبوه ذرات [9] و کلونی مورچگان [10] در سا ل هاي اخیر توسعه دادهشده اند .
همان طور که بیان شد، هدف از این مقاله، ارایه مدلی است که با کاهش سوخت مصرفی، علاوه بر فراهم آوردن منافع اقتصادي، باعث کاهش اثرات مخرب گازهاي گلخانه اي، کربن دي اکسید و آلودگی هوا شود و از این طریق، منافع بی شماري را به محیط زیست و سلامتی افراد جامعه بازگرداند. از سوي دیگر، یکی دیگر از اهداف این مقاله آن است که با حداقل کردن اندازه ناوگان، هزینه هاي ثابت و دیگر هزینه هاي مرتبط با وسائط نقلیه، به حداقل برسد. ثابت شده است که مسئله مسیریابی وسائط نقلیه، یک مسئله NP-Hard است [11] و استفاده از روش هاي دقیق در مورد مسایل با ابعاد به نسبت بزرگ، نمی تواند توجیه پذیر باشد؛ به همین دلیل، با افزایش ابعاد مسئله باید از الگوریتم هاي فراابتکاري براي حل مسایل استفاده شود. به همین منظور الگوریتم بهبود یافته بهینه سازي انبوه ذرات (IPSO) براي حل مسایل در ابعاد بزرگ در نمونه مسائل کریستوفیدز و همکاران [12] ارایه شده است. سپس براي نشان دادن کارآیی الگوریتم طراحی شده، جواب هاي به دست آمده با نرم افزار لینگو مقایسه خواهند شد.

2- تعریف مسئله
تحقیقات محققان حاکی از آن است که هزینه ها ي حمل و نقل به عوامل بسیاري وابسته است که می توانند به دو دسته کلی تقسیم بندي شوند. عوامل دسته اول شامل فاصله، بار، سرعت، وضعیت جاده، نرخ مصرف سوخت (در هر واحد فاصله)، قیمت سوخت و… که ارتباط مستقیم با برنامه زمانبندي سفر دارند، است. عوامل دسته دوم، ارتباط غیر مستقیم با زمانبندي سفر دارند و شامل استهلاك وسیله نقلیه، نگهداري و تعمیرات، دستمزد رانندگان، مالیات و… می شوند[13]. همان طور که مشخص است، عوامل دسته اول ارتباط مستقیم با مصرف سوخت و انرژي دارند و بنابراین می توانند به عنوان هزینه متغیر یا هزینه سوخت مصرفی در نظر گرفته شوند. در مجموع اگر دیگر عوامل ذکرشده ثابت نگاه داشته شوند، مصرف سوخت به طور عمده به مسافت طی شده و بار حمل شده وابسته خواهد بود. براي مثال هزینه متغیر یک وسیله نقلیه خالی، کمتر از هزینه وسیله نقلیه با بار پر خواهد بود؛ هنگامی که یک مسیر مشخص را با سرعت یکسان طی می کنند. با وجود گسترش انواع مختلف مسئله هاي VRP، بیشتر آن ها روي کمینه کردن هزینه توسط کاهش مسافت طی شده تمرکز کرده اند و نرخ مصرف سوخت به عنوان عامل تأثیر گذار در اغلب موارد نادیده انگاشته شده است. از این رو می توان به تحقیقات ساهین و همکارانش [14] اشاره کرد که بیانگر آن است که یک کامیون با ظرفیت 20 تن هنگامی که پر از بار است، هزینه سوخت مصرفی آن در طی مسیر 1000 کیلومتر با 60% کل هزینه حمل و نقل آن برابري دارد. بنابراین کاهش سوخت مصرفی توسط بهبود کارآیی عملیاتی ضروري به نظر می رسد. بر اساس جنبه هاي شناسایی شده از مطالعات مروري VRP و نیز جنبه هاي جدید مشاهده شده از مسایل دنیاي واقعی، این مقاله به دنبال طراحی و حل مدلی براي مسیریابی وسائط نقلیه براي کاهش سوخت مصرفی و اندازه ناوگان است که در ادامه بیان خواهد شد.
فرضیات مسئله به صورت ذیل قابل بیان هستند:
هر وسیله نقلیه از پایانه شروع به حرکت می کند و در نهایت باید به پایانه باز گردد.
تقاضاي مشتریان ثابت و قطعی است.
هر مشتري فقط و فقط از یک وسیله نقلیه توزیع کننده، خدمت دریافت می کند و سرویس دهی چندگانه مجاز نیست.
ظرفیت وسایط نقلیه باید به طور دقیق شامل مجموع تقاضاي مشتریانی باشد که وسیله نقلیه باید آن ها را سرویس دهد و در هر بار سرویس دهی، همه تقاضاي مشتریان، ارضا می شود.
مجموع زمان هاي سرویس دهی وسایط نقلیه به مشتریان محدودیت دارند و ثابت است.
مسیرها باید طوري تعیین شوند که میزان هزینه حمل و نقل حداقل شود.

2 -1 مدل ریاضی پیشنهادي مسئله
مسئله مسیریابی وسائط نقلیه را می توان به وسیله
یک گراف G=(S,A) نشان داد، به طوري که { , … ,0 = | } =S مجموعه نقاط گره ها و A={(Si,Sj): i≠j } مجموعه اي از کمان هاي متصل کننده گره ها است. نقطه 0S نشانگر مبدأ است. 0 ≥ dij که با هر کمان(i,j) مرتبط است، نشانگر مسافت یا زمان مسافرت و یا هزینه مسافرت بین دو نفطهj وi است. براي هر مشتريSi یک تقاضاي 0≥ qi و یک زمان خدمت در نظر گرفته شده است. همان طور که بیان شد ،یکی از نوآوري هاي این مقاله، در نظرگرفتن دو تابع هدف به طور همزمان است. هدف تعیین مسیر بهینه به گونه اي است که همه مشتري ها توسط حداقل تعداد وسیله نقلیه سرویس داده شوند و میزان مصرف سوخت توسط زمانبندي تحویل به موقع کالاهاي سنگین تر، به حداقل برسد. پارامترهاي به کار رفته در مدل به این شکل بیان می شوند:
تعداد نقاط (مشتري ها) است و گره 0 نشان دهنده پایانه است.
{ , … ,1} = تعداد خودروهاي در دسترس تقاضاي گره است بنابراین 0 = است.
فاصله میان گره به
میزان باري است که وقتی وسیله نقلیه به گره می رسد، به همراه دارد
میزان سوخت مصرفی در واحد فاصله بدون بار
میزان اضافی سوخت مصرفی در واحد فاصله براي واحد بار
زمان مورد نیاز براي ارایه خدمت به مشتري ، توسط وسیله نقلیه
زمان مورد نیاز براي طی مسیر ( , ) توسط وسیله نقلیه
حداکثر زمان خدمتدهی جهت و زمان طی مسیر توسط وسیله نقلیه ظرفیت وسیله نقلیه
S زیر مجموعه اي که در آن = | } =S { , … ,0 است.
1 = اگر مسیر به توسط وسیله نقلیه طی شود؛ در غیر این صورت برابر 0 است.

در ادامه به ارائه مدل پیشنهادي مسیریابی وسائط نقلیه مبتنی بر کاهش سوخت مصرفی و اندازه ناوگان می پردازیم:
Minimize
=(+)
+

Minimize =
s.t

= 1 ; = 1,2,…,
= 1 ; = 1,2,… ,
(3)
−= 0 ;
(4)
= 1,2,… , ;
= 1,2,… ,
−−= 0 ;
= 0,1,… ,; = 1,2,…,
≤ ; = 1,2,… ,
+≤ ;
(7)
= 1,2,…,
≤ 1 ; = 1,2,… , (8)
≤ 1 ; = 1,2,…,
(9)
97536-200077

(10)

∈ ,∈ [0,1],≥ 0 (11)

تابع هدف این مدل پیشنهادي، از دو جزء تشکیل شده است. جزء اول تابع هدف، به کاهش هزینه هاي سوخت مصرفی توسط زمانبندي تحویل به موقع کالاهاي سنگین تر می پردازد و جزء دوم آن به دنبال حداقل کردن اندازه ناوگان است. محدودیت (2) و (3) باعث می شود که هر گره تقاضا فقط از یک وسیله نقلیه توزیع کننده، خدمت دریافت کند. قید (4)، بیان می کند که اگر وسیله نقلیهاي به گره اي وارد شود، باید از آن خارج شود و به این ترتیب پیوستگی مسیرها برقرار است. محدودیت (5) بیان می کند که اگر 1 = باشد، بار حمل شده به گره ( ) برابر است با بار حمل شده به گره ( ) منهاي تقاضاي گره . محدودیت (6) مربوط به حداکثر ظرفیت وسائط نقلیه است. محدودیت (7) بیانگر آن است که مجموعزمان سرویس دهی در گره ها و مدت زمان عبور از مسیرها توسط وسائط نقلیه، نباید بیشتر از زمان باشد. قیدهاي (8) و (9) بیانگر آن هستند که مبدأ و مقصد همه وسائط نقلیه ،پایانه است. همچنین رابطه (10) مربوط به حذف زیرگردش ها است.

3- رویکردهاي حل مسئله
3 -1 – الگوریتم بهینه سازي بهبود یافته انبوه ذرات
براي حل این مدل، از الگوریتم بهبود یافته بهینه سازي انبوه ذرات (IPSO) استفاده می شود. الگوریتم IPSO همانند الگوریتم PSO است، با این تفاوت که در هر بار محاسبه مقدار تابع هدف، از روش هاي بهبود همانند * opt-2 استفاده می شود . با استفاده از این روش، زمان حل نسبت به PSO کمتر می شود. همچنین جواب هاي ارایه شده بهتر می شوند [15و 16].
الگوریتم IPSO، یک الگوریتم بهینه سازي تصادفی بر اساس جمعیت است که از شبیه سازي رفتار اجتماعی گروه پرندگان و ماهیان مدل سازي شد. در ابتداي الگوریتم ،تعدادي از ذرات (پرنده) به طور تصادفی تولید می شوند، سپس به هر یک از آن ها، سرعتی نسبت داده می شود. بر اساس سرعت فعلی ذره و فاصله آن از بهترین موقعیتی که تا کنون توسط خود او دیده شده است و نیز فاصله او از بهترین موقعیت یافت شده توسط ذرات مجاور، سرعت جدیدي براي آن ذره محاسبه می شود و با توجه به این نکته که مقدار سرعت به دست آمده، برابر با مقدار جابه جایی ذره در طی یک مرحله است، میتوان موقعیت جدید ذره را در مرحله بعدي، پس از به روز رسانی موقعیت به دست آورد. این فرآیند سپس تا تعداد تکرار مشخصی انجام می گیرد و در نهایت، بهترین مکان ملاقات شده توسط همه ذرات به عنوان جواب مسئله ارایه می شود [16]. هر ذره در الگوریتم بهینه سازي انبوه ذرات، از سه بردار d بعدي تشکیل شده است؛ d بعد فضاي جستجو است. براي ذره i اُ-ُم این سه بردار عبارتند از: xi موقعیت فعلی ذره ،vسرعت حرکت ذره و yi بهترین موقعیتی که ذره تا به حال تجربه کرده است و ŷi بهترین مکانی که تا کنون توسط ذرات مجاور یافت شده است. الگوریتم بهینه سازي ذرات انبوه، چیزي فراتر از یک مجموعه ذرات است و هیچ یک از ذرات به تنهایی توانایی حل مسئله را ندارند و فقط هنگامی می توانند مسئله را حل کنند که با یکدیگر تعامل داشته باشند. در واقع براي انبوه ذرات، حل مسئله یک مفهوم اجتماعی است که از رفتار تک تک ذرات و تعامل میان آنها به وجود می آید. با این وجود، اگر تابع برازندگی مسئله مفروضی، تابع f باشد ،مقادیر ŷi ،yi ،vi ،xi در هر مرحله به صورت زیر به روزرسانی می شوند:

v tijc r(  ( )[1)ty twv t( )-ij ( )x t( )] (12)
1 1 jijij
c r2 2 j( )[t y tj ( )- x tij( )] x tij (  1) x ij ( )t v tij ( ) (13)
yi(t)if f(xi(t1))f(yi(t))
yi(t1)
xi(t1) if f(xi(t1))f(yi(t)) (14)

در روابط بالا ،w ضریب اینرسی ،r1,j و r2,j اعداد تصادفی یکنواخت در فاصله (1و0) و 1c و 2c اعداد ثابت هستند که به ضرایب شتاب دهنده معروف بوده و به ترتیب ،پارامتر ادراکی و پارامتر اجتماعی نامیده می شوند. 1c ضریب یادگیري مربوط به تجارب شخصی هر ذره است و در مقابل 2c ضریب یادگیري براي کل جامعه است. 2r1,r باعث می شود که نوع گوناگونی در جواب ها به وجود بیاید و به این شکل جستجوي کامل تري روي فضا انجام گیرد[17]. همان طور که مشاهده می شود، موقعیت و سرعت هر ذره در هر مؤلفه (j=1,2,…,n) به طور جداگانه به روز رسانی می شود.
شبه کد الگوریتم بهبود یافته بهینهسازي انبوه ذرات در شکل (1) نشان داده شده است.

For each particle
Initialize particle
END
Do
For each particle
Calculate fitness value
If the fitness value is better than the best fitness value
(pbest) in history set current value as the new pbest End

Choose the particle with the best fitness value of all the
particles as the gbest For each particle
Calculate particle velocity according equation (12)
Update particle position according equation (13)
End While maximum iterations or minimum error criteria is not
attained
is satisfiedTerminate the algorithm when the convergence criterion شکل 1: شبه کد الگوریتم فراابتکاري بهبود یافته ي بهینه سازي انبوه ذرات

-2 – الگوریتم تولید حل اولیه
در این بخش، شیوه نمایش جواب ها بررسی می شود. براي تولید حل اولیه، رویکرد ابتکاري زیر مورد استفاده قرار میگیرد:
تشکیل مسیر جدید: ابتدا میزان تقاضاي همه گرهها را به ترتیب نزولی مرتب کنید؛ سپس گره را با بیشترین میزان تقاضا که تا کنون سرویس داده نشده است، انتخاب کرده و از مبدأ به گره ، یک وسیله نقلیه مانند با حداکثر ظرفیت بفرستید.
تعیین گره هاي همسایه: نزدیک ترین گره به گره با بیشترین میزان تقاضا(مانند گره) را به گونه اي بیابید که اگر وسیله نقلیه از به برود ( را سرویس دهد)، محدودیت هاي احتمالی عبور از مسیرها براي رسیدن به گره و همچنین ظرفیت وسیله نقلیه نقض نشود. اگر چنین گره اي یافت شد، وسیله نقلیه از به فرستاده می شود (1 = ) و در غیر این صورت به مبدأ باز میگردد.
تکمیل مسیر: گام 2 را آنقدر تکرار کنید تا وسیله نقلیه به مبدأ بازگردد.
تکمیل سرویس: گام هاي بالا را آنقدر تکرار کنید تا به همه گره ها سرویس داده شود.
تعیین تعداد بهینه وسائط نقلیه: بعد از پایان الگوریتم بالا، تعداد وسیله نقلیه مورد نیاز تعیین می شود.
همان طور که بیان شد، براي بهبود جواب ها در این مسئله، از روش بهبود opt-2 استفاده می شود که در ادامه بیان میشود:

3-2-1 روش بهبود opt-2: در این روش جستجوي محلی، ابتدا دو گره (مشتري) در داخل یک تور انتخاب میشوند و سپس ترتیب عبوري وسیله نقلیه در آن دو گره (مشتري) با یکدیگر تعویض میشوند. اگر این تعویض هزینه تور را کاهش داد، آن را انتخاب کنید، در غیر این صورت تور دو گره دیگر را انتخاب کرده و سپس مسیر آنها را با یکدیگر تعویض کنید. این کار را براي همه گرههاي موجود در تور باید انجام دهید و هر تعویضی که بیشترین کاهش را در هزینه داشت، انتخاب کنید.

3-2-2-تعیین پارامتر ها
الگوریتم هاي فراابتکاري اغلب روي پارامتر هاي خود بسیار حساس هستند و پاسخ هاي به دست آمده، بسیار به میزان پارامتر هاي آن ها بستگی دارند. پارامتر هاي در نظر گرفته شده براي حل مدل پیشنهادي توسط الگوریتم IPSO در جدول (1) نشان داده شده است. براي تنظیم پارامترهاي این مسئله از روش آزمایش و خطا استفاده شده است.

جدول 1: پارامترهاي الگوریتم IPSO
50 تعداد ذره ها
500 تعداد تکرارها
1/49 پارامتر 1c
1/49 پارامتر 2c
0/729 پارامتر w
3- نتایج محاسباتی
در این بخش عملکرد الگوریتم پیشنهادي بررسی می شود؛ به همین منظور، دو گروه مسئله، یکی در ابعاد کوچک و دیگري در ابعاد بزرگ طراحی می شود. در گروه اول ، دسته اي از مسایل نمونه کوچک توسط الگوریتم فراابتکاري پیشنهادي حل شده و جواب هاي حاصل با جواب هاي حاصل از حل مدل با نرم افزار لینگو مقایسه می شوند. هدف از آزمایش اول، بررسی توانایی روش پیشنهادي در رسیدن به جواب هاي بهینه است. در گروه دوم، عملکرد الگوریتم فراابتکاري پیشنهادي در حل مسایل بزرگ و با ابعاد واقعی بررسی می شود. همچنین ،اجراي برنامه ها توسط کامپیوتري Corei3 با توانایی GHZ 5/2 و حافظه داخلی GB 4 انجام شده است.
براي ایجاد مسایل کوچک، از توزیع احتمال یکنواخت استفاده شده است. براي تولید اعداد مربوط به مختصات هر مشتري از توزیع یکنواخت با پارامتر هاي 0 و 50 استفاده شده است. میزان تقاضاي مشتریان با استفاده از توزیع یکنواخت در بازه 1 و 10 به دست آمده است. همچنین، مدت زمان لازم براي سرویس دهی، با استفاده از توزیع یکنواخت در بازه 1 و20 به دست آمده است . این میزان مصرف سوخت در واحد فاصله بدون همراه داشتن بار 65/. و با به همراه داشتن بار 35/. در نظر گرفته شد.
براي بررسی الگوریتم هاي مورد نظر، تعداد 7 مسئله با ابعاد کوچک تولید شد که مشخصات مسایل در جدول (2) ارایه شده است. در این جدول، ستون هاي اول و دوم به ترتیب شماره مسئله و تعداد مشتریان است. ستون سوم ،نشان دهنده تعداد وسیله نقلیه است. ستون هاي چهارم تا ششم به ترتیب نشان دهنده مقدار بهینه، زمان حل و خطاي محاسباتی حل مسئله توسط لینگو است و ستون ششم تا نهم نشان دهنده مقدار بهینه، زمان حل و خطاي محاسباتی حل مسئله توسط الگوریتم بهبودیافته بهینه سازي انبوه ذرات(IPSO) هستند.
از مقایسه نتایج محاسباتی توسط الگوریتم بهبودیافته بهینه سازي انبوه ذرات IPSO با جوابهاي به دست آمده از لینگو، میتوان مشاهده کرد که میانگین خطاي نتایج محاسباتی توسط الگوریتم توسعه داده شده، بهینه سازي انبوه ذرات IPSO با نتایج به دست آمده توسط نرم افزار لینگو 12/4 % است که نشان دهنده کارآیی الگوریتم پیشنهادي است. همچنین زمان حل مسایل توسط لینگو و IPSO به ترتیب برابر 71/1974 و 32/37 است که نشان دهنده کارآیی الگوریتم پیشنهادي براي حل مسایل در زمان کوتاه است.
همچنین براي بررسی قابلیت الگوریتم ارایه شده در ابعاد بزرگ، از مجموعه آزمایش هاي کریستوفیدز و همکاران (1979) استفاده شد که تعداد مسایل نمونه این دسته از مسایل 14 عدد است. نتایج محاسباتی حاصل شده در جدول (3) قابل مشاهده است. در این جدول، ستون اول شماره مسئله است، ستون هاي دوم و سوم به ترتیب نشان دهنده تعداد مشتریان و تعداد وسائط نقلیه هستند. ستون هاي چهارم تا نهم به ترتیب نشان دهنده مقدار بهینه، زمان حل و خطاي محاسباتی حل مسئله توسط لینگو و IPSO است.
در جدول (3)، براي هر یک از مسایل نمونه، نرم افزار لینگو به مدت 1000 ثانیه اجرا شد که نتایج به دست آمده در ستون چهارم جدول قابل مشاهده است. میانگین جواب ها براي لینگو و IPSO به ترتیب برابر 24/1550 و 88/1406 است و میانگین خطا براي لینگو برابر 43/9 درصد است که می توان نتیجه گرفت که جواب ارایه شده توسط الگوریتم بهبود یافته بهینه سازي انبوه ذرات (IPSO) قادر به حل مسایل در ابعاد بالا است. همچنین زمان حل نمونه مسایل توسط IPSO برابر 80/109 ثانیه است که نسبت به حل نمونه مسایل توسط لینگو به مراتب بهتر است.

4- نتیجه گیري
به طور سنتی، مسئله مسیریابی وسائط نقلیه، به یافتن کوتاه ترین مسیرها، با در نظر گرفتن انواع مختلف محدودیت ها مانند محدودیت ظرفیت، طول مسیر، پنجره زمانی و… می پردازد. اگرچه یافتن کوتاه ترین مسیر در بسیاري از موارد منجر به یافتن جواب بهینه براي تابع هدف کاهش سوخت مصرفی و آلودگی هوا نمی شود؛ زیرا مصرف سوخت به عوامل بسیاري همانند میزان بار وسیله نقلیه ،سرعت، وضعیت جاده و… وابسته است. از این رو در این مقاله، یک مدل مسیر یابی وسائط نقلیه دو هدفه شامل
جدول2: مقایسه نتایج براي مسایل با ابعاد کوچک
338328-119448تعداد

حل

توسط

لینگو

توسط

حل

IPSO

تعداد

حل

توسط



قیمت: تومان


دیدگاهتان را بنویسید