مساله‌ی جهت‌یابی با سودهای متغیر و تابع هدف کسری و تقاضا روی کمان

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