مسیریابی از گذشته تاکنون همواره مورد بحث محققین بوده است. علت این توجه نیز کاربرد فراوان مسیریابی در حوزههای مختلف میباشد. پیدا کردن مسیر مناسب میتواند بر هزینه و درآمد واحدهای اقتصادی، بازاریابی، جهانگردی و … تاثیرگذار باشد. طراحی سیستم حمل و نقل به منظور اینکه خدمترسانی خدمات مورد نیاز در کوتاهترین مسیر ممکن یا کمترین زمان ممکن باعث افزایش سودآوری و همچنین کاهش برخی از هزینهها مانند هزینه سوخت، استهلاک ماشین و دیگر موارد خواهد شد.
هدف از مسئله بازدید از یکسری گرهها (نقاط) میباشد، طوری که میزان مسافت طی شده (زمان سفر) بهینه (کمینه) شود. برای نوشتن مدل ریاضی مسئله به یکسری از مفروضات نیاز است که به این صورت میباشند: حداکثر زمان بازدید از منابع در هر روز مشخص میباشد (پنجره زمانی)، شخص از منزل خود (دیپات) شروع به بازدید در هر روز مینماید و در پایان به منزل باز میگردد، بازدید از هر منبع شامل زمان میباشد که مقادیر آن از قبل مشخص است، هر منبع در هر دوره تنها یکبار مورد بازدید قرار میگیرد.
تعریف مجموعهها و پارامترهای مسئله:
: مجموعه نقاط برای بازدید و .
: مجموعه نقطه شروع ابتدایی (منزل شخص یا دیپات).
:مجموعه دورههای زمانی (تعداد روزهای مدنظر).
: میزان مسافت از گره به گره .
: حداکثر میزان زمان بازدید از منابع در هر روز.
: میزان زمان سفر از گره به گره .
: زمان لازم برای بازدید از گره .
تعریف متغیرهای مسئله:
: متغیر باینری یا صفر و یک که نشان میدهد که گره به گره در دوره متصل شده است.
: متغیر باینری یا صفر و یک که نشان میدهد گره به گره متصل شده است.
: متغیر کمکی صفر و یک.
: متغیر کمکی صفر و یک برای نوشتن محدودیتهای حذف زیرتور.
مدل ریاضی مسئله مسیریابی با در نظر گرفتن پنجره زمانی به صورت زیر میباشد:
تابع هدف مسئله:
این رابطه، تابع هدف مسئله میباشد که به دنبال کمینهسازی مسافت طی شده است. البته میتوانستیم زمان سفر را نیز در تابع هدف در نظر بگیریم که با توجه به اینکه مسافت و زمان سفر تاثیر مستقیمی روی هم دارند، فرق چندانی ندارد که تابع هدف مسئله را کمینهسازی زمان سفر و یا کمینهسازی مسافت طی شده قرار بدهیم.
محدودیتهای مسئله:
این محدودیتها، بیان میکنند که حتما باید در طی دوره زمانی، گرهها به یکدیگر متصل باشند، به عبارت دیگر بایستی بازدید از گرهها حتما صورت پذیرد.
محدودیت بالا، تعیین بازدید از گرهها را به ترتیب از مبدا (دیپات) به گره و گره به گرههای دیگر و در نهایت از گره آخر به مبدا (دیپات) تعیین میکند.
این محدودیت، حداکثر زمان بازدید در هر روز را نشان میدهد. به عبارت دیگر در هر روز نباید زمان بازدید از مقدار تعیین شده فراتر رود.
این محدودیتها نیز محدودیتهای بالانس مسیر میباشند.
این محدودیت نیز، محدودیت کمکی برای حذف زیرتور میباشند. لازم به ذکر است از روش MTZ برای حذف زیر تور در این مسئله استفاده شده است.
مدل بالا در نرم افزار گمز کدنویسی شده است که خروجی متغیرهای مسئله پس از حل در قسمت display نرم افزار قابل مشاهده میباشد.
تحلیل نتایج برای یک نمونه داده در کد گمز:
تعداد مجموعه نقاط برای بازدید در کد گمز قابل تعیین میباشد. به عبارت دیگر کافی است در قسمت مجموعهها (Set)، مقادیر مدنظر خود را تعریف نمایید.
به عنوان نمونه در کد گمز پیشفرض، مقادیر تعیین شده به صورت زیر میباشد:
SETS Node dc and customer /d1,c1*c10/ d(Node) dc /d1/ c(Node) customer /c1*c10/ V /v1*v2/
که خط اول اشاره میکند که مسئله شامل یک دیپات و 10 گره است. خط دوم اشاره به یک دیپات دارد، خط سوم نیز تعداد 10 گره را نشان میدهد. در نهایت خط چهارم مجموعه وسایل نقلیه را نشان میدهد که البته مدل بعد از حل تعداد بهینه وسایل را نیز تعیین خواهد کرد. به عبارت دیگر لزوما تمامی وسایل نقلیه تعریف شده در این مجموعه ممکن است پس از حل به کار گرفته نشوند. یعنی با توجه به محدودیت پنجره زمانی ممکن است نیاز نباشد که وسایل بیشتری خریداری شود.
مسئله (کد گمز) پس از حل (با توجه به دادههای تعریف شده) خروجی زیر را نشان میدهد:
که اشاره دارد که در مسیر اول بایستی به ترتیب گره 6، 5، 4 و 3 بازدید شوند و همچنین در مسیر دوم به ترتیب گره 9، 8، 1، 7، 2 و 10 بازدید شوند.
هنوز بررسیای ثبت نشده است.