مروری بر مسئله طراحی مسیر گردشگر (بخش دوم): مدل ریاضی مسئله

مقدمه

در مقاله قبل ماهیت مسئله طراحی مسیر گردشگر^[۱] معرفی شده و جایگاه این مسئله در بین مسائل شبکه مشخص گردید. همچنین اهمیت این مسئله از دو منظر زیر نیز مورد بررسی قرار گرفت:

• منظر هزینه های حمل و نقل سفر
• منظر محدودیت های زمانی

در این مقاله مدل ریاضیاتی این مسئله ارائه خواهد شد. لازم به ذکر است مدل سازی های متعددی برای این مسئله ارائه شده است که مدل ارائه شده در این مقاله به عنوان آخرین و مناسب ترین مدل مسئله مذکور شناخته می شود.

مدل سازی مسئله در قالب یک مسئله جهت یابی

با تطبیق مفاهیم مسئله جهت‏یابی با «مسئله طراحی مسیر گردشگر (TTDP)»، در مسئله مذکور مجموعه‌ای از مقاصد گردشگری به صورت  که هر کدام دارای امتیاز (تمایل گردشگر)  می‌باشند، مفروض است. نقطه‌ی شروع، رأس ۱ و نقطه‌ی پایان، راس  بوده و زمان سفر  برای سفر از رأس i به رأس j نیز برای تمام رئوس معلوم است. از آنجایی که افق زمانی^[۲] به مقداری مانند  محدود می‏باشد (بیشینه زمان سفر)، فلذا نمی‌توان تمام رئوس را در زمان در دسترس بازدید نمود. هدف این مسئله، تعیین مسیری محدود به  است به طوری که در آن از مقاصدی بازدید شود که در نهایت برای گردشگر رضایت حداکثری را ایجاد نماید. اساساً در این مسئله فرض بر این است که هر مقصد تنها یک بار بازدید شود.

تفاوت مسئله با سایر مسائل مسیریابی

بنابراین تفاوت عمده این مسئله با سایر مسائل مسیریابی را می‏توان محدود بودن افق زمانی (زمان در دسترس) دانست؛ بدین معنا که پیمایش کل مسیر انتخابی، بایستی در یک افق زمانی مشخص و از قبل تعیین شده صورت پذیرد. بدیهی است در صورتی که مقدار این افق زمانی در مقایسه با زمان مورد نیاز برای بازدید همه مقاصد (رئوس) قابل توجه باشد این مسئله به «مسئله فروشنده دوره‏گرد^[۳] (TSP)» تبدیل خواهد شد و امتیاز هر رأس تاثیری در توالی بازدید آن‏ها نخواهد داشت، اما در صورتی که بازه زمانی در دسترس به گونه‏ای باشد که کفایت بازدید همه رئوس را نکند طبیعتاً امتیاز رئوس (میزان علاقمندی گردشگر به هر مقصد)، در بازدید و یا عدم بازدید آن‏ها و همچنین در توالی بازدید موثر خواهد بود. این ویژگی مسئله طراحی مسیر گردشگر، در مقایسه با سایر مسائل پایه‏ای حوزه مسیریابی انطباق بیشتری با شرایط دنیای واقعی را فراهم می‏کند.

مدل پایه مسئله طراحی مسیر گردشگر

مدل پایه این مسئله به شرح ذیل می‌باشد (۲, ۳):

توضیحات تکمیلی مدل

که در آن x_ij=1 در صورتی که بازدید رأس jام پس از بازدید رأس iام صورت پذیرد و در غیر اینصورت مقدار آن صفر است. همچنین u_i  موقعیت ترتیبی رأس iام در مسیر است. تابع هدف مربوط به حداکثر کردن مجموع امتیازات جمع‌آوری شده (حاصل از بازدیدها) بوده و محدودیت اول شروع مسیر از رأس ۱ و اتمام آن در رأس N را تضمین می‌کند. محدودیت دوم به منظور اطمینان از متصل بودن مسیر و اطمینان از بازدید حداکثر یکبار هر رأس به مدل اضافه شده است. محدودیت سوم بیانگر محدودیت افق زمانی بوده و محدودیت چهارم و پنجم نیز مربوط به حذف زیرتور با استفاده از فرمول‌بندی «میلر-تاکر-زملین^[۴] (MTZ)» (۱۱) می‌باشد.

یک مثال تصویری از مسئله طراحی مسیر گردشگر

مثالی از «مسئله طراحی مسیر گردشگر (TTDP)» در شکل (۱) نمایش داده شده است. هر یک از مقاصد گردشگری با دایره نمایش داده شده و امتیاز (میزان علاقمندی گردشگر به بازدید) هر کدام از مقاصد در داخل دایره‌ها نشان داده شده است. رأس (۱) رأس آغازین (برای مثال محل اقامت فعلی) و رأس  رأس پایانی (برای مثال محل اقامت آتی) بوده و با مثلث نمایش داده شد‌اند. محدودیت زمانی کل سفر (T_max) نیز برابر ۴ واحد زمانی می‌باشد. یک جواب شدنی برای این مسئله، با طول مسیر برابر ۴ واحد و امتیاز مسیر برابر ۱۸ با دنبال کردن کمان‌ها از نقطه‌ی شروع به نقطه‌ی پایان در شکل (۱) قابل مشاهده می‌باشد.

شکل (۱)- یک جواب شدنی برای «مسئله طراحی مسیر گردشگر (TTDP)»(۱۲)

پاورقی ها

[۱] Tourist Trip Design Problem (TTDP)

[۲]  در تعاریف موجود در تولیدات علمی این حوزه، اکثراً محدودیت افق زمانی را مورد بحث قرار داده‏اند و تعداد کمی از فعالیت‏ها محدودیت طول مسیر در مسئله جهت‏یابی را لحاظ کرده‏اند. در صورتی که مبنای مدل‏سازی مسافت طی شده باشد طبیعتاً می‏توان محدودیت طول مسیر را اعمال نمود. به هر حال این دو گونه مدل‏سازی به سادگی قابل تبدیل به یکدیگر هستند.

[۳] Travelling Salesman (or Salesperson) Problem (TSP)

[۴] Miller–Tucker–Zemlin (MTZ)