مسیریابی بهینه کریدورهای انرژی و زیرساخت گسترده چندوجهی

چکیده

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

کلید واژه ها:

مسیریابی راهرو چند وجهی ; LCP گسترده ; مسیریابی کریدور انرژی و حمل و نقل

۱٫ مقدمه

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

داده های شطرنجی هزینه همراه با GIS به طور گسترده برای مسیریابی زیرساخت های خطی بهینه، مانند خطوط برق، جاده، راه آهن و خطوط لوله استفاده می شود. در قالب داده های شطرنجی، منطقه مورد مطالعه به یک شبکه مربع تقسیم می شود و هر سلول شبکه دارای یک مقدار از معیار و موقعیت جغرافیایی خاص است [ ۱ ]. به طور کلی، روش های مسیریابی کامپیوتری ابزارهای GIS و تجزیه و تحلیل تصمیم چند معیاره (MCDA) را برای یافتن یک LCP در فضای شطرنجی ادغام می کنند. اساس این رویکرد مشابه روشی است که ایان مک هارگ در کتاب طراحی با طبیعت [ ۲ ] توضیح داده است.]. برای هر معیاری که بر هزینه سفر تأثیر می گذارد، یک نقشه سایه دار تک رنگ ارائه می شود که رنگ های تیره تر نشان دهنده هزینه های بالاتر و رنگ های روشن تر نشان دهنده هزینه های کمتر است. سپس این نقشه‌های شفاف روی هم قرار می‌گیرند و با عبور از نواحی روشن‌تر و اجتناب از مناطق تاریک‌تر تا حد امکان، مسیر بهینه به صورت بصری تعیین می‌شود [ ۳ ].

به طور کلی استفاده از ابزارهای GIS LCP در کنار تکنیک های MCDA برای مسیریابی بهینه در چهار مرحله انجام می شود. اول، شناسایی اهداف و معیارهای مهم برای ذینفعان پروژه. دوم، جمع آوری داده ها در مورد عوامل مهم موثر بر مناسب بودن یک مسیر به شکل سلول های شبکه مربعی، یعنی داده های شطرنجی. سوم، تخصیص یک مقدار مناسب برای هر سلول، نشان دهنده موانع فیزیکی، محیطی و اجتماعی برای سهولت سفر در سلول. مناسب تر به معنای هزینه کمتر و اثرات منفی کمتر بر محیط زیست و جامعه است. وزن تخصیص داده شده به هر سلول – که هزینه، اصطکاک یا مقاومت نیز نامیده می شود – نشان دهنده دشواری عبور آن سلول است. هزینه را می توان با پول، زمان، مسافت یا ریسک اندازه گیری کرد [ ۴]. روش‌های MCDA، مانند فرآیند سلسله مراتبی تحلیلی، برای تعیین رتبه‌بندی معیارهای مهم و وزن‌دهی به آنها برای ایجاد یک رستر هزینه انباشته استفاده می‌شوند. ادغام GIS و MCDA را می توان برای اهداف طراحی، به عنوان مثال، یافتن مسیرهای جایگزین، یا برای ارزیابی مسیرهایی که قبلاً وجود دارد، استفاده کرد [ ۳ ]. در نهایت، یک الگوریتم LCP، مانند [ ۵ ] را برای شبکه شبکه وزن دار اعمال می کنیم تا کوتاه ترین مسیری را که مبدا را به مقصد متصل می کند، پیدا کنیم [ ۶ ].

۲٫ کارها و شکاف های مرتبط

داده های شطرنجی هزینه و GIS به طور گسترده برای یافتن LCP برای زیرساخت های خطی مانند جاده ها [ ۷ ، ۸ ، ۹ ]، راه آهن [ ۱۰ ، ۱۱ ، ۱۲ ]، خطوط انتقال نیرو [ ۱۳ ، ۱۴ ]، خطوط لوله [ ۱۵ ، ۱۶ ] استفاده می شود. و قرار دادن راهروهای حیات وحش [ ۱۷ ، ۱۸ ]. معیارهای مهم و رتبه بندی هر حالت حمل و نقل متفاوت است. برخی از مطالعات در ادبیات این عوامل و روش های وزن دهی را برای نوع خاصی از زیرساخت شناسایی می کنند. به عنوان مثال، ر. [ ۱۹] روشی را برای وزن دهی و ترکیب عوامل مهم برای یک جاده قطب شمال با آب و هوا ارائه می دهد. کار دیگر بر بهبود تکنیک ها برای اهداف خاص متمرکز است. به عنوان مثال، ر. [ ۴ ] از یک نمودار اتصال چند جهته برای در نظر گرفتن هزینه های شیب ناهمسانگرد در مسیریابی جاده و کانال استفاده می کند و [ ۲۰ ] یک روش برنامه ریزی راه را توسعه می دهد که پل ها و تونل ها را با اتصال سلول های غیر مجاور در یک نمودار اتصال ترکیب می کند. همچنین کارهایی برای سریع‌تر کردن الگوریتم‌های LCP وجود دارد، مانند [ ۲۱ ، ۲۲ ]. رشته دیگری از ادبیات بر یافتن مسیرهای جایگزین یا k-کوتاه‌ترین مسیرها تمرکز دارد [ ۲۳ ، ۲۴]. یافتن مسیرهای جایگزین مهم است زیرا فرآیند وزن دهی معیارها ذهنی است و الگوریتم های LCP به این فرآیند بسیار حساس هستند. بنابراین، معقول است که به جای تمرکز بر یک LCP، به مجموعه ای از گزینه ها نگاه کنیم.

دو چالش در یافتن کوتاه‌ترین مسیر برای یک کریدور چندوجهی گسترده وجود دارد که این فرآیند را نسبت به مسیریابی تک حالته و مسیر باریک پیچیده‌تر می‌کند. اول، کار کمی در مورد یافتن راهروهای وسیع وجود دارد [ ۲۵ ]. دوم، روش‌های گسترده فعلی یافتن LCP، چندوجهی بودن یک راهرو را در نظر نمی‌گیرند.

بیشتر ادبیات موجود در مورد مسیریابی، عرض مسیر را در مقایسه با اندازه سلول شطرنجی صفر و بی اهمیت فرض می کند. این فرض زمانی که داده های با وضوح بالا با اندازه سلول کوچکتر در دسترس هستند و مسیریابی یک مسیر وسیع (راهرو) مورد نظر است، واقعی نیست. مرجع. [ ۲۶ ] یکی از اولین مطالعاتی است که به عرض مسیر توجه دارد. آنها هزینه مسیری را که مبدا را به مقصد متصل می کند به عنوان هزینه مناطق تحت پوشش مسیر تعریف می کنند. در [ ۶ ]، مراکز سلولی گره در نظر گرفته می شوند و هر لبه ای که دو گره را به هم متصل می کند، مستطیلی به عرض w است. هزینه هر یال برابر است با مجموع هزینه های کسری از سلول های ایجاد کننده آن مستطیل. با استفاده از این تعریف، یک مسیر عریض با عرض wرا می توان یافت. با این حال، استفاده از دنباله ای از این لبه های مستطیل منجر به ایجاد شکاف و همپوشانی در نقاط عطف می شود. در نتیجه، هنگام افزایش عرض، خطاهای قابل توجهی رخ می دهد [ ۲۷ ].

مرجع. [ ۲۷ ] روش‌های مختلف را برای یافتن LCPهای گسترده مانند بافر یا نمونه‌گیری مجدد بررسی می‌کند. به طور کلی، در نمودار اتصال هر روش کارآمد برای یافتن یک مسیر بهینه گسترده، با عرض بزرگتر از اندازه سلول، وزن هر لبه (یعنی قوس) را نمی توان تنها از روی هزینه یک سلول محاسبه کرد. در این مورد، هزینه های سلول های همسایه نیز مهم است. بنابراین، هزینه یک لبه باید از مجموعه ای از سلول های مجاور که عرض مورد نظر را ایجاد می کنند، محاسبه شود. به عنوان مثال، ر. [ ۲۸ ] از وزن گره های w استفاده می کند که مجموعه ای از سلول های پیوسته هستند، و [ ۲۷ ] از وزن w توسط w استفاده می کند.بلوک ها این دو روش پیچیده ترین برای یافتن LCPهای گسترده هستند. مرجع. [ ۲۸ ] فرض می‌کند که عرض یک مسیر بر حسب تعداد سلول‌ها ثابت است، در حالی که [ ۲۷ ] مسیری با عرض ثابت را با استفاده از فاصله اقلیدسی پیدا می‌کند.

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

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

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

۳٫ روش شناسی

ما دو روش را برای تعیین مسیریابی بهینه کریدورهای زیرساخت چندوجهی گسترده پیشنهاد می کنیم. اولین مورد، یک LCP گسترده را در رستر هزینه انباشته (FWLA) پیدا می کند. در FWLA، اولاً، تمام رسترهای هزینه برای همه حالت ها وزن و جمع می شوند تا یک رستر هزینه مرکب واحد ایجاد شود و ثانیاً یک LCP گسترده در این رستر هزینه یافت می شود. هر یک از روش های گسترده LCP موجود مانند روش نمونه گیری مجدد یا روش هایی که در [ ۲۷ ] یا [ ۲۸ توضیح داده شده است.] را می توان در بخش دوم روش FWLA برای تراز کردن یک راهرو چند وجهی استفاده کرد. دوم، می توان از یک گراف تبدیل شده چند لایه (MLTG) استفاده کرد. روش MLTG گراف اصلی یعنی گرید را به یک گراف جدید تبدیل می‌کند و LCP را روی آن پیدا می‌کند و سپس مسیر پیدا شده روی گرید اصلی نگاشت می‌شود. در این روش وزن یال ها در نمودار اتصال از روی رسترهای هزینه حالت های مختلف با در نظر گرفتن جهت حرکت ها و ترتیب حالت ها در راهرو محاسبه می شود. توضیحات بیشتر در بخش های بعدی ارائه شده است.

۳٫۱٫ یافتن یک LCP گسترده در رستر هزینه انباشته (FWLA)

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

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

پس از این مرحله مقدماتی، یک LCP به پهنای راهرو چندوجهی بر روی رستر هزینه مرکب با استفاده از یک روش موجود یافت می شود (به عنوان مثال، Shirabe [ ۲۷ ]). در نهایت با توجه به چیدمان مطلوب حالت ها، تمامی حالت ها در داخل راهرو جای می گیرند. روش FWLA که در شکل ۱ خلاصه شده است، چهار مرحله را دنبال می کند: (۱) استفاده از تکنیک های MCDA برای ایجاد یک رستر هزینه برای هر حالت بر اساس معیارهای مهم آنها، (۲) تجمیع تمام رسترهای هزینه در یک رستر هزینه مرکب، (iii) یافتن یک مسیر گسترده در رستر هزینه مرکب، و (iv) قرار دادن راهرو چند وجهی مورد نظر در مسیر موجود در (iii). قابل توجه است که، در مرحله (iii)، تمام تکنیک های LCP گسترده مانند آنهایی که توسط [ ۲۷ و ۲۸ معرفی شده اند.] را می توان برای یافتن یک مسیر گسترده در سطح هزینه کل استفاده کرد.

نقص این روش این است که چیدمان مطلوب مدها در داخل راهرو تنها در مرحله نهایی در نظر گرفته شده است و نه در فرآیند یافتن گسترده LCP. به عبارت دیگر، الگوریتم‌های گسترده LCP موجود نمی‌توانند ترتیبات حالت‌ها را در نظر بگیرند. این الگوریتم ها از میانگین وزنی هزینه ها صرف نظر از ترتیب حالت ها استفاده می کنند. در نتیجه، برای اینکه یک سلول با هزینه متوسط کم “مناسب” در نظر گرفته شود، باید برای همه حالت ها کم هزینه باشد. این موضوع محدودیت های غیر ضروری را بر الگوریتم تحمیل می کند. شکل ۲ یک مثال گویا را نشان می دهد. دو رستر هزینه مصنوعی برای یک بزرگراه و یک خط برق در شکل ۲ نشان داده شده استالف، ب. هدف یافتن یک مسیر دو سلولی است که به طور مساوی بین حالت ها تقسیم شده است و بزرگراه در بالای مسیر از چپ به راست حرکت می کند. وزن این رسترهای هزینه یکسان و برابر در نظر گرفته شده است ۰٫۵٫ رستر هزینه کل در شکل ۲ c نشان داده شده است. ردیف C هزینه کمتری نسبت به ردیف A و B دارد زیرا هر دو بزرگراه و خط برق در این ردیف هزینه های نسبتا کمی دارند. مسیر بهینه دو سلولی که با این روش یافت می شود در کادر قرمز در شکل ۲ ج نشان داده شده است. با این حال، اگر میانگین هزینه در نظر گرفته نشود و از شبکه های اصلی استفاده شود، مسیر بهینه مانند شکل ۲ d خواهد بود، که در آن هزینه های ردیف A برای رستر هزینه بزرگراه کمترین و هزینه های ردیف B برای توان کمترین است. شطرنجی هزینه خط. این نقص با روش پیشنهادی MLTG حل می‌شود، که در آن هزینه‌های لبه‌ها بر اساس آرایش‌های مورد نظر حالت‌ها در هر جهت محاسبه می‌شود. ما از روش MLTG در زیر استفاده کردیم.

۳٫۲٫ روش نمودار تبدیل شده چند لایه (MLTG).

برای ایجاد یک مسیر گسترده، هزینه های مجموعه ای از سلول های همسایه باید در هر لبه در نظر گرفته شود نه هزینه تنها یک سلول. فرض کنید در هر جهت مجموعه ای از سلول ها به شکل مستطیل به عرض راهرو برای ایجاد یک مسیر گسترده استفاده می شود و هر حالت بر اساس عرض مورد نظر خود نسبتی از این مستطیل را پوشش می دهد. در نمودار اتصال، اگر هر سلول به هشت سلول مجاور خود متصل شود، هشت جهت مجاز وجود دارد (معادل جهت هایی که یک ملکه می تواند در صفحه شطرنج انجام دهد). با تثبیت چیدمان حالت ها در یک جهت، آرایش هفت جهت دیگر نیز ثابت می شود زیرا تلاقی حالت ها مجاز نیست. بنابراین، راهروی چند وجهی را می توان با چسباندن مستطیل هایی ایجاد کرد که دارای آرایش خاصی از حالت ها برای هر جهت هستند. با این حال،بخش ۲ ، با استفاده از یک دنباله از این مستطیل ها لبه ها منجر به هر دو شکاف و همپوشانی می شود. برای غلبه بر این چالش در روش MLTG، نمودار اتصال اصلی به گونه‌ای تبدیل می‌شود که همپوشانی ایجاد نمی‌کند و با اضافه کردن هزینه‌های اضافی، یعنی هزینه‌های چرخشی، جایی که راهرو جهت خود را تغییر می‌دهد، شکاف‌ها را پر می‌کند. قابل توجه است که در مقایسه با گراف اتصال مرسوم در MLTG، گره ها، لبه ها و وزن آنها تغییر می کند و در مرحله بعد می توان از هر یک از الگوریتم های LCP مانند Dijkstra [ ۵ ] استفاده کرد. به عبارت دیگر، MLTG مستقل از استفاده از هر الگوریتمی برای یافتن LCP در نمودارهای اتصال است.

MLTG راهروهای چند وجهی را به عنوان لگو می سازد. هر قطعه لگو در یک رنگ خاص است و هر رنگ نشان دهنده یک حالت خاص است. ایجاد یک راهروی پیوسته با چیدمان و عرض دلخواه برای هر حالت مستلزم مجموعه خاصی از قطعات لگو است. هزینه یک راهرو مجموع هزینه های قطعات ایجاد کننده آن است. هر قطعه لگو از تعدادی بلوک ساخته شده است و هر بلوک از یک سلول یا بخش هایی از سلول ها در حالت های هزینه شطرنجی ساخته شده است. برای محاسبه وزن هر قطعه لگو، مفهوم “همسایگی” را اعمال می کنیم [ ۲۹]، “مجموعه ای از مکان هایی که در فواصل نقشه برداری و/یا جهت های مشخص از یک مکان خاص قرار دارند”. در هر قطعه یک بلوک خاص به عنوان نقطه مرجع آن در نظر گرفته می شود و وزن هر قطعه بر اساس محل نقطه مرجع و نوع محله آن یعنی قطعه لگو محاسبه می شود. در هر نقطه، وزن هر محله برابر است با مجموع هزینه مناطق اشغال شده توسط رنگ های مختلف. برای هر رنگ (حالت)، هزینه از شطرنجی هزینه آن حالت به دست می آید.

سه نوع همسایگی در MLTG وجود دارد: (i) متحرک، (ii) چرخش در جهت عقربه‌های ساعت و (iii) چرخش در خلاف جهت عقربه‌های ساعت. محله متحرک بر اساس جهت آن نامگذاری می شود، مثلاً از چپ به راست. محله های چرخشی شکاف های ایجاد شده بین دو محله متحرک را به دلیل تغییر جهت پر می کنند. با توجه به جهت محلات قبل و بعد از نقطه عطف نامگذاری شده اند. میز ۱نماد استفاده شده برای هر نوع محله و جهت را نشان می دهد. استفاده از هزینه یک محله به جای وزن یک سلول به ما امکان می دهد یک LCP گسترده را به جای یک مسیر باریک پیدا کنیم. علاوه بر این، ساختن هزینه یک محله از لایه‌های هزینه مختلف به برنامه‌ریز اجازه می‌دهد تا هزینه‌های همه حالت‌ها را به صورت جداگانه در نظر بگیرد و بنابراین از مشکلات مربوط به استفاده از هزینه انباشته همه حالت‌ها، همانطور که در بخش ۳٫۱ بحث شد، اجتناب کند .

با حرکات مجاز در هشت جهت مختلف، به عنوان حرکات ملکه روی صفحه شطرنج، هشت محله متحرک مورد نیاز است. برای حفظ آرایش خاص حالت ها، ترتیب حالت ها در جهت معکوس باید معکوس شود. به عنوان مثال، آرایش در یک محله LR برای حرکت در جهت مخالف در RL منعکس شده است. همین قانون برای چرخش در جهت عقربه های ساعت و خلاف جهت عقربه های ساعت نیز صدق می کند. این مفهوم در یک مثال راهرو ۳ حالته در شکل ۳ نشان داده شده است. عرض مورد نیاز یک سلول برای هر یک از حالت های اول و سوم و دو خانه برای حالت میانی است. شکل مجموعه ای از محله های متحرک و جهت حرکت آنها را نشان می دهد. چندین محله چرخشی نیز برای نشان دادن ترتیب معکوس حالت ها در چرخش در جهت عقربه های ساعت و خلاف جهت عقربه های ساعت برجسته شده اند.

همسایگی ها را می توان به گونه ای تعریف کرد که تعداد سلول ها در هر جهت ثابت باشد یا به گونه ای که فاصله اقلیدسی دو یال مسیر با هم سازگار باشد. داشتن یک همسایگی مشخص برای هر جهت به مدل انعطاف پذیری می دهد تا در جهات مختلف عرض های متفاوتی داشته باشد. عرض هر حالت در هر جهت می تواند یک عدد شناور باشد. با این حال، در این مقاله چندین فرض ساده را برای ساده‌تر کردن هندسه مطرح می‌کنیم: (۱) راهرو از نظر فاصله اقلیدسی در همه جهات عرض ثابتی دارد، (ب) عرض هر حالت در حرکت متعامد عاملی است از اندازه سلول رستر هزینه، و (iii) عرض هر حالت در حرکات مورب عاملی است ۲×سلول-اندازه. بر اساس این مفروضات، محله هایی ایجاد می شوند که در پاراگراف های زیر توضیح داده شده است.

یک راهرو چند وجهی متشکل از حالت های M را در نظر بگیرید (م۱،م۲،…مم)که در آن عرض حالت m برابر است wمترو اندازه سلول از رسترهای هزینه برابر است با جس. تعداد سلول های لازم برای هر حالت nمتر، در حرکات متعامد، که ایجاد می کنند wمتررا می توان به صورت زیر استخراج کرد:

nمتر=wمترجس

(۱)

عرض کل راهرو که با تعداد سلول ها اندازه گیری می شود برابر است با تیwn=∑متر=۱مnمتر. در فاصله اقلیدسی است تیwه=تیwn×جس. یک محله در حال حرکت از چپ به راست (LR) را فرض کنید. مبدأ سیستم مختصات دکارتی در گوشه سمت چپ بالای منطقه مورد مطالعه است و طول ( i ) و عرض جغرافیایی ( j ) به ترتیب از چپ به راست و از بالا به پایین افزایش می یابد. ترتیب حالت ها در محله های LR از بالا به پایین ۱ تا M با لایه های هزینه مربوطه است سی۱،سی۲،…،سیمو مربوطه nمتراس از n1،n2،…،nم. تعداد سلول ها از سلول مرجع تا شروع هر حالت جدید m برابر است نمتر، مطابق با:

عددازسلول هاقبل ازحالتمتر=نمتر=∑۱متر-۱nمتر(توسطتعریفن۱=۰)

(۲)

هزینه هر محله برابر است با مجموع هزینه های سلول های آن محله از لایه های هزینه مربوطه آنها. برای محله های LR، سلول مرجع سلول بالایی است در حالی که برای RL، UD، و DU سلول های مرجع به ترتیب پایین ترین، چپ ترین و راست ترین سلول ها هستند. این تضمین می‌کند که ترتیب حالت‌ها از سلول مرجع در همه حرکت‌ها ثابت است و سلول مرجع همیشه سلول ابتدایی حالت اول است ( م۱). یک مجموعه کلی از هشت محله متحرک در شکل ۴ نشان داده شده است . خطوط نقطه چین بین بلوک ها به این معنی است که تعداد بلوک ها ممکن است در هر جهت متفاوت باشد. هر حالت رنگ متفاوتی دارد. حالت اول (آبی) حالتی است که شامل سلول مرجع می شود. سلول مرجع اولین بلوک حالت اول است و با یک نقطه سیاه در وسط شکل به تصویر کشیده شده است. نام هر محله و جهت آنها در شکل درج شده است.

اشکال کلی محله های LR، LRtoLURD و LURD، در شکل ۵ نشان داده شده است. همسایگی های ورودی و خروجی برای این چرخش به ترتیب LR و LURD هستند. مساحت کل محله چرخش، LRtoLURD، در یک خط بنفش جامد محصور شده است. هزینه این پیچ، مشابه هر ۱۶ محله چرخشی، برابر است با مساحتی که محله ورودی آن برای رسیدن به محله خروجی جاروب کرده است. در این مورد، هزینه، مجموع هزینه های سلول های محصور شده توسط خط بنفش جامد، از لایه های هزینه های مختلف حالت های مختلف است.

هزینه محله LR در سلول (من،j)است سیLآرمنjو به صورت زیر محاسبه می شود:

اگرj=<(جی-تیwn+1)سپس:سیLآرمنj=∑متر=۱م∑n=1nمترسیمتر(من،j+نمتر+n-1)

(۳)

معادله ( ۳ ) هزینه منطقه تحت پوشش محله را از لایه های هزینه مربوطه محاسبه می کند: سیمتر(من،j)هزینه سلول است (من،j)در قیمت شطرنجی حالت m . فرض بر این است که منطقه مورد مطالعه شامل سلول های I در عرض و سلول های J در ارتفاع است. محدودیت‌های یک منطقه مورد مطالعه باید در هنگام ایجاد محله‌ها در نظر گرفته شود که چرا سلول انتهایی محله‌ها مجاز به قرار گرفتن بر روی مرزهای منطقه مورد مطالعه نیست. عبارت شرطی در معادله ( ۳ ) فضای کافی را در منطقه مطالعه برای حرکت راهرو در آن جهت تضمین می کند. این محدودیت به این معنی است که در این سلول ها، راهرو فضای کافی برای حرکت در جهت آن محله را ندارد. به عنوان مثال، در یک منطقه مطالعه ۱۰۰ در ۱۰۰ سلول با یک راهرو به عرض ۱۰ مشتق شده از ( ۱ )، حرکت از چپ به راست مجاز نیست. j>100-10+1=91. برای سایر محله های متعامد، هزینه ها را می توان به روشی مشابه محاسبه کرد.

شکل ۶ یک نمونه مسیر دو سلولی از چپ به بالا به راست به پایین (LURD) را برای دو روش پیچیده موجود برای LCPهای گسترده نشان می دهد [ ۲۷ ، ۲۸ ]. در هر دوی این روش ها، در جهت های مورب، لبه های مسیر پیدا شده با شکل زیگزاگ فرورفته می شوند. در [ ۲۷ ]، عرض مورب در نوسان است ۲×جسیعنی قطر یک سلول. این موضوع با مسیری که عرض آن به طور قابل توجهی بزرگتر از اندازه سلول است یا با سطح هزینه صاف که در آن تغییرات شدیدی در هزینه های سلول های مجاور وجود ندارد، مهم نیست. با این حال، زمانی که عرض مسیر از نظر اندازه سلول خیلی زیاد نباشد یا زمانی که تغییرات چشمگیری در هزینه سلول‌های مجاور وجود دارد، نوسان می‌تواند مهم‌تر شود و منجر به یافتن یک مسیر غیربهینه شود.

با روش MLTG، همسایه های مورب را می توان تصور کرد که از تعدادی بلوک با هندسه یکسان ساخته شده اند. بلوک اول از چهار نیم سلول تشکیل شده است که یکی از آنها زیرمجموعه ای از خود سلول مرجع است. سه نیم سلول دیگر بر اساس جهت حرکت تعیین می شوند. به عنوان مثال، در محله های LURD، سه نیم سلول دیگر سلولی هستند (من+۱،j)، سلول (من،j+1)و سلول (من+۱،j+1)جایی که i و j محل سلول مرجع همسایگی هستند. به این ترتیب عرض هر بلوک برابر است ۲×جس. این بلوک ها را می توان ۴۵ درجه نسبت به شبکه اصلی چرخش در نظر گرفت. مفهوم ساخت یک بلوک با استفاده از چهار نیم سلول بدون چرخش محور در شکل ۷ نشان داده شده است . شکل ۷ ب یک بلوک LURD متشکل از چهار نیم سلول از چهار سلول همسایه را نشان می دهد. وزن این بلوک برابر است با مجموع چهار نیم سلول نشان داده شده در شکل ۷ a. برای محله‌های LDRU، RULD و RDLU فقط مکان سلول مرجع (سیاه) متفاوت است. با استفاده از این روش از فرورفتگی و نوسانات عرض مسیر جلوگیری می شود و ایجاد مسیری با عرض ثابت در حرکات مورب امکان پذیر می شود. محدودیت عامل بودن از ۲×جسبرای عرض مورب را می توان با هندسه پیچیده تری حل کرد که از حوصله این مقاله خارج است.

یک محله LURD در سمت راست شکل ۵ نشان داده شده است . برای تعریف حرکات مورب، این را فرض کنید wمترعرض مورد نظر حالت m در یک راهرو چند وجهی است. برای تضمین حداقل عرض wمتر، تعداد بلوک های هر حالت دمتراز رابطه ( ۷ ) محاسبه می شود و با استفاده از ( ۱ ) در رابطه ( ۸ ) به دست می آید. ترتیب حالت ها مانند حرکت های متعامد است. سلول مرجع یکی از سلول های بلوک اول حالت اول است. عرض کل راهرو در حرکات مورب که با تعداد بلوک ها اندازه گیری می شود برابر است با:

تیwد=∑متر=۱مدمتر،

(۴)

و در فاصله اقلیدسی اندازه گیری می شود:

تیwهد=۲×تیwد×جس.

(۵)

نسبت عرض راهرو در حرکات مورب به عرض در حرکات متعامد برابر است با:

آر=تیwدتیwn=2×∑متر=۱مدمتر∑متر=۱مnمتر،

(۶)

که با افزایش عرض راهرو به یک نزدیک می شود. تعداد بلوک ها از سلول مرجع تا بلوک اول هر حالت m است Dمترو از ( ۹ ) مشتق شده است . هزینه یک محله LURD در نقطه ( i ، j ) است سیLUآرD(من،j)و از ( ۱۰ ) به شرح زیر مشتق شده است. هزینه سایر محله ها نیز به همین ترتیب محاسبه می شود.

دمتر=|wمتر۲×جس|+۱

(۷)

دمتر=|nمتر۲|+۱

(۸)

Dمتر=∑۱متر-۱دمتر(توسطتعریف:D1=0)

(۹)

و اگر من≥(تیwد-۱)و j≤(جی-تیwد):

سیLUآرDمنj=∑متر=۱متر=م∑د=۱د=دمتر∑منمن=۰منمن=۱∑jj=0jj=10.5×(سیمتر(من-Dمتر-د+۱+منمن،j+Dمتر+د-۱+jj)

(۱۰)

برخی از محله های چرخشی با فلش های سیاه در شکل ۳ نشان داده شده اند. شکاف بین محله متحرک موجود (یعنی ورودی) و محله بعدی (یعنی خروجی) با چرخش محله ها پر می شود. هر محله چرخشی بخشی از یک دایره کامل است که از لایه های مختلف بسته به ترتیب حالت ها در یک راهرو چند وجهی ساخته شده است. برای ثابت نگه داشتن آرایش در همه جهات، ترتیب حالت ها در چرخش های عقربه های ساعت و خلاف جهت عقربه های ساعت برعکس است. به عنوان مثال، دایره های کامل پیچ های یک راهرو سه حالته برای هر دو چرخش خلاف جهت عقربه های ساعت و جهت عقربه های ساعت در شکل ۸ نشان داده شده است.a، b، به ترتیب. در این شکل، هر حالت رنگ متفاوتی دارد و چیدمان حالت های مورد نظر در این راهرو به این صورت است که وقتی راهرو از چپ به راست حرکت می کند، حالت مشکی در بالا قرار دارد. برای ساده‌تر کردن هندسه و محاسبه وزن‌ها در این مقاله، دو دایره چرخشی به‌عنوان دو هشت ضلعی محدود مدل‌سازی شده‌اند ( شکل ۸ c,d). برای هر محله متحرک ورودی و خروجی یک بخش در هر هشت ضلعی وجود دارد که بسته به جهت چرخش می توان از آن استفاده کرد، که در شکل ۸ نشان داده شده است.e, f. برای هر حالت، اگر تعداد بلوک‌های موجود در حرکت‌های مورب آن برابر با تعداد سلول‌های حرکات متعامد باشد، هشت ضلعی به شکل مربع تبدیل می‌شود. این زمانی اتفاق می‌افتد که عرض یک حالت کمتر از سه سلول باشد، در حالی که برای یک راهرو وسیع‌تر، یک هشت ضلعی خواهد بود.

برای جلوگیری از همپوشانی حتی به اندازه نصف سلول، چندین شرط تعیین کردیم. از آنجایی که پیچ ها در مدل MLTG 45 درجه هستند، هر محله چرخشی دارای یک همسایگی ورودی یا خروجی متعامد و مورب است. نیمی از هزینه محله متعامد باید در محله تراش در نظر گرفته شود در حالی که حرکات مورب حذف می شوند. این به این دلیل است که در همسایگی های مورب از بلوک ها ساخته می شوند در حالی که همسایگی های متعامد از سلول های منفرد ساخته می شوند – شکل ۵ را ببینید . در چرخش جهت عقربه های ساعت، همسایگی ورودی به دور سلول مقابل سلول مرجع خود، نقطه قرمز در شکل ۵ می چرخد.، در حالی که در چرخش های خلاف جهت عقربه های ساعت، به دور سلول مرجع خود می چرخد (نقطه سیاه). در چرخش های خلاف جهت عقربه های ساعت، سلول مرجع محله ورودی باید از وزن چرخش حذف شود. به طور مشابه، سلول مقابل سلول مرجع باید در چرخش جهت عقربه های ساعت حذف شود. دلیل آن این است که نیمی از سلول توسط همسایگی ورودی، در اینجا LR، و نیمی دیگر توسط محله خروجی، در اینجا LURD پوشانده شده است. جزئیات و معادلات بیشتر برای هزینه چرخش در [ ۳۰ ] موجود است.

در روش های متداول LCP، نمودار اتصال از گره ها و لبه های وزن دار تشکیل شده است. گره ها مراکز سلول ها در رستر هزینه و یال ها پیوندهایی هستند که گره های همسایه را به هم متصل می کنند. وزن یک یال برابر است با میانگین هزینه دو گره متصل ضربدر فاصله آنها [ ۳۱ ]. در روش MLTG، نمودار اتصال مرسوم توضیح داده شده به گراف دیگری تبدیل می شود، سپس LCP بر روی نمودار تبدیل شده پیدا می شود و در نهایت LCP یافت شده به مسیری در گراف اتصال اصلی ترجمه می شود.

الگوریتم [ ۵ ] یا سایر الگوریتم‌های کوتاه‌ترین مسیر، تفاوتی بین حرکات مستقیم و چرخش قائل نمی‌شوند. به عبارت دیگر، این الگوریتم‌ها از گره‌ها و وزن لبه‌های پیوند دهنده برای یافتن یک LCP استفاده می‌کنند بدون اینکه در نظر بگیرند که آیا مسیر در حال چرخش است یا در همان جهت ادامه می‌یابد. به عنوان راه حل، در روش MLTG، هر سلول در رستر هزینه به عنوان یک نمودار با هشت گره مربوط به هشت ورودی و خروجی احتمالی آن در نظر گرفته می شود، زیرا در الگوی حرکت ملکه در صفحه شطرنج، هر سلول توسط هشت سلول مجاور خود احاطه شده است. هر یک از این هشت گره به عنوان یک پایانه برای لبه های ورودی و خروجی کار می کند ( شکل ۹آ). مرکز یک سلول با رنگ سیاه و هر یک از هشت گره با رنگ متفاوتی نشان داده شده است. نمادهای استفاده شده برای هر گره، حرکات مجاز روی آن گره را نشان می دهد و مانند نمادهای همسایگی ها و لبه های نشان داده شده در جدول ۱ است.

هزینه یک مسیر برابر است با مجموع هزینه های محله هایی که آن مسیر را ایجاد می کنند و می توان از رابطه ( ۱۱ ) محاسبه کرد که در آن سیOپ، سیمترnو سیتیnهزینه های مسیر و هزینه های مترnتیساعتدر حال حرکت و تیnتیساعتمحله های چرخشی در این معادله، منو تینتعداد کل محله های متحرک و چرخشی هستند. بنابراین در روش MLTG از هزینه های محله ها به عنوان هزینه های لبه های اتصال استفاده می شود. سه نوع لبه در روش MLTG وجود دارد: (۱) لبه های حرکت مستقیم، (۲) لبه های چرخشی در جهت عقربه های ساعت، و (iii) لبه های چرخشی خلاف جهت عقربه های ساعت. هر گره دارای دو یال حرکت مستقیم است، یکی برای هر ورودی و خروجی. این دو لبه هر گره را از دو سلول قابل دسترسی در آن جهت به گره های مربوطه خود متصل می کنند. به عنوان مثال، لبه حرکت مستقیم ورودی در گره LR در سلول (من،j)از گره LR سلول می آید (من-۱،j)و لبه حرکت مستقیم خروجی به گره LR سلول می رود (من+۱،j)که در آن طول i از چپ به راست افزایش می یابد. با توجه به هشت گره هر سلول، هشت زوج لبه با حرکت مستقیم ورودی و خروجی در هر سلول وجود دارد که برای سلول مرکزی در یک نشان داده شده است. ۳×۳نمونه سلول در شکل ۹ ب.

بر اساس هندسه تعریف شده همسایگی ها، وزن لبه های متحرک متعامد برابر است با میانگین هزینه های دو همسایگی متناظر که مساحت بین آن گره ها را پر می کنند و از رابطه ( ۱۲ ) قابل محاسبه است. اینجا، دبلیوم(من،j)-(پ،q)وزن یک یال متحرک است که از گره می آید (من،j،م)و رسیدن به گره (پ،q،م)جایی که i و j طول و عرض جغرافیایی سلول را نشان می دهد و M نوع گره است. سیممن،jهزینه محله M با سلول مرجع آن واقع در است (من،j). به عنوان مثال، وزن لبه LR اتصال (۵،۱۰)به (۶،۱۰)در معادله ( ۱۳ ) نشان داده شده است. با این حال، وزن لبه های متحرک مورب و تمام لبه های چرخشی شروع از (من،j)برابر است با هزینه محله مربوطه با سلول مرجع آن واقع در (من،j). وزن لبه های متحرک مورب و پیچ ها را می توان از رابطه ( ۱۴ ) محاسبه کرد، جایی که دبلیوE(من،j)-(پ،q)وزن لبه E است که از آن شروع می شود (من،j)، و سینEمن،jهزینه محله E با سلول مرجع آن در است (من،j).

سیOپ=∑مترn=1مترn=منسیمترn+∑تیn=1تیn=تینسیتیn

(۱۱)

دبلیوم(من،j)-(پ،q)=سیممن،j+سیمپ،q2

(۱۲)

دبلیوLآر(۵،۱۰)-(۶،۱۰)=سیLآر۵،۱۰+سیLآر۶،۱۰۲

(۱۳)

دبلیوE(من،j)-(پ،q)=سینEمن،j

(۱۴)

نوع دوم لبه برای چرخش های خلاف جهت عقربه های ساعت است. در روش MLTG، هشت گره در هر سلول وجود دارد و برای هر یک از این گره ها، هفت گره دیگر در جهت خلاف جهت عقربه های ساعت وجود دارد. این هفت لبه در شکل ۱۰ a برای یک گره LR نشان داده شده است. از آنجایی که در هر سلول هشت گره وجود دارد، ممکن است وجود داشته باشد ۸×۷=۵۶لبه ها ( شکل ۱۰ ب). با این حال، پیچ های بزرگتر از ۴۵ درجه از اجزای کوچکتر ۴۵ درجه تشکیل شده است و همه این نوع چرخش ها با اتصال هر گره (ترمینال) به گره همسایه خود در خلاف جهت عقربه های ساعت ایجاد می شوند. این مفهوم در شکل ۱۰ ج نشان داده شده است. به این ترتیب، برای مثال، یک چرخش ۹۰ درجه در خلاف جهت عقربه های ساعت از LR به DU را می توان با دو چرخش ۴۵ درجه ایجاد کرد: ابتدا از LR به LDRU و سپس از LDRU به DU. هشت لبه چرخش خلاف جهت عقربه های ساعت یک سلول در شکل ۱۰ ج نشان داده شده است.

سومین و آخرین نوع لبه ها لبه های چرخشی در جهت عقربه های ساعت است. این لبه ها شکاف بین محله های ورودی و خروجی را در چرخش جهت عقربه های ساعت پر می کنند. برخلاف چرخش های خلاف جهت عقربه های ساعت، سلول مرجع همسایگی های ورودی و خروجی در چرخش های عقربه های ساعت یکسان نیستند. در این چرخش ها، همسایگی ورودی به دور سلول مقابل سلول مرجع خود می چرخد. بنابراین هر دو سلول مرجع و گره پایانه در جهت عقربه های ساعت تغییر می کنند. به عنوان مثال، فلش قرمز رنگ در شکل ۵ یک لبه LRtoLURD را نشان می دهد. سلول مرجع ورودی، یعنی LR با نقطه سیاه نشان داده می شود در حالی که سلول مرجع همسایگی خروجی، یعنی LURD مربع سیاه است.

مشابه لبه‌های چرخش خلاف جهت عقربه‌های ساعت، هشت چرخش ۴۵ درجه در جهت عقربه‌های ساعت وجود دارد و با اضافه کردن این چرخش‌های ۴۵ درجه‌ای می‌توان پیچ‌های بزرگ‌تر را ایجاد کرد. برای چرخش در جهت عقربه های ساعت، همسایگی ورودی در اطراف سلول در سمت مخالف سلول مرجع می چرخد. شکل ۱۱ یک چرخه کامل از چرخش در جهت عقربه های ساعت را نشان می دهد. به عنوان مثال، اگر چرخش از گره LR شروع شود، به گره LURD که گره بعدی در جهت عقربه های ساعت است می رود. این گره LURD از همان سلول نیست زیرا سلول مرجع خروجی با سلول مرجع ورودی برای چرخش در جهت عقربه های ساعت متفاوت است. سلول مرجع ورودی (من،j)و سلول مرجع خروجی (پ،q)یک چرخش LRtoLURD در شکل ۵ نشان داده شده است. همانطور که معادلات مرتبط در این شکل نشان می دهد، تغییرات از (من،j)به (پ،q)به تعداد سلول های راهرو در حرکات متعامد و مورب بستگی دارد.

به طور خلاصه، مدل MLTG هر سلول را به هشت گره پایانه تقسیم می کند. هر گره دارای سه ورودی و سه لبه خروجی است. لبه های ورودی عبارتند از: (i) یک لبه مستقیم از گره همتا از سلول قبلی در آن جهت، (ب) یک لبه چرخشی خلاف جهت عقربه های ساعت از گره قبلی در چرخه خلاف جهت عقربه های ساعت در همان سلول، و (iii) یک لبه چرخش در جهت عقربه های ساعت از گره قبلی در چرخه عقربه های ساعت از یک سلول دیگر. به طور مشابه، سه سلول خروجی عبارتند از: (۱) یک لبه مستقیم به گره همتا به سلول بعدی در آن جهت، (ب) یک لبه چرخشی خلاف جهت عقربه های ساعت به گره بعدی در چرخه خلاف جهت عقربه های ساعت در همان سلول، و (iii) یک لبه چرخشی در جهت عقربه های ساعت به گره بعدی در چرخه عقربه های ساعت به سلول دیگر. این لبه ها در شکل ۱۲ نشان داده شده است.

۴٫ نتایج عددی

این بخش شبیه‌سازی‌های عددی برای یافتن یک LCP تحت سه سناریو ارائه می‌کند. ابتدا، ما عملکرد روش MLTG را با دو مدل موجود دیگر – [ ۲۸ ] و [ ۲۷ ] – در یافتن یک LCP تک حالته دو سلولی مقایسه می کنیم. اگرچه روش MLTG برای یافتن راهروهای عریض چند وجهی ایجاد شد، اما با تخصیص رستر هزینه یکسان به همه حالت‌ها، برای یافتن مسیرهای عریض تک حالته قابل استفاده است. دوم، ما عملکرد روش‌های MLTG و FWLA را در یافتن یک کریدور چند وجهی مقایسه می‌کنیم. در روش FWLA ابتدا یک سطح هزینه واحد با وزن دهی به تمام سطوح هزینه و سپس [ ۲۷ ] ایجاد می شود.روش ] برای یافتن یک LCP گسترده استفاده می شود. در نهایت، روش MLTG برای یافتن یک راهرو سه حالته در یک منطقه مطالعاتی ۲۰۰ در ۲۰۰ سلول استفاده می شود.

۴٫۱٫ مقایسه MLTG با روش های موجود در مسیریابی یک راهرو عریض تک حالته

اگرچه روش MLTG برای یافتن LCP برای راهروهای چند وجهی گسترده طراحی شده است، اما می توان از آن برای راهروهای عریض تک حالته استفاده کرد. این در صورتی امکان پذیر است که محله های آن از یک رستر هزینه واحد ساخته شده باشد. این بخش عملکرد MLTG و دو روش موجود دیگر را برای یافتن یک LCP تک حالت گسترده مقایسه می‌کند. به طور خاص، ما از سه روش استفاده می کنیم – MLTG، ref. [ ۲۸ ] و [ ۲۷ ] – برای یافتن یک LCP تک حالته دو سلولی در یک شطرنجی ساده ده در ده هزینه. داده ها مصنوعی و به صورت تصادفی ساخته شده اند و از [ ۲۸ ] هستند.

ابتدا، MLTG برای یافتن یک مسیر دو سلولی استفاده می شود. عرض آن ثابت و برابر با دو سلول است. این شبیه به هدف روش در [ ۲۸ ] است. محله های متحرک و چرخشی طوری تعریف شده بودند که تعداد سلول ها ثابت بماند. نتیجه در شکل ۱۳ نشان داده شده است . شکل ۱۳ a داده هایی است که به عنوان لایه هزینه استفاده می شود. شکل ۱۳ b LCP یافت شده توسط [ ۲۸ ] با هزینه مجموع ۳۱ است، و شکل ۱۳ c LCP یافت شده توسط روش MLTG با هزینه کل ۳۰ است. نتایج نشان می دهد LCP یافت شده توسط روش MLTG برای یک حالت تک است. کمتر از LCP یافت شده توسط [ ۲۸] زمانی که هدف ثابت نگه داشتن تعداد سلول ها در تمام انتقال ها باشد.

در مرحله بعد، روش های MLTG و [ ۲۷ ] را با هم مقایسه می کنیم. داده ها مانند آزمایش قبلی است و هدف این است که عرض LCP بر حسب فاصله اقلیدسی ثابت شود. نتیجه در شکل ۱۴ نشان داده شده است . شکل فرعی (a) مقادیر هزینه را برای هر سلول نشان می دهد، شکل فرعی (b) MLTG LCP یافت شده زمانی است که هدف رفع فاصله اقلیدسی دو لبه مسیر است، و شکل فرعی (c) مسیر را روی مقادیر هزینه نشان می دهد. هزینه کل روش MLTG 55 است. تثبیت فاصله اقلیدسی در روش [ ۲۷ ] برای یک مسیر دو سلولی به معنای استفاده از همسایگی دو در دو بلوک است. همانطور که در بالا توضیح داده شد و در شکل ۶ ب نشان داده شد، مسیر پیدا شده توسط [ ۲۷] نمی تواند به طور دقیق عرض را به دلیل نوسانات تعیین کند ۲×جسیا توسط یک سلول از نظر تعداد سلول. بنابراین، همانطور که در شکل ۱۴ d نشان داده شده است، مسیر یافت شده توسط [ ۲۷ ] در حرکت های مورب، یک یا دو سلول در نوسان است. برای سازگاری این مسیر با هدف خود (عرض دو سلول در همه جهات)، هر جا که عرض آن تنها یک سلول در حرکت مورب باشد، چند مثلث اضافه می شود. شکل ۱۴ e. مسیر اصلاح شده بر روی مقادیر هزینه نشان داده شده است. برای محاسبه هزینه کل این مسیر، هر جایی که مسیر یک مثلث از یک سلول را اشغال کند، نیمی از هزینه یک سلول اضافه می شود. هزینه کل [ ۲۷ ] برابر با ۵۷٫۵ است که بالاتر از هزینه مسیر یافت شده توسط روش MLTG است (۵۵).

۴٫۲٫ مقایسه روش‌های MLTG و FWLA در مسیریابی یک راهرو پهن دو حالته

در اینجا، ما عملکرد روش‌های MLTG و FWLA را برای یافتن LCP برای یک راهرو دو حالته در یک منطقه مطالعاتی ۱۰ در ۱۰ مقایسه می‌کنیم. عرض هر حالت یک سلول است. در این راهرو، عرض در فاصله اقلیدسی ثابت است و برای جهات متعامد برابر است. ۲×جس. برای حرکات مورب، برابر است ۲×۲×جس. مبدا مسیر در گوشه بالا سمت چپ و مقصد در گوشه پایین سمت راست است. ما فرض می کنیم که یکی از حالت ها بزرگراه و دیگری یک خط برق است، با آرایش دلخواه بزرگراه در بالای (شمال) خط برق از چپ به راست.

نتیجه روش FWLA در شکل ۱۵ نشان داده شده است . در این آزمایش، ما از روش [ ۲۷ ] برای یافتن یک LCP گسترده در رستر هزینه مرکب استفاده می‌کنیم. شکل ۱۵ a همان داده های مورد استفاده در آزمایش قبلی است و به عنوان لایه هزینه برای بزرگراه استفاده می شود، در حالی که شکل ۱۵ b داده جدیدی است که به طور تصادفی ایجاد شده است، با هزینه های بین ۱ تا ۴ برای استفاده به عنوان لایه هزینه برق. خط روش [ ۲۷ ] برای کار بر روی یک لایه هزینه طراحی شده است. برای یافتن راهروی دو حالته همانطور که در بخش ۴٫۲ و بخش ۴٫۳ توضیح داده شده است، می توان از مقادیر انباشته تمام لایه های هزینه یا میانگین آنها استفاده کرد. شکل ۱۵c میانگین (الف) و (ب) است. شکل ۱۵ d مسیر دو سلولی را از رویکرد [ ۲۷ ] روی لایه متوسط نشان داده شده در شکل ۱۵ ج نشان می دهد. در مرحله بعد، (d) به (e) تغییر می‌یابد تا مشکل لبه‌های فرورفته که در آن عرض فقط یک سلول است برطرف شود. در (f) فضای راهرو (ه) بین دو حالت با آرایش دلخواه راهرو تقسیم شده است. با این حال، این مسیر در لایه هزینه متوسط دو حالت یافت می شود، در حالی که هزینه واقعی باید بر روی لایه های هزینه اصلی (a) و (b) محاسبه شود. در (g) مسیر بر روی لایه هزینه بزرگراه نشان داده شده است ( شکل ۱۵آ). مجموع مقادیر در ناحیه زرد هزینه بزرگراه است که ۲۷ است. در (h)، (f) روی لایه هزینه خط برق، شکل ۱۵ ب نشان داده شده است. مجموع مقادیر در ناحیه سفید هزینه خط برق در لایه هزینه اصلی آن است که ۴۳ است. هزینه کل دو حالت در (i) نشان داده شده است که برابر با ۷۰ است.

داده ها، آرایش، عرض ها و مبدا و مقصد مانند مثال فوق در اینجا برای اعمال روش MLTG استفاده می شود. نتایج در شکل ۱۶ نشان داده شده است ، با شکل فرعی a که راهروی دو حالته پیدا شده را نشان می دهد. هزینه بزرگراه که به رنگ زرد است در زیرشکل b محاسبه شده و ۲۸ می باشد. هزینه خط برق که با رنگ سفید نشان داده شده است در زیرشکل ج نشان داده شده است و برابر با ۳۷ است. هزینه های دو حالت و در مجموع ۶۵ است که کمتر از هزینه مسیر یافت شده توسط FWLA است (۷۰). این نشان می دهد که روش MLTG یک مسیر چند وجهی با هزینه کمتر پیدا کرده است.

۴٫۳٫ کاربرد روش MLTG برای مسیریابی یک راهرو سه حالته در ناحیه سلولی ۲۰۰ در ۲۰۰

برای بررسی قابلیت مدل MLTG برای یک منطقه نسبتاً بزرگتر، یک رستر هزینه سلولی ۲۰۰ در ۲۰۰ به طور تصادفی ساخته شد ( شکل ۱۷ a). برای طبیعی تر شدن آن، دو بار با استفاده از فیلتر ۵ در ۵ صاف شد. اولین و دومین سطح صاف شده در شکل ۱۷ نشان داده شده استb,c به ترتیب. در این مثال، فرض می‌کنیم که داده‌ها شطرنجی شیب‌دار هستند و تنها معیار مهم برای مسیریابی یک راهرو سه حالته متشکل از بزرگراه، راه‌آهن و خط انتقال نیرو، با عرض‌های مورد نیاز ۳، ۱ و ۲ سلول است. ما آزمایش را با اضافه کردن دستی مناطق اجتنابی مانند دریاچه‌ها، مستطیل‌های سیاه و رودخانه‌ها، خطوط سفید یا زرد، به سطح بیشتر کردیم. علاوه بر این، برخی مناطق ارزان قیمت مناسب به منطقه اضافه می‌شوند تا ببینند آیا مدل می‌تواند آنها را متمایز کند یا خیر. سپس با استفاده از سه روش مختلف که نشان دهنده سه حالت ذکر شده است، مقادیر سلول های روی این سطح طبقه بندی می شوند. از آنجایی که حساسیت این حالت ها در مورد شیب متفاوت است، تغییرپذیری هزینه های طبقه بندی مجدد از خط انتقال نیرو به بزرگراه و سپس به راه آهن افزایش می یابد. شکل فرعی (د) حاصل فرآیند مذکور است که به عنوان لایه هزینه بزرگراه استفاده می شود. مشابه شکل فرعی (د)، شکل فرعی (ه) برای راه آهن و شکل فرعی (f) برای خط انتقال نیرو است. LCP سه حالته حاصل در نشان داده شده استشکل ۱۸ الف، که در آن عرض بزرگراه، خط برق و راه آهن به ترتیب ۳، ۱ و ۲ سلول است. قابل توجه است که برای یافتن یک LCP، مدل MLTG به مبدا و نقاط مقصد و گره ها یا پایانه ها در آن دو نقطه نیاز دارد. در این مثال، محله شروع یک LR است در حالی که محله مقصد یک UD است. شکل ۱۸ a نشان می دهد که چگونه آرایش حالت ها در تمام طول مسیر حفظ می شود.

۵٫ نتیجه گیری ها

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

ما از شبیه سازی های عددی برای ارزیابی عملکرد این روش ها استفاده می کنیم. نتایج نشان می‌دهد که روش MLTG در مسیریابی راهروی عریض چند حالته و تک حالته مؤثر است. مشارکت های انجام شده در روش MLTG سه برابر است: (۱) به جای استفاده از همسایگی های تک لایه از یک رستر هزینه مرکب، از همسایگی های چند لایه از رسترهای هزینه های مختلف استفاده می کند. (ii) نمودار اتصال را به گونه ای ایجاد می کند که شکاف ها در نقطه عطف متمایز شده و با هزینه های چرخشی پر شوند. و (iii) با استفاده از مفهوم بلوک در حرکت های مورب، روش MLTG یک مسیر تورفتگی در این جهت ها ایجاد نمی کند. شبیه‌سازی‌های عددی نشان داد که روش‌های پیشنهادی قادر به یافتن مسیرهای بهینه در حالی که محدودیت‌های تحمیل‌شده توسط ماهیت چندوجهی راهروهای مورد مطالعه را برطرف می‌کنند، هستند.

منابع

مونتیرو، سی. Ramírez-Rosado، IJ; میراندا، وی. زورزانو-سانتاماریا، پی جی. گارسیا-گاریدو، ای. Fernández-Jiménez، تجزیه و تحلیل فضایی LA GIS برای بهینه‌سازی مسیریابی خطوط الکتریکی اعمال می‌شود. IEEE Trans. قدرت تحویل. ۲۰۰۵ ، ۲۰ ، ۹۳۴-۹۴۲٫ [ Google Scholar ] [ CrossRef ]
مک هارگ، طراحی IL با طبیعت ؛ موزه تاریخ طبیعی آمریکا: نیویورک، نیویورک، ایالات متحده آمریکا، ۱۹۶۹٫ [ Google Scholar ]
یانکوفسکی، پ. Richard, L. ادغام تجزیه و تحلیل مناسب بودن مبتنی بر GIS و ارزیابی چند معیاره در یک سیستم پشتیبانی تصمیم فضایی برای انتخاب مسیر. محیط زیست طرح. B طرح. دس ۱۹۹۴ ، ۲۱ ، ۳۲۳-۳۴۰٫ [ Google Scholar ] [ CrossRef ]
کولیشون، دبلیو. Pilar, JV یک الگوریتم مسیر کمترین هزینه وابسته به جهت برای جاده ها و کانال ها. بین المللی جی. جئوگر. Inf. علمی ۲۰۰۰ ، ۱۴ ، ۳۹۷-۴۰۶٫ [ Google Scholar ] [ CrossRef ]
Dijkstra، EW یادداشتی در مورد دو مشکل در ارتباط با نمودارها. عدد. ریاضی. ۱۹۵۹ ، ۱ ، ۲۶۹-۲۷۱٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
هوبر، دی ال. کلیسا، مدل‌سازی مکان راهرو انتقال RL. J. Transp. مهندس ۱۹۸۵ ، ۱۱۱ ، ۱۱۴-۱۳۰٫ [ Google Scholar ] [ CrossRef ]
ساری، اف. Sen, M. طراحی الگوریتم مسیر کمترین هزینه برای انتخاب مسیر بزرگراه. بین المللی J. Eng. Geosci. ۲۰۱۷ ، ۲ ، ۱-۸٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
سینگ، نماینده مجلس؛ سینگ، پی. سینگ، P. تحلیل تصمیم گیری چند معیاره مبتنی بر AHP فازی برای برنامه ریزی هم ترازی مسیر با استفاده از سیستم اطلاعات جغرافیایی (GIS). جی. جئوگر. سیستم ۲۰۱۹ ، ۲۱ ، ۳۹۵-۴۳۲٫ [ Google Scholar ] [ CrossRef ]
سکولیچ، م. مارینکوویچ، م. Ivković، I. روش ارزیابی چند معیاره فضایی برای برنامه ریزی ترازهای بهینه جاده ها، با تاکید بر تحلیل استحکام. بین المللی J. Traffic Transp. مهندس ۲۰۲۱ ، ۱۱ ، ۴۲۴-۴۴۱٫ [ Google Scholar ]
پو، اچ. آهنگ، تی. شونفلد، پی. لی، دبلیو. ژانگ، اچ. هو، جی. پنگ، ایکس. وانگ، جی. بهینه‌سازی تراز راه‌آهن کوهستانی با استفاده از بهینه‌سازی ازدحام ذرات گام به گام و ترکیبی با ترکیب اپراتورهای ژنتیکی. Appl. محاسبات نرم. ۲۰۱۹ ، ۷۸ ، ۴۱-۵۷٫ [ Google Scholar ]
ییلدیریم، وی. Bediroglu، S. یک مدل مبتنی بر سیستم اطلاعات جغرافیایی برای تعیین مسیر راه آهن پرسرعت اقتصادی و سازگار با محیط زیست با استفاده از فرآیند تحلیل سلسله مراتبی و تحلیل مسیر کم هزینه. سیستم خبره ۲۰۱۹ , ۳۶ , e12376. [ Google Scholar ] [ CrossRef ]
ابوالحسینی، س. Alesheikh, AA الگوریتم جدیدی برای در نظر گرفتن طول بحرانی نمرات در تحلیل مسیر کمترین هزینه مبتنی بر شطرنجی. عرب جی. ژئوشی. ۲۰۲۰ ، ۱۳ ، ۱۰۳۲٫ [ Google Scholar ] [ CrossRef ]
باگلی، س. ژنلتی، دی. Orsi، F. مسیریابی خطوط برق از طریق تحلیل مسیر کم هزینه و ارزیابی چند معیاره برای به حداقل رساندن اثرات زیست محیطی. محیط زیست ارزیابی تاثیر Rev. ۲۰۱۱ , ۳۱ , ۲۳۴-۲۳۹٫ [ Google Scholar ] [ CrossRef ]
کاستیلیو، جی. کلاس، جی. دال فورنو، ام. Resener, M. مسیریابی خطوط برق با توجه به جنبه های توسعه پایدار و محیط های پیچیده. در مجموعه مقالات کنفرانس فناوری‌های شبکه هوشمند نوآورانه IEEE PES 2021 – آمریکای لاتین (ISGT آمریکای لاتین)، لیما، پرو، ۱۵ تا ۱۷ سپتامبر ۲۰۲۱؛ صص ۱-۵٫ [ Google Scholar ]
Kursah, MB خط لوله کم‌هزینه با استفاده از سیستم اطلاعات جغرافیایی: محدودیت‌های فنی. بین المللی J. Appl. ژئوسپات. Res. (IJAGR) ۲۰۱۷ ، ۸ ، ۱-۱۵٫ [ Google Scholar ] [ CrossRef ]
دورماز، هوش مصنوعی؛ اونال، E.Ö.; آیدین، طراحی خودکار مسیر خط لوله CC با ارزیابی چند معیاره بر اساس تحلیل مسیر کم‌هزینه و ساده‌سازی نقشه‌برداری مبتنی بر خط: مطالعه موردی پروژه mus در ترکیه. ISPRS Int. J. Geo-Inf. ۲۰۱۹ ، ۸ ، ۱۷۳٫ [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
بییر، پی. ماژکا، دی. Jenness, J. گام های مفهومی برای طراحی راهروهای حیات وحش . CorridorDesign: Flagstaff, AZ, USA, 2007. [ Google Scholar ]
لی، اچ. لی، دی. لی، تی. کیائو، کیو. یانگ، جی. ژانگ، اچ. کاربرد مدل مسیر کم‌هزینه برای شناسایی شبکه کریدور پراکنده پانداهای غول‌پیکر پس از زلزله ونچوان – مطالعه موردی ذخیره‌گاه طبیعی Wolong در چین. Ecol. مدل. ۲۰۱۰ ، ۲۲۱ ، ۹۴۴-۹۵۲٫ [ Google Scholar ] [ CrossRef ]
اتکینسون، دی.م. ددمن، پ. دودیچا، دی. Traynor، S. ارزیابی چند معیاره و تجزیه و تحلیل مسیر کمترین هزینه برای یک جاده قطب شمال با آب و هوا. Appl. Geogr. ۲۰۰۵ ، ۲۵ ، ۲۸۷-۳۰۷٫ [ Google Scholar ] [ CrossRef ]
یو، سی. لی، جی. Munro-Stasiuk، MJ توسعه‌های الگوریتم‌های مسیر کم‌هزینه برای برنامه‌ریزی راه. بین المللی جی. جئوگر. Inf. علمی ۲۰۰۳ ، ۱۷ ، ۳۶۱-۳۷۶٫ [ Google Scholar ] [ CrossRef ]
آهوجا، RK; مهلهورن، ک. اورلین، جی. الگوریتم‌های ترجان، RE سریع‌تر برای مشکل کوتاه‌ترین مسیر. J. ACM (JACM) ۱۹۹۰ ، ۳۷ ، ۲۱۳-۲۲۳٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
لوفور، ن. Balmer, M. محاسبه سریع کوتاهترین مسیر در شبکه های ترافیک وابسته به زمان. Arbeitsberichte Verkehrs-Und Raumplan. ۲۰۰۷ ۴۳۹ . _ [ Google Scholar ]
کندروگیانیس، تی. بوروس، پ. گمپر، جی. لسر، یو. Blumenthal، DB یافتن k-کوتاه ترین مسیرها با همپوشانی محدود. VLDB J. ۲۰۲۰ ، ۲۹ ، ۱۰۲۳-۱۰۴۷٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
پنج‌شنبه، M. یافتن مسیر جایگزین در شبکه جاده. در مجموعه مقالات سومین کنفرانس جهانی علوم و فناوری های زیستی (LifeTech) IEEE 2021، نارا، ژاپن، ۹ تا ۱۱ مارس ۲۰۲۱؛ صص ۴۵۷-۴۶۰٫ [ Google Scholar ]
تاملین، دی. مسیریابی بهینه راهروهای وسیع. در مجموعه مقالات کنفرانس فابوس در مورد برنامه ریزی چشم انداز و راه سبز، Amherst، MA، ایالات متحده، ۱۲-۱۳ آوریل ۲۰۱۳٫ جلد ۴، ص. ۲٫ [ Google Scholar ]
Newkirk، RT یک سیستم برنامه ریزی مبتنی بر کامپیوتر برای بهینه سازی تخصیص منابع زیست محیطی هنگام مکان یابی تاسیسات. Ph.D. پایان نامه، دانشگاه وسترن انتاریو، لندن، ON، کانادا، ۱۹۷۶٫ [ Google Scholar ]
Shirabe, T. روشی برای یافتن یک مسیر وسیع کم‌هزینه در فضای شطرنجی. بین المللی جی. جئوگر. Inf. علمی ۲۰۱۶ ، ۳۰ ، ۱۴۶۹-۱۴۸۵٫ [ Google Scholar ] [ CrossRef ]
Gonçalves، AB گسترش مدل‌سازی مسیر کم‌هزینه مبتنی بر GIS به مکان مسیرهای گسترده. بین المللی جی. جئوگر. Inf. علمی ۲۰۱۰ ، ۲۴ ، ۹۸۳-۹۹۶٫ [ Google Scholar ] [ CrossRef ]
Tomlin, CD سیستم های اطلاعات جغرافیایی و مدل سازی نقشه کشی ; Prentice-Hall: Englewood Cliffs, NJ, USA, 1990. [ Google Scholar ]
سلامتی، م. مسیریابی بهینه کریدورهای انرژی و زیرساخت گسترده چندوجهی. پایان نامه کارشناسی ارشد، دانشگاه کلگری، کلگری، AB، کانادا، ۲۰۲۱٫ [ Google Scholar ]
Etherington، TR مدل‌سازی کم‌هزینه بر روی نمودارهای چشم‌انداز نامنظم. Landsc. Ecol. ۲۰۱۲ ، ۲۷ ، ۹۵۷-۹۶۸٫ [ Google Scholar ] [ CrossRef ]

شکل ۱٫ یافتن یک LCP گسترده در روش رستری هزینه انباشته (FWLA). شکل فرعی ( a ) رستر هزینه را برای n حالت مختلف نشان می دهد. شکل فرعی ( b ) رستر هزینه ترکیبی ایجاد شده برای همه حالت ها را نشان می دهد. در شکل فرعی ( c )، LCP گسترده در رستر هزینه مرکب یافت می شود. در شکل فرعی ( d )، ترتیب مورد نظر حالت ها در LCP گسترده یافت شده قرار می گیرد.

شکل ۲٫ زیربهینه بودن روش FWLA با حالت های متعدد. زیرشکل های ( a ، b ) به ترتیب رسترهای هزینه مصنوعی برای یک بزرگراه و یک خط برق هستند. شکل فرعی ( c ) رستر میانگین وزنی هزینه را برای دو حالت نشان می دهد. LCP دو سلولی که توسط FWLA یافت می شود در یک کادر قرمز در شکل فرعی ( c ) مشخص شده است. حسابداری LCP دو سلولی بهینه برای کمترین هزینه مخصوص حالت در شکل فرعی ( d ) نشان داده شده است.

شکل ۳٫ نمونه ای از یک راهرو با عرض ۴ سلولی ۳ حالته و هشت محله متحرک آن که در آن هر حالت رنگ متفاوتی دارد.

شکل ۴٫ شکل کلی هشت محله متحرک. هر رنگ نشان دهنده یک حالت است و سلول مرجع مربع سیاه در وسط شکل است.

شکل ۵٫ دو محله متحرک LR و LURD و محله چرخشی LRtoLURD که شکاف بین آنها را پر می کند در اینجا نشان داده شده است. لبه مربوط به LRtoLURD فلش قرمز است. سلول مرجع LR در سلول ( i ، j ) و نقطه مقابل آن به ترتیب با نقاط سیاه و قرمز نشان داده می شود. هزینه هر سلول یا بلوک در ورودی و خروجی در شکل ذکر شده است. مثلا سیم۱۱هزینه سلول اول حالت اول در LR است. تعداد سلول های حالت m در LR از ۱ تا متغیر است nمتردر حالی که برای LURD تعداد بلوک ها در حالت m بین ۱ تا است دمتر. سلول مرجع LURD در سلول قرار دارد (پ،q).

شکل ۶٫ رفتارهای دو روش موجود برای LCPهای عریض برای یک مورب نمونه در مسیری با عرض دو سلول حرکت می کند. شکل فرعی ( a ) یک حرکت مورب نمونه است زمانی که عرض بر حسب تعداد سلول ها ثابت است در حالی که شکل فرعی ( b ) سعی می کند عرض را بر حسب فاصله اقلیدسی ثابت کند.

شکل ۷٫ ساخت یک بلوک چرخیده از چهار سلول همسایه. مجموع وزن چهار نیم سلول نشان داده شده در زیرشکل ( a ) برابر با وزن بلوک چرخانده شده در شکل فرعی ( b ) است.

شکل ۸٫ دایره های کامل چرخش برای یک نمونه راهرو سه حالته برای هر دو چرخش خلاف جهت عقربه های ساعت و جهت عقربه های ساعت به ترتیب در شکل فرعی ( a ) و زیرشکل ( b ) نشان داده شده است. برای ساده نگه داشتن هندسه، این دایره ها با چرخاندن هشت ضلعی های نشان داده شده در زیرشکل ( c ) و زیرشکل ( d ) مدل شده اند. هر پیچ از یک ورودی و یک همسایگی متحرک خروجی ساخته شده است که بخش هر پیچ را در هشت ضلعی های چرخشی مشخص می کند. این بخش ها در شکل فرعی ( e ) و زیرشکل ( f ) به ترتیب برای چرخش های خلاف جهت عقربه های ساعت و در جهت عقربه های ساعت نشان داده شده اند.

شکل ۹٫ یک سلول که مرکز آن با مربع سیاه مشخص شده است به هشت گره تقسیم شده است که مربوط به هشت حرکت مجاز آن است در شکل فرعی ( a ) نشان داده شده است. این هشت گره با رنگ های مختلف اطراف مرکز سیاه نشان داده شده اند. هشت زوج لبه با حرکت مستقیم ورودی و خروجی در هر سلول برای سلول مرکزی در یک نشان داده شده است. ۳×۳مثال سلول در شکل فرعی ( b ). رنگ هر لبه زوج با رنگ گره مربوط به آن یکی است.

شکل ۱۰٫ ( الف ) هشت لبه چرخشی خلاف جهت عقربه های ساعت برای LR. ( ب ) ۵۶ لبه چرخش خلاف جهت عقربه های ساعت برای هر هشت پایانه در یک سلول. ( ج ) لبه های ( b ) را می توان با هشت یال متوالی نشان داده شده در ( ج ) ساخت.

شکل ۱۱٫ هشت چرخش متوالی در جهت عقربه های ساعت برای هشت سلول. هر گره در یک سلول چرخه خاص خود را از چرخش در جهت عقربه های ساعت دارد که در اینجا برای ساده تر کردن شکل نشان داده نشده است. فلش ها همرنگ گره های شروع آنها هستند.

شکل ۱۲٫ سه لبه ورودی (خطوط جامد) و سه لبه خروجی (خطوط چین) را برای یک گره LR نشان می دهد. رنگ لبه ها با گره های شروع آنها یکسان است.

شکل ۱۳٫ ( الف ) مقادیر شطرنجی هزینه مطابق با [ ۲۸ ]. ( ب ) LCP تک حالته دو سلولی که توسط [ ۲۸ ] به رنگ خاکستری یافت می شود. ( ج ) LCP تک حالته دو سلولی که با روش MLTG به رنگ سبز یافت می شود.

شکل ۱۴٫ ( الف ) مقادیر شطرنجی هزینه مطابق با [ ۲۸ ]. ( ب ) MLTG LCP دو سلولی تک حالته، که در آن هدف تثبیت عرض مسیر اقلیدسی است. ( ج ) مسیر یافت شده در ( ب ) که بر روی ارزش‌های هزینه نشان داده شده است. ( د ) LCP تک حالته دو سلولی [ ۲۷ ]. برای رفع مشکل مسیر تورفتگی موجود در ( d )، چند مثلث اضافه می شود که عرض آنها به جای دو خانه برابر با یک سلول است. نتیجه در ( e ) نشان داده شده است و بر روی مقادیر هزینه در ( f ) نشان داده شده است.

شکل ۱۵٫ شکل فرعی ( a ) لایه هزینه بزرگراه است که از مقادیر شطرنجی هزینه در راستای [ ۲۸ ] استفاده می کند. شکل فرعی ( b ) هزینه خط برق است، داده هایی که به طور تصادفی ایجاد می شوند. شکل فرعی ( c ) رستر میانگین هزینه زیرشکل های ( a , b ) است. شکل فرعی ( d ) روش LCP دو سلولی است [ ۲۷ ]. در شکل فرعی ( e ) چند مثلث به شکل فرعی ( d ) اضافه می شود تا عرض ثابت شود. در زیرشکل ( f )، فضای درون شکل فرعی ( e ) بین دو حالت تقسیم شده است که حالت اول زرد و حالت دوم سفید است. در شکل های فرعی ( g، f ) در شکل فرعی a برای محاسبه هزینه بزرگراه پوشانده شده است. در شکل‌های فرعی ( h , f ) روی شکل فرعی ( b ) قرار داده شده است تا هزینه خط برق محاسبه شود. هزینه کل مجموع زیرشکل های ( g , h ) است که در شکل فرعی ( i ) نشان داده شده است.

شکل ۱۶٫ داده های مشابه در شکل ۱۵ در این آزمایش استفاده شده است. شکل فرعی ( a ) یک راهرو دو حالته است که با روش MLTG پیدا شده است که مسیرهای بزرگراه و خط برق به ترتیب به رنگ قرمز و سبز نشان داده شده است. شکل فرعی ( ب ) مسیر بر روی لایه هزینه بزرگراه و هزینه محاسبه شده بزرگراه ۲۸ است. شکل فرعی ( ج ) مسیر بر روی لایه هزینه خط برق و هزینه محاسبه شده خط برق ۳۷ نشان داده شده است. هزینه کل. مجموع این دو هزینه است که در شکل فرعی ( a ) برابر با ۶۵ است.

شکل ۱۷٫ اعمال روش MLTG در یک منطقه وسیع شامل ۲۰۰ در ۲۰۰ سلول برای یافتن یک راهرو سه حالته که در آن حالت اول، بزرگراه، دارای سه سلول است، حالت دوم، راه آهن، یک راهرو دو سلولی است. عریض و حالت سوم، خط انتقال نیرو، یک مسیر تنها یک سلولی است. رستر هزینه به طور تصادفی در شکل فرعی ( a ) نشان داده شده است. این رستر هزینه دو بار صاف می شود و نتایج در زیرشکل های ( b , c ) نشان داده شده است. سلول‌های زیرشکل ( c ) با استفاده از سه روش مختلف که سه حالت ذکر شده را نشان می‌دهند طبقه‌بندی می‌شوند و برخی مناطق مناسب و همچنین برخی مناطق اجتنابی برای طبیعی‌تر کردن آن اضافه می‌شوند. رسترهای هزینه نهایی برای بزرگراه، راه آهن و خط برق در زیرشکل ها نشان داده شده است ( d– f ) به ترتیب. مستطیل های سیاه نشان دهنده دریاچه های اضافه شده هستند که مناطق اجتنابی هستند.

شکل ۱۸٫ شکل فرعی ( a ) LCP یافت شده با روش MLTG را نشان می دهد. شکل فرعی ( b ) آرایش مورد نظر یک محله LR از راهرو است که بزرگراه در بالا، خط برق در وسط، و راه آهن در پایین قرار دارد.