قید 12 : همه متغیر ها با نام های y , z , p به ازای همه اندیس ها متغیر صفر و یک (باینری) اند.
فصل چهارم
روش حل و نتایج محاسباتی
4-1- مقدمه
همان طور که گفته شد تاکنون بارها از الگوریتم ژنتیک برای حل مسائل طراحی شبکه زنجیره تأمین دو و سه مرحله ای استفاده شده است. یکی از مهم ترین قسمت ها در حل یک مسئله با الگوریتم ژنتیک چگونگی کد کردن آن مسئله است که می تواند دشوارترین بخش کار هم باشد. تاکنون سه روش برای کدگذاری مسائل شبکه زنجیره تأمین ارائه شده است :

  • Edge-based encoding ( Gen&cheng,)[26]
  • Vertex-based encoding ( Gen&Cheng,)[26]
  • Edge-and-Vertex encoding ( Palmer& Kershenoaum,)[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+K+K+J+J+I ژن برای نمایش سه مرحله شبکه استفاده می شود. در روش اولویت محور[11] از یک کروموزوم با طول S+K+K+J+I ژن برای نشان دادن مراحل شبکه زنجیره تأمین سه مرحله ای تک محصوله استفاده می شود. در شبکه زنجیره تأمین سه مرحله ای چند محصوله برای نمایش مرحله سوم شبکه از I ژن، برای نمایش مرحله دوم شبکه از L(K+J) ژن و برای نمایش مرحله اول از R(S+K) ژن استفاده می کنیم.
4-2- روش کدگذاری اولویت محور[79]
در حل مسائل طراحی شبکه زنجیره تأمین سه مرحله ای به روش اولویت محور، هر کروموزوم از سه بخش تشکیل شده است که هر بخش یک مرحله از شبکه را در بر می گیرد. در واقع 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 ژن استفاده می شود. کد گشایی کروموزوم شبکه زنجیره تأمین از انتها به ابتدا صورت می گیرد. یعنی ابتدا مرحله 3 کدگشایی شده، بعد از آن مرحله 2 و در آخر مرحله 1 کدگشایی می شود.
در ابتدا مسیر حمل و نقل میان مراکز توزیع باز شده و مشتریان مشخص می شود که این اتفاق با کدگشایی مرحله آخر صورت می پذیرد، در قدم بعدی تصمیم گرفته می شود که کدام کارخانه ها باید باز شوند سپس مسیر حمل و نقلی مشخص