بررسی و حل مدل پویا برای مساله مکان‌یابی میانه محور با تخصیص چندگانه

بشیری, مهدی; حمیدیان, خسرو

تعداد نشریات	43
تعداد شماره‌ها	1,713
تعداد مقالات	14,041
تعداد مشاهده مقاله	33,964,308
تعداد دریافت فایل اصل مقاله	13,600,119

بررسی و حل مدل پویا برای مساله مکان‌یابی میانه محور با تخصیص چندگانه

پژوهش در مدیریت تولید و عملیات

مقاله 6، دوره 5، شماره 2، مهر 1393، صفحه 108-93 اصل مقاله (864.57 K)

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

نویسندگان

مهدی بشیری^* ¹؛ خسرو حمیدیان²

¹دانشیار دانشکده فنی و مهندسی، گروه مهندسی صنایع، دانشگاه شاهد

²دانشجوی کارشناسی ارشد مهندسی صنایع، دانشگاه پیام نور

چکیده

مساله مکان‌یابی میانه محور با تخصیص چندگانه شامل جانمایی تسهیلات محور و تخصیص گره‌های غیرمحور به محورها است و البته، از نوع مسایل مکان‌یابی در کلاس NP-hard است. هدف اصلی در این مقاله، مساله مکان‌یابی میانه محور با تخصیص چندگانه در حالت تغییرات پویای جریان است که ظرفیتی برای محورها و کمان‌ها وجود ندارد و باز و بسته شدن محورها در دوره‌های گوناگون افق برنامه‌ریزی امکان‏پذیر است. مدل و الگوریتم پیشنهادی برای حل، با داده های شبکه حمل و نقل هوایی ایران بر مبنای تعداد مسافران جا به‌جا شده ،آزمایش می‌شود. نتایج بررسی نشان می‌دهد؛ تشکیل شبکه پویا در مقایسه با حالت ایستا، هزینه کمتری در پی خواهد داشت و هرچه تعداد دوره‌های زمانی در حالت پویا بیشتر شود؛ روند بهبود (کاهش هزینه‌ها) ادامه می‌یابد.

کلیدواژه‌ها

مکان‏یابی؛ طراحی شبکه؛ تقاضای پویا؛ برنامه‌ریزی خطی؛ الگوریتم شبیه‌سازی تبرید

اصل مقاله

1-مقدمه

مسایل مکان‌یابی محور[1] از مسائل کلاسیک بهینه‌سازی ترکیبی هستند که در شبکه‌های حمل و نقل و ارتباط از راه دور مورد استفاده می‌شوند؛ به طوری که نقاط مبدا- مقصد، جنس ها و کالاها (برای مثال، انتقال اطلاعات،‌ مسافر، بسته‌بندی‌های سریع، پست و ...) را از نقاط مراوده یا تسهیلات خاصی که محور گفته می‌شوند، دریافت و ارسال می‌کنند. این شبکه‌ها با ادغام جریان‌های عبور و مرور از مبداهای گوناگون به سمت مقصدهای یکسان در نقطه محور و ارسال آنها به مقصدهای نهایی، در جستجوی کاهش هزینه کل مراودات هستند. برخی از کاربردهای مسایل محور عبارتند از: خطوط هوایی و فرودگاه ها ، مسائل حمل و نقل و مراودات ، سیستم‌های ارتباط از راه دور و خدمات اضطراری (اورژانسی).

مساله مکان‌یابی محور برای استقرار تسهیلات محور و تخصیص گره‌ها به محورها استفاده می‌شود. دو گونه اساسی از شبکه‌های محور وجود دارد: تخصیص یگانه[2] و تخصیص چندگانه[3]. تفاوت آنها به چگونگی تخصیص گره‌های غیرمحور به محورها برمی‌گردد. در تخصیص یگانه، تمامی مراودات ورود و خروج در هر مرکز تقاضا از میان تنها یک محور که به آن تخصیص داده می‌شود،‌ عبور می‌کند؛ اما در تخصیص چندگانه، هر مرکز تقاضا می‌تواند ارسال و دریافت کالاها را از میان بیش از یک محور انجام دهد.

در دنیای واقعی، تصمیمات تنها برای یک دوره خاص (برای مثال سالانه) گرفته نمی‌شود. در طول پیاده‌سازی عملیات ساختاری گسترده، گاهی اوقات افق برنامه‌ریزی با دوره‌‌های ویژه‌ای پیش‌بینی می‌شود. این بدین معنی است که پیکره اولیه تصمیمات ممکن است تحت عوام گوناگون تغییر کند. در شبکه‌های حمل و نقل، تقاضا (یا جریان) در دوره‌های گوناگون ممکن است تغییر کند. در طول تغییر جریان برای یک مساله، با استفاده از دوره‌های قبلی، تشکیل شبکه برای دوره بعد در افق برنامه‌ریزی تغییر می‌کند و تا پایان همان دوره ثابت باقی می‌ماند.

در این مقاله، دوره‌های زمانی گوناگون در افق برنامه‌ریزی برای مساله مکان‌یابی محور در نظر گرفته می‌شود به طوری که مکان‌های محورها و مسیرهای بین هر گره مبدا - مقصد برای هر دوره در افق برنامه‌ریزی تعیین می‌شود. از مساله مکان‌یابی میانه محور در این تحقیق استفاده می‌شود و علاوه بر ارتباط کامل بین محورها، تخصیص هر گره به بیش از یک محور (تخصیص چندگانه) امکان‌پذیر است. در مروری که بر مطالعات مساله مکان‌یابی محور انجام گرفته است، تحقیقی مبنی بر تغیبر جریان در افق برنامه‌ریزی صورت نگرفته است اوکلی[4] (۱۹۸۷) نخستین بار مدل ریاضی برای مساله مکان‌یابی میانه محور ارائه داد که مدل او با نام مساله مکان‌یابی میانه محور با تخصیص یگانه و به صورت برنامه‌ریزی عدد صحیح درجه دو فرموله شده بود. کمپبل[5] (۱۹۹۴) نخستین فرمول برنامه‌ریزی خطی عدد صحیح را برای این مساله معرفی کرد و اسکورین کاپف و همکاران[6] (۱۹۹۶) با کاهش خطی در تعداد محدودیت‌های مدل کمپبل (۱۹۹۴)، مدل مختلط عدد صحیح جدیدی ارائه کردند به طوری که نخستین تلاش برای حل بهینه مساله مکان‌یابی میانه محور با تخصیص یگانه را انجام دادند.

ارنست و کریشنامورسی[7] (۱۹۹۶) نوع دیگری از این مساله را به صورت برنامه‌ریزی خطی عدد صحیح ارائه دادند که با تعداد کمتر متغیر (متغیر با سه اندیس) و محدودیت، اقدام به حل اندازه‌های بزرگتر مساله کردند. ابری[8] (۲۰۰۱) فرمول‌بندی دیگری برای این نوع مساله تعریف کرد که با متغیر با دو اندیس، دارای کمترین تعداد متغیر مورد نیاز نسبت به تمام مدل‌سازی‌های گذشته بود.

جدول(1): مروری بر مطالعات انجام شده در مساله مکان‌یابی میانه محور با رویکرد مدل‌سازی

تخصیص یگانه

اوکلی (۱۹۸۷)،کمپبل (۱۹۹۴)، اسکورین کاپف و همکاران (۱۹۹۶)، ارنست و کریشنامورسی (۱۹۹۶)، اوکلی و همکاران (۱۹۹۶)، ابری (۲۰۰۱)

تخصیص چندگانه

کمپبل (۱۹۹۲)، کمپبل (۱۹۹۴)، اسکورین کاپف و همکاران (۱۹۹۶)،

ارنست و کریشنامورسی (الف۱۹۹۸)، ساساکی و همکاران^{^[9]} (۱۹۹۹)، مارین و همکاران (۲۰۰۶)

در این مقاله، بررسی مدل پویا برگرفته از مدل آیکین (۱۹۹۴)

درحالت تخصیص چندگانه، کمپبل (۱۹۹۲) نخستین بار این مساله را به صورت برنامه‌ریزی خطی عدد صحیح ارائه نمود. کمپبل (١٩٩٤) حالت‌های بیشتری از این مدل با فرضیات متفاوت از جمله محدودیت ظرفیت برای محورها و مساله با هزینه‌های ثابت را معرفی کرد. ارنست و کریشنامورسی (الف۱۹۹۸) نوع دیگری از فرمول‌بندی را برای حالت تخصیص چندگانه برپایه ایده‌ای که ارنست و کریشنامورسی (۱۹۹۶) برای تخصیص یگانه به کار بردند، ارائه کردند و نشان دادند که این فرمول بسیار کارآمدتر از مدل اسکورین کاپف و همکاران (۱۹۹۶) است. مارین و همکاران[10] (۲۰۰۶) فرمول‌بندی جدیدی بر مبنای تعمیمی بر مدل های پیشین ارائه دادند که از تمام مدل‌های قبل بهتر عمل کرد. جدول(1)، مطالعات کاربردی در حوزه فرمول‌بندی مساله میانه محور را نشان می‌دهد.

اوکلی (۱۹۸۷) پس از ارائه نخستین فرمول ریاضی برای این مساله، دو الگوریتم ابتکاری شمارشی برای حل آن به کار برد. در روش اول، تخصیص به نزدیکترین محور انجام می‌گرفت در صورتی که در روش دوم، تخصیص به نزدیکترین اولین یا دومین محور انجام می‌شد. کلینس ویز[11] (۱۹۹۱، ۱۹۹۲) روش‌های ابتکاری متعددی برای حل این مساله به کار برد. اولین روش او بر پایه تعویض‌های تکی و دوتایی است؛ به طوری که روش دوم بر مبنای خوشه‌بندی است. روش‌های ابتکاری کلینس ویز (۱۹۹۱، ۱۹۹۲) عملیات محاسباتی کمتری نسبت به روش ابتکاری شمارشی اوکلی (۱۹۸۷) داشت و برای حل مسایل در مقیاس‌های بزرگ استفاده شد. همچنین، اسکورین کاپف و اسکورین کاپف (۱۹۹۴) و کلینس ویز (۲۰۰۲) از جستجوی ممنوع برای حل مساله مکان‌یابی میانه محور استفاده کردند.

به تازگی، سیلوا و کیونها[12] (۲۰۰۹) و لیک و همکاران[13] (۲۰۱۰) الگوریتم‌های ابتکاری موثر و کارامدی را مطرح کردند. دو مطالعه جامع و فراگیر پیرامون مساله مکان‌یابی محور توسط کمپبل (۲۰۰۲) و آلومور و کارا[14] (۲۰۰۸) فراهم شده است که انواع تحقیقات در مساله محور را بحث و بررسی می‌کند. جدول(2)، مطالعات انجام شده پیرامون روش‌های حل به کار رفته در مساله میانه محور را نشان می‌دهد.

مدل‌های مکان‌یابی پویای تسهیلات را می‌توان توسعه مدل‌های ایستا یا تک دوره‌ای درنظر گرفت؛ به طوری که شامل تغییرات دوره‌ای تقاضا هستند.

جدول(2) مروری بر روش‌های حل به کار رفته در مساله مکان‌یابی میانه محور
روش حل	نویسنده (ها)
الگوریتم ابتکاری	اوکلی (۱۹۸۷)، کمپبل (۱۹۹۶)، کلینس ویز (۱۹۹۱)، سونگ و جین^{^[15]} (۲۰۰۱)، لیک و همکاران (۲۰۱۰)
جستجوی ممنوع	اسکورین کاپف و اسکورین کاپف (۱۹۹۴)، کلینس ویز (۲۰۰۲)، سیلوا و کیونها (۲۰۰۹)
شاخه و کران	آیکین[16] (۱۹۹۴)، اسکورین کاپف و همکاران (۱۹۹۶)، ارنست و کریشنامورسی (ب۱۹۹۸)، ساساکی و همکاران (۱۹۹۹)
روش لاگرانژ	پیرکول و شیلینگ^{^[17]} (۱۹۹۸)، یمن^{^[18]} (۲۰۰۸)
شبیه سازی تبرید	ارنست و کریشنامورسی (۱۹۹۶)، ابدینور هلم^{^[19]} (۲۰۰۱)
الگوریتم ژنتیک	کراتیکا و همکاران^{^[20]} (۲۰۰۷)

جدول(3):مروری بر مطالعات انجام شده در مکان‌یابی پویای تسهیلات
نویسنده (ها)	شرح مختصری از مقاله	روش حل
داسکین و همکاران[21] (۱۹۹۲)	مکان‌یابی با افق برنامه‌ریزی نامعلوم	رویکرد تجربی (آزمایشی)
اندریتا و ماسن[22] (۱۹۹۴)	مکان یابی- تخصیص مجدد تک وسیله ای	برنامه‌ریزی پویا
درزنر[23] (۱۹۹۵)	مکان‌یابی میانه با تقاضای پویا	حل بهینه
چاردیر و همکاران[24] (۱۹۹۶)	برنامه‌ریزی درجه دو بدون محدودیت ظرفیت	شبیه سازی تبرید
کنل و خیوماوالا[25] (۱۹۹۶)	مکان‌یابی چند دوره ای با و بدون محدودیت ظرفیت	حل بهینه
سالدانها داگاما و کپدیوو[26] (۱۹۹۸)	مکان‌یابی- تخصیص مجدد بدون محدودیت ظرفیت	الگوریتم ابتکاری دو فازی
حکیمی و همکاران[27] (۱۹۹۹)	مکان‌یابی میانه تک وسیله ای و چند وسیله ای	الگوریتم ابتکاری
کنل و داس[28] (۱۹۹۹)	مکان‌یابی چند دوره ای با حداکثر کردن سود	الگوریتم شاخه و کران
دیاس و همکاران[29] (۲۰۰۱)	مساله با محدودیت ظرفیت	الگوریتم اولیه-ثانویه
بهمردی و لی[30] (۲۰۰۸)	مکان‌یابی چند کالایی با ظرفیت در زنجیره تامین	الگوریتم ابتکاری

به طور کلی می‌توان مدل‌های پویا را به دو حالت پیوسته و گسسته طبقه‌‌بندی کرد که البته، مطالعات پیرامون مدل گسسته به مراتب غنی‌تر از مدل پیوسته است. بیشتر مدل‌ها در این زمینه با این فرض است که تسهیلات در بین دوره‌ها می‌تواند مجددا مکان‌یابی شود. جدول(3)، تحقیقات پایه‌ای انجام شده (از دهه ۹۰ تا زمان حال) در حوزه مکان‌یابی پویای تسهیلات را نشان می‌دهد.

قسمت‌های تشکیل دهنده این مقاله به شرح ذیل است. در بخش دوم، شرح مدل‌سازی مساله آمده است. مثال عددی و تحلیل آن به ترتیب در بخش‌های سوم و چهارم بیان می‌شود و در بخش پنجم نتیجه‌گیری آمده است

2-مدل‌سازی مساله

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

برای فرموله کردن این مساله از مدل ارائه شده توسط آیکین (۱۹۹۴) استفاده شده است. در این مدل، تعداد کل گره‌های تقاضا تعریف می‌شود که در دوره زمانی t به وسیله p^t محور پوشش داده می‌شود و با مجموعه N نشان داده می‌شود. محورها از بین مجموعه‌ای از گره‌ها که برای محور شدن مجاز هستند، انتخاب می‌شوند و آن مجموعه با M نشان داده می‌شود؛ همچنین، گره‌های انتخاب شده به عنوان محور در مجموعه‌ای به نام M_c قرار می‌گیرد که امکان بسته شدن در دوره‌های زمانی را دارد. W_ij^t و d_ij^t به ترتیب نشان دهنده جریان و مسافت بین دو گره i و j در دوره زمانی t هستند. F_k^t عبارتست از هزینه جانمایی محور در گره k در دوره زمانی t و هزینه بستن محور واقع شده در گره k در دوره زمانی t برابر با F’_k^t است. نرخ تخفیف α برای عبور از بین دو محور منظور می‌شود که بین صفر و یک است. برای ارتباط گره با محور و بالعکس، معمولا فاکتورهای χ و δ را تعریف می‌کنند که در این مقاله فاکتورهای مذکور در نظر گرفته نمی‌شوند، به عبارت دیگر مقدار یک را دارند. هزینه سفر بین گره‌ها متناسب با مسافت بین آنها محاسبه می‌شود به این ترتیب که برای دوره زمانی t، هزینه جریان از گره (مبدا) i به گره (مقصد) j که از محورهای (به ترتیب) k و m عبور می کند، از رابطه (۱) به دست می‌آید.

C_ijkm^t = (d_ik^t + α d_km^t + d_mj^t) W_ij^t

(۱)

متغیرهای تصمیم

y_k^t	برابر با یک است اگر در دوره زمانی t، محور در گره k قرار گیرد و در غیر این صورت صفر است.
X_ijkm^t	برابر با یک است اگر در دوره زمانی t، جریان از گره مبدا i به گره مقصد j به ترتیب از محورهای k و m عبور کند و در غیر این صورت صفر است.

تابع هدف و محدودیت های این مدل به شرح زیر است.

(۲)	Min ∑_tєTS∑_iєN∑_jєN∑_kєM∑_mєM C_ijkm^t X_ijkm^t +∑_tєTS∑_kєM F_k^t y_k^t -∑_tєTS∑_kєM F'_k^t y_k^t
(۳)	s.t. ∑_k y_k^t = p^t ∀ t є [1, ... , T]
(۴)	y_k^t-1 ≥ y_k^t ∀ t є [2, ... , T], ∀ k є M_c
(۵)	y_k^t-1 ≤ y_k^t ∀ t є [2, ... , T], ∀ k є M
(۶)	∑_kєM∑_mєM X_ijkm^t = 1 ∀ t є TS, ∀ i ≠ j є N
(۷)	∑_iєN∑_l,hєM (X_iklh^t +X_kilh^t) ≤ V(1 - y_k^t) ∀ t є TS, ∀ k є M ^{i ≠ k l,h ≠ k}
(۸)	∑_hєM (X_kmkh^t +X_kmhm^t +X_mkmh^t +X_mkhk^t)+∑_hєM (X_kmhh^t +X_mkhh^t) ≤ V(2 - y_k^t -y_m^t) ^{h ≠ k ,m} ^{h ≠ k ,m} ∀ t є TS, ∀ k, m є M, k ≠ m
(۹)	∑_i,jєN∑_lєM (X_ijkl^t +X_ijlk^t +X_jikl^t +X_jilk^t)+∑_iєN∑_lєM (X_kikl^t +X_iklk^t)+∑_i,jєN (X_ijkk^t ^{i,j ≠ k l ≠ k} ^{i ≠ k l ≠ k} ^{i,j ≠ k} +X_jikk^t) ≤ V y_k^t ∀ t є TS, ∀ k є N
(۱۰)	∑_i,jєN (X_ijkm^t +X_ijmk^t +X_jikm^t +X_jimk^t)+∑_hєN (X_kmkh^t +X_kmhm^t +X_mkmh^t +X_mkhk^t ^{i,j ≠ k ,m} +X_kmmh^t +X_kmhk^t +X_mkkh^t +X_mkhm^t) ≤ V(y_k^t +y_m^t) ∀ t є TS, ∀ k, m є N, k ≠ m
(۱۱)	y_k^t , X_ijkm^t є [0,1] ∀ t є TS, ∀ i, j є N, ∀ k, m є M

به طوری که TS = [1 , . . . , T] مجموعه‌ای است که افق برنامه‌ریزی به دوره‌های زمانی، تقسیم می‌شود و V یک عدد مثبت بزرگ است.

اکنون چند نکته پیرامون متغیرهای تصمیم، هزینه‌های خدمت رسانی و محدودیت ها توضیح داده می‌شود. متغیر X_ijkm برای گره‌های i و j ؛ و برای گره‌های محور k و m تعریف می‌شود. اگر i و j دو گره غیرمحور و m ≠k ، متغیر یک حرکت با دو توقف از گره i به گره j از میان محورهای k و m را نشان می‌دهد. از طرف دیگر، اگر m=k ، متغیر، مسیری با یک توقف از گره i به گره j از میان محور k را نشان می‌دهد. در این حالت، هزینه خدمت رسانی به صورت C_ijkk = (d_ik + d_jk)W_ij محاسبه می‌شود. در رابطه (۱)، هزینه خدمت دهی به این ترتیب محاسبه می‌شود که بخش اول ارتباط بین مبدا غیرمحور و محور است و بخش سوم به ارتباط بین محور و مقصد غیرمحور می‌پردازد و البته، بخش دوم ارتباط بین محورها است. اگر مبدا (یا مقصد) در یک مسیر، خودش محور باشد، آنگاه هزینه محاسبه شده از رابطه (۱) ممکن است بیشتر از هزینه واقعی باشد. در این حالت، هزینه واقعی عبور از بین محورهای k و m برابر با C_ijkm = (α(d_ik + d_km) + d_mj)W_ij است. و اگر گره مقصد j محور باشد، هزینه واقعی عبور از بین محورهای k و m برابر با C_ijkm = (d_ik + α(d_km + d_mj))W_ij است. این موقعیت ممکن است برای حالت هایی با دو، سه یا چهار محور به وجود آید. با توجه به اینکه در این تحقیق عبور از سه یا چهار محور (بیش از دو محور) مجاز نیست، متغیرهای X_ijkm نشان دهنده این نوع از مسیرها به وسیله رابطه‌های(۷) و (۸) برابر با صفر قرار می‌گیرد. بنابراین، نمونه‌ای برای مسیر با دو محور در این حالت توسط متغیرهای X_ijkk و X_ijik فراهم می‌شود. هر دوی این متغیرها مسیر مشابهی از محور (گره) i به گره مقصد j را نشان می‌دهند. بنابراین، C_ijkk محاسبه شده از رابطه(۱) بیشتر از هزینه محاسبه شده صحیح C_ijik است. در این حالت، متغیر X_ijik با مشخصه خدمت دهی و ضریب هزینه صحیح در مساله به کار می‌رود، مادامی که متغیرهای دیگر نشان دهنده حالت مشابه توسط رابطه(۷) برابر با صفر قرار می‌گیرد. همچنین، تمام متغیرهای خلاف قاعده مانند X_kjmk و X_kmmk برای m ≠ k؛ نیز از مدل حذف می‌شوند. عکس شرایط فوق را برای گره‌های غیرمحور نیز باید فراهم کرد. برای گره مبدا (مقصد) i، تمام مسیرهایی که در آن گره غیرمحور i در حالت محور قرار می‌گیرد توسط رابطه(۹) مساوی صفر قرار می‌گیرد. از جمله، مسیرهایی که در آن گره i به تنهایی محور است (برای مثال X_ljii)، مسیرهایی که در آن گره i به صورت محور در حالت مبدا (مقصد) قرار گیرد (برای مثال X_ijii) و یا مسیرهایی که در آن به همراه محور دیگری تشکیل مسیری با دو توقف ایجاد کنند (برای مثال X_ijik). برای دو گره i و j، و j ≠i ؛ رابطه(۱۰) تمام مسیرهایی که در آن، این گره‌ها چه به صورت مجزا (برای مثال X_lhij) و چه به صورت مبدا یا مقصد، در حالت محور قرار می‌گیرند (برای مثال X_ijik و X_ijkj) را از مدل خارج می سازد. تعداد محورها برای هر دوره توسط رابطه (۳) تعیین می‌شود. رابطه‌های (۴) و (۵) صحت راه اندازی محورهای بسته شده و یا حذف محورهای ایجاد شده را، برای دوره‌های گوناگون زمانی تضمین می‌کند. رابطه(۶) نوع ارتباط بین دو گره را مشخص می‌کند، این که ارتباط بین مبدا و مقصد از چه محوری(هایی) عبور می‌کند. رابطه(۱۱) نشان دهنده صفر و یک بودن همه متغیرها است.

آیکین (۱۹۹۴) مدلی برای طراحی شبکه محور در نظر تحقیق مذکور، برای محورها ظرفیت محدودی تعریف شده و امکان ارتباط مستقیم برای مجموعه‌ای از گره‌ها مجاز است، اما در مدل این مقاله ظرفیت محورها نامحدود است و ارتباط گره‌ها تنها از طریق محور انجام می‌گیرد و البته، اضافه شدن t به مدل، که برای پویا بودن مساله است. بنابراین، محدودیت‌های (۳)، (۶)، (۷) و (۸) مدل این مقاله مشابه با مدل آیکین است، اما یکی از محدودیت‌های مدل وی مربوط به وجود ظرفیت برای گره‌ها است که در مدل این مقاله به کار نمی‌رود. دو محدودیت (۴) و (۵) وﻳﮋه پویا بودن مدل است و البته، محدودیت های (۹) و (۱۰) که برای کامل شدن شبکه محور به این مدل اضافه می‌شود تا جبران کننده عدم محدودیت ظرفیت در مدل آیکین باشد. گرفت که مدل این مقاله دارای تفاوت‌هایی نسبت به مدل اول است که به آن اشاره می‌شود.

۳.- مثال عددی

در این بخش عملکرد محاسباتی مدل پویا برای مساله مکان‌یابی میانه محور با استفاده از مجموعه داده کریمی و بشیری (۲۰۱۱) که از خطوط هوایی ایران در سال ۱۳۸۸ است، آزمایش می‌شود. داده‌های به کار رفته در این قسمت شامل ۳۲ شهر از این مجموعه است و % ۳۸ / ۹۸ از کل جریان داده مذکور را در بر می‌گیرد. الگوریتم(1): شبیه سازی تبرید به کار رفته برای مدل پویای مساله مکان‌یابی میانه محور جریان بین شهرها برای فصل‌های بهار، تابستان، پاییز و زمستان متغیر فرض شده است؛ در نتیجه تعداد دوره‌های زمانی (t) در این مثال برابر با چهار است. به علاوه، برای فصل‌های بهار و پاییز میزان کل جریان تقریبا مشابه و به ترتیب برابر با % ۵۷ / ۲۵ و % ۵۴ / ۲۳ است. با توجه به تعطیلات قابل پیش بینی در تابستان، بیشترین مراودات در این فصل قرار می‌گیرد که برابر با % ۵۵ / ۳۳ و با توجه به سرمای زمستان، سهم این فصل %۳۴ / ۱۷ است. تعداد محورها (p) برای هر دوره یکسان و برابر با ۳ گرفته می‌شود.

مجموعه گره‌هایی که پتانسیل محور شدن را دارند، متناسب با درصد جریان عبوری در آن گره از کل جریان مسافران در شبکه حمل و نقل هوایی کشور انتخاب می‌شوند. برای مثال، سهم تهران از حمل و نقل هوایی در کشور ٥٨٦ /٣٩ درصد است که پر ترددترین فرودگاه را دارد و سهم اصفهان، ١٠٥/٥ درصد است که در رتبه پنجم از نظر سهم ترافیک است. به همین ترتیب، رتبه تمام فرودگاه‌ها به صورت نزولی مرتب می‌شود و مجموعه گره‌هایی که می‌توانند محور شوند را مشخص می‌کند.

در این مساله از دو روش حل دقیق و الگوریتم فراابتکاری برای حل مدل استفاده شد. از نرم افزار لینگو^{^[31]} برای حل بهینه مساله و برای روش فراابتکاری، الگوریتم شبیه‌سازی تبرید^{^[32]} در نرم افزار متلب^{^[33]} برنامه نویسی شد که بر روی یک رایانه شخصی با پردازنده AMD Athlon 64X2 Dual (2.60GHz) و رم 2GB اجرا شد و حداکثر زمان مجاز برای اجرای برنامه ها ۴۰ ساعت منظور شد. در ادامه، پس از مروری بر الگوریتم شبیه سازی تبرید، نتایج عددی حل مدل بررسی می‌شود.

الگوریتم شبیه سازی تبرید (SA)

این الگوریتم به این شکل عمل می‌کند که در هر دما از ذوب شدن، تعداد معینی جواب برای دوره اول تولید می‌شود و بهترین جواب آن به دوره دوم منتقل می‌شود. سپس تعداد معینی جواب برای دوره دوم تولید می‌شود و ...؛ این روند آنقدر ادامه می‌یابد تا برای تمام دوره‌ها انجام شود. پس از آن، مقدار تابع هدف کل که از جمع تابع هدف‌های دوره‌های گوناگون به دست می‌آید، در صورت بهتر شدن پذیرفته می‌شود. این حلقه تا رسیدن دمای ذوب به دمای انجماد تکرار می‌شود. الگوریتم(1) زیر جزئیات بیشتری را به نمایش می‌گزارد. اکنون، مقدار در نظر گرفته شده برای پارامترهای الگوریتم بررسی می‌شود. برای دمای انجماد مقدار ۱/.۰ و نرخ انجماد مقدار ۹۵/.۰ قرار داده شد که مقادیر پیشنهاد شده در اکثر کتاب‌ها و مقالات معتبر است. البته، نرخ انجماد با دو مقدار ۹۸/۰ و ۹/.۰ نیز آزمایش شد که به ترتیب به علت افزایش ناگهانی در زمان حل مساله و مقدار نامناسب تابع هدف مقبول واقع نشده است. برای دو پارامتر مهمتر در این الگوریتم، دمای ذوب و تعداد تولید جواب شدنی در هر دما، مقادیر به صورت صعودی آزموده شد که در هر دو، روند افزایش مقادیر با افزایش ناگهانی زمان حل مساله و همین طور مقادیر کم با مقادیر ضعیف برای تابع هدف همراه بوده است. جدول(4) مقادیر آزمایش شده و جدول(5) نتایج حاصل از حل مساله را در اندازه‏های ۱۱، ۲۰ و ۳۲ نشان می‌دهد

الگوریتم (1): شبیه سازی تبرید به‏کار رفته برای مدل پویای مسئله مکان یابی میانه محور

۱	قدم ۱	مقدار دهی اولیه پارامترهای الگوریتم؛
۲	قدم ۲	تا وقتی که	دمای ذوب (T) بیشتر از دمای انجماد (T_f) است
۳	قدم ۳		برای	تعداد (n) تولید جواب شدنی در دوره اول: تولید جواب جدید و محاسبه مقدار تابع هدف جدید
۴				پذیرش مقدار تابع هدف جدید مطابق با ساختار کلاسیک الگوریتم شبیه سازی تبرید
۵			تولید جواب شدنی اولیه برای دوره دوم به وسیله جواب نهایی به دست آمده در دوره اول
۶			برای		تعداد (n) تولید جواب شدنی در دوره دوم: تولید جواب جدید و محاسبه تابع هدف جدید
۷					پذیرش مقدار تابع هدف جدید مطابق با ساختار کلاسیک الگوریتم شبیه سازی تبرید
۸			تولید جواب شدنی اولیه برای دوره سوم به وسیله جواب نهایی به دست آمده در دوره دوم
۹			برای		تعداد (n) تولید جواب شدنی در دوره سوم: تولید جواب جدید و محاسبه تابع هدف جدید
۱۰					پذیرش مقدار تابع هدف جدید مطابق با ساختار کلاسیک الگوریتم شبیه سازی تبرید
۱۱			تولید جواب شدنی اولیه برای دوره چهارم به وسیله جواب نهایی به دست آمده در دوره سوم
۱۲			برای		تعداد (n) تولید جواب شدنی در دوره چهارم: تولید جواب جدید و محاسبه تابع هدف جدید
۱۳					پذیرش مقدار تابع هدف جدید مطابق با ساختار کلاسیک الگوریتم شبیه‌سازی تبرید
۱۴			محاسبه مقدار تابع هدف کل (جمع چهار مقدار پذیرفته شده تابع هدف برای دوره‌های اول تا چهارم)
۱۵			اگر		تابع هدف بهتر شد آنگاه پذیرش مقدار جدید
۱۶	قدم ۴	در صورت کمتر بودن دمای ذوب از دمای انجماد، توقف کنید؛ در غیر این صورت کاهش دمای ذوب و رفتن به قدم ۲

.جدول(4): مقادیر آزمایش شده برای تنظیم پارامترهای الگوریتم شبیه سازی تبرید
ارامترهای الگوریتم	جواب ضعیف	مقدار مناسب	زمان حل زیاد
دمای ذوب (T)	کمتر از ۵	۱۰ – ۵	۱۰۰۰ – ۲۰
تعداد تولید جواب (n)	کمتر از ۳۰	۵۰ –۳۰	۷۰ و بیشتر
نرخ انجماد (r_f)	۹ /۰ و کمتر	۹۵ /۰	۹۸ /۰ و بیشتر

جدول(5): نتایج حل مدل برای اندازه‏های گوناگون مساله محور پویای میانه فرودگاه‌های کشور

تعداد گره‌ها (n)	مقدار تابع هدف		زمان (ثانیه)
جواب بهینه		١٠٣٥٤١٢٧٢٨		٤٥٣
الگوریتم شبیه سازی تبرید		۱۰۳۷۷۷۹۵۸۴		۶ /۷۱
جواب بهینه		١٢٦١٦٥٧٧٣٩		٢٦ ساعت و ٤٥ دقیقه
الگوریتم شبیه سازی تبرید		۱۳۳۷۱۴۸۱۶۱		۵ / ۲۴۰
جواب بهینه		غیر قابل حل		بالای ٤٠ ساعت
الگوریتم شبیه سازی تبرید		۸۶۶۴۸۷۱۷۰۹		۱۸۸۰

شکل (1): نمونه ای از شبکه حمل و نقل هوایی ایران برای مدل پیشنهادی در دوره‌های زمانی گوناگون با تعداد 32 شهر

شکل(1) بخشی از شبکه ارتباطی حاصل از حل مساله را به نمایش می‌گذارد. همان طور که می‌توان دید، محورها برای دوره‌های اول، سوم و چهارم یکسان و شامل شهرهای تهران، مشهد و اصفهان است. اما در دوره دوم یک جابه‌جایی در انتخاب محورها رخ داده به طوری که در آن شیراز به جای اصفهان در حالت محور قرار گرفته است. برای نمایش گره‌های غیرمحور از شهرهای تبریز، اهواز، بندرعباس و زاهدان استفاده شد. برای مثال، مسافران اهواز در حال عبور از محورهای اصفهان و تهران، با دو توقف به تبریز و با یک توقف در اصفهان، به زاهدان سفر می‌کنند که البته، برای دوره دوم شیراز جای اصفهان را می‌گیرد. ضمنا در بیشتر سفرهای بین المللی خطوط هوایی، محورهای بین المللی کشورها، در ورود اولیه (نخستین مقصد) قرار می گیرد و در بیشتر موارد با دو توقف در محورها همراه است

۴.-تحلیل بیشتر

در قسمت اول مطالعه عددی، اندازه‌های گوناگون برای تعداد دوره زمانی در افق برنامه‌ریزی بررسی شده است. چهار اندازه ۱، ۲، ۳ و ۴ برای دوره‌های زمانی اجرا شد. در حالت اول که تعداد دوره‌ها برابر با یک است، همان حالت مرسوم در تشکیل شبکه محور است که تاکنون تمام تحقیقات مساله محور حول این حالت انجام شده است. برای دو دوره زمانی، داده‌های جریان با نسبت های ۵۹ و ۴۱ درصد به ترتیب برای دوره‌های اول و دوم جاری است و در دوره زمانی سه تایی، جریان در دوره‌های اول، دوم و سوم به ترتیب دارای درصدهای ۴۲، ۳۲ و ۲۶ از سهم کل جریان هستند. نسبت‌های دوره زمانی چهارتایی، همان درصدهای ارائه شده در ابتدای بخش قبل است.

جدول(6) نتایج حاصل از حل مساله را در تعداد متفاوت دوره‌های افق برنامه‌ریزی نشان می‌دهد. در اولین نگاه می‌توان دید که همگام با افزایش تعداد دوره‌های زمانی، مقدار تابع هدف کاهش می‌یابد، اما مقدار کاهش محسوس در تابع هدف برای یک تعداد دوره خاص رخ نداده است. علاوه بر این، مقادیر تابع هدف حاصل از مساله تخصیص چندگانه، کمتر از مساله تخصیص یگانه است و این کاهش همواره برقرار است، چراکه مساله تخصیص یگانه دارای محدودیت‌های بیشتری است و پیچیده‌تر از حالت تخصیص چندگانه است. درصد فاصله تابع هدف هم بر مبنای مساله اول که همان مساله مکان‌یابی میانه محور است، محاسبه می‌شود. بدین ترتیب که:

OF_t₌₁

مقدار تابع هدف برای تک دوره

OF_t_=i

مقدار تابع هدف برای تعداد دوره i

%GAP

درصد فاصله تابع هدف ها از تابع هدف

دوره اول

%GAP =	OF_t=1 - OF_t=i	۱۰۰ ×	(۱۲)
	OF_t=1

در اولین نگاه می توان دید که همگام با افزایش تعداد دوره های زمانی، مقدار تابع هدف کاهش می یابد. مقدار کاهش محسوس در تابع هدف برای تعداد دوره خاصی اتفاق نمی افتد و شاید بتوان پیش بینی کرد که با ادامه این روند به مقادیر بهتری برای تابع هدف رسید اما نباید از زمان حل مسئله و اندازه منطقی و عملی برای تعداد دوره های زمانی نیز غافل شد.

در قسمت دوم مطالعه محاسباتی، نتایج حل مدل برای گروه های گوناگون مساله در جدول(7) آمده است. در این مساله، هزینه جانمایی برای تمام گره‌های دارای پتانسیل محور شدن F_k)) و هزینه حذف کردن محورهای ایجاد شده (F’_k) به طور برابر و یکسان (صفر قرار دادن هزینه ها برای راحتی در محاسبات) فرض می‌شود. آزمایش عددی شامل تعداد ۲۴ گروه مساله است که در آن مجموعه گره‌های قابل محور شدن (m) اعداد ۵، ۸ و ۱۲، نرخ تخفیف برای عبور از بین محورها (α) اعداد ۲ / ۰، ۵ / ۰ و ۸ / ۰ و تعداد محورها (p) اعداد ۲، ۳ و ۵ را اختیار می‌کنند. سه ستون اول (از چپ) در جدول(7)، به ترتیب مقادیر α، m و p را نشان می‌دهد. در چهار ستون بعد، مکان‌های انتخاب شده محور برای هر دوره زمانی تحت عنوان محورها در هر دوره آمده است. دو ستون آخر هم به ترتیب مقدار تابع هدف در هر مساله و زمان (دقیقه) لازم برای حل را نمایش می‌دهد.

	جدول(6): تحلیل حساسیت تعداد دوره‌های زمانی در مساله محور پویای میانه برای فرودگاه‌های کشور
	مقدار تابع هدف با تخصیص چندگانه	درصد فاصله تابع هدف با تخصیص چندگانه از حالت تک دوره ای	مقدار تابع هدف با تخصیص یگانه
۸۹۳۲۴۴۹۵۴۷		۰	۸۹۷۷۱۱۱۷۹۵
۸۸۳۳۲۲۵۸۵۷		۱۱ /١	۸۸۷۷۳۹۱۹۸۶
۸۷۲۸۸۲۹۴۹۲		۲۸/۲	۸۷۷۲۴۷۳۶۳۹
۸۶۶۴۸۷۱۷۰۹		۹۹ /۲	۸۷۰۸۱۹۶۰۶۸

نتایج آزمایشات انجام شده اطلاعات مناسبی در زمینه چگونگی تشکیل شبکه ارائه می دهد. به منظور نشریح این مطلب از چندین ساختار شبکه برای مقادیر مختلف α و p بهره برده می شود. از دوره دوم در افق برنامه ریزی برای نمایش شبکه ها استفاده می شود چراکه دارای بیشترین سهم از جریان کل داده ها است شکل(4) تغییراتساختاری انتخاب شده در شبکه را برای مقادیرگوناگون نرخ تخفیف نشان می‌دهد وقتی که p مقدار ثابت ۳ را دارد. در تمام موارد گره‌های ۱۶ (مشهد) و ۲۶ (تهران) به عنوان محور انتخاب شده‌اند. به علاوه، همان طور که می‌توان دید، با افزایش مقدار نرخ تخفیف، انتخاب مکان محورها در شبکه به یکدیگر نزدیکتر می‌شود. شکل(3)، تفاوت در ساختار شبکه را برای مقدار ثابت α و مقادیر خواسته شده برای p را نشان می‌دهد. علاوه براین، می‌توان دریافت که در تمام حالت‌ها، گره ۲۶ (تهران) در حالت محور قرار گرفته است. سرانجام، برای همه مقادیرگوناگون α و p ، گره ۲۶ برای محور شدن انتخاب می‌شود که البته، یکی از پرترافیک‌ترین گره‌ها از نظر جریان ورودی و خروجی است.

نکته دیگر اینکه مقدار تابع هدف با افزایش تعداد محورها، کاهش می‌یابد. نتیجه به دست آمده به این دلیل است که در تعداد بیشتر برای p، از گزینه‌های بیشتری برای برآورده‌سازی تقاضاها استفاده می‌شود که به دنبال آن، نقش فاکتور نرخ تخفیف پررنگتر می‌شود. ادامه این روند هم با ادامه کاهش در هزینه کل همراه است زیرا فارق از بحث مساله مکان‌یابی محور، کمترین مقدار برای هزینه کل در یک شبکه کامل (شبکه‌ای که در آن تمام گره‌ها به یکدیگر مرتبط باشند) به دست می‌آید.

جدول(7): تحلیل حساسیت تغییرات تعداد محور، نرخ تخفیف و تعداد فرودگاه‌های با قابلیت محور بودن
زمان (دقیقه)	تابع هدف	محورها در هر دوره				p	m	α
زمان (دقیقه)	تابع هدف	۴	۳	۲	۱	p	m	α
۲ /۱۵	۴ /۹۶۹۱	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۵	۲ /۰
۹ /۱۹	۰ /۷۸۶۶	۲۶ ،۹ ،۲	۲۶ ،۹ ،۲	۲۶ ،۲۳ ،۹	۲۶ ،۹ ،۲	۳	۵
۵ /۱۸	۵ /۹۷۳۲	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۸
۸ /۱۹	۸ /۷۹۰۷	۲۶ ،۱۶ ،۲	۲۶ ،۲۳ ،۹	۲۶ ،۲۳ ،۹	۲۶ ،۹ ،۲	۳	۸
۰ /۱۸	۲ /۶۷۹۷	۲۶ ،۲۳ ،۱۶ ،۹ ،۲	۲۶ ،۲۳ ،۱۶ ،۹ ،۲	۲۶ ،۲۵ ،۲۳ ،۱۶ ،۹	۲۶ ،۲۵ ،۲۳ ،۱۶ ،۹	۵	۸
۱ /۲۳	۲ /۹۷۶۳	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۱۲
۷ /۲۳	۵ /۸۱۷۳	۲۶ ،۱۴ ،۹	۲۶ ،۲۳ ،۲	۲۶ ،۱۳ ،۲	۲۶ ،۱۳ ،۹	۳	۱۲
۱ /۲۱	۶ /۷۰۴۹	۲۶ ،۲۳ ،۱۶ ،۱۴ ،۹	۲۶ ،۲۳ ،۱۶ ،۱۴ ،۹	۲۶ ،۲۳ ،۱۶ ،۱۴ ،۹	۲۶ ،۲۵ ،۱۶ ،۹ ،۲	۵	۱۲
۸ /۱۵	۹ /۱۰۳۳	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۵	۵ /۰
۱ /۱۶	۰ /۹۰۴۹	۲۶ ،۲۳ ،۲	۲۶ ،۱۶ ،۲	۲۶ ،۱۶ ،۲	۲۶ ،۱۶ ،۹	۳	۵
۲ /۱۹	۰ /۱۰۳۸	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۸
۳ /۱۹	۰ /۹۱۰۹	۲۶ ،۲۳ ،۹	۲۶ ،۲۳ ،۲	۲۶ ،۹ ،۲	۲۶ ،۹ ،۲	۳	۸
۱ /۱۷	۰ /۹۴۴۵	۲۶ ،۲۳ ،۱۶ ،۹ ،۲	۲۶ ،۲۳ ،۱۶ ،۹ ،۲	۲۶ ،۲۵ ،۱۶ ،۹ ،۲	۲۶ ،۲۳ ،۱۶ ،۱۳ ،۹	۵	۸
۸ /۲۲	۲ /۱۰۳۶	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۱۲
۴ /۲۳	۱ /۹۱۹۷	۲۶ ،۱۶ ،۹	۲۶ ،۱۶ ،۹	۲۶ ،۱۶ ،۲	۲۶ ،۱۶ ،۹	۳	۱۲
۷ /۲۱	۲ /۱۰۲۸	۲۶ ،۱۶ ،۱۳ ،۹ ،۲	۲۶ ،۲۵ ،۱۴ ،۹ ،۲	۲۶ ،۲۵ ،۲۳ ،۱۳ ،۹	۲۶ ،۲۵ ،۱۶ ،۹ ،۲	۵	۱۲
۰ /۱۶	۳ /۱۰۹۸	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۵	۸ /۰
۲ /۱۶	۱ /۱۰۱۷	۲۶ ،۹ ،۲	۲۶ ،۱۶ ،۹	۲۶ ،۲۳ ،۹	۲۶ ،۹ ،۲	۳	۵
۷ /۱۸	۴ /۱۱۰۰	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۸
۱ /۲۱	۰ /۱۰۲۴	۲۶ ،۱۶ ،۹	۲۶ ،۱۶ ،۲	۲۶ ،۱۶ ،۹	۲۶ ،۱۳ ،۹	۳	۸
۶ /۱۷	۱ /۱۲۰۴	۲۶ ،۲۳ ،۱۶ ،۹ ،۲	۲۶ ،۲۳ ،۱۳ ،۹ ،۲	۲۶ ،۲۳ ،۱۳ ،۹ ،۲	۲۶ ،۲۳ ،۱۶ ،۹ ،۲	۵	۸
۵ /۲۲	۱ /۱۱۰۵	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲۶ ،۹	۲	۱۲
۴ /۲۴	۲ /۱۲۷۰	۲۶ ،۹ ،۲	۲۶ ،۹ ،۲	۲۶ ،۱۶ ،۹	۲۶ ،۲۳ ،۹	۳	۱۲
۴ /۲۱	۷ /۱۰۳۹	۲۶ ،۲۳ ،۱۶ ،۹ ،۲	۲۶ ،۲۵ ،۲۳ ،۱۶ ،۹	۲۶ ،۲۵ ،۱۶ ،۹ ،۲	۲۶ ،۲۵ ،۲۳ ،۹ ،۲	۵	۱۲
* واحد اعداد در تابع هدف ۱۰^۶× است.

(۸ /۰ = α ، ۳ = p) (۵ /۰ = α ، ۳ = p) (۲ /۰ = α ، ۳ = p)

شکل(2): شبکه‌های حاصل از حل مساله برای مقادیر متفاوت α

	(۵ /۰ = α ، ۵ = p)	(۵ /۰ = α ، ۳ = p)	(۵ /۰ = α ، ۲ = p)
شکل(3): شبکه‌های حاصل از حل مساله برای مقادیر متفاوت p

۵. –نتیجه‏ گیری

در این مقاله، به مطالعه یک مدل پویا برای مساله مکان‌یابی میانه محور با تخصیص چندگانه پرداخته شده است. در مساله بحث شده، جریان برای دوره‌های زمانی گوناگون در افق برنامه‌ریزی تغییر می‌کند. تعداد محورها در هر دوره معلوم است؛ به طوری که امکان باز کردن و بستن محورها در دوره‌های زمانی وجود دارد. از الگوریتم شبیه‌سازی تبرید برای حل این مدل استفاده شده است که با داده‌های خطوط هوایی ایران با ۳۲ گره (شهر)، آزمایش می‌شود. همچنین، مدل پویا با اندازه‌های گوناگون برای تعداد دوره‌های زمانی در افق برنامه‌ربزی حل شد و نتایج آن با حالت ایستا مقایسه گردید. نتایج بررسی نشان می‌دهد که تشکیل شبکه پویا در مقایسه با حالت ایستا، هزینه کمتری در پی خواهد داشت و هرچه تعداد دوره‌های زمانی در حالت پویا بیشتر شود، بهبود بهتری در مقدار تابع هدف ایجاد می‌گردد.

در بحث تحقیقات آتی این مساله، می‌توان بر روی نوع تخصیص مدل متمرکز شد و از تخصیص یگانه استفاده کرد که برای مثال، می‌تواند در سیستم‌های ارسال کالاهای پستی آزمایش شود. همچنین، می‌توان برای مدل، محدودیت ظرفیت را اعمال کرد و حتی ظرفیت متغیر برای محورها در نظر گرفت.

[1]. Hub Location Problems (HLP)

[2]. Single allocation

[3]. Multiple allocation

[4]. O'Kelly

[5]. Campbell

[6]. Skorin-Kapov et al.

[7]. Ernst and Krishnamoorthy

[8]. Ebery

[9]. Sasaki et al.

[10]. Marin et al.

[11]. Klincewicz

[12]. Silva and Cunha

[13]. Llic et al.

[14]. Alumur and Kara

[15]. Sung and Jin

[16]. Aykin

[17]. Pirkul and Schilling

[18]. Yaman

[19]. Abdinnour-Helm

[20]. Kratica et al.

[21]. Daskin et al.

[22]. Andreatta and Mason

[23]. Drezner

[24]. Chardaire et al.

[25]. Canel and Khumawala

[26].. Saldanha da Gama and Captivo

[27]. Hakimi et al.

[28]. Canel and Das

[29]. Dias et al.

[30]. Behmardi and Lee

[31]. Lingo

[32]. Simulated annealing

[33]. MATLAB

مراجع

Abdinnour- Helm, S. (2001). "Using simulated annealing to solve the p- hub median problem". International Journal of Physical Distribution & Logistics Management, 31(3), 203-220.

Alumur, S. A., & Kara, B. Y. (2008). "hub location problems: The state of the art". European Journal of Operational Research, 190, 1–21.

Andreatta, G., & Mason, F.M., (1994). "A note on: A perfect forward procedure for a single facility dynamic location/relocation problem". Operations Research Letters, 15(2), 81-83.

Aykin, T. (1994)." Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem". European Journal of Operational Research, 79, 501-523.

Bastian, M., & Volkmer, M. (1992). "A perfect forward procedure for a single facility dynamic location/relocation problem". Operations Research Letters, 12(1), 11-16.

Behmardi, B., & Lee, S. (2008). "Dynamic multi-commodity capacitated facility location problem in supply chain". Proceedings of the 2008 industrial engineering research conference 1914–1919.

Campbell, J. F. (1992). "Location and allocation for distribution systems with transshipments and transportation economies of scale". Annals of Operations Research, 40, 77-99.

Campbell, J. F. (1994). "Integer programming formulations of discrete hub location problems". European Journal of Operational Research, 72, 387-405.

Campbell, J. F. (1996). "Hub location and P-hub median problem". Operational Research, 44(6), 923-935.

Campbell, J. F., Ernst, A. T. & Krishnamoorthy, M. (2002). "Hub location problems, In Z. Drezner & H. W. Hamacher (Eds)". Facility location application and theory, 373-408 Heidelberg: Springer.

Canel, C., & Khumawala, B. M. (1996). "A mixed-integer programming approach for the international facilities location problem". International Journal of Operations & Production Management, 16(4), 49-68.

Canel, C., & Das S. R. (1999). "The uncapacitated multi-period facilities location problem with profit maximization". International Journal of Physical Distribution & Logistics Management, 29(6), 409-433.

Chardaire, P., Sutter, A., & Costa, M. C. (1996). "Solving the dynamic facility location problem". Networks, 28(2), 117-124.

Daskin, M.S., Hopp, W. J., & Medina, B. (1992)." Forecast horizons and dynamic facility location planning". Annals of Operations Research, 40(1), 125-151.

Dias, J., Captivo M.E., & Climaco, J. (2001). "Capacitated dynamic location problems with opening, closure and reopening of facilities". Research report, INESC-Coimbra, Lisboa, Portugal.

Drezner, Z. (1995). "Dynamic facility location: The progressive p-median problem". Location Science, 3(1), 1-7.

Ernst, A.T., & Krishnamoorthy, M. (1996). "Efficiant algorithms for the uncapacitated single allocation p-hub median problem". Location Science, 4, 139-154.

Ernst, A.T., & Krishnamoorthy M. (1998a). "Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem". European Journal of Operational Research, 104, 100-112.

Ernst, A.T., & Krishnamoorthy, M. (1998b). "An exact solution approach based on shortest-paths for p-hub median problems". Informs Journal on Computing, 10(2), 149-162.

Hakimi, S. L., Labbe, M., & Schmeichel, E. F. (1999). "Locations on time-varying networks". Networks, 34(4), 250-257.

Karimi, H., & Bashiri, M. (2011). "Hub covering location problems with different coverage types". Scientia Iranica, (Accepted Paper).

Klincewicz, J.G. (1991). "Heuristics for the P-hub location problem". European Journal of Operational Research, 53, 25-37.

Klincewicz, J. G. (1992). "Avoiding local optima in the P-hub location problem using tabu search and grasp". Annals of Operations Research, 40, 283-302.

Klincewicz, J. G. (2002). "Enumeration and search procedures for a hub location problem with economies of scale". Annals of Operations Research, 110, 107-122.

Kratica, J., Stanimirovic, Z., Tosic, D., & Filipovic, V. (2007). "Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem". European Journal of Operational Research, 182, 15-28.

Ilic, A., Urosevic, D., Brimberg, J., & Mladenovic, N. (2010). "A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem". European Journal of Operational Research, 206, 289–300.

Marin, A., Canovas, L., & Landete, M. (2006). "New formulations for the uncapacitated multiple allocation hub location problem". European Journal of Operational Research, 172(1), 274-292.

O'Kelly, M. E. (1987). "A quadratic integer program for the location of interacting hub facilities". European Journal of Operational Research, 32, 393-404.

Pirkul, H., & Schilling, D. A. (1998). "An efficient procedure for designing single allocation hub and spoke systems". Management Science, 44(12), 235-242.

Saldanha da Gama, F., & Captivo, M. E. (1998). "A heuristic approach for the discrete dynamic location problem". Location Science, 6(1), 211-223.

Sasaki, M., Suzuki, A., & Drezner, Z. (1999). "On the selection of hub airports for the airline hub-and-spoke system". Computers & OR, 26, 1411-1422.

Silva, M. R., & Cunha, C. B. (2009). "New simple and efficient heuristics for the uncapacitated single allocation hub location problem". Computers & Operations Research, 36, 3152–3165.

Skorin-Kapov, D., & Skorin-Kapov, J. (1994). "On Tabu search for the location of interacting hub facilities". European Journal of Operational Research, 73, 502-509.

Skorin-Kapov, D., Skorin-Kapov, J., & O'Kelly, M. (1996)." Tight linear programming relaxations of uncapacitated p-hub median problems". Proc Natl Decis Sci Conf, Boston, (94), 582-593.

Sung, C.S., & Jin, H. W. (2001). "Dual-based approach for a hub network design problem under non-restrictive policy". European Journal of Operational Research, 132, 88- 105.

Yaman, H. (2008). "Star P-hub median problem with modular arc capacities". Computers and Operational Research, 35(9), 3009-3019

آمار

تعداد مشاهده مقاله: 3,283

تعداد دریافت فایل اصل مقاله: 1,923

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

بررسی و حل مدل پویا برای مساله مکان‌یابی میانه محور با تخصیص چندگانه