به آن می پردازیم :
۱) هزینه ایجاد کارخانه ها :
CC=∑_(k=k)^K▒g_k p_k
۲) هزینه ایجاد مراکز توزیع :
CC=∑_(j=j)^J▒〖v_j z_j 〗

۳) هزینه خرید و حمل و نقل کل مواد اولیه از تأمین کنندگان به کارخانه ها :
CC=∑_(s=s)^S▒∑_(k=k)^K▒∑_(r=r)^R▒〖t_skr b_skr 〗
۴) هزینه تولید و حمل و نقل کل محصولات از کارخانه ها به مراکز توزیع :
CC=∑_(k=k)^K▒∑_(j=j)^J▒∑_(l=l)^L▒〖a_kjl f_kjl 〗
۵) هزینه توزیع و حمل و نقل کل محصولات از مراکز توزیع به مشتریان :
CC=∑_(i=i)^I▒∑_(j=j)^J▒∑_(l=l)^L▒〖c_ijl q_ijl 〗
هزینه کل شبکه مجموع این پنج هزینه می باشد و ما این حاصل جمع را TC می نامیم که مخفف عبارت Total Cost به معنی هزینه کل است :
Min TC=CM+C++C++C++C+
در بخش ۳-۲ معیاری به نام deg برای میزان تأمین نیاز مشتری معرفی کردیم که به صورت حاصل تقسیم مساحت S (شکل ۳-۲) بر مساحت کل ذوزنقه، Area بود. حال اگر برای هر مشتری i و هر محصول l مقادیر S_il و Area_il را داشته باشیم می توانیم درجه تأمین تقاضای همه مشتریان DEG را به صورت زیر تعریف کنیم :
DEG=(∑_(i=i)^I▒∑_(l=l)^L▒S_il )/(∑_(i=i)^I▒∑_(l=l)^L▒Area_il )
این کمیت مقداری بین صفر و یک اختیار می کند و هرچه مقدار آن به یک نزدیکتر باشد میزان تأمین تقاضای مشتریان نیز بیشتر است. در نتیجه هدف دوم ما بیشینه کردن آن می باشد :
Max DEG
حال باید این دو تابع هدف را ترکیب کرده و به صورت یک هدف درآوریم تا بتوانیم مسئله را حل کنیم. در اینجا ما به دو طریق این کار را انجام داده ایم و هر دو حالت را به صورت جداگانه حل نموده و نتایج حاصل را مقایسه کرده ایم. در ابتدا توابع هدف را نرمال سازی می کنیم :
همان طور که قبلا بیان کردیم هدف DEG مقداری بین صفر و یک اختیار می کند، برای راحتی کار این مقدار را در عدد صد ضرب می کنیم تا بتوانیم میزان تأمین تقاضای مشتری را به صورت درصد بیان کنیم، پس تعریف می کنیم :
DEG%=DDD×DEG
جهت نرمال سازی TC ابتدا بـه دو کران بالا و پایین بـرای آن احتیاج داریم. ایـن دو کران را می توانیم برای مقدار بهینه آن به ازای تقاضاهای مختلف مشتریان بدست آوریم. برای این کار لازم است دوبار مسئله را در حالت قطعی (غیر فازی) به صورت زیر حل نموده و مقادیر بهینه TC را بدست آوریم :
ابتدا به ازای همه مقادیر i , l قرار می دهیم : d_il=〖dd〗_il یعنی همه تقاضاها را برابر با کمترین مقدار ممکن آنها قرار می دهیم و مقدار کمینه TC را در این حالت lower_bnd می نامیم. به همین ترتیب بار دیگر مسئله قطعی را به ازای d_il=〖dd〗_il برای همه مقادیر i , l یعنی بیشترین مقادیر ممکن برای تقاضاها حل می کنیم و مقدار کمینه بدست آمده برای TC را upper_bnd نامگذاری می نماییم. اکنون برای هر مقادیر دلخواهی که d_il ها اختیار کنند مقدار کمینه TC عددی در بازه بسته [lower_bnd,upper_bnd] خواهد بود. لازم به دقت است که این کران ها ، کران هایی برای مقدار کمینه TC به ازای تقاضاهای مختلف مشتریان است و نه برای خود مقدار آن، اما چون مسئله در جهت کمینه سازی TC حرکت می کند، بعد از تکرار های کافی سرانجام مقدار TC نیز در این بازه قرار می گیرد. پس برای نرمال سازی TC می توانیم به صورت زیر عمل کنیم :
lower_bnd l TC upper_bnd TC lower_bnd l upper_bnd lower_bnd
(TCTlower_bnd)/(upper_bndu lower_bnd)
×(TCTlower_bnd)/(upper_bnde lower_bnd)
قرار می دهیم :
TC%=TTT×(TCTlower_bnd)/(upper_bndu lower_bnd)
حال دو تابع هدف داریم که هر دوی آنها به شکل متغیری در بازه بسته [[ , ] می باشند و یکی از آنها باید کمینه سازی و دیگری باید بیشینه سازی شوند. در اینجا ما به دو طریق این دو هدف را با هم ترکیب نموده و به طور جداگانه حل کرده ایم.
روش اول :
Max OBM=DEG% = TC%
روش دوم :
Min OBM=TC% = DEG%
۳-۳-۵- محدودیت های مدل
قید ۱ : هر مشتری همه نیاز خود را برای هر محصول فقط از یک مرکز توزیع دریافت می کند :
ق i : ∑_(j=j)^J▒y_ij = =
قید ۲ : تطبیق تعداد محصول ارسال شده از مرکز توزیع با تقاضای مشتری :
ق i j l : q_ijl = d_illy_ij
قید ۳ : محدودیت ظرفیت مراکز توزیع :
ق j : ∑_(i=i)^I▒∑_(l=l)^L▒〖d_il y_ij 〗 W_jjz_j
قید ۴ : حد بالا برای تعداد مراکز توزیع قابل ایجاد :
∑_(j=j)^J▒z_j J
قید ۵ : تضمین حفظ جریان محصولات بین مراحل دوم و سوم شبکه :
ق j l : ∑_(k=k)^K▒f_kjl = ∑_(i=i)^I▒q_ijl
قید ۶ : محدودیت ظرفیت کارخانه ها برای تولید محصولات :
ق k : ∑_(j=j)^J▒∑_(l=l)^L▒f_kjl D_kkp_k
قید ۷ : حد بالا برای تعداد کارخانه های قابل ایجاد :
∑_(k=k)^K▒p_k K
قید ۸ : تضمین حفظ جریان محصولات بین مراحل اول و دوم شبکه :
ق k r : ∑_(j=j)^J▒∑_(l=l)^L▒〖u_rl f_kjl 〗 = ∑_(s=s)^S▒b_skr
قید ۹ : محدودیت ظرفیت تأمین کنندگان برای تأمین مواد اولیه :
ق s : ∑_(k=k)^K▒∑_(r=r)^R▒b_skr E_s
قید ۱۰ : کران بالا و پایین تقاضای مشتریان :
پ i l : 〖dd〗_il d_il 〖dd〗_il
قید ۱۱ : همه متغیرها با نام های d , q , f , b به ازای همه اندیس ها صحیح نامنفی اند.
قید ۱۲ : همه متغیر ها با نام های y , z , p به ازای همه اندیس ها متغیر صفر و یک (باینری) اند.

فصل چهارم
روش حل و نتایج محاسباتی

۴-۱- مقدمه
همان طور که گفته شد تاکنون بارها از الگوریتم ژنتیک برای حل مسائل طراحی شبکه زنجیره تأمین دو و سه مرحله ای استفاده شده است. یکی از مهم ترین قسمت ها در حل یک مسئله با الگوریتم ژنتیک چگونگی کد کردن آن مسئله است که می تواند دشوارترین بخش کار هم باشد. تاکنون سه روش برای کدگذاری مسائل شبکه زنجیره تأمین ارائه شده است :
Edge-based encoding ( Gen&cheng,EEEE)[26]
Vertex-b
ased encoding ( Gen&Cheng,VVVV)[26]
Edge-and-Vertex encoding ( Palmer& Kershenoaum,EEEE)[34]
اولین پیاده سازی مسائل حمل و نقل و توزیع با استفاده از GA توسط Michalewicz[35] صورت گرفت، او از روش ماتریس محور که تعلق به روش edge-based داشت برای نمایش شبکه تولید و توزیع استفاده کرد. Gen&Li[36] از روش کدگذاری prüfer number برای مسئله حمل و نقل استفاده کردند تا درخت پوشای مسئله را نمایش دهند. این روش جزو روش vertex-based محسوب می شود. شبکه زنجیره تأمین سه مرحله ای تک محصوله توسط Syarif&Gen[37] با استفاده از روش prüfernumber مورد حل قرار گرفته است. روش دیگری که برای حل شبکه زنجیره تأمین به کمک الگوریتم ژنتیک استفاده شد بر پایه کدگذاری اولویت محور بود که توسط Altiparmak&Gen[14] برای حل شبکه زنجیره تأمین تک محصوله با چندین تابع هدف استفاده شد که این روش متعلق به روش edge–based می باشد.
تعریف کروموزوم در روند حل با الگوریتم ژنتیک یکی از مراحل چالش برانگیز است. در مسائل شبکه زنجیره تأمین که از روش کدگذاری prüfer number استفاده می شود، از پنج زیر رشته استفاده می شود، اولین و دومین قسمت این زیر رشته ها شامل ژن هایی برای نشان دادن باز یا بسته بودن کارخانه ها و مراکز توزیع می باشد که به صورت باینری است، سه زیر رشته بعدی برای کدکردن هر یک از مراحل شبکه زنجیره تأمین مورد استفاده قرار می گیرد. در این روش از یک کروموزوم با طول K+J+S+KKK+K+J+++J+I++ ژن برای نمایش سه مرحله شبکه استفاده می شود. در روش اولویت محور[۱۱] از یک کروموزوم با طول S+K+K+J+I ژن برای نشان دادن مراحل شبکه زنجیره تأمین سه مرحله ای تک محصوله استفاده می شود. در شبکه زنجیره تأمین سه مرحله ای چند محصوله برای نمایش مرحله سوم شبکه از I ژن، برای نمایش مرحله دوم شبکه از L(K+J) ژن و برای نمایش مرحله اول از R(S+K) ژن استفاده می کنیم.
۴-۲- روش کدگذاری اولویت محور۷۹
در حل مسائل طراحی شبکه زنجیره تأمین سه مرحله ای به روش اولویت محور، هر کروموزوم از سه بخش تشکیل شده است که هر بخش یک مرحله از شبکه را در بر می گیرد. در واقع x امین بخش یک کروموزوم نشان دهنده x امین مرحله از شبکه است. هر ژن در کروموزوم با دو فاکتور مهم مشخص می شود، یکی لوکاس که بیانگر موقعیت ژن در طول کروموزوم می باشد و دیگری آلل که ارزش نسبت داده شده به آن ژن را بیان می کند. موقعیت هر ژن برای نمایش یک گره از شبکه (تأمین کننده، کارخانه، مرکز توزیع، مشتری) استفاده می شود و ارزش هر ژن به صورت اولویت آن گره برای ایجاد و برقراری ارتباط در شبکه می باشد. برای نشان دادن هر کروموزوم در شبکه تک محصوله، در مرحله اول شبکه از S+K ژن، برای مرحله دوم از K+J ژن و برای نمایش مرحله آخر از I ژن استفاده می شود که مقدار هر ژن نشان دهنده اولویت آن گره در باز شدن و برقراری ارتباط با سایر گره های موجود در شبکه است، در مجموع برای کدکردن کروموزوم هر محصول، از کروموزومی با طول S+K+K+J+I ژن استفاده می شود. برای نمایش کروموزوم شبکه زنجیره تأمین سه مرحله ای چند محصوله از R(S+K) ژن برای نمایش مرحله اول، از L(K+J) ژن برای نمایش مرحله دوم و از I ژن برای نمایش مرحله سوم استفاده می شود. در مجموع برای کدگذاری شبکه زنجیره تأمین سه مرحله ای چند محصوله از R(S+K)+L(K+J)+I ژن استفاده می شود. کد گشایی کروموزوم شبکه زنجیره تأمین از انتها به ابتدا صورت می گیرد. یعنی ابتدا مرحله ۳ کدگشایی شده، بعد از آن مرحله ۲ و در آخر مرحله ۱ کدگشایی می شود.
در ابتدا مسیر حمل و نقل میان مراکز توزیع باز شده و مشتریان مشخص می شود که این اتفاق با کدگشایی مرحله آخر صورت می پذیرد، در قدم بعدی تصمیم گرفته می شود که کدام کارخانه ها باید باز شوند سپس مسیر حمل و نقلی مشخص شده و در قدم آخر که با کدگشایی مرحله اول صورت می گیرد، مسیر حمل و نقلی مواد اولیه به کارخانه های باز شده مشخص می شود. بنابراین توجه به این نکته ضروری است که تصمیمات اصلی شبکه پیرامون اینکه کدامیک از مراکز توزیع و کارخانه ها بایستی باز شوند و کدامیک باید بسته بمانند، در طول کدگشایی مراحل سوم و دوم اتفاق می افتد. بنابراین روند کلی کدگشایی کروموزوم در روش اولویت محور به صورت زیر است که ابتدا سومین مرحله شبکه زنجیره تأمین کدگشایی می شود که در آن مراکز توزیعی که بایستی باز شوند، مشخص می گردد و تقاضای هر مشتری باید توسط تنها یکی از آنها برآورده شود، در این رویه میزان q_ijl مشخص می شود. در مرحله بعد کارخانه هایی که باید باز شوند مشخص می شود و تقاضای مراکز توزیع توسط آنها پاسخ داده می شود، در این مرحله امکان اینکه چند کارخانه با هم به تقاضای یک مرکز توزیع پاسخ دهند، وجود دارد، در این مرحله نیز f_kjl تعیین می شود. در مرحله بعدی مقدار مواد اولیه ای که از هر تأمین کننده به هر کارخانه فرستاده می شود تعیین می گردد، یعنی b_skr بدست می آید و در آخر تابع برازندگی که همان تابع هدف است با بدست آمدن متغیرهای مسئله محاسبه شده و الگوریتم وارد فازهای انتخاب، ترکیب و جهش می شود تا اینکه بعد از تکرارهای مشخصی به جواب بهینه همگرا شود. اکنون به بیان الگوریتم کدگشایی برای مراحل مختلف شبکه زنجیره تأمین می پردازیم :
کدگشایی مرحله سوم :
قبلا در فرضیات مسئله بیان کردیم که هر مشتری همه تقاضای خود را برای محصولات شبکه تنها از یک مرکز توزیع دریافت می کند. این شرط باعث می شود که شکل کروموزوم مربوط به این مرحله و روش کدگشایی آن نسبت به دو مرحله دیگر متفاوت باشد. در اینجا کروموزومی به طول I ژن یعنی به تعداد مشتریان، داریم که یک جایگشت تصادفی از اعداد صحیح مثبت تا I
می باشد.
ورودی های الگوریتم :
I تعداد مشتریان
J تعداد مراکز توزیع
L تعداد محصولات
d ماتریس حاوی تقاضاهای مشتریان
W بردار حاوی ظرفیت های مراکز توزیع
c آرایه سه بعدی حاوی هزینه های توزیع و حمل و نقل واحد محصولات از مراکز به مشتریان
cc ماتریس حاوی هزینه های کل توزیع و حمل و نقل تقاضاها از مراکز به مشتریان با ابعادی برابر با IIJ
vv کروموزوم مرحله سوم
خروجی های الگوریتم :
z بردار صفر و یک برای تعیین باز شدن یا بسته ماندن مراکز توزیع
y ماتریس صفر و یک برای تعیین اینکه هر مشتری از کدام مرکز خرید می کند
q آرایه سه بعدی مقدار خرید هر مشتری از هر محصول از هر مرکز توزیع
M ماتریس تقاضای کل مشتریان از هر محصول روی هر مرکز توزیع
بردار z به ما می گوید کدام یک از مراکز توزیع باز شده اند، ماتریس y نشان می دهد که هر مشتری از کدام مرکز خرید نموده، q می گوید که هر مشتری از هر مرکز توزیع چه مقدار از انواع محصولات را خریداری کرده و ماتریس M حاوی مقادیر نیازهای هر مرکز توزیع به هر یک از انواع محصولات می باشد. z , y , q همان متغیر های مدل مسئله می باشند که قبلا معرفی شده اند و در این مرحله مقادیر آنها مشخص می شود و M یک ماتریس با ابعاد JJL است که برای کدگشایی مرحله دوم مورد نیاز می باشد.
گام ۱ : مقدار دهی اولیه
z=z___J , y= _I_J , q= _IIJJL , M= _JJL
گام ۲ : تا زمانی که vv درایه مثبت دارد یعنی مشتری ای باقی مانده که نیاز او تأمین نشده باشد :
i^*=argmax({v=(i) ( i= ,…,I}) مشتری i^* برای خرید انتخاب می شود و به گام بعد می رویم. در غیر این صورت به گام ۶ می رویم.
گام ۳ : j^*=argmin({cc(i^*,j) , j= ,…,J}) مرکز توزیع j^* به علت