بخشی از مقاله
مدل سازي مسئله مکان يابي متوازن با استفاده از مدل جاذبه روي شبکه و حل آن به کمک يک رويکرد ابتکاري مؤثر
چکيده
در اين مقاله يک مفهوم جديد در حوزه مکان يابي، به نام "مسئله مکان يابي با بار کاري متوازن بر مبناي مدل جاذبه " معرفي شده است . متوازن سازي در جستجوي توزيع عادلانه تقاضا يا برقراري تعادل در ظرفيت تسهيلات هنگام پاسخگويي به تقاضاي مشتريان است ؛ به طوري که آنها تسهيلات را بر اساس معيار مناسب تري مانند قانون جاذبه انتخاب کنند.تابع هدف درصدد کمينه سازي حداکثر بار کاري موجود بين تسهيلات ، هزينه استقرار آنها و هزينه جابه جايي تا مشتريان ، با در نظر گرفتن مدل جاذبه است . در ادامه ، بر اساس ساختار مسئله ، يک رويکرد حل ابتکاري طراحي و روي مثال هاي عددي با ابعاد مناسب با روش دقيق ، تحليل مقايسه اي انجام شده است . نتايج محاسباتي نشان ميدهد که رويکرد حل پيشنهادي، با ميانگين اختلاف تقريبا ٦ درصد و زمان محاسباتي قابل قبول ، روشي بسيار کارآ بوده و جواب هاي نزديک به بهينه را براي مثال هاي تصادفي توليدشده ايجاد ميکند.
واژه هاي کليدي:مکان يابي تسهيلات ، متعادل سازي، قانون جاذبه ، بار متوازن ، الگوريتم ابتکاري، برنامه ريزي عدد صحيح
مقدمه
در طول دهه هاي اخير تلاش فراواني براي ايجاد مدل - هاي مکان يابي که مشخصه هاي بيشتري از دنياي واقعي را در نظر ميگيرند انجام گرفته است . يکي از اين مشخصه ها که در متدولوژيهاي جديد تحقيق در عمليات ظاهر شده ، مفهوم "تعادل " است . مشتريان يک سيستم ، براساس قوانين اجتماعي انتظار رفتار عادلانه دارند. بنابراين تصميمات مکان يابي اين مسائل ميتواند استقرار مراکز در مکان هايي باشد که با در نظر گرفتن معيارهاي خاصي، با کاربران به روشي عادلانه رفتار شود.يک طبقه بندي از اهداف مکان يابي، آنها را براساس مفاهيم فيزيکيِ نيروهاي کششي، فشاري و تعادل به سه دسته تقسيم کرده است :[1]
١- دسته اول اهداف کششي هستند و تمايل دارند به هر طريقي نزديک بودن تسهيلات و نقاط تقاضا را تضمين کنند، مانند حداقل کردن هزينه هاي حمل ونقل يا حداکثرکردن سهم بازار. اکثر تحقيقات انجام گرفته تا اواسط دهه ١٩٦٠،دربرگيرنده اين دسته از اهداف هستند.
اين مدل ها براي مکان يابي تسهيلات مطلوب يا جذاب به کار ميروند. در ميان هزاران مدل بررسيشده ، ميتوان به چهار مدل مکان يابي p-ميانه ، p-مرکز، مکان يابي با ظرفيت نامحدود و تخصيص نمايي اشاره کرد که زماني با عنوان مسائل مکان يابي الگو شناخته ميشدند و همچنان نقش بارزي در اين حوزه ايفا ميکنند.
٢- از دهه ١٩٧٠ محققان به مطالعه مدل هايي پرداختند که در آنها مشتريان خواهان دورکردن تسهيلات و استقرار آنها در دورترين نقطه بودند. اين نوع اهداف با عنوان اهداف فشاري نام گذاري ميشوند و شامل مکان يابي تسهيلات نامطلوب يا زيان آور و مدل هاي پراکندگي است .
٣- سومين دسته از اهداف ، دستيابي به تعادل است . اين مدل ها تلاش ميکنند تسهيلات را طوري مکان يابي کنند که مثلا فواصل نقاط تا حد امکان "مشابه " يکديگر باشند.
مشخصه ديگري که در مکان يابي موردتوجه قرار دارد، نحوه انتخاب خدمت دهنده است . در اينحالت ، اغلب فرض ميشود مشتريان نزديک ترين تسهيل را انتخاب ميکنند.
چنين فرضي (فرض مجاورت )، هنگامي منطقي به نظر مي - رسد که تخصيص تقاضا توسط برنامه ريز انجام گيرد يا تسهيلات به طور مساوي جذاب هستند. در اين صورت ، نزديک ترين تسهيل ، بهترين انتخاب به شمار ميآيد[٥-٢].
دلايل بسياري براي اينکه چرا اين فرض توصيف کننده واقعي رفتار مشتري نيست ، وجود دارد، به عنوان مثال [٦]:
١- تغيير کوچکي در مکان تسهيلات ، ممکن است تقاضاي يک منطقه را به تسهيل ديگري انتقال دهد. اگر نزديک ترين تسهيل در فاصله ٤.٩ مايلي و نزديک ترين تسهيل دوم در فاصله ٥ مايلي باشد، کل تقاضا به تسهيل اول اختصاص مييابد. در حاليکه اگر اولين تسهيل در فاصله ٥.١ مايلي قرار گيرد، کل تقاضا به تسهيل دوم اختصاص مييابد.
٢- تسهيلات جذابيت متفاوت داشته و برخي مشتريان خواهان طي مسافت به تسهيل دورتر، ولي جذاب تر هستند.
٣- مشتريان ، هنگام انتخاب تسهيل به دليل ضرورت فاصله دقيق را اندازه نميگيرند، بلکه تسهيلي را انتخاب ميکنند که احساس ميکنند به آنها نزديک تر است . افراد به احتمال زياد درک متفاوتي نسبت به مسافت ها داشته و تسهيل انتخاب شده توسط آنها يکسان نخواهد بود.
در ادامه ضمن مرور ادبيات مسئله متعادل سازي و مدل جاذبه روي توسعه مدل مکان يابي بارکاري متعادل با در نظر گرفتن معيار جاذبه ، تشريح رويکردهاي حل براي ايجاد جواب ها و ارائه نتايج محاسباتي روي مثال هاي عددي تصادفي به کمک اين رويکردها پرداخته ميشود.
مرور ادبيات
مسئله توازن
تعادل يا توازن اغلب با حداقل کردن آنچه به اصطلاح "معيار توازن " ناميده ميشود، به صورت کمي در ميآيد.
در حاليکه براي دستيابي به "کارآيي و اثربخشي" تقريبا توافق جمعي وجود دارد که "ميانه و مرکز" به ترتيب معمول ترين توابع هدف مورد استفاده اند، به نظر ميرسد توافق خاصي در به کارگيري يک معيار مناسب براي "متعادل سازي" وجود ندارد. بنابراين توابع زيادي را ميتوان در ادبيات يافت که توازن يا عدم توازن را محاسبه ميکنند. به عنوان مثال ، مارش و شلينگ ٢٠ معيار متفاوت براي اندازه گيري ميزان متعادل بودن سناريوهاي مختلف مسئله مکان يابي تسهيلات ارائه کردند [٧] وايسِلت و لاپورته بحث جالبي در رابطه با نحوه انتخاب معيار توازن نشريه تخصصي مهندسي صنايع , دوره ٤٥ ، شماره ٢، مهر ماه ١٣٩٠ متناسب با مسئله انجام دادند[٨]. جدول (١) معيارهاي معمول مورد استفاده در مسائل مختلف متعادل سازي را نشان ميدهد.
کوستراوا وُ اگريکزاک، از توازن براي حل مسائل چندهدفه استفاده کردند. بر اساس کارآيي پارتو، معيارها غيرقابل قياس هستند، در حاليکه توازن فرض ميکند که ميتوان معيارها را در مقياس مشترک اندازه گيري کرد، به طوريکه مقادير به دست آمده نسبت به هر يک ، عادلانه باشد. اين ويژگي توزيع عادلانه مطلوبيت بين معيارها را مهم تر از تخصيص آن به معيار خاصي فرض کرده و تخصيص متعادل مطلوبيت به اين روش مدلسازي مي شود[٢٦].ُ اگريکزاک [٢٧]، مسائل مکان يابي را به صورت مدل هاي چند معياره بررسي کرد. وي با استفاده از رويکرد مارش و شلينگ [٧]، براي هر مشتري يک تابع هدف اختصاصي در نظر گرفت تا تأثير يک الگوي مکاني را روي رضايت مشتري اندازه بگيرد. مدل با تعيين توزيع کل تأثيرهاي فردي، قادر به معرفي مفهوم کارآيي متوازن مي - شود. هووانگ و همکاران مدل هايي براي تصميمات مسيريابي-تخصيص کمک هاي بشردوستانه با تعريف سه معيار توازن و اثربخشي و کارآيي ايجاد کردند[٢٥]. وانگ با ارائه يک مدل تجربي به بررسي توازن در تفريحگاه ها و تأثير آن بر رضايت و وفاداري مشتري پرداخت [٢٨].
استيوانز رابطه بين عدم توازن و نابرابري درآمد و ميزان رشد اقتصادي جامعه در آمريکا را مورد بررسي قرار داد[٢٩]. شي و ژو مدلي براي بررسي تأثير توازن روي ارزيابي سرمايه گذاري زيرساخت هاي حمل ونقل معرفي و با تحليل هزينه - فايده مقايسه کردند [٣٠].
همزمان با شکل گيري اين بخش از ادبيات ، زمينه جديدي از تحقيقات براي مدلسازي مسائل مکان يابي با اهداف متوازن ايجاد شد. برمن و کراس ، مسائل مکان يابي احتمالي را مورد توجه قرار دادند[٣١]. سورانا و همکاران ، متعادل کردن بار کاري را در سيستم هاي ساخت يافته زوجي مورد بررسي قرار دادند [٣٢]. مسئله بار کاري متوازن بدون محدوديت پوشش توسط دِرِزنر و دِرِزنر، در مسائل مکان يابي روي صفحه با فواصل اقليدسي بررسي شده است [٣٣]. آنهاهمچنين در مطالعه ديگري به مدلسازي مکان يابي با دو هدف حداقل کردن واريانس و دامنه مسافت ها تا تسهيل پرداختند و آنرا با استفاده از روش مثلث بزرگ -مثلث کوچک حل کردند [٣٤]. بارون و همکارانش ، مکان يابي روي يک مربع واحد را به منظور حداقل کردنِ حداکثر تقاضايي که هر تسهيل با آن مواجه ميشود و در نظر گرفتن نزديک ترين تخصيص ها و محدوديت پوشش مورد بررسي قرار دادند. حدود بالا و پايين براي موجه بودن مسئله و يک الگوريتم ابتکاري براي حل مسئله ايجاد شد [٣٥]. سوزوکيو دِرِزنر مکان - يابي تسهيلات با حداقل شعاع متوازن براي پاسخ گويي به تقاضاي يک ناحيه پيوسته را بررسي کردند و براي اين مسئله سه تابع هـــدف در نظـــــر گرفتند [٣٦]. برمن و همکاران ، مسئله مکان يابي شبکه را به نحوي که اوزان جذب شده به هر تسهيل نزديک ترين مقدار ممکن به يکديگر را داشته باشند، مطرح کردند [٢٢]. پوِرتو و همکاران ، مسائل مکان يابي تسهيلات گسترده را روي يک شبکه درختي با معيارهاي توازن بررسي کردند؛ در حالي که طول شبکه نامحدود و تسهيلات به شکل مسير در نظر گرفته شده بود. هدف ، يافتن مسيري بود که دامنه اختلاف ميان کمترين و بيشترين فاصله از يک گره شبکه تا هر تسهيل را حداقل کند [٣٧]. چانتا و همکاران يک مدل مکان يابي را براي توزيع متوازن مراکز اورژانس (EMS) علاوه بر توزيع مؤثر فضايي آنها ايجاد کردند[٢٣].
برکي و همکاران ، مکان هاي بهينه مراکز مراقبت از سلامتي را در ٤ ايالت آمريکا با درنظر گرفتن معيارهاي اثربخشي و توازن جستجو کردند[٣٨]. بارباتي براي حل مسئله مکان يابي متوازن براساس ضريب جيني، يک چارچوب مبتني بر نماينده ٢ ارائه کرد[٢٤].
مدل جاذبه
در اکثر مدل هاي مکان يابي، انتخاب خدمت دهنده توسط مشتريان بر اساس فرض نزديک ترين تسهيل (فرض مجاورت ) انجام ميگيرد، در حاليکه اين فرض در بسياري از موقعيت ها واقعي به نظر نميرسد.
مدل جاذبه اولين بار توسط رِيلي در سال ١٩٣١ مطرح شد. در مسئله مورد نظر، با فرض اينکه يک مشتري در يک شهر مياني نزديک دو شهر بزرگ قرار دارد، احتمال انتخاب يکي از شهرها نسبت مستقيم با اندازه شهر و نسبت عکس با مربع فاصله تا آن شهر دارد [٣٩].
هاف [٤٠ و ٤١]، مدل رِيلي را به صورت احتمالي براي مدل سازي سهم بازار در وضعيت رقابتي و پيش بيني رفتار مصرف کننده هنگام انتخاب يک فروشگاه مورد استفاده قرار داد. او ثابت کرد احتمال انتخاب يک فروشگاه توسط مصرف کننده متناسب با مساحت زمين فروشگاه بوده و نسبت عکس با برخي توان هاي فاصله تا فروشگاه دارد.
تابع نزولي فاصله ميتواند به صورت تواني از فاصله ، که معرف کاهش جذابيت است ، بيان شود. وقتي توان به سمت بينهايت ميل ميکند، مشتري نزديک ترين فروشگاه را با احتمال "يک " انتخاب ميکند. بنابراين قانون جاذبه هاف تعميمي از فرض مجاورت و قاعده اي کليتر بوده و به عنوان بيشترين مدل مطلوبيت مورد استفاده شناخته شده است [٤٢]. به جاي فرم چند جمله اي، ويلسون [٤٣]
و هوجسون [٤٤]تابع فاصله نزولي نمايي وِ بل [٤٥] ساير توابع رياضي را پيشنهاد کردند. دِرِزنر و دِرِزنر [٤٨-٤٦] و فوترينگام [٤٩ و ٥٠]توزيع هاي مختلف تقاضا را با توابع مطلوبيت يکسان و تصادفي در اين مدل تحليل کردند.
مک فِيدين [٥١] مدل انتخاب گسسته را با عنوان لاجيت چندجمله اي ابداع کرد. قانون جاذبه به طور گسترده در حل مسائل بسياري از حوزه هاي مختلفي مانند علوم جغرافي (ويلسن [٥٢]و لوِ و سِن [٥٣])، برنامه ريزي حمل ونقل (اوانس [٥٤]، ارلندر و استوارت [٥٥])، بازاريابي (هاف و رولند [٥٦]) و به ويژه در مطالعات مکان يابي به کار رفته است . به عنوان مثال دِرِزنر و دِرِزنر [٥٧]وِ ايسلت و مارياُنو [٥٨]از آن براي تعيين مکان قطب ، دِرِزنر و دِرِزنر [٤٢ و ٥٩]در مسئله ميانه ، هوجسون [٦٠] و اُکِلي و استورِبک [٦١] در مکان يابي روي فضاي گسسته ، کوکوکايدين و همکاران [٦٢] براي مکان يابي تسهيلات رقابتي استفاده کردند.
در اين پژوهش ، توسعه اي از مسئله مکان يابي با بارکاري متوازن انجام گرفته است . هدف مسئله ، تعيين مکان ، تعداد و ظرفيت چندين تسهيل که از نظر مطلوبيت متفاوت هستند براي پاسخگويي به نياز شبکه اي از نقاط تقاضا است .
بر اساس مطالعات به عمل آمده ، نزديک ترين تحقيق مرتبط در بحث متعادل کردن بار کاري بر اساس فواصل واقعي (تحت شبکه ) تحقيقي است که توسطِ برمن و همکاران [٢٢] ارائه شده و در آن روي متعادل سازي بدون در نظر گرفتن هزينه هاي مدل مکان يابي تمرکز شده است .
شبکه نقاط تقاضا مسيري با دو گره روي يک شبکه درختي در نظر گرفته شده است .
انتخاب خدمت دهنده توسط مشتري برمبناي نزديک ترين تسهيل موجود انجام گرفته که اين موضوع بخصوص در تسهيلات عمومي، که متوازن سازي اهميت بيشتري دارد، چندان واقعي نيست . در نهايت چند الگوريتم ابتکاري و فراابتکاري براي حل مسئله ايجاد شده که هريک در معيار عملکردي خاصي کارآيي دارد.
بر اين اساس در اين مقاله روي بهبود موارد ذکرشده تأکيد شده است . هدف مکان يابي، به صورت ترکيبي از کاهش هزينه هاي استقرار تسهيلات و حمل و نقل مشتريان در کنار توزيع عادلانه کل تقاضا بين تسهيلات خدمت دهنده است . در انتخاب تسهيل توسط هر مشتري تنها نزديک بودن حائز اهميت نبوده ، بلکه معيارهاي نشريه تخصصي مهندسي صنايع , دوره ٤٥ ، شماره ٢، مهر ماه ١٣٩٠ مطلوبيت و عدم مطلوبيت مختلف در نظر گرفته شده است . به طور کلي، در اين پژوهش احتمال انتخاب خدمت دهنده به صورت تابعي از ميزان جذابيت تخميني هر تسهيل ، فاصله و تراکم موجود در آن تعريف شده است .
شبکه مشتريان به صورت عمومي (و نه لزوما درختي) فرض شده است . الگوريتم هاي حل ابتکاري و دقيق نيز براي حل مسئله پيشنهاد شده که با توجه به نتايج محاسباتي کارآيي خوبي را نشان داده است .
تشريح مسئله
مسئله مکان يابي تعدادي تسهيل مشابه را در يک منطقه جغرافيايي با تقاضاي معلوم در نظر بگيريد. ظرفيت تسهيلات بايد براي پاسخگويي به کل تقاضاي مورد انتظار کافي باشد. فرض کنيد تکميل نکردن ظرفيت ، هزينه بر بوده و کل تقاضا بايد توسط تسهيلات و به طور "يکنواخت " پوشش يابد. همچنين هر مشتري خواهان دريافت سرويس از "جذاب ترين تسهيل " است . مسئله مکان يابي، معادل يافتن مکان هايي در نظر گرفته ميشود که علاوه بر کمينه سازي هزينه هاي استقرار و جابه جايي، حجم تقاضاي مشغول ترين تسهيل را حداقل کند. چون ظرفيت توسط پرکارترين تسهيل تعيين ميشود، تسهيلي که با تقاضايي کمتر از پرکارترين آنها مواجه باشد، مقداري ظرفيت استفاده نشده خواهد داشت . بنابراين مکان هاي ايده آل ، آنهايي هستند که تقاضا بين تسهيلات به صورت يکسان پخش شده باشد.
با تخصيص تقاضا به جذاب ترين تسهيلات و کوتاه ترين فواصل ، ميخواهيم مکان تعدادي نامعلوم از تسهيلات مشابه را جهت تأمين نيازمندي مجموعه مشتريان ، طوري تعيين کنيم که حداکثر تقاضايي که هر تسهيل با آن مواجه ميشود در کنار هزينه هاي مکان يابي-تخصيص حداقل شود. با اعمال تغييرات در مدل پايه نام گذاري جديدي براي آن با عنوان "مسئله توازن بر مبناي مدل جاذبه ١" در نظر ميگيريم .
مدل جاذبه و اندازه گيري جذابيت تسهيل
تحليل عوامل مربوط به جريان کالا يا سرويس ، پيش - بيني حجم تبادلات تجاري بخصوص در سطح بين المللي، تأسيس مراکز مراقبت از سلامتي، برنامه ريزي حمل و نقل ، پيش بيني فروش ، توزيع ترافيک ، مهاجرت و حتي جهت وزش تندباد و به طور کلي هريک از انواع جابه جايي بين دو نقطه از جمله مسائلي هستند که ميتوان آنها را به کمک قانون جاذبه مدلسازي و حل کرد.
جذابيت
مدل توصيف رفتار مشتري بهکمک قانون جاذبه ، اغلب بر اساس فرمول است . Gij ميزان جريان از گره i به گره j است که به جذابيت تسهيل بستگي دارد. مفهوم اين وزن ها بسته به کاربرد مسئله و اهميت آن ها متأثر از مشخصه هاي متفاوتي است . در اينجا تابعي از ويژگيهاي تسهيل در نظر گرفته شده است . اختلاف نقاط نيز براساس تابع از فاصله i و j،Dij ، محاسبه ميشود. براي مثال ، در مکان يابي مراکز خريد براي تخمين جذابيت ، ميتوان فاصله تا مراکز، قيمت کالاها، تنوع فروشگاه ها، تعداد پارکينگ هاي کافي، ميزان امنيت ، دسترسي به سيستم حمل و نقل عمومي، وجود کافيشاپ يا رستوران ، ويژگي - هاي ظاهري، مارکهاي تجاري مورد علاقه ، سرگرميها و.... را در نظر گرفت [٦٣]. گام هاي زير براي تخمين جذابيت تسهيلات ، بر اساس داده هاي گذشته و روش هاي برآورد، پيشنهاد ميشود.
(١) شناسايي معيارهاي مؤثر در ارزيابي تسهيلات :
بسته به ماهيت مسئله و نوع تسهيل ممکن است معيارها يا پيچيدگي تحليل آنها متفاوت باشد
M=
