بخشی از مقاله
چکیده
شبکههای هاب نقش مهمی در ارتباطات بین مبدأها و مقصدها از طریق تسهیالت هاب دارند. هابها نقش واسطهای را در شبکه ایفا میکنند و وظایف جمعآوری، انتقال و توزیع جریان را بهعهده دارند. در بیشتر مسائل مکانیابی هاب کالسیک، یک ضریب تنزیل برای تمام کمانهای هاب درنظر گرفته شده و همچنین اتصاالت بین تمامی گرههای هاب، بهصورت گراف کامل فرض شده است. با توجه به اینکه این فرضها ممکن است به نتایج غیرواقعی منجر شود، دسته جدیدی از مسائل مکانیابی هاب به نام مسائل مکانیابی q کمان هاب توسعه داده شدهاند که به مکانیابی -qکمان هاب و تخصیص گرههای غیرهاب به هابهای انتخابشده میپردازد، بهطوری که مجموع هزینههای حملونقل و استقرار کمینه شود.
از آنجا که مکانیابی تسهیالت هاب اغلب به صورت بخشی از فرایند تصمیمگیری استراتژیک حل میشوند، راهحل ارائهشده، اثرات بلندمدتی خواهد داشت و پیادهسازی آن به زمان قابلتوجهی نیاز دارد. از طرفی این پیادهسازی باید قبل از شروع عملیات شبکه به پایان برسد. از اینرو بسیاری از پارامترهای مربوط به مسائل مکانیابی هاب در زمان تصمیمگیری برای طراحی شبکه، بهطور دقیق مشخص نیستند و باید در یک محیط تحت عدم قطعیت مطرح شوند . در این مقاله برای نخستین بار، با دخیل کردن عامل عدم قطعیت روی پارامتر جریان بین گرهها، یک مساله مکانیابی کمان/هاب تحت شرایط عدم قطعیت جریانها، با استفاده از روش کمینهسازی بیشینه پشیمانی که یکی از انواع بهینهسازی استوار است، توسعه و بهینهسازی میشود.
-1 مقدمه
جریان - مسافر، کاال و اطالعات و... - از نقاط مبدأ به مقصد، بحث اصلی سیستمهای حملونقل، لجستیک و سیستمهای ارتباطی دوربرد است. شبکههای هاب نقش مهمی در ارتباطات بین مبدأها و مقصدها از طریق تسهیالت هاب1 دارند که به عنوان نقاط راهگزینی، اتصال و ترکیب جریانهای بین مبدأ و مقصد عمل میکنند .]1[ در طراحی شبکه هاب، تصمیمات استراتژیک مکانیابی هابها و تخصیص نقاط مبدأ و مقصد به هابها اتخاذ میگردد. شبکههای هاب دارای این مزیت هستند که جریان را در اندازههای اقتصادی توسط وسایل نقلیه ارسال میکنند و بدینترتیب موجب بهرهگیری از صرفه اقتصادی در استفاده از وسایل نقلیه و بهبود سطح خدمتدهی خواهند شد.
در شبکه هاب، هر گره غیرهاب به حداقل یک هاب متصل میشود و بین هر د و گره غیرهاب حداقل یک مسیر وجود دارد. مشخصه اصلی بهکارگیری شبکه هاب، صرفه اقتصادی آن به دلیل ایجاد ارتباط غیرمستقیم میان نقاط مبدأ و مقصد با استفاده از تسهیلهاب است. در شبکه هاب معموالً استفاده از ارتباطات بین هاب باعث کاهش هزینه با ضریب - 0˂α˂1 - α و بهدنبال آن کاهش هزینه حملونقل و بهرهگیری از صرفه اقتصادی، در مقایسه با شبکه ارسال مستقیم میشود .]2[
در بیشتر مسائل مکانیابی هاب میانه2، به صورت پیشفرض، یک ضریب تنزیل3 برای تمام کمانهای هاب درنظر گرفته شده و همچنین اتصاالت بین تمامی گرههای هاب به صورت گراف کامل درنظر گرفته شده است. این دو فرض به هم مرتبطند زیرا فرض میشود که مزایای اقتصادی مربوط به مقیاس، برای جریانهای روی کمانهای هاب، تخفیف هزینهای برای این کمانها ایجاد میکند. این فرض ممکن است به نتایج غیرواقعی منجر شود، زیرا راهحلهای بهینه در مسائل مکانیابی هاب ممکن است جریانهای بهمراتب کوچکتری روی کمانهای هاب نسبت به کمانهای بین یک هاب و یک غیرهاب نتیجه دهد، در حالی که ضریب تنزیل فقط بین نقاط هاب درنظر گرفته شده است .]3[
کمپب ل و همکارانش در سال 2002، به معرفی نوع جدیدی از مسائل مکانیابی هاب به نام "مدلهای مکانیابی کمان/هاب" 4 پرداختند، که با آزاد کردن فرضهای مذکور، بر مکانیابی کمانهای تخفیفدار هاب - کمانهایی که دو سر آنها نقاط هاب وجود دارد - تمرکز میکند. این مدلها دیدگاههای مسائل طراحی شبکه2 را هم به مسائل مکانیابی هابهایی که ممکن است کامال هم متصل نباشند، اضافه میکند .]4[
مدلهای مکانیابی کمان/هاب به رفع نقصهای ذکر شده برای مسائل مکانیابی هاب میانه میپردازند. در واقع، مدلهای هاب میانه میتوانند به عنوان نوع خاصی از مدلهای مکانیابی کمان/هاب بررسی شوند که در آنها کمانهای هاب یک گراف کامل را تشکیل میدهند. بنابراین، مسائل مکانیابی -qکمان هاب، به انتخاب q کمان هاب و تخصیص گرههای غیرهاب به هابهای انتخابشده میپردازد بهطوری که مجموع هزینههای حملونقل و استقرار کمینه شود.
-1-1 پیشینه تحقیق
در ارتباط با پیشینه تحقیق مسائل مکانیابی کمان/هاب، کمپبل و همکارانش در سال 2002 در دو مقاله به معرفی این مدلها پرداختند .]2[ ,]3[ مقاله اول شامل تعاریف و مفاهیم مسائل مکانیابی کمان/هاب میباشد. در این مدلها فرض کامال متصل بودن گرههای هاب آزاد شده است و نتایج، نشاندهنده کاهش هزینه جریانها میباشد. آنها با ارائه چهار مدل از مسائل مکانیابی کمان/هاب، نتایج این مسائل را با مسائل مشابه هاب میانه در ادبیات کالسیک مکانیابی هاب مقایسه کردند. مقاله دوم آنها در سال 2002، فرمولبندی برنامهریزی عدد صحیح و الگوریتمهای حلی برای این مدل مسائل ارائه میکند.
کمپبل و همکاران پس از معرفی مسائل مکانیابی کمان/هاب در مقاله فوقالذکر، در تحقیقی با عنوان "حل مسائل مکانیابی کمان/هاب بر مجموعه ای از ایستگاههای کاری" ، به بررسی این نوع مسائل در ترافیک مسافران هوایی ایاالت متحده و همچنین عملیات پستی در سیدنی استرالیا پرداختند .]6[ آنها اولین مدل از چهار مدل ارائه شده در مقاله قبلی را درنظر گرفتند و با پیادهسازی موازی الگوریتمهای بر پایه شمارش6، حل مسائل مکانیابی کمان/هاب را بررسی کردند.
میهیروساساکی و همکارانش نیز در سال 2002 به بررسی مساله مکانیابی کمان/هاب با درنظرگیری عامل رقابت پرداختند. فرض این است که دو شرکت برای به دست آوردن مشتریان بیشتر رقابت میکنند و شرکت رهبر و شرکت پیرو، کمانهای هاب خود را برای بیشینهسازی درآمد مکانیابی مینمایند .]7[ آنها نتایج را تا تعداد سه کمان هاب برای هر شرکت رقابتکننده به دست آوردند و نقش مهم محیط رقابتی را در طراحی سیستم حملونقل نشان دادند.
در مقاله دیگری در سال 2002، مکانیابی هاب برای حملونقل با زمان معین7 توسط کمپبل بررسی شد. در این مقاله با درنظرگیری محدودیت سطح خدمت، مدل مکانیابی چندگانه هاب میانه و مکانیابی کمان/هاب حل شد و نتایج به دست آمده از دو مدل ارائهشده، مقایسه میشود. سطوح خدمت توسط محدود کردن بیشینه مسافت سفر از طریق شبکه هاب برای هر یک از جفت مبدأ-مقصدها اعمال شده است. او در این مقاله نشان میدهد که با افزایش سطح سرویس، کمانهای هاب کوتاهتر و گرههای هاب متمرکزتر خواهند شد .]8[
-2-1 شکاف تحقیقاتی و ضرورت تحقیق
با توجه به جدید بودن مسائل مکانیابی کمان/هاب، هیچ تحقیقی در ارتباط با وجود شرایط عدم قطعیت در مسائل مکانیابی کمان/هاب، تا به حال صورت نگرفته است. با توجه به اینکه مسائل مکانیابی کمان/هاب نسبت به مسائل مکانیابی کالسیک هاب در ادبیات کمتر مورد بررسی قرار گرفته، ما در این مقاله بهدنبال توسعه اینگونه مسائل با درنظر گرفتن پارامترهای نادقیق میباشیم تا مساله را تحت شرایط عدم قطعیت بررسی کنیم.
مکانیابی تسهیالت هاب یک مساله طراحی شبکه است که اغلب به صورت بخشی از فرایند تصمیمگیری استراتژیک حل میشود، بنابراین راهحل ارائهشده، اثرات بلندمدتی خواهد داشت و پیادهسازی آن به زمان قابلتوجهی نیاز دارد. از طرفی این پیادهسازی باید قبل از شروع عملیات شبکه به پایان برسد. از اینرو بسیاری از پارامترهای مربوط به مسائل مکانیابی هاب در زمان تصمیمگیری برای طراحی شبکه بهطور دقیق مشخص نیستند ]2[ و باید در یک محیط دارای عدم قطعیت مطرح شوند. پارامترهایی مانند هزینهها - هزینه راهاندازی و یا هزینههای حملونقل - ، تقاضا، مسافت، تراکم و غیره میتوانند به صورت احتمالی بررسی شوند؛ به این معنی که احتمال تغییر آنها بعد از اتخاذ تصمیمهای استراتژیک مکانیابی وجود دارد. با این وجود، مدلهای HLP8 استاندارد، دادهها را به صورت قطعی درنظر گرفته است که این موضوع منجر به نتایج کمتر بهینهای خواهد شد.
سه نوع تحقیق در ارتباط با بهینهسازی تحت شرایط عدم قطعیت وجود دارد: بهینهسازی احتمالی2، بهینهسازی استوار10 و بهینهسازی فازی.11 در بهینهسازی احتمالی فرض میشود که مقادیر پارامترهای احتمالی از طریق توزیع احتمالی شناخته شدهای کسب میشوند. در حالی که در بهینهسازی استوار، فرض بر این است که پارامترها دارای عدم قطعیت هستند اما هیچ اطالعاتی در مورد توزیع احتمالی آنها موجود نیست و فقط مشخصات بازههایی که شامل این مقادیر است در دسترس میباشد . ]10[ در بهینهسازی فازی هم پارامترهای نادقیق از منطق فازی پیروی میکنند.
-3-1 نوآوری تحقیق
در این تحقیق برای نخستینبار، با دخیل کردن عامل عدم قطعیت روی پارامتر جریان بین گرهها، یک مساله مکانیابی کمان/هاب تحت شرایط عدم قطعیت توسعه و بهینهسازی میشود. در این مقاله سعی شده تا برخی از کاستیهای موجود در ادبیات را برطرف کرده و مدلی کاربردی ارائه شود. به این صورت که ابتدا مدلسازی ریاضی مسائل مکانیابی کمان/هاب موجود در ادبیات در غالب برنامهریزی عدد صحیح مخلوط خطی توسعه داده شده تا برخالف فرمولبندیهای موجود در ادبیات مسائل مکانیابی کمان/هاب، هاب ایزوله12 را نیز دربرگیرد. سپس برای اولینبار، مساله در شرایط عدم قطعیت مدلسازی میشود . برای این کار از روش کمینهسازی بیشینه پشیمانی13 که یکی از انواع روشهای بهینهسازی استوار است، بهره بردیم. به منظور حل دقیق سناریوهای قطعی مورد نیاز در روند حل و همچنین حل مدل بهینهسازی استوار، از نرمافزار گمز14 استفاده کردیم.
-2 مفاهیم مکانیابی کمان/هاب
مدلهای مکانهای کمان/هاب این محدودیت را که هزینه جریان بین هر جفت هاب تخفیفدار باشد، آزاد میکند. این مسائل به دنبال مکانیابی کمانهای هابی است که در دو سر آنها هابها قرار گرفتهاند .]3[ این موضوع میتواند به عنوان یک مساله طراحی شبکه بررسی شود تا تعیین گردد که بر کدام کمانها باید سرمایههای موثر دارای هزینه محدود - وسایل حملونقل بزرگتر - قرار داده شود. بنابراین، شبکه هاب در این نوع مسائل لزوماً گراف کامل نیست.
-1-2 فرضیات مدل مکانیابی کمان/هاب
فرض.1 تمام مسیرهای مبدأ-مقصد حداقل شامل یک گره هاب میباشند. این فرض بیان میکند که - با توجه به قضیه نابرابری مثلث - 12 هیچ کمانی مستقیمی بین دو گره مبدأ- مقصد غیرهاب وجود ندارد .]3[
فرض. 2 هزینه ≤واحد جریان بر کمانهای هاب با استفاده از ضریب تخفیف - 0>α 1 - α دارای تخفیف است. این موضوع اجازه میدهد که هابها گراف کامل نباشند . بنابراین نوع دیگری از کمان به نام کمان پل16 معرفی میشود که دو گره هاب بدون ضریب تخفیف را به هم متصل میکند .]3[
